Coding LMC Control FlowMost 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. 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. IF and WHILE StatementsNote 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. Basic IF StructureThe 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 pseudocode structure for a simple IF statement (no ELSE clause) is as follows: // Simple IF statement structure pseudocode: 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 SKIP statement that transfer 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. Mathematics, Lights, and SKIPEach 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 written an expression 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: LDA 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 OUTIf A and B are equal, subtracting them will cause the Zero flag to come on. The SKZ instruction will then operate to skip over the JUMP instruction. In other words, the SKZ causes a skip into the body of the IF statement. If A and B are not equal, the Zero flag will not come on, and the SKZ will do nothing. The JMP will jump around the body of the IF statement. All LMC flow control statements (IF, WHILE) can be programmed using the above structure:
How do we choose what mathematics to perform, and which SKIP instruction to use? We will examine that later in this document. IF with an ELSE clauseIF 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: 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 ELSE LDA B ; 3,4. body of FALSE part of IF SUB A STO B ENDIF HLT ; 5,6. ENDIF; after IFCompare 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.) 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. A WHILE StatementThe 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: TEST 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 - start over ENDWH LDA A ; end of WHILE statement - continue on OUTThe 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 skip over the JUMP instruction. In other words, the SKZ causes a skip into the body of the WHILE statement. If A and B are not equal, the Zero flag will not come on, and the SKZ will do nothing. The JMP will jump around the body of the WHILE statement. 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 StatementsFOR 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 assembler LDA ZERO ; ZERO is a mailbox containing 000 STO I TEST LDA I ; do mathematics to set the lights SUB TEN ; TEN is a mailbox containing 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:
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. Choosing the Mathematics and SKIPAll of the above control structures (IF, IF/ELSE, WHILE, FOR) have the same structure for their test conditions:
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. LMC Flag Lights TableHere 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:
For example, if we were to perform "A-B", the first row of the table applies; for A-B the table shows that if A were larger than B (column 3 in the table) the Positive light would come on. There is no "Non-Zero" 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 Non-Zero 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 reverse subtraction, "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 again) the Negative light would come on and the fictitious Non-Zero 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. Example 1 using the table
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):
LDA B SUB A SKN JMP ENDIF Example 2 using the table
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 this row 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: LDA B SUB A SKP JMP ENDWHILE Example 3 using the table
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 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 NZ fictitious flag 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 SUB B SKNZ JMP ENDWHILE Nested AND LogicHere 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: if ( a != b ) then if ( c >= d ) then ... IF body goes here ... endif endif ... linear code resumes here ...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: 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. Nested OR LogicHere 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: First, we must apply deMorgan's theorem to invert the condition to an opposite condition that uses AND instead of OR: original condition: a != b || c >= d inverted condition: !(a != b || c >= d) deMorgan applied: !(a != b) && !(c >= d) simplified: a == b && c < dWe then use that new inverted condition to branch around the loop body: if ( a == b && c < d ) then goto around endif ... IF body goes here ... around: ... linear code resumes here ...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: 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 around the IF body, the above code uses an inverted condition and the ENDIF labels lead to the IF body. 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. |
Web Author: Ian! D. Allen idallen@idallen.ca Updated: 2003-05-04 01:19 Support free and non-commercial Internet. This site works best in Any Browser, a campaign for non-specific WWW. This work is licensed under a Creative Commons License. |