puts the index and the limit on the loop control stack.
In Chap. 4 we learned to program the computer to make "decisions" by branching to different parts of a definition depending on the outcome of certain tests. Conditional branching is one of the things that make computers as useful as they are.
In this chapter, we'll see how to write definitions in which execution can conditionally branch back to an earlier part of the same definition, so that some segment will repeat again and again. This type of control construct is called a "loop." The ability to perform loops is probably the most significant thing that makes computers as powerful as they are. If we can program the computer to make out one payroll check, we can program it to make out a thousand of them.
For now we'll write loops that do simple things like printing numbers at your terminal. In later chapters, we'll learn to do much more with them.
One type of loop structure is called a "definite loop." You, the programmer, specify the number of times the loop will loop. In Forth, you do this by specifying a beginning number and an ending number (in reverse order) before the word DO. Then you put the words which you want to have repeated between the words DO and LOOP. For example
: TEST 10 0 DO CR ." Hello " LOOP ;will print a carriage return and "Hello" ten times, because zero from ten is ten.
TEST
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello ok
Like an IF...THEN statement, which also involves branching, a DO...LOOP statement must be contained within a (single) definition.
The ten is called the "limit" and the zero is called the "index."
FORMULA:
limit index DO ... LOOP
Here is what happens inside a DO...LOOP:
First DO
puts the index and the limit on the loop control stack.
| 
|
| Then execution proceeds to the words inside the loop, | up till the word LOOP. |
First LOOP adds one to the loop index. If the loop index is then equal to ten, it lets execution move on to the next word in the definition. Otherwise, LOOP reroutes execution back to DO.
Remember that the Forth word I copies the top of the loop control stack onto the parameter stack. You can use I to get hold of the current value of the index each time around. Consider the definition
: DECADE 10 0 DO I . LOOP ;
which executes like this:
DECADE 0 1 2 3 4 5 6 7 8 9 ok
Of course, you could pick any range of numbers (within the range of -2147483648 to +2147483647):
: SAMPLE -243 -250 DO I . LOOP ;
SAMPLE -250 -249 -248 -247 -246 -245 -244 ok
Notice that even negative numbers increase by one each time. The limit is always higher than the index.
You can leave a number on the stack to serve as an argument to something inside a DO loop. For instance,
: MULTIPLICATIONS CR 11 1 DO DUP I * . LOOP DROP ;
will produce the following results:
7 MULTIPLICATIONS
7 14 21 28 35 42 49 56 63 70 ok
Here we're simply multiplying the current value of the index by seven each time around. Notice that we have to DUP the seven inside the loop so that a copy will be available each time and that we have to DROP it after we come out of the loop.
A compound interest problem gives us the opportunity to demonstrate some trickier stack manipulations inside a DO loop.
Given a starting balance, say $1000, and an interest rate, say 6%, let's write a definition to compute and print a table like this:
1000 6 COMPOUND
YEAR 1 BALANCE 1060
YEAR 2 BALANCE 1124
YEAR 3 BALANCE 1191
etc.
for twenty years.
First we'll load R%, our previously-defined word from Chap. 5, then we'll define
: COMPOUND ( amt int -- )
CR SWAP 21 1 DO ." YEAR " I . 3 SPACES
2DUP R% + DUP ." BALANCE " . CR
LOOP 2DROP ;
Each time through the loop, we do a 2DUP so that we always maintain a running balance and an unchanged interest rate for the next go-round. When we're finally done, we 2DROP them.
The index can also serve as a condition for an IF statement. In this way you can make something special happen on certain passes through the loop but not on others. Here's a simple example:
: RECTANGLE 256 0 DO I 16 MOD 0= IF CR THEN
." *"
LOOP ;
RECTANGLE will print 256 stars, and at every sixteenth star it will also perform a carriage return at your terminal. The result should look like this:
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
And here's an example from the world of nursery rhymes. We'll let you figure this one out.
: POEM CR 11 1 DO I . ." Little "
I 3 MOD 0= IF ." indians " CR THEN
LOOP
." indian boys. " ;
In the last section we defined a word called MULTIPLICATIONS, which contains a DO...LOOP. If we wanted to, we could put MULTIPLICATIONS inside another DO...LOOP, like this:
: TABLE CR 11 1 DO I MULTIPLICATIONS LOOP ;
Now we'll get a multiplication table that looks like this:
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
3 6 9 12 15 18 21 24 27 30
etc.
10 20 30 40 50 60 70 80 90 100
because the I in the outer loop supplies the argument for MULTIPLICATIONS.
You can also nest DO loops inside one another all in the same definition:
: TABLE CR 11 1 DO
11 1 DO I J * 5 U.R LOOP
CR LOOP ;
Notice this phrase in the inner loop:
I J *
In Chap. 5 we mentioned that the word J copies the third item on the loop control stack onto the parameter stack. It so happens that in this case the third item on the loop control stack is the index of the outer loop.
Thus the phrase "I J *" multiplies the two indexes to create the value in the table.
Now what about this phrase?
5 U.R
This is nothing more than a fancy . that is used to print numbers in table form so that they line up vertically. The five represents the number of spaces we've decided each column in the table should be. The output of the new table will look like this:
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
3 6 9 12 15 18 21 24 27 30 etc.
Each number takes five spaces, no matter how many digits it contains. (U.R stands for "unsigned number-print, right justified." The term "unsigned," you may recall, means you cannot use it for negative numbers.)
If you want the index to go up by some number other than one each time around, you can use the word +LOOP instead of LOOP. +LOOP expects on the stack the number by which you want the index to change. For example, in the definition
: PENTAJUMPS 50 0 DO I . 5 +LOOP ;
the index will go up by five each time, with this result:
PENTAJUMPS 0 5 10 15 20 25 30 35 40 45 ok
while in
: FALLING -10 0 DO I . -1 +LOOP ;
the index will go down by one each time, with this result:
FALLING 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ok
The argument for +LOOP, which is called the "increment," can come from anywhere, but it must be put on the stack each time around. Consider this experimental example:
: INC-COUNT DO I . DUP +LOOP DROP ;
There is no increment inside the definition; instead, it will have to be on the stack when INC-COUNT is executed, along with the limit and index. Watch this:
Step up by one:
1 5 0 INC-COUNT 0 1 2 3 4 ok
Step up by two:
2 5 0 INC-COUNT 0 2 4 ok
Step down by three:
-3 -10 10 INC-COUNT 10 7 4 1 -2 -5 -8 ok
Our next example demonstrates an increment that changes each time through the loop.
: DOUBLING 32767 1 DO I . I +LOOP ;
Here the index itself is used as the increment (I +LOOP), so that starting with one, the index doubles each time, like this:
DOUBLING
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 ok
Notice that in this example we don't ever want the argument for +LOOP
to be zero, because if it were we'd never come out of the loop. We would have created what is
known as an "infinite loop."
There are a few things to remember before you go off and write some DO loops of your own.
First, keep this simple guide in mind:
Execution makes its exit from a loop when, in going up, the index has reached or passed the limit.
Or, when in going down, the index has passed the limit--not when it has merely reached it.
But a DO loop always executes at least once (this example will loop millions of times on a true ANS Forth system, so be prepared):
: TEST 100 10 DO I . -1 +LOOP ;
TEST 10 9 8 7 ...
Second, remember that the words DO and LOOP are branching commands and that therefore they can only be executed inside a definition. This means that you cannot design/test your loop definitions in "calculator style" unless you simulate the loop yourself.
Let's see how a fledgling Forth programmer might go about design/testing the definition of COMPOUND (from the first section of this chapter). Before adding the ." messages, the programmer might begin by jotting down this version on a piece of paper:
: COMPOUND ( amt int -- )
SWAP 21 1 DO I . 2DUP R% + DUP . CR LOOP 2DROP ;
The programmer migh test this version at the terminal, using . or .S to check the result of each step. The "conversation" might look like this:
Sometimes a beginner will unwittingly write a loop which leaves a whole lot of numbers on the stack.
For example
: FIVES 100 0 DO I 5 . LOOP ;
instead of
: FIVES 100 0 DO I 5 * . LOOP ;
If you see this happen to anyone (surely it will never happen to you!) and if you see the beginner typing in an endless succession of dots to clear the stack, recommend typing in
XX
XX is not a Forth word, so the text interpreter will execute the word ABORT", which among other things clears all stacks. The beginner will be endlessly grateful. |
While DO loops are called definite loops, Forth also supports "indefinite" loops. This type of loop will repeat indefinitely or until some event occurs. A standard form of indefinite loop is
BEGIN ... UNTIL
The BEGIN...UNTIL loop repeats until a condition is "true."
The useage is
BEGIN xxx f UNTILwhere "xxx" stands for the words that you want to be repeated, and "f" stands for a flag. As long as the flag is zero (false), the loop will continue to loop, but when the flag becomes non-zero (true), the loop will end.
An example of a definition that uses a BEGIN...UNTIL statement is one we mentioned earlier, in our washing machine example:
: TILL-FULL BEGIN ?FULL UNTIL ;which we used in the higher-level definition
: FILL FAUCETS OPEN TILL-FULL FAUCETS CLOSE ;
?FULL will be defined to electronically check a switch in the washtub that indicates when the water reaches the correct level. It will return zero if the switch is not activated and a one if it is. TILL-FULL does nothing but repeatedly make this test over and over (millions of times per second) until the switch is finally activated, at which time execution will come out of the loop. Then the ; in TILL-FULL will return the flow of execution to the remaining words in FILL, and the water faucets will be turned off.
Sometimes a programmer will deliberately want to create an infinite loop. In Forth, the best way is with the form
: BEGIN xxx 0 UNTIL
The zero supplies a "false" flag to the word UNTIL, so the loop will repeat eternally.
Beginners usually want to avoid infinite loops, because executing one means that they lose control of the computer (in the sense that only the words inside the loop are being executed). But infinite loops do have their uses. For instance, the text interpreter is part of an infinite loop called QUIT, which waits for input, interprets it, executes it, prints "ok," then waits for input once again. In most microprocessor-controlled machines, the highest-level definition contains an infinite loop that defines the machine's behavior.
Another form of indefinite loop is used in this format:
BEGIN xx f WHILE yyy REPEAT
Here the test occurs halfway through the loop rather than at the end. As long as the test is true, the flow of execution continues with the rest of the loop, then returns to the beginning again. If the test is false, the loop ends.
Notice that the effect of the test is opposite that in the BEGIN...UNTIL construction. Here the loop repeats while something is true (rather than until it's true).
The indefinite loop structures lend themselves best to cases in which you're waiting for some external event to happen, such as the closing of a switch or thermostat, or the setting of a flag by another part of an application that is running simultaneously. So for now, instead of giving examples, we just want you to remember that the indefinite loop structures exist.
There is a way to write a definite loop so that it stops short of the prescribed limit if a truth condition changes state, by using the word LEAVE. LEAVE causes the loop to end immediately.
Watch how we rewrite our earlier definition of COMPOUND. Instead of just letting the loop run twenty times, let's get it to quit after twenty times or as soon as our money has doubled, whichever occurs first.
We'll simply add this phrase:
2000 > IF LEAVE THENlike this:
: DOUBLED
6 1000 21 1 DO CR ." YEAR " I 2 U.R
2DUP R% + DUP ." BALANCE " .
DUP 2000 > IF CR CR ." more than doubled in "
I . ." years " LEAVE
THEN
LOOP 2DROP ;
The result will look like this:
DOUBLED
YEAR 1 BALANCE 1060
YEAR 2 BALANCE 1124
YEAR 3 BALANCE 1191
YEAR 4 BALANCE 1262
YEAR 5 BALANCE 1338
YEAR 6 BALANCE 1418
YEAR 7 BALANCE 1503
YEAR 8 BALANCE 1593
YEAR 9 BALANCE 1689
YEAR 10 BALANCE 1790
YEAR 11 BALANCE 1897
YEAR 12 BALANCE 2011
more than doubled in 12 years ok
One of the problems at the end of this chapter asks you to rework DOUBLED so that it expects the parameters of interest and starting balance, and computes by itself the double balance that LEAVE will try to reach.
To give a neater appearance to your loop outputs (such as tables and geometric shapes), you might want to
clear the screen first by using the word PAGE. You can execute
PAGE interactively like this:
PAGE RECTANGLE
which will clear the screen before printing the rectangle that we defined earlier in this chapter.
Or you could put PAGE at the beginning of the definition. like this:
: RECTANGLE PAGE 256 0 DO I 16 MOD 0= IF CR THEN ." *" LOOP ;
If you don't want the "ok" to appear upon completion of execution, use the word QUIT. Again, you can use QUIT interactively:
RECTANGLE QUIT
or you can make QUIT the last word in the definition (just before
the semicolon).
|
Here's a list of the Forth words we've covered in this chapter:
| DO ... LOOP | DO: ( limit index -- ) LOOP: ( -- ) | Sets up a finite loop, given the index range. |
| DO ... +LOOP | DO: ( limit index -- ) +LOOP: ( -- ) | Like DO ... LOOP except adds the value of n (instead of always one) to the index. |
| LEAVE | ( -- ) | Terminate the loop immediately. |
| BEGIN ... UNTIL | UNTIL: ( f -- ) | Sets up an indefinite loop which ends when f is true. |
| BEGIN xxx WHILE yyy REPEAT | WHILE: ( f -- ) | Sets up an indefinite loop which always executes xxx and also yyy if f is true. Ends when f is false. |
| U.R | ( u width -- ) | Prints the unsigned single-length number, right-justified within the field width. |
| PAGE | ( -- ) | Clears the terminal screen and resets the terminal's cursor to the upper left-hand corner. |
| QUIT | ( -- ) | Terminates execution for the current task and returns control to the terminal. |
| definite loop | a loop structure in which the words contained within the loop repeat a definite number of times. In Forth, this number depends on the starting and ending counts (index and limit) which are placed on the stack prior to the execution of the word DO. |
| Infinite loop | a loop structure in which the words contained within the loop continue to repeat without any chance of an external event stopping them, except for closing the Forth window or shutting down or resetting the computer. |
| Indefinite loop | a loop structure in which the words contained within the loop continue to repeat until some truth condition changes state (true-to-false or false-to-true). In Forth, the indefinite loops begin with the word BEGIN. |
In Problems 1 trough 6, you will create several words which will print out patterns of stars (asterisks). These will involve the use of DO loops and BEGIN...UNTIL loops.
10 STARS[answer]********** ok
10 3 BOX
**********
**********
********** ok
[answer]
3 \STARS
**********
**********
********** ok
[answer]
2 DIAMONDS
*
***
*****
*******
*********
***********
*************
***************
*****************
*******************
*******************
*****************
***************
*************
***********
*********
*******
*****
***
*
*
***
*****
*******
*********
***********
*************
***************
*****************
*******************
*******************
*****************
***************
*************
***********
*********
*******
*****
***
*
[answer]
7 2 ** . 49 ok(seven squared)
2 4 ** . 16 ok(two to the fourth power)
For simplicity, assume positive exponents only (but make sure ** works correctly when the exponent is one--the result should be the number itself). [answer]
