August 2022
To dislike a programming language is easy, but to particularly dislike one requires a good reason, and here’s mine for particularly disliking both Lisp and Forth: They’re not so much languages as they are meta-languages. Step 1 of any project is to write a bunch of compile-time macros to create the actual language you will use for your project. But designing a language takes time and experience and taste and restraint, all of which you are short of, and the future maintainer of the project (maybe you) will suffer the consequences of the garbage you just spewed out so you could get started on the real work.
This doesn’t happen in languages that don’t have macros. You simply write the project, and you do it in a language designed by an experienced professional language designer. That is, unless you’re programming in PHP, in which case you’re programming in a language designed by someone who literally hates programming.
That’s the theory. In addition to having a good reason, it’s useful to have actual experience with the language, so I wrote a Forth interpreter. And because I do things in hard mode, the interpreter is written in assembly language for an ancient CPU called the Z80, targeting an ancient machine called the TRS-80.
(An alternative origin story is that my friend Dan Collens and I were building a Z80-based single-board computer, and I got tired of writing assembly language for it, so I put to the test the old maxim that Forth is the easiest language to port to a new machine. I later ported this interpreter to the TRS-80.)
Forth is famously stack-based. I originally thought this meant that the only thing it could do was access a stack, but if that were true, it wouldn’t be Turing-complete. Turns out it can also access memory randomly, allocate new memory, and from that do anything else, such as create variables and complex data structures.
Still, when you implement a Forth interpreter, you do start with a stack. Two, in fact, because there’s a way to define functions and call them, so you need a call stack (to remember where to return to after a function ends) and a data stack. The data stack in a normal programming language is intertwined with the call stack, and Forth’s separation of these two is what makes it fundamentally stack-based. You can push a parameter onto the data stack and call a function, then that function can push more stuff onto the data stack and return to you! They’re decoupled.
One design question is whether to use the system stack for the call stack or for the data stack. Usually the data stack is chosen, because operations that mess with it are more common than function calls. The call stack is therefore implemented manually using an ordinary register for the stack pointer.
The typical way to implement an interpreter is to convert the raw text to some kind of bytecode format, then have a large switch statement to implement each type of bytecode. Python works like this. Most Forth interpreters do something that’s somewhere between an interpreter and a compiler. The bytecodes, instead of being fixed like 5 always means “add two numbers”, are the address of the “add two numbers” function. Running the program entails simply reading the address and jumping to it. (And here “jumping” doesn’t mean sending the virtual program counter to it; it means literally jumping the CPU to it and executing it like machine language.) That routine can either do something using native code, or start the process of following a sequence of addresses again.
This is pretty great, not only because it saves a switch dispatch for every bytecode, but it also causes the lookup of symbols and functions to be done at compile time instead of runtime. Interpreted Forth has little overhead compared to assembly language.
Forth is simple to implement mostly because it requires few built-in functions. Mine has 56, including graphics routines, and you could get away with fewer if you wanted to sacrifice some performance. The rest of the language is defined in a normal Forth text file (init.fs) that’s parsed at start-up. This file defines surprisingly low-level functions like “if” statements, looping constructs, and the ability to create variables.
What makes all this possible is the distinction between immediate mode and compiling mode. As in Lisp, you can write code that is executed when a function is parsed. This lets the code hijack not only the code-generation phase, but (in Forth, not Lisp) the parsing itself.
As a warm-up, here’s the definition of a function that squares a number:
: square dup * ;
The colon means “start new function definition” which goes into compiling mode and expects the name of the new function (square). The dup duplicates the item at the top of the stack (that’s the input parameter) and * multiplies the top two items (which are the same now) and pushes the result. The semicolon finishes the function definition. You can call it like this from within another function, or in the interactive Forth prompt (the REPL):
5 square
The “square” function ends up being two words long, with the words pointing to the addresses of the “duplicate” and “multiply” built-in functions. Here’s a function foo that prints a number if it’s greater than 5:
: foo dup 5 > if . then ;
(The dot means “print the number on the stack”.) But if is not a built-in function, and you wouldn’t be able to define if yourself if all you had were regular functions like square. How would it skip the stuff you didn’t want to do (the part until the then)?
The solution is to mark the definition of the if function as immediate, meaning that it runs immediately when seen in another function, instead of being added to that other function’s code block. It’s in every other way like a normal function, and is kinda equivalent to a macro in Lisp. The first thing it does is add a “conditional jump” instruction to the code block and leaves a blank space for the target of that jump. It doesn’t yet know the address of the end of the function, so it just pushes a zero. It also pushes the address of this blank space on the data stack (at compile time):
: if immediate ' 0branch , here @ 0 , ;
Note the immediate qualifier. The final then function pops that address off the stack and writes to it the address of the end of the function we just compiled, so that the original branch goes to the right place:
: then immediate dup here @ swap - swap ! ;
The original foo function gets compiled to this sequence of words:
The number 2 is the number of bytes to skip if the condition is false. That’ll skip over the dot call. Lines 5 and 6 were generated by the if macro, and the rest were compiled normally. That’s the power of immediate functions: they can generate any code, and do so procedurally. They extend the compiler with user-written functions.
I copied the definitions of if and then from some Forth website, I can’t remember where, but pretty soon I wanted “for” loops (called “do-loops” in Forth). According to the Forth spec, these specify an initial and final value for the index, provide the i variable inside the loop to refer to the index, and can be nested three deep (using the variables j and k). It took me a while to figure out how to define these two macros—mine run 54 lines long! But then you can write this to fill the TRS-80 screen with sweet sweet rectangular pixels:
48 0 do
128 0 do
i j set
loop
loop
Note that this won’t actually run at the Forth command prompt. That’s because code at the prompt is entirely interpreted, whereas the do and loop functions assume they’re being run as part of the compilation of a new function. But that code will work fine if it’s part of a function.
I have to mention one cool thing about the way the interpreter is written. It keeps all known functions (which I keep calling “functions” but Forth calls “words”), both built-in and user-defined, in a linked list. The built-in ones are just defined in the assembly language source code, and you’d expect some kind of initialization step where they’re added to the run-time linked list, but instead the code cleverly uses assembly language macros to build the linked list at assembly time. The M_forth_native macro here defines the swap function (which swaps the two top items on the stack) and adds it to the linked list by generating the “next” pointer to the previous function and updating that pointer to itself:
M_forth_native "swap", 0, swap pop hl push bc ld bc, hl jp forth_next
Yes I’m aware of the irony of bragging about an assembly language macro to define essentially a mini-language in a blog post bashing exactly that.
In the end I find Forth even harder to program in than I’d predicted (it’s really hard to think about what’s on the stack at all times), but I didn’t make a large enough program that I could succumb to the temptation to make my own mini-language and screw my future self over. So I guess that question is still open.
You can try a live version of the interpreter in my web-based TRS-80 emulator. Try demo-lines for a graphics demo, or type a bunch of numbers and math operators (separated by spaces) if you want to experience true reverse Polish power.
The source code is available on GitHub.
(Cover image credit: Midjourney, “Very high stack of plates, illustration.”)