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  <cond>  THEN  <true statements>  ELSE  <false statements>

        In Forth the IF statement works like this:

              <cond>  IF  <true statements>  ELSE  <false statements>  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 <true statements> are executed.  If a false flag is on top of
        the stack, then the <false statements> are executed.  After the
        <true statements> or <false statements> 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 <Forth statements> <flag> UNTIL

        If the <flag> is FALSE, the program branches to the word following
        BEGIN.  If the <flag> 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 <Enter> 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  <words>  <flag> WHILE  <words>  REPEAT

        If the <flag> is TRUE, the words between WHILE and REPEAT are
        executed, and then a branch is taken to the word following BEGIN.
        If the <flag> 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;