Some time ago I decide to fix one of the holes in my software engineering knowledge and learn about writing compilers. My undergraduate curriculum provided an overview of parsing and some general programming language design issues, but nothing at all on code generation or optimization. I bought a few books on compilers, started familiarizing myself with ANTLR, then became completely and utterly side-tracked by the programming language Forth.
Forth is a strange little language. Chance are that unless you’re an astronomer or have mucked around with Sun’s OpenBoot, you’ve never even heard of it; or if you have heard of it, you’ve never used it. Forth saw its heyday during the 80’s and has largely faded away with the 8- and 16-bit processors to which it was most suited. But boy was it suited to those processors — if I ever needed to develop code to run on a 16-bit processor with less than 128k of RAM, Forth is probably the language I’d turn to.
Forth’s key property is that it’s a purely stack-based language. Forth
functions — or “words,” as Forth calls them — do not take arguments explicitly,
but instead implicitly via a system-wide parameter stack. There aren’t any
local variables — instead the language provides a rich set of
stack-manipulation primitives like DUP1, SWAP2, and ROT3 to facilitate
juggling the top handful of stack items to provide the correct parameters to
each function call. Even control structures are implemented with Forth-level
function calls!4 For example, here’s my implementation of IF / THEN:
: if compile ?branch here 0 , ; immediate : then here swap ! ; immediate
This means that a Forth program consists of nothing more than a list of functions to call in sequence, a feature which the language exploits in two ways.
First, to simplify syntax. Just as a Forth program abstractly consists of nothing more than a list of function “words,” the source code of a Forth program consists of just lists of those words’ human-readable names separated by spaces. Adding the ability to switch the Forth system between executing each word as parsed and appending it into a new definition allows the system to act as both interpreter and compiler in one. That’s a full interactive interpreter and compiler in under 8k.
Second, to simplify implementation. There are “traditional” optimizing compilers for Forth, but that isn’t the most common or most obvious approach to Forth compilation, especially in-target. More frequently, Forth systems will use an approach known as “threaded code.” This has nothing to do with multithreaded execution, but instead refers to the technique of generating code which consists of only of calls to other functions. The more specific techniques of so-called “direct” and “indirect” threaded code drop even the calls themselves5 and instead encode only the function addresses. A list of address can’t be executed directly, so this necessitates an “inner interpreter” to load and call each in sequence, but this interpreter need only be a few machine instructions long, and on some architectures imposes no additional overhead over directly-expressed function calls. In a Forth system using this approach, compiling a function call into a new definition literally consists of just appending the address of the function to call to the end of the definition in progress. It just can’t get any simpler than that.
And because it’s all so simple, you can implement it yourself! Or rather, I can lose the thin thread of sanity and decide to implement one myself. There are existing F/OSS Forth systems out there for pretty much every environment under the sun, which provide plenty of examples to turn to for inspiration, but also mean that the whole Forth thing is pretty well done. This needn’t be a hindrance to implementation-as-a-learning-exercise, but I wanted to contribute something new. I happened to think of the Z-machine, and lo-and-behold, although there is a Z-machine scheme implementation, there was no Z-machine Forth.
Until now! Ladies and gentlemen, I present to you ZmForth!, an ANS Forth implementation for the Z-machine. It passes the woefully incomplete ANS Forth test suite I found and runs existing Forth programs that don’t depend on file I/O. It plays Tetris, performs 32-bit arithmetic and unsigned comparisons, and provides exceptions, a compiler, and a de-compiler. All of this in a 16-bit virtual machine with only 64k of addressable memory. The whole project was one giant rabbit hole, but I had to write my own Z-code assembler to provide the directives I wanted, which is at least in the direction of what I initially planned to work on.
I had a good time working it, and I hope someone else may be at least half as entertained by it as I was.
1 Duplicate the stop stack item.
2 Swap the top two stack items.
3 Rotate the third stack item to the top.
4 In fact, in my system all the control structures are implemented in Forth.
5 The call instructions, that is.