\ 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;