Forth Lesson 4

Review

In the previous lesson we learned that:

• Forth has the usual collection of integer arithmetic and logical operators
• You have to do calculations in postfix (Reverse Polish) form
• Some Forth systems have floating point support but Open Firmware usually omits it

Making New Words

So far we have done everything interactively, using only numbers and predefined words - and only a miniscule fraction of the predefined words that exist. Now we will learn how to make our own new words.

Suppose that we want to add 12345 to several other numbers and display the results. Using just what we have learned so far, we could write:

 ok 55 12345 + .
 1239a
 ok 98a 12345 + .
 12ccf

and so on. This wouldn't even be particularly tedious if you use the line editor to recall and edit previous lines. But we want to learn to make new words, so we will.

 ok : foo 12345 + .  ;
 ok 55 foo
 1239a
 ok 98a foo
 12ccf

We made a new word "foo" whose behavior is the same as "12345 + ." . Now "foo" can be used just the same as any other word in the system. Here's how the process works:

The Forth word ":" (which must be followed by whitespace, just like every other word) calls the input parser to get a whitespace-delimited name ("foo" in this case). It then creates a new word with that name and tells the Forth interpreter to enter "compile state" (normally the interpreter is in "interpret state"). In compile state, instead of executing each word that it encounters, the interpreter compiles the behavior of the encountered word into the body of the new word. When it sees a number in compile state, the interpreter compiles code that will push that number on the stack when the new word later executes. When the interpreter encounters ";", it compiles something akin to "return from subroutine" and switches back to interpret state.

What about arguments and results? Well, since the stack is used for passing arguments, everything just works. The "+" that is compiled inside "foo" can pop two numbers off the stack (e.g. the "55" that was pushed outside of foo, and the "12345" that is pushed during the execution of foo), in the same way as it would if you executed "+" directly from the interpreter.

But wait, you say, what about the return address that is necessary to get back when foo executes? Doesn't that go on the stack, and thus interfere with the numbers? No, because a separate stack (the "return stack") is used for return addresses.

Compiled Code

What does the compiled code (inside the new word "foo") look like? Well, the Forth standard doesn't specify that. It just says that the result of executing "foo" has to be the same as if you executed its constituent words. Different Forth implementations use different code generation strategies. Some generate optimized machine language code. Others generate machine language code that consists of a sequence of subroutine calls, one call to each constituent word. Perhaps the most common approach is "threaded code", in which the body of "foo" consists of an array of addresses, one for each constituent. A tiny "tree walker" machine language code sequence grabs each address in turn and jumps to it. Each approach has its advantages and disadvantages. Threaded code offers a good balance between speed, compactness, simplicity, portability, and ease of debugging.

Redefinitions

What happens if you try to make a new word that has the same name as an existing one? Perhaps surprisingly, Forth will let you do that. Consider:

 ok : word1   5678 .  ;
 ok word1
 5678
 ok : word2   word1  123 .  ;
 ok word2
 5678 123
 ok : word1  999 .  ;
 word1 isn't unique
 ok word1
 999
 ok word2
 5678 123

Whoa! This is weird! Or is it?

First we create "word1" that displays "5678". Then we create "word2" that calls "word1" then displays "123". So far so obvious.

Now we create "word1" again. The system warns us ("isn't unique"), but goes ahead and does it. Now when we interpret "word1" we see "999" instead of "5678". But when we interpret "word2", it still shows "5678".

What has happened is that the both definitions of "word1" exist in the system, as separate chunks of code that happen to have the same name. "word2" still calls the first one - the only one that existed when "word2" was compiled (early binding). But the interactive interpreter sees that most recent one, because the search for defined words starts with later definitions and stops when it gets a match. There are ways to find earlier definitions that have been thus "hidden", but that is a topic for later.

Keyboard Interrupt

PROTIP: If you find you have accidentally created an infinite loop, you may interrupt the interpreter by pressing the frame key at the upper right corner of the OLPC keyboard or del. If you are working from a serial port, send a line break to interrupt. If you are running Forth under an OS, try typing Ctrl-C - it might exit all the way back to the OS, or it might get you back to the ok prompt, depending on which Forth you are using.

After a keyboard interrupt on XO-1 and XO-1.5, further keyboard interrupts are turned off, so if you want to be able to interrupt again, you must type "enable-interrupts".

Recursion and Chaining

This next topic is perhaps a bit too advanced for this stage of the lesson series, but I'm including it anyway because I know that some readers will wonder about it...

At this point any curious reader will write an infinite recursive loop. Therefore it is necessary to explain how to abort an infinite loop in OLPC Open Firmware. I don't know how to do this, and so my first OLPC Open Firmware program may still be running in Mako's apartment, for all I know... --- Kragen Sitaker

Okay, what happens if you try to use the word "xyz" inside the definition of "xyz"? The question is especially interesting in light of the fact that you can have multiple definitions with the same name. You might reasonably want a new definition to "xyz" to call a previous version of "xyz" and then extend its behavior. You might also reasonably want recursion. And in fact, you can do either.

 ok : factorial  recursive  dup 1 >  if  dup 1-  factorial *  then  ;
 ok decimal 5 factorial .  hex
 120

(I switched to decimal to try it out because it looks too weird to see the result of factorial in hex.)

Don't worry about the words you don't yet know. Just notice that "factorial" calls "factorial" recursively, which works because we said "recursive" first. If we hadn't said "recursive", the compiler would have complained:

 ok : fact   dup 1 > if  dup 1-  fact *  then  ;
 fact ?

The deal here is that when you are in the process of defining a new word, the new word is not yet visible to the interpreter/compiler. The new word is only revealed after its definition is finished (i.e. after ";"). So all that "recursive" does is to reveal the new definition early.

Now let's look at the other possibility, in which we want a new definition to call and extend an existing definition of the same name:

 ok : init   111 .   ;
 ok init
 111
 ok : init  init  222 .  ;
 init isn't unique
 ok init
 111 222
 ok : init 0 . init ;
 init isn't unique
 ok init
 0 111 222

Here we have created a word "init" that displays the number 111, then we made a new word of the same name that calls the old one and also displays "222", and finally we made a third one that first displays "0", then calls the second one (which still calls the first one). It works because the name of each successive redefinition is hidden until complete, so the interpreter/compiler finds the previous one during the compilation of the new one.

Clearly, you should use this redefinition thing sparingly, lest confusion reign, but there are situations where this sort of thing can be extremely useful. It's especially nice for initialization sequences where each module can just add its own init code to whatever is already there. Open Firmware has several "initialization chains" that work that way.

The reason I'm explaining how all this works is because, unlike most other languages, Forth gives the programmer explicit access to the same machinery that the compiler uses. This, perhaps more than any other feature, is what makes Forth so powerful with such a small memory footprint. (LISP is similar in that respect.) Since the machinery is an integral part of the proposition, you have to understand the basics of how it works.

Stack Comments, Reprised

So far I have just been tossing out new definitions willy-nilly, without any documentation. That is fine when you are just fooling around interactively, experimenting. But, of course, when you are writing "keepers", source code that you want to save in a file, you need some documentation. The minimum documentation is a stack diagram. If I were to save the previous recursive definition of factorial in a file, I would probably write:

 : factorial  ( n -- n! )  recursive
    dup 1 >  if   dup 1-  factorial  *  then
 ;

The stack diagram "( n -- n! )" indicates that there is one argument and one result. For this example, that would probably be enough, since factorial is a well-known mathematical function and the name is pretty clear. If the intent of the new word were not so obvious, I would have added a line or two of commentary (beginning with "\ ") before the definition.

Forth also supports nameless recursion using the word "recurse" which simply calls the current definition. Using recurse, the definition of factorial could be written:

 : factorial  ( n -- n! )
    dup 1 >  if   dup 1-  recurse  *  then
 ;

Thus endeth the lesson.

Next Lesson