Forth
Wow, it's been a long time since I wrote a blog post. Sorry about the delay in finishing my Haskell state monad series; it's coming, I promise.
The reason for this post is that I stumbled upon a very cool free (and well-documented) interpreter for the Forth language written in x86 assembly language. That implementation, by Richard Jones, can be found here, if you're impatient. In my previous post about foundational programming languages, I described Forth as a very cool but not quite foundational language. Here I'll expand on why I think Forth is cool, and why every serious computer language geek should look into Forth.
I go back a long way with Forth. I learned the language from a wonderful book by Leo Brodie called Starting Forth. It's out of print but can easily be obtained used, and there is a web version here. A version of Forth running on a microcomputer was one of the first language implementations I ever seriously worked with. At the time, the mainstream languages on microcomputers were Pascal and C, both of which I found uninspiring. Forth was a revelation to me.
In Forth you can write a bit of code and immediately execute it. Programming in Forth feels more "organic" than programming in most compiled languages. (Forth has a compiler too, but it doesn't work the same as most compilers do.)
Forth code can talk directly to the machine much like C code; in fact, you can easily hand-code snippets of assembly language directly into your Forth program (this is possible in C as well, but it's much less of a hassle in Forth).
Forth is "concatenative". What this means is that Forth function calls don't explicitly pass arguments. Instead, arguments are kept on a data stack, and argument passing is implicit. This means that chaining together a series of function calls to make a new function just involves concatenating the function calls (do-this-then-do-that-then-do-that), with possibly some stack juggling to make sure that the arguments are in the right position.
Function definitions are typically very short. In fact, good Forth style is to have function definitions be no more than one or two lines. Code is "micro-factored" because the overhead of function calls is extremely low. This leads to a very different style of programming.
Forth is built around a virtual machine which is completely open. You can inspect the state of the virtual machine at any time. More importantly, you can modify the VM. Everything is under direct user control at all times! You can change the command interpreter if you like. You can extend the compiler. Basically, you can do anything you want (though some things are naturally easier to do than others). For instance, control constructs in Forth are just normal function calls, and you can implement new ones if you want to. These new control constructs can be just as efficient as the built-in ones.
Forth is small, small, small. An entire Forth-based operating system can be implemented in only a few kilobytes of code. Yes, kilobytes; you didn't read that wrong. Of course, it's going to be incredibly primitive, but it will allow you to write programs, edit them, store them, and execute them.
Here is a simple snippet of Forth code:
: squared dup * ;
This defines a new function called "squared" which will square the top element on the stack. It works by duplicating this element (the dup function) and then multiplying the top two stack elements (the * function). Note that there is no notion of "operators" in Forth; operators are just regular functions. Pretty short, huh? It also illustrates that functions work in a "postfix" style, though really that's a by-product of functions executing immediately (in other words, there is (almost) no parsing). By the way, the : in the function definition above starts a new function and the ; terminates the definition. I say that there is almost no parsing because : does in fact read the next token to get the name of the function being defined. That's about as much parsing as Forth ever does. Of course, the : and the ; are not operators or special syntactic forms; they're just regular function calls.
You use the above function like this:
10 squared
The 10 puts the number 10 on the top of the stack. The squared function call changes it into 100. Done.
Forth has historically been used mainly for programming embedded systems, systems for which memory is so limited that assembly language is normally the only other way to program them. Forth is used as a thin layer over the assembly language, and the Forth code is often smaller than the equivalent assembly code would have been (due to the "micro-factoring" I alluded to above).
There is little standardization of the language; though a standard exists, many, many implementations deviate from it wildly. As the saying goes, "When you've seen one Forth -- you've seen one Forth." Furthermore, this is not willful anarchy, it's part of the Forth philosophy. Chuck Moore, the inventor of Forth, even went so far as to say that he hated the whole idea of Forth standardization and encouraged variant Forths.
So what is this "Forth philosophy", anyway? Well, first I'll make this disclaimer: I'm not by any means a Forth expert, though I have written a decent amount of Forth code over the years and have implemented a couple of Forth-like languages and read some books on the language. Anyway, as far as I can tell, the Forth philosophy is one of extreme, almost Zen-like simplicity. Basically, a Forth programmer wants to throw out absolutely everything he possibly can in his program and in his programming environment except that which is absolutely essential for solving the problem at hand. In addition, since the programming language and environment are so tiny, they can be part of every program, and they can be specifically tweaked for that program. So instead of having one Forth and many programs, each Forth can be specific to a particular program. In other words, the language is the program. Furthermore, the program is not written "top-down"; instead, you grow the language up so that it reaches the problem domain. Every Forth program is a domain-specific language. You see this approach in other languages (notably Lisp; see Paul Graham's book On Lisp), but Forth carries it to an extreme. By the way, Leo Brodie wrote another great book called Thinking Forth describing the Forth philosophy in detail.
To say that this is disorienting to an average programmer would be a massive understatement. If you find unusual programming paradigms unpleasant, you should definitely look elsewhere. And even if you don't, trying to use techniques from other programming languages while you're writing a Forth program is almost guaranteed to fail big time. Forth doesn't just encourage a different style of programming; it demands it. For one thing, a Forth implementation typically lacks many features that you would expect from a programming language. Many Forths don't even support floating point numbers. Many have only rudimentary string support. Most have almost no notion of modularity. And you can find Forths that have all of these features, plus many more. The point is, you have to ask yourself if your specific problem actually needs those features. If it doesn't, why should the language (and remember, the language is the program) have to support them? Why should I use a giant fully-loaded Forth to write a program that only uses 1% of its features when I can write a tiny, stripped-down Forth that only contains the features I need?
Parenthetically, if you do want to experiment with a fully-loaded Forth, I recommend gforth, by Anton Ertl and Bernd Paysan. Gforth takes up a whopping 80 kilobytes of space, so it's a monster by Forth standards ;-)
As I said above, I've written a couple of Forth-like language implementations for fun in the past. One was in Ocaml and wasn't really very Forth-like; it was more of a cross between Forth and Scheme. The other was in C and was pretty close to standard Forth. Since C is already a pretty low-level language you'd think it would be a natural choice for implementing Forth. However, as I worked on my implementation I started to wonder about this. It turns out that there are things you need to do in a Forth implementation that are hard to do in C, or hard to do efficiently. (Gforth is written in C, but it uses non-standard extensions of C supported by gcc as an essential component of the inner interpreter code). Basically, Forth is implemented most naturally directly in assembly language. I like to say that "The Forth that is not implemented in assembly language is not the True Forth". Maybe I'm wrong about this (and no offense to the authors of gforth, who have forgotten more about Forth than I will ever know), but it's clear at least that implementing Forth in assembly language is an interesting task. Furthermore, it will teach you how Forth works in a way that nothing else will.
That's where this implementation, by Richard Jones, comes in. It's an implementation of Forth in x86 assembly language, with extensive comments explaining how the code works. The implementation actually consists of two files: the assembly code itself (2313 lines including comments) and the Forth source code (1790 lines including comments). The Forth source code is necessary because a large part of Forth is itself implemented in Forth. The assembly code is a minimal layer necessary to bootstrap the language.
If you're interested in grokking how Forth is implemented, I can think of no better starting place.
One other thing: even though I think Forth is way cool, it would not be my first choice for most of my programming projects. There are too many features I consider essential for most of my programming work that are missing from Forth (and are very hard to add to it). These include garbage collection, first-class functions and a type discipline. So Forth is not going to steal the place in my programmer's heart where Scheme, Ocaml, Haskell or even Python currently live. Nevertheless, I still think it's one of the most beautiful ideas in the history of programming languages, and it's well worth studying and admiring.