Forth: The Other White Meat

Lisp has been constantly touted as a language that any self respecting coder must learn. The proponent's of Lisp have every right to make the claims that they do. From the prospect of stretching your mind Lisp actually is as good as they say it is. Lisp is a principle member of a small, elite group of languages, the use of which really causes a fundamental change in the way people think about programming and system design. However, it is not the only member of this group. The group includes at least one other language, Forth. Forth is just as mind bendy, introspective and universal as Lisp but it doesn't tend to get the same amount of press as its older brethren. Well, I intend to change that. At least for the small corner of the world that reads this column.

I know that as soon as I mentioned the F word (Forth that is ;) a general groan went up from those of you that have some experience with it. Don't worry, groaners, I feel your pain. However, take a couple of aspirin sit back and listen to me for a bit and you might gain a different prospective on the language. For those of you not familiar with the language, the reason for the groaning will become obvious as our story progresses.

I had given some thought to going about and gathering up all of the 'quotes' that people use to promulgate Lisp and then justifying them for forth. After thinking about it, I decided to take a slightly different tack. I went this other route mostly because Bill Clementson has already done most of the gathering work for me and also because I think that you're smart enough to draw correlations without me beating you over the head with them. So take a couple of minutes, pop over Bill's site and read the quotes. Don't worry, I'll wait.

What Is Forth

Back so soon? good. Forth is a language that takes a wildly different tack then any other language out there. It was initially developed by Charles Moore at the US National Radio Astronomy Observatory in the early 1970s. Back in the early sixties, while working for the Smithsonian Astrophysical Observatory Mr. Moore found a need for a little bit more dynamisim then he had had in the past. To that end he put together a little interpreter intended to control a punch reader. By using this interpreter he could compose different equations for tracking satellites without recompiling the entire system. This was no small feat for the time. Mr. Moore, like any good hacker, took his interpreter with him when he left that job. He carried it around for the next five or ten years constantly tweeking it. By 1968 it was finished enough to build up a little game called SpaceWar as well as pretty nifty Chess system. This version of the language was the first to be called 'Forth'.

This early evolution and constant tweaking produced a fairly interesting language. A forth program is simply a series of tokens, called words, and two stacks. The stacks represent the main data stack and the return stack. For right now we will ignore the return stack and talk about the data stack. To give you comparitive examples, lets look at an operation in Lisp and Forth. The Lisp version is perfectly recognizable to just about anyone. It just adds two numbers together.

> (+ 1 2) 
 3

In Forth, it goes as follows.

> 1 2 +
 3

A more complex example

> (/ (+ 27 18) (* 3 3))
 5

In Forth, it goes as follows.

> 27 18 + 3 3 * /
 5

If you have been exposed to some of the old TI calculators or even Postscript you may be able to tell whats going on here. Each number as it appears gets pushed onto the explicit data stack. The '+' words (and words they are) take exactly two numbers off the stack and replace them with the value resulting from there addition. So what we get on terms is.

> 1 2 + ( results in 3 on the stack)

This explicit stack is the way all data is handled in Forth, everything. You may remember that I said everything is a token. Thats absolutly correct. Forth reads each token and looks it up in a special dictionary that is used to store references to words. We create entries in that dictionary as follows.

 : square
    DUP * ; 

The colon is an immediate word (read macro) that reads ahead one word in the token stream and uses that word to create a new entry in the system dictionary.

It then reads ahead until it finds a semi-colon ';' which it uses to indicate the close of the word. It then compiles the intervening tokens into references to words. It is as simple as that. 'Hold on, Hold on!' you say. 'You said everything was tokens in a forth system, aren't these special'. Nope, I didn't lead you astray. The colon and semi-colon aren't special at all and can be overwritten and changed at any point you like. The are examples of Forths powerful macro facility in which you can create syntax for a language that essentially has none. This is a powerful concept that Lisp shares. As Paul Graham says you can use this to build up your language to the system instead of the other way around. Of course, there is a downside. Any time you give the programmer extreme flexibility someone is going to abuse it. For example take a look at this example from a Forth library in the wild.

: rework-% ( add - ) { url }  base @ >r hex 
   0 url $@len 0 ?DO 
       url $@ drop I + c@ dup '% = IF 
           drop 0. url $@ I 1+ /string 
           2 min dup >r >number r> swap - >r 2drop 
       ELSE  0 >r  THEN  over url $@ drop + c!  1+ 
   r> 1+ +LOOP  url $!len 
   r> base ! ;

Granted I have taken away the context, but you begin to understand the impetus behind those groans you heard a short while ago. Forth is one of the most flexible languages available, but the very flexibility that makes it interesting also makes it dangerous. It takes diligence on the part of the programmer to write really clean and maintainable code. However, if the coder does take that care he can write imminently readable and maintainable code. Take a look at the following examples that appeared in Starting Forth by Leo Brodie. You can get a good feel for whats going on even without knowing the context.

 : WASHER  WASH SPIN RINSE SPIN ;
 : RINSE  FAUCETS OPEN  TILL-FULL  FAUCETS CLOSE ;

So doing Forth well or not is entirely in the hands of the coder, that's why the Forth experience varies so much. That's why Forth is a Language for Smart People.

Forth Basics

I have the very good luck of owning a copy of the book Thinking Forth. This is one of those books that you should add to your library even if you never intend to write a single line of Forth code. It has a huge amount of great insight onto coding and system design in general, though you probably don't want to use it as your first introduction to Forth. In any case, I am going to be borrowing some topics and examples from that book to see us on our way.

: breakfast
    hurried? if cereal else eggs then clean ;

The above example illustrates the fundamental building block of every Forth system, the word. This specific example is whats called a colon definition. Its how you define a word in Forth. Basically the colon ':' in an immediate word (think macros operating on the word stream) that takes the very next word and creates an entry in the dictionary based on that word. It then reads all the words up to the semi-colon ';' that tells it to stop. For each word it encounters it looks up the position in the dictionary and puts that location in the code stream. Of course, in this case we have the if immediate word that takes control for a little while before handing it back. So what specifically might be going on here. In this case, hurried? probably looks at some parameter in the system to decide if haste is in order and puts a boolean on the stack. 'If' is an immediate word that compiles to a jump based on the 'else' and 'then' words. You can probably figure out what it does from here.

This, admittedly simplistic, example does illustrate a few of the special characteristics of Forth. Most notably, the stack, words, and use of immediate words.

Factoring

Long before any one had ever heard of Agile Methodologies or Extreme Programing the idea of factoring was already hard at work in the Forth community. The idea of constantly looking at code, breaking up functions and generally simplifying the systems in a foundational concept in Forth. In fact it's taken to something of an extreme. Words are a huge part of Forth systems and the factoring process. For example, consider the following word which finds the sum of squares of two integers:

 : sum-of-squares   dup * swap dup * + ;

The Stack inputs to the word at run-time are two integers. The Stack output is a single integer. By the process of factoring, the example would be re-written in Forth using a new definition called 'squared' to allow sharing the common work of duplicating and multiplying a number. The first version was overly complex and illustrated the notorious line noise aspect of Forth. Fortunately, by factoring the system we can make a much more readable and understandable system.

 : squared  dup *  ;
 : sum-of-squares  squared swap squared + ;

Good Forth programmers strive to write programs containing very short (often one-line), well-named word definitions and reused factored code segments. The ability to pick just the right name for a word is a prized talent. Factoring is so important that it is common for a Forth program to have more subroutine calls than stack operations. Writing a Forth program is equivalent to extending the language to include all functions needed to implement an application. Therefore, programming in Forth may be thought of as creating a Domain Specific Language. As Lispers well know, this paradigm, when coupled with a very quick edit/compile/test cycle, seems to significantly increase productivity.

Immediate Words (The Macros of Forth)
In comparison with more main stream languages, Forth's compiler is completely backwards. Most traditional compilers are huge programs designed to translate any foreseeable, legal combination of available operators into machine language. In Forth, however, most of the work of compilation is done by a single definition, only a few lines long. As I have said before, special structures like conditionals and loops are not compiled by the compiler but by the words being compiled (IF, DO, etc.) You may recognize this sort of thing from Lisp and it's macro system. Defining new, specialized compilers is as easy as defining any other word, as you will soon see. As you know, When you've got an extensible compiler, you've got a very powerful language!

Forths I Have Known

There are a couple of new Forths out there that are breaking with the Forth tradition somewhat and innovating in this area. One that I especially like is Factor. It's a very minimal but consistent for with some modern ideas like garbage collection, CLOS like object system, strait forward higher order functions, etc. This forth kind of bridges the gap between Lisp and Forth. A good traditional forth is Gforth. Its reasonably fast, reasonably stable and implements the full ANSI spec. You really can't go wrong with gforth if you want a good forth that will stand the test of time. If you just want an easy, interesting forth that will run just about anywhere I suggest you take a look at Ficl. Its ANSI compliant Forth written with in C as a subroutine threaded interpreter. It is stupid simple and about as robust as you can get. This is a really nice forth to start you tinkering with. Now if you want a Forth that is really stretching the bounds of what is possible and desirable take a look at Chuck Moore's latest Forth, Color Forth. It's the only language that I know of where color (yes, color) actually has semantic meaning. That the custom 25 core chip that color forth is designed to run show the Mr. Moore is really pushing the boundaries. It's worth while taking a bit of time exploring ColorForth just because of it's divergence from mainstream.

So Why the Comparisons to Lisp?

I think that many more people have had some exposure to Lisp then Forth. Because, Lisp and forth share so much 'meta' philosophy, I thought it would be beneficial to draw comparisons between Lisp and Forth. You will have to be the judge of whether this was a successful approach or not.