Forth Lesson 7
Review
In the previous lesson, we learned how to:
- Use variables and values to store numbers
- Use "create" and "," to make named data structure instances
- Perform simple address arithmetic
- Use "constant" to make efficient symbolic names for constants
Control Structures
Conditionals
ok hex ok : hex-digit ( n -- ascii ) \ Convert low nibble of n to ASCII hex ] h# f and ( low-nibble ) ] dup 9 <= if ( low-nibble ) ] h# 30 + ( ascii ) ] else ( low-nibble ) ] h# 37 + ( ascii ) ] then ( ascii ) ] ; ok 6 hex-digit . \ . displays the numerical value 36 ok 6 hex-digit emit \ Emit displays the number as an ASCII character 6 ok f hex-digit . 46 ok f hex-digit emit F
This simple example illustrates quite a few points. First, observe that you can continue definitions across lines. When you are doing so interactively, the prompt changes from "ok" to "]" to remind you that you are in the middle of a definition.
Also note the commenting style of listing the stack contents at the end of each line. This simple expedient is extremely helpful in making Forth code easy to write, debug, analyze, and maintain.
Finally, let's focus on the conditional structure "if ... else ... then", the main topic of this lesson.
These names are unfortunate, causing immediate confusion. The names should have been "if ... else ... endif", but for some reason, the name "then" was chosen as the end of the structure.
The general usage is
<code_to_compute_a_flag> if <true_clause> else <false_clause> then
"<code_to_compute_a_flag>" can be anything that leaves a number on the top of the stack. "<true_clause>" can be any sequence of Forth code; it is executed if the flag (the number on top of the stack when you get to "if") is nonzero. "<false_clause>" is executed if the flag is zero.
You can think of "if" as a conditional branch to just after the "else" and "else" as an unconditional branch to just after the "then". In fact that is essentially how it is implemented.
The "else <false_clause>" is optional; you can just write "if ... then".
Comparison Operators
The "flag" value that "if" tests can be an ordinary number (0 is considered false, nonzero true) or a well-formed flag. A well-formed flag is either 0 (false) or -1 (true). In either case, it is just a number on the top of the stack. There are quite a few operators that perform comparisons, typically used to create flags for control structures. All of these operators return well-formed (0 or -1) flags.
= ( n1 n2 -- flag ) \ True if n1 = n2 <> ( n1 n2 -- flag ) \ True if n1 != n2 < ( n1 n2 -- flag ) \ True if n1 < n2 (signed) u< ( u1 u2 -- flag ) \ True if n1 < n2 (unsigned) > ( n1 n2 -- flag ) \ True if n1 > n2 (signed) u> ( u1 u2 -- flag ) \ True if n1 > n2 (unsigned) <= ( n1 n2 -- flag ) \ True if n1 <= n2 (signed) u<= ( u1 u2 -- flag ) \ True if n1 <= n2 (unsigned) >= ( n1 n2 -- flag ) \ True if n1 >= n2 (signed) u>= ( u1 u2 -- flag ) \ True if n1 >= n2 (unsigned) 0= ( n -- flag ) \ True if n = 0 (logical not, like '!' in C) 0<> ( n -- flag ) \ True if n != 0 0< ( n -- flag ) \ True if n < 0 0> ( n -- flag ) \ True if n > 0 0<= ( n -- flag ) \ True if n <= 0 0>= ( n -- flag ) \ True if n >= 0 true ( -- -1 ) \ Pushes true (-1) false ( -- 0 ) \ Pushes false (0) between ( n low high -- flag ) \ True if low <= n <= high within ( n low high -- flag ) \ True if low <= n < high
Let's break down the "if" line in the example above. It reads "dup 9 <= if". Before this line starts executing, the top of the stack is a number that is the low nibble of the argument value, i.e. a number from 0..f, as indicated by the stack comment at the end of the "h# f and" line.
( low-nibble ) dup ( low-nibble low-nibble ) 9 ( low-nibble low-nibble 9 ) <= ( low-nibble flag ) if ( low-nibble )
The "dup" makes a copy of the number, because we will still need that number after we do the comparison. "9" pushes the number nine. "<=" pops two numbers from the stack (low-nibble and 9), performs the comparsion, and pushes a flag that represents the result. "if" pops the flag. If the flag was nonzero, the code between "if" and "else" is executed, otherwise the code between "else" and "then" is executed. In either case, low-nibble is on the stack ready for the addition. (The "+" could be moved out of the conditional, after the "then".)
Conditional Loops
Conditional looping works in a similar fashion; a flag on the stack
controls whether or not looping continues. There are several forms:
begin again \ Executes forever
begin ( flag ) until \ Executes until the flag is true
begin <code1> ( flag ) while <code2> repeat \ See below
- PROTIP: If you find you have accidentally created an infinite loop, you may interrupt the OLPC Open Firmware interpreter by pressing the frame key at the upper right corner of the OLPC keyboard
"begin <code> until" is an "exit at the end" loop. It executes
<code>, which should leave a flag on the top of the stack.
"until" pops that flag and if it is zero, "until" branches back to just
after the "begin".
"begin <code1> while <code2> repeat" is an "exit at the beginning"
loop. "while" pops a flag from the stack (presumably left by <code1>).
If the flag is nonzero, loop execution continues with <code2> and
"repeat" branches back to just after the "begin". If the flag is zero,
"while" branches to just after the "repeat". Normally <code1> does
the conditional test and <code2> does the "work", but you can put
anything you want in <code1> so long as it leaves a flag value on
the stack when it is done.
Note that the sense of the flag is different for "while" and "until".
"while" loops while the flag is true, whereas "until" loops until the
flag is true (i.e. while it is false).
Here are some concrete examples:
ok 0 begin dup . 1+ dup 5 = until
0 1 2 3 4
Note that in Open Firmware control structures can be used either interactively as shown above
or inside colon definitions as shown in the "if" example. (By the way,
there is a better way to do counting loops, as we will see soon.)
ok begin 5 . key? until
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...
That will keep displaying 5 until you type a key. "key? ( -- flag )"
tests the input device to see if a character is available.
"begin ... key? until" is a handy way to beat on hardware registers;
just replace ... with code to do whatever you want. It will run
until you stop it by typing a key.
ok 5 begin dup while dup . 1- repeat
5 4 3 2 1
ok 0 begin dup while dup . 1- repeat
ok █
Do Loops
ok 7 2 do 9 . loop
9 9 9 9 9
ok 7 2 do i . loop
2 3 4 5 6
ok 7 2 do i . 3 +loop
2 5
"( limit start ) do <code> loop" iterates over integers beginning with
start (the top of the stack when "do" is first encountered) and ending when
the index reaches limit (second on stack). Note that the loop stops when
limit is reached, so the index value is never equal to limit inside the loop.
ok 5 0 do i . loop
0 1 2 3 4
If "start" is 0 and "limit" is n, the body of the loop will execute n times.
"i" pushes the loop index onto the stack. If you nest do-loops and need to
"reach out" and get the index of the enclosing loop, that is "j", and then
"k" for triply-nested loops. That is as far as it goes.
"( n ) +loop" adds n to the loop index instead of 1.
"do" always executes the body at least once, even if start and limit
are the same. "?do" is like "do" except that it won't execute the
body if start and limit are the same limit.
To specify the loop boundaries as "( start length )" instead of
"( limit start )", use "bounds" to do the conversion:
bounds ( start length -- limit start )
Here is an example:
ok 10000 5 bounds do i . loop
10000 10001 10002 10003 10004
You can run a loop backwards, with a negative increment value to "+loop".
The stopping condition is somewhat surprising:
ok 1 5 do i . -1 +loop
5 4 3 2 1
Why did it display 1, since up-counting loops don't execute when the
index is equal to the limit value? The rule is this: The loop stops
when the index crosses the boundary between limit-1 and limit. So on
the way up, the last index value is less than limit, while on the way
down, the last index is equal to limit. Takes a bit of getting used
to, but the rule is precise, and there is really no way to do it
better, considering that "+loop" cannot know in advance which way the
loop is going (because the increment value can be computed at run time).
You can terminate a do loop prematurely, before the limit has
been reached, with "leave".
ok 1000000 0 do i . key? if leave then loop
0 1 2 3 4 ...
That would count up to 1000000, stopping early if you type a key.
You can terminate a do loop prematurely before exit in a definition:
: counting 1000000 0 do i . key? if unloop exit then loop ." finished!" ;
That would count up to 1000000, stopping early if you type a key, but if you did not then it would print "finished!".
How Control Structures Work
You might find it difficult to reconcile the behavior of control
structures with what previous lessons have said about how the compiler
works. In compilation state, the interpreter/compiler is supposed
to simply add the behavior of each word to the new definition. So
how do the various parts of control structures "hook up" with each
other? For example, how does "if" find the target of its forward
branch?
The answer is that a few words are specially marked with an "immediate" bit.
Those "immediate" words are not compiled directly, but instead are
executed when encountered in compilation state. They can be thought
of as parts of the compiler mechanism. The compiler mechanism is thus
extensible, because you can create your own immediate words.
Most of the control structure words are immediate. Consider the
sequence "if ... then" inside a definition. Since "if" is immediate,
the compiler doesn't compile it in the usual way, but instead executes
it. When "if" executes, it uses compiler primitives to compile a
conditional branch token into the current definition, followed by
a dummy branch offset (since the true branch offset is not yet known).
Then it pushes the address of that branch offset onto the stack, thus
remembering it for later. "if" then returns to the compiler, which
proceeds to compile the body of the control structure in the normal
way. The compiler eventually gets to "then", which is also immediate,
so it gets executed too. "then" gets the address of the dummy branch
offset from the stack and fixes up the offset, since the branch distance
is now known.
Other control structure words work in similar fashion, executing during
compilation to compile conditional or unconditional branches, resolving
the offsets as they become known. All of the stack activity surrounding
the branch resolution occurs during compilation. When the new definition
is later executed, the only stack activity related to the conditional
control structures is the popping of the flag value that controls which
path is taken.
There is an additional wrinkle with do loops. They have to manage the
loop index and the limit value, neither of which is necessarily known
at compile time. Do loops use the return stack (the auxiliary stack
that holds subroutine return addresses) for storing loop control parameters.
This is possible because do loops must be properly nested with respect
to definitions, i.e. a do loop must finish in a controlled fashion
before you can return from the word that contains it.
How Interpreted Control Structures Work
As mentioned previously, in Open Firmware you can use control structures interactively,
without compiling them inside a colon definition. How does that work,
in light of the preceding description about how they are compiled?
When a control structure starting word (e.g. "begin") is executed but
the interpreter state is "interpretation" instead of "compilation",
it calls a word that starts a temporary anonymous colon definition,
and then everything works as before. When that control structure
is completed, the ending word (e.g. "until") notices that, and calls
a word that executes then discards the temporary definition. So
"interpreted" control structures execute at full compiled speed.
Note that in ANS Standard Forth, such as gforth, control structures are only allowed inside of definitions, not at the interactive command line.
Thus endeth the lesson.