Most programs contain some form of conditional logic, e.g. IF statements that affect the usual linear flow of control in the program. Programming conditional logic means turning the pseudocode logic into statements written in mnemonic form for the Little Man Computer (LMC). The LMC has no IF, WHILE, FOR or other structured statements; we must use the limited control flow instructions available to us to implement structured code.

High-level language conditional statements
contain a *test* expression that returns a TRUE or
FALSE, e.g. IF (count == 0), WHILE (sum >= MAX), etc.
The simplest test expression is a test that compares two
quantities, e.g. A<B. Let's name these two quantities
with variable names A and B and work out the translation of
two-variable test expressions to LMC instructions. More
complex expressions can be built using the techniques
developed here.

Note that the test in an IF statement and the test in a WHILE statement have exactly the same structure; both expressions return TRUE or FALSE and alter the flow of control around an enclosed body of statements:

if ( a == b ) then a = a + b // TRUE body endif while ( a == b ) do a = a + b // TRUE body endwhile

In both the above code fragments, the control flow enters the TRUE body only if the test expression comparing A and B for equality is true. If we know how to code one test in LMC instructions, we know how to code the other. We need only focus on the code for the test expression itself.

The basic LMC instructions that alter the flow of control are SKIP and JUMP statements. We must use these two LMC instructions to implement our pseudocode IF and WHILE control flow statements.

The LMC pseudocode structure for a simple IF statement (no ELSE clause) is as follows:

Evaluate the test expression using A and B SKIP the next statement if the test is true JUMP to ENDIF (the end of the IF statement) ...Perform the many... ...statements that are... ...the body of the IF here... ENDIF: Continue with rest of program

Note the placement of the SKIP and JUMP
instructions, above. The function of the JUMP is to get
around the body of the IF statement. The SKIP statement
precedes the JUMP and controls whether or not the JUMP is
taken. We must code a test expression and choose a SKIP
statement that transfers flow of control *into* the body of
the IF only if the test expression is TRUE. If the test
expression is FALSE, the JUMP should take control around
the body of the IF statement.

Think of the SKIP statement as meaning "skip *into* the
body" of the IF or WHILE.

Each type of SKIP instruction checks the settings of one of the three LMC flag lights: Negative, Zero, or Positive. Only mathematics, i.e. an ADD or SUBTRACT, sets the LMC lights; therefore, to use SKIP statements to alter the flow of control in our program, we must first perform an ADD or SUBTRACT using our two variables A and B. The mathematics will set the LMC lights based on the relationship between A and B, and we can then SKIP according to the setting of the lights.

For example, consider the following code fragment:

if ( a == b ) then a = a + b // TRUE body endif ouput a

We have an expression above that causes control flow to enter the TRUE body only if A is equal to B. Using the IF statement structure given above, we need to pick some mathematics to set the flag lights, follow the math with a SKIP instruction, and follow the SKIP instruction with a JUMP instruction. Using that structure, here is a translation of the above pseudocode into LMC instructions:

If A and B are equal, subtracting them will cause the Zero flag to come on. The SKZ instruction will then operate to skipLDA A ; do mathematics on A and B... SUB B ; ...to set the lights SKZ ; SKIP *into* IF body if A == B JMP ENDIF ; A is not equal to B - jump around LDA A ; body of IF... ADD B ; body of IF... STO A ; body of IF. ENDIF LDA A ; end of IF statement - continue on OUT

All LMC flow control statements (IF, WHILE) can be programmed using the above structure:

- Do some mathematics using A and B to set the LMC flag lights.
- Use one of the SKIP instructions to skip the next JUMP instruction.
- Use a JUMP instruction to jump around the body of the IF or WHILE.

How do we choose what mathematics to perform, and which SKIP instruction to use? We will examine that later in this document.

IF statements with ELSE clauses are only slightly more complex than simple IF statements. Here is a pseudocode program fragment using an IF/ELSE statement:

1. if ( a == b ) then 2. a = a + b 3. else 4. b = b - a 5. endif 6. stop

Here is a translation of the above pseudocode fragment into LMC assembler, with the statement numbers inserted as comments:

Compare the above LMC code with that used in the simple IF statement. Note the identical placement of the test expression mathematics, the SKIP, and the JUMP instruction on line 1, above. The function of the first JUMP is still to get around the TRUE body of the IF statement; however, instead of jumping to the end of the IF statement, it now jumps to the first statement in the ELSE clause. (If the test expression of an IF/ELSE statement is FALSE, control passes over the TRUE body and into the FALSE body.)LDA A ; 1. start IF: test ( a == b ) SUB B SKZ JMP ELSE LDA A ; 2. body of TRUE part of IF ADD B STO A JMP ENDIF ; jump around FALSE part of IF ELSE LDA B ; 3,4. body of FALSE part of IF SUB A STO B ENDIF HLT ; 5,6. ENDIF; after IF

A new "JMP ENDIF" instruction has been added to the end of the TRUE body of the IF statement (just before the ELSE label) to jump around the FALSE body that makes up the ELSE part of the IF. If this jump were not there, the flow of control would run from the statements at the end of the TRUE body into the statements at the beginning of the FALSE body.

The following pseudocode fragment is almost identical to the simple IF example used earlier; only the keywords IF have been changed to WHILE:

while ( a == b ) then a = a + b // TRUE body endwhile ouput a

Again, we have written an expression that causes control flow to enter the TRUE body only if A is equal to B. We need to pick some mathematics to set the flag lights, follow the math with a SKIP instruction, and follow the SKIP instruction with a JUMP instruction. We use almost the same statement structure as for the simple IF statement. Here is a translation of the above pseudocode into LMC instructions:

The analysis of the above LMC code is similar to the analysis of the code for the simple IF statement: If A and B are equal, subtracting them will cause the Zero flag to come on. The SKZ instruction will then operate to skipTEST LDA A ; do mathematics on A and B... SUB B ; ...to set the lights SKZ ; SKIP *into* WHILE body if A == B JMP ENDWH ; A is not equal to B - jump around LDA A ; body of WHILE... ADD B ; body of WHILE... STO A ; body of WHILE. JMP TEST ; WHILE is a loop - jump to top to start over ENDWH LDA A ; end of WHILE statement - continue on OUT

The key difference between the above code and the code for the simple IF statement is the addition of a "JMP TEST" instruction at the bottom of the body of the WHILE statement. WHILE statements need to loop; IF statements do not. The jump returns control to the top of the WHILE loop, which is to the test expression that begins the loop.

FOR statements are simply a shorthand way of writing the equivalent WHILE statements. To code a FOR statement, turn it into the equivalent WHILE statement and then translate that into assembler:

// the original FOR statement for ( i=0; i < 10; i++ ) do x = x + i endfor // translated into a WHILE statement i = 0 while ( i < 10 ) do x = x + i i = i + 1 endwhile ; turned into LMC assembly language LDA ZERO ; ZERO is a mailbox containing constant 000 STO I TEST LDA I ; do mathematics to set the lights SUB TEN ; TEN is a mailbox containing constant 010 SKN ; SKIP into WHILE body if I < 10 JMP ENDWH ; I is >= 10 - jump around LDA X ; body of WHILE... ADD I ; body of WHILE... STO X ; body of WHILE. LDA I ; increment... ADD ONE ; increment... STO I ; increment. JMP TEST ; WHILE is a loop - start over ENDWH ... ; end of WHILE statement - continue on

The Initialization clause of the FOR loop precedes the WHILE statement. The body of the WHILE loop ends with the Increment clause of the FOR loop, just before jumping back to the top of the loop. The WHILE loop itself has exactly the same structure as before:

- Do some mathematics to set the LMC flag lights.
- Use one of the SKIP instructions to skip the next JUMP instruction.
- Use a JUMP instruction to jump around the body.

A common error when programming FOR loops is to mis-code the jump to the top of the loop. Some people mistakenly code the jump to go to the first statement of the Initialization clause. The correct jump is to the first statement of the Test part of the WHILE loop, not to the Initialization clause.

All of the above control structures (IF, IF/ELSE, WHILE, FOR) have the same structure for their test conditions:

- Do some mathematics on A and B to set the LMC flag lights.
- Use one of the SKIP instructions to skip the next JUMP instruction.
- Use a JUMP instruction to jump around a body.

How do we choose what mathematics to perform using A and B, and which SKIP instruction do we use in front of the JUMP instruction?

Since we are testing the relationship between A and B - equal, less than, greater than, etc. - the operation that works best to set the LMC flag lights is SUBTRACT. Subtracting A from B or B from A sets the lights according to the relative values of A and B; ADDING would not have the same effect. The only issues to resolve are whether to do A-B or B-A to set the lights, and which of the few SKIP instructions we need to use.

Here is a table of LMC flag lights that will help us choose the order of the subtraction and which SKIP to use. The intersection of a row and column gives the flag lights that come on when A and B are subtracted from each other and have the relationship to each other given in the column heading:

Table
of LMC Lights |
Actual relationship of A and B | |||
---|---|---|---|---|

A < B | A == B | A > B | ||

Order of Subtraction |
A - B | N NZ | Z P | P NZ |

B - A | P NZ | Z P | N NZ |

For example, if we were to perform
subtraction "**A - B**", the
first row of the table applies. For **A-B** the table shows that if A were less
than than B (the first column in the table) the **Negative** and **NonZero** lights would
come on. There is no "**NonZero**" light; but, we do have an
extended "skip if non zero" SKNZ instruction that skips if
the **Zero** light
is *off*. To express this feature in the table, we
invent a fictitious **NonZero** flag "NZ" that is "on" whenever
the **Zero** light
is *off*. The NZ flag will be on whenever A and B are
not equal; it doesn't matter which way we subtract
them.

If we were to perform the subtraction in the
reverse order, "**B - A**", the
second row of the table applies. For **B-A** the table shows that if A were larger
than B (column 3 in the table) the **Negative** light would
come on and the fictitious **NonZero** flag "NZ" would also be on.

To pick a subtraction order and SKIP
instruction for a conditional expression, we compare the
condition in the expression with the conditions at the top
of the columns in the table. We seek to find an LMC flag
light that is **ON** *only* in the column or
columns that match our conditional expression. We code our
SKIP instruction to skip into the body of our statement
based on that flag light.

A < B | A == B | A > B | |
---|---|---|---|

A - B | N NZ | Z P | P NZ |

B - A | P NZ | Z P | N NZ |

For example, suppose we want to pick the subtraction order and the SKIP instruction for this test expression:

if ( a > b ) then ...

The expression **A>B** matches column 3
in the table. To set the lights we need and choose the
correct SKIP instruction, we must choose between
subtraction order **A-B** (row 1) and subtraction order
**B-A** (row 2):

**Row 1: A-B:**If we try row 1, subtraction order**A-B**, we see that the Positive and Non-Zero flags are set when we do**A-B**and A is greater than B. We might think of programming our SKIP instruction to be either SKP or SKNZ; either one would produce a skip*into*the body of our statement if A were actually greater than B. However, note that in this row of the table the Positive light also comes on even if A is*equal to*B (column 2), so using SKP would also cause an incorrect execution of our statement body if A were equal to B. So we can't skip using the Positive light. Similarly, we can't use the NonZero flag (as in SKNZ), since it would skip into the body of our statement both if A were greater than B (column 3) or if A were less than B (column 1).

There is no LMC flag in this**A-B**row that is on only for**A>B**and off for the other two columns. This rules out using any of the lights set using subtraction in the order**A-B**in row 1; we must try the other order in row 2 of the table.**Row 2: B-A:**If we try row 2, subtraction order**B-A**, we see that the Negative and NonZero flags are set when we do B-A and A is greater than B. We can't skip using the NonZero flag, since the flag also comes on in this row if A is less than B. However, the Negative light comes on in this row*only*if A is greater than B. The Negative light is on*only*in the**A>B**column. This is exactly what we need - the second row has the correct subtraction order we need (row**B-A**), the column containing the condition we want is the third column (column A>B), and the skip instruction to use will be SKN to select the Negative light:

LDA B ; subtract B-A (second row of table) SUB A SKN ; choose the Negative light to skip into the body for A>B JMP ENDIF

A < B | A == B | A > B | |
---|---|---|---|

A - B | N NZ | Z P | P NZ |

B - A | P NZ | Z P | N NZ |

For a second example, suppose we want to pick the subtraction order and the SKIP instruction for this test expression:

while ( a <= b ) do ...

The expression **A<=B** doesn't match
any single column in the table. We need to satisfy two
columns for this condition: the **A<B** column (column 1) *or* the
**A==B** column (column 2). We
need a flag that is **ON** in both of these columns, and
off in the other column. We again examine both rows of the
table to pick the correct subtraction order and correct
lights to check.

By looking at the table, we see that the
Positive light in the second row (**B-A**) is the only flag that satisfies our
requirements. The Positive light comes on in the second row
*only* if A is less than B *or* if A is equal to
B. This is exactly what we need - the second row is the
correct subtraction order we need (**B-A**) and the skip instruction to use will
be SKP to select the Positive light:

LDA B ; subtract B-A (second row of table) SUB A SKP ; choose the Positive light to pick A<B or A==B JMP ENDWHILE

A < B | A == B | A > B | |
---|---|---|---|

A - B | N NZ | Z P | P NZ |

B - A | P NZ | Z P | N NZ |

Here is a third example:

while ( a != b ) do ...

The expression **A!=B** doesn't match any
column in the table. Since another way of saying "is not
equal" is to say "is greater than *or* is less than",
we actually need to satisfy two columns for this condition:
the **A<B** column (column 1)
*or* the **A>B** column
(column 3). We need a flag that is **ON** in these two
columns, and is off everywhere else.

We eventually settle on the fictitious flag
NZ (NonZero) as being on in columns 1 and 3 and off in
column 2. The order of subtraction doesn't matter; both
rows are identical with respect to the NZ flag. We pick
the first row (**A-B**), and
the code fragment we write is:

LDA A ; subtract A-B (first row of table) SUB B SKNZ ; choose the NonZero pseudo-flag to pick A<B or A>B JMP ENDWHILE

Here is a more complex example using two test expressions joined by AND:

if ( a != b && c >= d ) then ... body goes here ... endif

The above test expression is not a simple one involving two quantities, so the methods we have been using so far will not work directly. However, we can rewrite the above compound test expression into two nested IF statements, each of which uses a simple A/B-type expression that we know how to translate:

Since the IF statements are nested, the body will not be executed unless both the outer AND inner IF conditions are both true. We can now translate these two IF statements directly into LMC assembler:if ( a != b ) then if ( c >= d ) then ... IF body goes here ... endif endif ... linear code resumes here ...

LDA A ; this test is the outer IF SUB B SKNZ JMP ENDIF1 LDA C ; this test is the inner IF SUB D SKP JMP ENDIF2 ... IF body goes here ... ENDIF2 ENDIF1 ... linear code resumes here ...

Both ENDIF1 and ENDIF2 are actually labels for the same location; jumping to either label jumps to the same code at the end of the IF statement. We might therefore simplify the code and use only a single ENDIF label for both jumps.

Here is another complex example, this time using two expressions joined by OR:

if ( a != b || c >= d ) then ... IF body goes here ... endif

The above two conditional test expressions are joined by OR, so we cannot implement a solution using two nested IF statements as we did when they were joined by AND.

With a bit of help from deMorgan's theorem in
Boolean logic, we can invert the condition so that it
becomes one containing AND instead of OR, and then use the
inverted condition to branch *around* the loop body:
(We use the inverted condition to branch *around*, so
the if the condition *fails*, we enter the body, as
desired.) We are going to turn this original
statement:

if (CONDITION) then ... IF body goes here ... endif

into this equivalent code using an inverted
("*NOT*") condition:

if (NOT CONDITION) then goto around endif ... IF body goes here ... around: ... linear code resumes here ...

First, we must invert the condition, then apply deMorgan's theorem. Doing so will turn the condition into one that uses AND instead of OR:

We then use that new inverted condition to branchoriginal condition: a != b || c >= d inverted condition: !(a != b || c >= d) deMorgan applied: !(a != b) && !(c >= d) simplified: a == b && c < d

We now have a compound condition joined by AND, a problem we can solve with nested IF statements, as we did in the previous section. The GOTO becomes a simple JUMP statement in LMC assembler:if ( a == b && c < d ) then goto around endif ... IF body goes here ... around: ... linear code resumes here ...

LDA A ; this test is the outer IF SUB B ; that tests a == b SKZ JMP ENDIF LDA C ; this test is the inner IF SUB D ; that tests c < d SKN JMP ENDIF JMP AROUND ENDIF ... IF body goes here ... AROUND ... linear code resumes here ...Unlike previous examples, where the JUMP to ENDIF branched

You might observe that our solution generated a SKN preceding two JMP instructions, one of which only jumps one instruction. If we were concerned about memory usage, the code might be optimized (at the expense of clarity) by inverting the SKN to SKP and removing one of the JUMPs:

... LDA C ; this test is the inner IF SUB D ; that now tests c >= d SKP JMP AROUND ENDIF ... IF body goes here ... AROUND ... linear code resumes here ...Making this optimization makes it harder to see the relationship between the code and the pseudocode. Unless memory space is tight, do not optimize your code. Make it right, first!

DO/WHILE loops have this structure, with the conditional test at the bottom of the loop:

do { a = a + b; // TRUE body } while ( a == b ); ouput a

Unlike the IF statement and WHILE statement,
the TRUE body of a DO/WHILE is always executed at least
once. We have a conditional expression that causes control
flow to *repeat* the TRUE body only if A is equal to
B. As before, we will need to pick some mathematics to set
the flag lights, follow the math with a SKIP instruction,
and follow the SKIP instruction with a JUMP instruction.
Unlike before, the JUMP instruction does not jump
*out* of the loop, it jumps back *into* the loop.
This means that everything we've done for IF and WHILE
statements to choose the order of subtraction and the SKIP
instruction is *backwards* for DO/WHILE statements.
We have to *invert the condition* to make the DO/WHILE
loop work; because, the JUMP must jump *into* the
loop, not *out of* the loop.

The condition at the end of the above DO/WHILE loop is "A==B". To code it in LMC assembler, we must pick a subtraction order and SKIP that implements the inverted condition: "A!=B". We consult the LMC Flag Light Table to do that. Here is a translation of the above pseudocode into LMC instructions:

LOOP LDA A ; body of DO/WHILE... ADD B ; body of DO/WHILE... STO A ; body of DO/WHILE. LDA A ; do mathematics on A and B... SUB B ; ...to set the lights SKNZ ; SKIP *out of* DO/WHILE loop if A != B JMP LOOP ; DO/WHILE is a loop - jump to top to start over LDA A ; end of WHILE statement - continue on OUT

If A and B are equal,
subtracting them will cause the Zero flag to come on. The SKNZ
instruction will do nothing, and the JUMP instruction will repeat
the loop. When A and B are *not* equal, the SKNZ instruction
will detect this, skip over the JUMP, and cause the loop to exit.
In other words, the SKNZ causes a skip *out of* the body of
the DO/WHILE loop. (The SKIP caused a skip *into* the body of
a WHILE loop.)