=================================
Quiz 27: Other Control Structures					[TOC]
=================================

If you came so far your current code is already worth 20 points. You can
increase your score by implementing more control structures. The fun you will
have will be priceless.

Other Control Structures
========================
Other control structures like do-while loops, for loops and if statements can
be realized very similarly. Here the grammar:

---- LATEX ---------------------------------------------------------------------
\begin{array}{rcl}
\text{statement}
    & = &
    \text{io-hack-statement}\;
    \\
    & | &
    \text{expr-statement}\;
    \\
    & | &
    \text{compound-statement}\;
    \\
    & | &
    \text{while-statement}\;
    \\
    & | &
    \text{do-while-statement}\;
    \\
    & | &
    \text{for-statement}\;
    \\
    & | &
    \text{if-statement}\;
    \\
\text{compound-statement}
    & = &
    \texttt{"\{"}\;
    \{\;
    \text{statement}\;
    \}\;
    \texttt{"\}"}\;
    \\
\text{while-statement}
    & = &
    \texttt{while}\;
    \texttt{"("}\;
    \text{assignment-expression}\;
    \texttt{")"}\;
    \text{compound-statement}\;
    \\
\text{do-while-statement}
    & = &
    \texttt{do}\;
    \text{compound-statement}\;
    \texttt{while}\;
    \texttt{"("}\;
    \text{assignment-expression}\;
    \texttt{")"}\;
    \texttt{";"}\;
    \\
\text{for-statement}
    & = &
    \texttt{for}\;
    \texttt{"("}\;
    [\; \text{assignment-expression}\; ]\;
    \texttt{";"}\;
    [\; \text{assignment-expression}\; ]\;
    \texttt{";"}\;
    [\; \text{assignment-expression}\; ]\;
    \texttt{")"}\;
    \\
&&
    \text{compound-statement}\;
    \\
\text{if-statement}
    & = &
    \texttt{if}\;
    \texttt{"("}\;
    \text{assignment-expression}
    \texttt{")"}\;
    \text{compound-statement}\;
    \\
&&
    [\;
    \texttt{else}\;
    \text{compound-statement}\;
    |\;
    \text{if-statement}\;
    ]\;
    \\
 \end{array}
--------------------------------------------------------------------------------

For all loops it is required that the loop body is a compound statement. The
then-branch of an if statement is also required to be a compound statement. The
else-branch of an if-statement can be either an if statement or a compound
statement. This avoids the __dangling else problem__ (See __Session 10, Page
2__).

Parsing the statements can be done by following the usual rules. For each
control structure the code generation can be implemented once we agreed on
a flow chart representation for it (if there are multiple options). 

---- SHELL (path=session25/git/abc_step9,hide) ---------------------------------
make
--------------------------------------------------------------------------------

Code Generation: Do-While Loop (Worth: 20 Points)
=================================================
We actually do not have much to choose here:

---- TIKZ ----------------------------------------------------------------------
  \begin{tikzpicture}
  \input{flowchart.tex}
  \SetMargin{1}{1}{0}{3.1}
  \renewcommand\BoxWidth { 7 }


  \PutStatement{0}{code before do-while statement}
  \PutStatement{1}{loop body}
  \PutJump{2}{cond}
  \PutStatement{3}{code after do-while statement}

  \AddPath{0}{1}
  \AddPath{1}{2}
  \AddCondJumpPath{2}{1}
  \AddPath{2}{3}

  \end{tikzpicture}
--------------------------------------------------------------------------------

Test your implementation with the program below. It reads in an unsigned integer
and should print its decimal digits in reverse order:

---- CODE (file=session25/git/abc_step9/examples/dowhile.abc) ------------------
$> x;
do {
    $< x % 10;
    x = x / 10;
} while (x != 0);
--------------------------------------------------------------------------------

---- SHELL (path=session25/git/abc_step9/examples,hide) ------------------------
make
--------------------------------------------------------------------------------

Here an example:

---- SHELL (path=session25/git/abc_step9/examples) -----------------------------
echo "123456789" | ./dowhile
--------------------------------------------------------------------------------

Code Generation: For Loop (Worth: 20 Points)
============================================
The control flow for an for loop statement of the form

---- CODE (type=c) -------------------------------------------------------------
for (initial-clause; condition; update) {
    loop-body;
}
--------------------------------------------------------------------------------

can be realized as follows:

---- TIKZ ----------------------------------------------------------------------
\begin{tikzpicture}
\input{flowchart.tex}
\SetMargin{1}{1}{0}{6.1}
\renewcommand\BoxWidth { 7 }

\PutStatement{0}{code before for loop}
\PutStatement{1}{initial-clause}
\PutJump{2}{condition}
\PutStatement{3}{loop body}
\PutStatement{4}{update}
\PutJump{5}{}
\PutStatement{6}{code after for loop}

\AddPath{0}{1}
\AddPath{1}{2}
\AddPath{2}{3}
\AddCondJumpPathAlt{2}{6}
\AddPath{3}{4}
\AddPath{4}{5}
\AddJumpPathLeft{5}{2}
\end{tikzpicture}
--------------------------------------------------------------------------------

Note that all expressions in the for loop are optional. Hence

---- CODE (type=abc) -----------------------------------------------------------
for (;;) {
}
--------------------------------------------------------------------------------

is legal by the grammar. It is also semantically legal. It is a busy loop that
never terminates. You will see that in the implementation the behavior that an
empty expression for the condition is treated as _true_ comes for free. Support
of empty expressions for the condition makes more sense when after we have added
break statements in the next session.

Test your implementation with the program below. It computes the factorial of
a non-negative integer using a for loop.

---- CODE (file=session25/git/abc_step9/examples/factorial_for.abc) ------------
$> n;
res = 1;
for (i = 1; i <= n; i = i + 1) {
    res = res * i;
}
$< res;
--------------------------------------------------------------------------------

---- SHELL (path=session25/git/abc_step9/examples,hide) ------------------------
make
--------------------------------------------------------------------------------

Here an example:

---- SHELL (path=session25/git/abc_step9/examples) -----------------------------
echo "5" | ./factorial_for
--------------------------------------------------------------------------------


Code Generation: If Statement (Worth: 40 Points)
================================================
The control flow for an if statement with an else-branch can be realized as
follows:

---- TIKZ ----------------------------------------------------------------------
\begin{tikzpicture}
\input{flowchart.tex}
\SetMargin{1}{1}{0}{5.1}
\renewcommand\BoxWidth { 5 }

\PutStatement{0}{code before if statement}
\PutJump{1}{condition}
\PutStatement{2}{then branch}
\PutJump{3}{}
\PutStatement{4}{else-branch}
\PutStatement{5}{code after if statement}

\AddPath{0}{1}
\AddPath{1}{2}
\AddCondJumpPathAlt{1}{4}
\AddPath{2}{3}
\AddPath{4}{5}
\AddJumpPathLeft{3}{5}

\end{tikzpicture}
--------------------------------------------------------------------------------

Technically a missing else-branch could be treated like an empty else-branch.
This means after the then-branch we would have an unconditional jump that jumps
forward by one instruction. This is not elegant and certainly not how we do
things in Ulm. An if statement without else-branch should be realized as
follows:

---- TIKZ ----------------------------------------------------------------------
\begin{tikzpicture}
\input{flowchart.tex}
\SetMargin{1}{1}{0}{3.1}
\renewcommand\BoxWidth { 5 }


\PutStatement{0}{code before if statement}
\PutJump{1}{condition}
\PutStatement{2}{then-branch}
\PutStatement{3}{code after if statement}

\AddPath{0}{1}
\AddCondJumpPathAlt{1}{3}
\AddPath{1}{2}
\AddPath{2}{3}

\end{tikzpicture}
--------------------------------------------------------------------------------

Tired of computing the factorial? Let's compute the greatest common divisor. Of
course this could be done with this program:

---- CODE (file=session25/git/abc_step9/examples/gcd_mod.abc) ------------------
$> a;
$> b;

while (b) {
    t = b;
    b = a % b;
    a = t;
}

$< a;
--------------------------------------------------------------------------------

---- SHELL (path=session25/git/abc_step9/examples,hide) ------------------------
make
--------------------------------------------------------------------------------

Here an example:

---- SHELL (path=session25/git/abc_step9/examples) -----------------------------
time echo "2 100001" | ./gcd_mod
--------------------------------------------------------------------------------


But this would not really test the if statement. It is also too fast in case
$a$ is much larger than $b$. We need some chill out test. So let's use this
program:

---- CODE (file=session25/git/abc_step9/examples/gcd_sub.abc) ------------------
$> a;
$> b;

while (a != b) {
    if (a > b) {
        a = a - b;
    } else {
        b = b - a;
    }
}

$< a;
--------------------------------------------------------------------------------

---- SHELL (path=session25/git/abc_step9/examples,hide) ------------------------
make
--------------------------------------------------------------------------------

Here an example:

---- SHELL (path=session25/git/abc_step9/examples) -----------------------------
time echo "2 100001" | ./gcd_sub
--------------------------------------------------------------------------------

Of course we also should test an if statement with an else-if. Use this:

---- CODE (file=session25/git/abc_step9/examples/elseif.abc) -------------------
$> x;

if (x % 2) {
    x = 1;
} else if (x > 5) {
    x = 2;
} else {
    x = 3;
}

$< x;
--------------------------------------------------------------------------------

---- SHELL (path=session25/git/abc_step9/examples,hide) ------------------------
make
--------------------------------------------------------------------------------

Here an example:

---- SHELL (path=session25/git/abc_step9/examples) -----------------------------
echo "3" | ./elseif
echo "6" | ./elseif
echo "4" | ./elseif
--------------------------------------------------------------------------------


Of course you should try to test even cooler stuff. For example, nesting all
kind of control structures.  Even cooler test can be done once we have
operators for a logical not, logical or and logical and ;-)

How to Submit
=============

You have to submit a __tarball__ _quiz27.tgz_ of your project. In your project
directory do the following:

- Run _make clean_
- Create the tarball with

  ---- CODE (type=txt) -----------------------------------------------------------
  tar cfvz quiz27.tgz *
  --------------------------------------------------------------------------------

- On _theon_ you can submit the tarball with _submit hpc quiz27 quiz27.tgz_


:links: tarball -> https://en.wikipedia.org/wiki/Tar_(computing)
	dangling else problem -> https://en.wikipedia.org/wiki/Dangling_else
	Session 10, Page 2 -> doc:session10/page02#toc6.3