Go Forth!
I was writing recently about my fondness for RPN [Reverse Polish Notation] and this reminded me of a programming language, designed specifically for real time and embedded applications, which has largely been forgotten: Forth. It is interesting to look at how Forth worked and the benefits it offered for embedded developers. I am not proposing that the language be revived and used for new developments, but I think there are valuable lessons to be learned.
My attention was originally draw to Forth when somebody told me that there was a programming language which facilitated the generation of code using less memory than an assembly language implementation of the same functionality. I did not believe them, but it hooked me in …
Forth is a Threaded Interpretive Language, which means that the code is compiled into an internal form, which is read by runtime software to give the effect of execution, much the same way that Java is normally implemented. It is possible to include native assembly language components as required.
A Forth program is comprised of a number of “words” – entities that are basically similar to functions in C. Each word consists of references to other words, which may be predefined or ones created by the developer. A word may also be an assembly language routine. In source form, a word is any sequence of non-space characters; when compiled, they become a list of addresses, which point to other words or assembly language.
A fundamental aspect of Forth is its use of a stack, which it uses for most data manipulation. Words tend to operate on the data on top of the stack, maybe removing it, and place results there.
Forth may be used interactively, where each line of code is executed when the RETURN key is pressed, or it may be compiled for create new words. For example, you could type this line:
3 dup + .
The interpreter would [probably] not find a word called “3”, so it would attempt to treat this as a constant and place the value on the stack.
The word “dup” results in the duplication of the top stack item [so now there are two stack entries of the number 3].
It is probably obvious that “+” adds together the 2 top items on the stack and pushes the result [6] there.The last word, “.”, pops a value off the stack and displays it.
If this were an operation that you wanted to perform frequently, you could define a word of your own to do it, thus:
: show2times dup + . ;
The word “:” tells the interpreter to start compiling a word with the name that follows – in this case “show2times”. The “;” marks the end of the text to be compiled. Having done this, you can double and print 3 by typing:
3 show2times
From this short description and trivially simple example, I hope that you can see that Forth is conceptually quite different from C and other more familiar languages and also has a lot of flexibility and expressiveness. Many people criticize Forth for being a “write only language”, as it is very easy to write code which is impossible to read. Although I would agree that this is true, I promise that I could write some completely unintelligible [but valid] C, if required to do so.
Last week I attended a seminar, where one of the speakers was discussing the history of their company over the last 25 years. He talked about their first project being done in Forth and commented that this was unlikely to be the way things would be done today. I wonder if Forth will ever see a revival. Or maybe there are people out there still using it …
Forth is still out there. It is beloved of test and hardware development engineers as it is good for bringing up and testing hardware. That is partly why it is the boot language of Sun systems. Charles Moore was a hardware hacker and invented Forth to help him do better hacking.
.
As you note, the data stack is the unusual part of Forth. Its primary function is to pass operands to and from the Forth words. You use the stack for the parameters rather than enumerating them explicitly in the call structure, as is required in almost all languages from Fortran to C and onward.
.
It turns out that the stack is not a bug, it is a feature. It has benefits: 1) You do not have to name your parameters to pass them. for example, a parameter on the stack can (and often is) the un-named result of a previous calculation. 2) You do not have to name your parameters to manipulate them. Languages that use equations to calculate and move data *require* that each piece of data be named, even if it is a temporary variable for one-time use. This clogs up the name space, and it does so approximately in proportion to the size of the program in lines of code.
.
I discovered this unknowingly many years ago when I tried a Forth variant for a consulting project. It worked amazingly well. My personal productivity was 10X what I had experienced using other languages. You can argue with benchmarks, but it is harder to argue with your own experience. This is partly why Forth people are a little zealous. They have experienced it, cannot explain it but propose it as The Solution based on their experience.
.
What I remembered recently but did not observe at the time is that I did *not* implement Forth. I only added a data stack for passing all subroutine parameters. That’s it. Full stop. But I got the speed up using it – using assembly language code!
.
Many have tried to explain the benefits of Forth. Most explanations cite the usual suspects: terse coding, interactive development, tight compile-test-recompile loops, etc. Most avoid discussing the stack because its DUP, OVER, SWAP, DROP operations are hard to justify versus familiar, you-learned-them-in-school equations. The stack seems to be mildly embarrassing.
.
But the stack is the real secret to Forth. Once you know this, things sort out nicely. The data stack eliminates most variable definition, because most variables are temporary, disappearing when program execution is complete. This is not because it is hard to define and use variables. It is easy. But if you do not need them, you tend not to bother. I have generated large programs that use less than 10 variables. And this is without any restrictions on their definition and use.
.
This is topical. One of the intended benefits of object oriented programming is to try to get control of the name space as programs expand. The Forth data stack does this automatically for data variables, which is often the fastest growing portion of the name space. And it does it without any explicit methodology or enforcement of name space control. Perhaps this is a subject that should be revisited.
Very interesting thoughts Dave. It would be interesting to write some C code that uses a data stack like that. All that would be needed is a library of primitive functions – push(), pop(), drop(), swap() and rot() might be enough.
Chuck Moore’s company GreenArrays, have just announced production of their 144 core microprocessor has commenced.
Thanks Craig. Interesting.
Very do-able. For example, there are several Forths written in C, such as gforth and ficl. It could result in an interesting blend. Here are some musings:
1. Use the stack to pass all parameters, both “by value” and pointers.
2. Use local variables inside the called routines. Inside the called routine, you would typically pull the items you need off the stack, put them in local variables, use equations to manipulate them and push the results back on the stack.
.
One additional potential advantage of the data stack approach is that the subroutine calls can be low overhead = quite fast if the compiler allows it. No need to set up a stack frame at run time to pass variables. A simple bare call, pushing the return address on the hardware return stack is sufficient for all routines.
.
Using the principle of eating your own dog food, I may just try this for fun soon. Thanks for the nudge.
You know Dave, there could be a whole new programming methodology here. I can see it now: books, conference papers …
I love the “eating your own dog food” concept.
Do let me know if you progress this.
I dabbled with Forth a while back (198s/90s). While Forth has largely fallen from grace, its ghost still lives on.
As Colin mentions RPN (and the more general RPL) is Forth-like. I’ve been using RPN calculators for over 30 years and have a collection of 8 or so and really struggle to use anything else.
The more common example of a Forth-like programming language is postscript. Most times you hit the print button you’ll be generating a postscript program which is sent to the printer for execution.
Forth lacks any types or type safety. That is a freedom or an oversight depending on how you look at it. If you put a string on a Forth stack and execution expects a float you’ll get a mess! RPL and ps both have a typed stack.
As noted, Forth is often smaller than the equivalent assembler because a word is just a list of addresses and there is no overhead for the call instructions.
On a general purpose CPU, Forth is rarely faster than the equivalent C code because each function(word) execution requires two steps: Read the address, call the address. That adds overhead that regular assembler/compilation code does not have to deal with.
Good input Charles. Thanks. I regard the untyped stack as a freedom – but you probably guessed that.
test
Hi Colin, thanks for this interesting post. I heard of some Forth fans lately and there is indeed a vibrant community supporting it.
Now, if you really want to implement a stack in C, you can switch to C++ and use the existing data structure. Now, I’m not sure I would do that on an AVR8 🙂 A native Forth implementation may be more efficient in this case.
Interesting to hear that it’s alive and well Olivier [and, indeed, that you are :-)].