=== Lesson 4 === \ Lesson 4 - Forth Decisions \ The Forth Course \ by Richard E. Haskell \ Dept. of Computer Science and Engineering \ Oakland University, Rochester, MI 48309 comment: Lesson 4 FORTH DECISIONS 4.1 BRANCHING INSTRUCTIONS AND LOOPS 4-2 4.2 CONDITIONAL WORDS 4-3 4.3 FORTH LOGICAL OPERATORS 4-4 4.4 THE IF STATEMENT 4-5 4.5 THE DO LOOP 4-6 4.6 THE UNTIL LOOP 4-10 4.7 THE WHILE LOOP 4-11 EXERCISES 4-12 4.1 BRANCHING INSTRUCTIONS AND LOOPS All computer languages must have some way of producing a conditional branch (if...then) and implementing loops. Forth uses the following well-structured constructs: IF ... ELSE ... THEN DO ... LOOP BEGIN ... UNTIL BEGIN ... WHILE ... REPEAT BEGIN ... AGAIN These instructions work somewhat differently than they do in other languages. The words IF, UNTIL and WHILE are Forth words that expect a true/false flag to be on top of the stack when the words are executed. A false flag has a value of 0. A true flag has a value of -1. F-PC defines the two constants -1 CONSTANT TRUE 0 CONSTANT FALSE The flag may be generated in any way, but the usual way is to use some type of conditional expression that leaves a flag on the stack. We will first look at Forth conditional words and then give examples of each of the branching and looping statements shown above. 4.2 CONDITIONAL WORDS -- true/false flags The following Forth conditional words produce a true/false flag: < ( n1 n2 -- f ) ( "less-than" ) flag, f, is true if n1 is less than n2. > ( n1 n2 -- f ) ( "greater-than" ) flag, f, is true if n1 is greater than n2. = ( n1 n2 -- f ) ( "equals" ) flag, f, is true if n1 is equal to n2. <> ( n1 n2 -- f ) ( "not-equal" ) flag, f, is true if n1 is not equal to n2. <= ( n1 n2 -- f ) ( "less-than or equal" ) flag, f, is true if n1 is less than or equal to n2. >= ( n1 n2 -- f ) ( "greater-than or equal" ) flag, f, is true if n1 is greater than or equal to n2. 0< ( n -- f ) ( "zero-less" ) flag, f, is true if n is less than zero (negative). 0> ( n -- f ) ( "zero-greater" ) flag, f, is true if n is greater than zero (positive). 0= ( n -- f ) ( "zero-equals" ) flag, f, is true if n is equal to zero. 0<> ( n -- f ) ( "zero-not-equal" ) flag, f, is true if n is not equal to zero. 0<= ( n -- f ) ( "zero-less-than or equal" ) flag, f, is true if n is less than or equal to zero. 0>= ( n -- f ) ( "zero-greater-than or equal" ) flag, f, is true if n is greater than or equal to zero. The following conditional words compare two unsigned numbers on the stack. U< ( u1 u2 -- f ) ( "U-less-than" ) flag, f, is true if u1 is less than u2. U> ( u1 u2 -- f ) ( "U-greater-than" ) flag, f, is true if u1 is greater than u2. U<= ( u1 u2 -- f ) ( "U-less-than or equal" ) flag, f, is true if u1 is less than or equal to u2. U>= ( u1 u2 -- f ) ( "U-greater-than or equal" ) flag, f, is true if u1 is greater than or equal to u2. 4.3 FORTH LOGICAL OPERATORS Some Forths have the word NOT which reverses the truth value of the flag on top of the stack. In F-PC the word NOT performs a one's complement of the word on top of the stack. As long as TRUE is -1 (hex FFFF) then NOT TRUE will be FALSE. You must be careful because any non-zero value may, at times, be treated as a true flag. The one's complement of anything other than hex FFFF will not produce zero (FALSE). You can always complement any flag by using the comparison word 0=. In addition to the logical operator NOT, Forth also has the following binary logical operators: AND ( n1 n2 -- and ) Leaves n1 AND n2 on top of the stack. This is a bitwise AND. For example, if you type 255 15 AND ( mask lower 4 bits ) the value 15 will be left on top of the stack. OR ( n1 n2 -- or ) Leaves n1 OR n2 on top of the stack. This is a bitwise OR. For example, if you type 9 3 OR the value 11 will be left on top of the stack. XOR ( n1 n2 -- xor ) Leaves n1 XOR n2 on top of the stack. This is a bitwise XOR. For example, if you type 240 255 XOR ( Hex F0 XOR FF = 0F ) the value 15 will be left on top of the stack. 4.4 THE IF STATEMENT The Forth IF statement works somewhat differently than an IF statement in other languages. A typical IF ... THEN ... ELSE statement that you may be familiar with works like this: IF THEN ELSE In Forth the IF statement works like this: IF ELSE THEN Note that a true/false flag must be on top of the stack when the IF word is executed. If a true flag is on top of the stack, then the are executed. If a false flag is on top of the stack, then the are executed. After the or are executed, the words following THEN are executed. The ELSE clause is optional. The IF word must be used within a colon definition. As an example, define the following words: comment; : iftest ( f -- ) IF CR ." true statements" THEN CR ." next statements" ; : if.else.test ( f -- ) IF CR ." true statements" ELSE CR ." false statements" THEN CR ." next statements" ; comment: Then type TRUE iftest FALSE iftest TRUE if.else.test FALSE if.else.test 4.5 THE DO LOOP The Forth DO loop must be defined inside a colon definition. To see how it works, define the following word: comment; : dotest ( limit ix -- ) DO I . LOOP ; comment: Then if you type 5 0 dotest the values 0 1 2 3 4 will be printed on the screen. Try it. The DO loop works as follows. The word DO takes the top two values from the top of the parameter stack and moves them to the return stack. At this point the two values are no longer on the parameter stack. The word LOOP adds one to the index value and compares the result to the limit value. If the incremented index value is less than the limit value, then a branch is taken to the word following DO. If the incremented index value is equal to the limit value, then the two values are removed from the return stack and the word following LOOP is executed. We will take a close look at how the DO loop is actually implemented in Lesson 9. The Forth word I copies the index value from the return stack to the top of the parameter stack. Therefore, the execution of the above example can be illustrated as follows: 5 \ 5 0 \ 5 0 DO I \ ix ( ix = 0,1,2,3,4) . LOOP Note that the limit value must be one greater than the largest index value you want. For example, 11 1 DO I . LOOP will print out the values 1 2 3 4 5 6 7 8 9 10 The +LOOP Word The index in the Forth DO loop can be incremented by a value other than 1 by using the word +LOOP instead of LOOP. To see how this works, define the following word: comment; : looptest ( limit ix -- ) DO I . 2 +LOOP ; comment: Then if you type 5 0 looptest the values 0 2 4 will be printed on the screen. Try it. The word +LOOP takes the value from the top of the parameter stack and adds it to the index value on the return stack. It then behaves the same as LOOP, branching back to the word following DO as long as the incremented index value is less than the limit value (if the increment value is positive). If the increment value is negative, then the loop will exit when the index value becomes less than the limit value. For example, if you define comment; : neglooptest ( limit ix -- ) DO I . -1 +LOOP ; comment: and then type 0 10 neglooptest the values 10 9 8 7 6 5 4 3 2 1 0 will be printed on the screen. Nested Loops - The Word J Forth DO loops can be nested. When you do this two pairs of index/limit values are moved to the return stack. The word I copies the index value of the inner loop from the return stack to the parameter stack, and the word J copies the index value of the outer loop from the return stack to the parameter stack. As an example of nested loops, define the following word: comment; : 1.to.9 ( -- ) 8 1 DO CR 3 0 DO J I + . LOOP 3 +LOOP ; comment: If you execute this word by typing 1.to.9 the following will be printed: 1 2 3 4 5 6 7 8 9 Do you see why? Try it. Nested loops are used much less frequently in Forth than in other languages. It is usually better to define smaller words that contain only a single DO loop, and then call this word within another loop. The Word LEAVE The Forth word LEAVE can be used to exit a DO loop prematurely. It is normally used within an IF statement inside the DO loop. The word LEAVE causes the immediate exit from the DO loop. (The address of the word following LOOP has been stored as the third word on the return stack.) A related word ?LEAVE (flag --) will exit a DO loop if the flag on top of the stack is true. This can avoid the need for an IF statement. As an example, suppose you want to define a word called find.n that will search for a specific value in a table and return the index of the value (i.e. its position in the table) under a true flag if the value is found; otherwise, a false flag will be left on top of the stack. The Forth statement comment; CREATE table 50 , 75 , 110 , 135 , 150 , 300 , 600 , comment: will create the following table in the code segment. table ________ | CFA | CODE | <------| |------| PFA | 50 | 0 |------| | 75 | 1 |------| | 110 | 2 <---index, ix |------| | 135 | 3 |------| | 150 | 4 |------| | 300 | 5 |------| | 600 | 6 <---imax-1 |------| Code Segment ?CS: The number of values in the table is imax (7 in this case). The value to be searched for in n. These two values will be on the stack when find.n is executed. The following is a definition of find.n. comment; : find.n ( imax n -- ff | index tf ) 0 SWAP ROT \ 0 n imax 0 DO \ 0 n DUP I table \ 0 n n ix pfa SWAP 2* + \ 0 n n pfa+2*ix @ = \ 0 n f IF \ 0 n DROP I TRUE \ 0 ix tf ROT LEAVE \ ix tf 0 THEN LOOP \ 0 n DROP ; \ 0 | ix tf comment: Study this definition until you see how it works. In general, when using a DO loop the stack picture should be the same after executing DO as it is after executing LOOP. You will often need to DUP some stack value(s) inside a DO loop and then DROP something after you leave the loop. Note in this case how the ROT before LEAVE is used to set up the stack so that the final DROP will leave the true flag on top of the stack. 4.6 THE UNTIL LOOP The Forth UNTIL loop must be used within a colon definition. The form of the UNTIL loop is BEGIN UNTIL If the is FALSE, the program branches to the word following BEGIN. If the is TRUE, the program continues with the word following UNTIL. The following two F-PC words can sense and read the keyboard. KEY? ( -- flag ) produces a TRUE flag if you have pressed a key. KEY ( -- char ) waits for a key to be pressed and leaves the ASCII code of the key on the stack. The F-PC word EMIT ( char -- ) will print on the screen the character whose ASCII code is on top of the stack. Define the word comment; : dowrite ( -- ) BEGIN KEY \ char DUP EMIT \ print on screen 13 = \ if equal to CR UNTIL ; \ quit comment: Executing this word will write all characters you type on the screen until you press the key (ASCII code = 13). Note that the word UNTIL removes the flag from the stack. 4.7 THE WHILE LOOP The Forth WHILE loop must be used within a colon definition. The form of the WHILE loop is BEGIN WHILE REPEAT If the is TRUE, the words between WHILE and REPEAT are executed, and then a branch is taken to the word following BEGIN. If the is FALSE, the program branches to the word following REPEAT. As an example, consider the following algorithm to compute the factorial of n. x = 1 i = 2 DO WHILE i <= n x = x * i i = i + 1 ENDDO factorial = x The following Forth word will compute this factorial. comment; : factorial ( n -- n! ) 1 2 ROT \ x i n BEGIN \ x i n 2DUP <= \ x i n f WHILE \ x i n -ROT TUCK \ n i x i * SWAP \ n x i 1+ ROT \ x i n REPEAT \ x i n 2DROP ; \ x comment: Note that the stack arrangement must be the same at the words BEGIN and REPEAT for the WHILE loop to work properly. Note also that whereas the algorithm given above uses the three variables x, i and n, the Forth implementation uses no variables at all! This is characteristic of Forth. You will find that you use far fewer variables than in other languages. Test this definition of of factorial by typing 3 factorial . 4 factorial . 0 factorial . EXERCISE 4.1 The Fibonacci sequence is a sequence of numbers in which each number (starting with the third) is the sum of the two immediately preceding numbers. Thus, the beginning of the sequence looks like this. 1 1 2 3 5 8 13 21 34 Define a Forth word called fib ( n -- ) that will print the fibonacci sequence for all values less than n. Test your word by typing 1000 fib EXERCISE 4.2 Create a table called weights that contains the following values: 75 135 175 115 220 235 180 167 Define a Forth word called heaviest ( pfa -- max.value ) that will put the maximum value from the table on the top of the stack. If you type weights heaviest . the value 235 should be printed on the screen. comment;