Thursday, February 20, 2014

How I came to join the underground computer cult of Forth

In which our protagonist talks at length about Forth with the disconcerting fervor of the newly converted and reorientates his grand project accordingly.

Since I never get anything done in November or December anyway -- somebody in the family is always sick -- I said "screw it" this year and left the Übersquirrel in a dust-proof box. Instead, I have been learning Forth, a programming language that everybody keeps talking about in the forum. It was time well spent: Forth will blow your mind and change the way you look at programming in general. It will also make the Übersquirrel that much more powerful.

So, this entry is all about Forth.

(If you are not interested in fringe programming languages or speculation on the mental state of their inventors, this is your cue to go do something else. From here on, it's stacks all the way down.)

Chances are, you dimly remember Forth as a minor programming language popular in the 80s for small computer systems and now mainly used in hardware setups, embedded systems, or boot loaders like Open Firmware. In fact, most people have never seen any actual Forth code. This is probably a good thing: What immediately comes to mind is that whoever invented the language must be either batshit crazy or a friggin' genius.

A snippet of Forth code from my first larger project, a 65c02 disassembler. What looks like the result of your cat stepping all over the keyboard actually makes sense.

That would be Charles Moore, and it is considered polite in Forth circles to go with the genius option. There is ample support for this idea, but you do have to survive the shock of first contact with the language and dig down a bit to appreciate it. Put briefly, you need to get from the weird to the wow.

Let's start with the word "language". Forth is actually a programming language, an operating system, and a shell rolled in to one. Even the language part is iffy: It is more a sort of low-level meta-language. As Leo Brodie explains in his classic Thinking in Forth:

Forth is a programming environment for creating application-oriented languages.

This "environment" is not limited to software. There are amazingly simple "stack machine" CPUs that are built just for Forth. Some are used in spacecraft such as the Cassini-Huygens mission currently at Saturn. We're are talking about a whole computer ecosystem outside of the mainstream.

In his (highly recommended) blog post "My history with Forth and stack machines", Yossi Kreinin compares Forth to bacteria that strip down their biochemical machinery to the absolute minimum. I'd compare it to a whole different branch in the tree of life, like suddenly discovering there is not only photosynthesis, but also chemosynthesis going on in the ocean vents. This gives us another parallel: Half of the time, nobody really knows what the hell is going on down there.

More on that later. Let's look at actual Forth.

It's a stack-based language with "postfix" or "reversed polish notation" (RPN) notation like the upmarket HP calculators. This is normal "infix" representation:

2 + 4 =

This is what they taught you in school, this is what you are familiar with, and this is probably how you think. In contrast, postfix looks like this:

2 4 +

Other people explain this all better and in more detail elsewhere. The important thing is that postfix makes a bunch of things a lot easier, because the order is implicit. There are situations where infix must use brackets and follow special rules:

2 * (4 + 6) =

Postfix thinks that is totally lame and stupid.

4 6 + 2 *

Done right, parameter passing becomes trivial, because what you need magically appears where it should be, right on top of the stack (do it wrong, and you spend your time moving stuff up and on the stack and feel like an idiot). Stack machines generally do some things better and worse than others, but we'll skip that here.

After a lifetime of thinking in infix, postfix makes your brain hurt (there is a lot of that with Forth initially; I'm still recovering from POSTPONE). Calculations like those above are not really the problem, at least with some practice. It's that Forth uses postfix for everything, including branching and loops. This is the Forth version of IF-THEN (using capital letters for readability):

done? IF stop-it THEN

IF-THEN-ELSE gets really screwy:

done? IF stop-it ELSE keep-going THEN

In the beginning, it helps to think of THEN either as "after all this is done" or simply ENDIF, which was actually a synonym in earlier versions of Forth.

This example shows us something else about Forth that takes getting use to: Special characters aren't. If you are used to the Unix shell, the Forth way of marking variable and word names with question marks, periods, hashes, quotation marks, and all sorts of other "reserved" characters will freak you out. However, these conventions make perfect sense once you have understood the conventions. Something like PARROTDEAD? returns a true or false value, while ?PARROTDEAD is only executed if the top "cell" on the stack is non-zero. Anything with a dot at the beginning such as .CURSE should print something, and >BYTE is understood to be an index.

I've been talking about "words". Now we're getting to the part that is not just weird, but actually kind of cool, if not quite wow yet. Forth starts you off in an interpreted mode -- type stuff and it happens, like Python -- but lets you compile code into "words", little subroutines. Their definitions start with a colon and end with a semicolon:

: .FOUR 2 2 + . ;

The single period at the end of the definition takes the first element on the stack -- the number four in our case -- and prints it to the screen. When Forth reaches the semicolon, the word .FOUR is compiled and added to the "dictionary" of the language. It is now just as much a first-class citizen as, say, IF or + (addition). Dude, you have just expanded the language.

In fact, Forth is basically just a bunch of words and a rather primitive loop structure to handle them. This is why implementations can be so small, and why lots of people write their own [PDF] interpreter/compiler from scratch. Try doing that with C.

Forth does come with a set of "core" words, defined by ANSI "ANS" Forth 94. Unfortunately, this takes us back to weird world, because it is hard to believe that they weren't picked by Dr. Seuss. Some are short -- BL or BYE -- some are long -- EXECUTE or ENVIRONMENT? -- some are cryptic -- >R or 2@ -- and some are chatty -- OPEN-FILE or TIME&DATE. There doesn't seem to be any system to the selection. You just have to memorize them, or hope your cat steps on the right keys.

Once you do know them, you can build your own words using the ":" and ";" syntax. Ideally, a Forth program is "highly factored", with each word consisting of not much more than two lines of code. You start off with low-level primitive words at the beginning, and use those as building-blocks to create more and more powerful stuff lower down.

In a prefect world, you steadily increase the abstraction level until you end up with something amazingly simple in plain English (or whatever) like


to control your Death Star.

At this point, your reaction is probably something like, big deal, I can write subroutines in my favorite language as well. True. But now we come to the part that separates the men from the boys, the women from the girls and the three-meter aliens from the dog-derivatives: In Forth, you can define new words that let you make your own definitions. Kreinin speaks of his shock upon figuring out that things like IF and THEN are defined through other code -- "conditional primitives aren't":

It's as if a conventional program modified the assembly instructions generated from it at compile time. What? How? Who? How do I wrap my mind around this?

Being able to new words that control "compiling" -- what Forth calls what you do between the ":" and the ";" -- are what gives the language its real power. More Kreinen (emphasis in the original):

To this day, I find it shocking that you can define defining words like CONSTANT, FIELD, CLASS, METHOD -- something reserved to built-in keywords and syntactic conventions in most languages -- and you can do it so compactly using such crude facilities so trivial to implement.

At this point, let's skip over the technical bits in what is already a way too long blog post and get to the larger picture.

Most languages give you a toolbox that you can use to solve your problem -- say, Python's Standard Library with its famous "batteries included". You get a hammer, a screwdriver, a chain saw, and used in the right sequence in the right way, these let you build a table. Forth lets you build your own tools. You can write your own language to fit the problem. It doesn't even bother with standard data types like lists: Roll your own, custom-fit to your task!

This is also where the problems start.

A screenshot of the PDF of the first page of the source listing of the ancient Forth version FIG Forth. Some of us remember the sound that those printers made.

In the hands of a good or even great programmer who understands the problem and has the clarity of vision to figure out the best solution, Forth is amazing. Brodie walks the reader through the design of a script to convert an Arabic number to Roman numerals and the result is so short and compact it will make you cry. This is Forth at its most elegant.

However, understanding Forth code requires extra effort, because you can't just trace the steps in the sense of hammer-saw-hammer. You have to understand the mental representation the programmer developed of the problem, the language he invented to realize it, and the whole Rube Goldberg contraption he built to replace saws and hammers.

So in the real world, reading other people's Forth code can be a joy, with words flowing from top to bottom in a well-structured narrative while the angels sing praise to its conceptional beauty. Or it can be a mind-bending hell of cryptic words set in a sea of low-level symbols that make the stack writhe and thrash in agony. This is why Forth has a certain reputation as a "write-only" language: Other people's code can be a serious pain in the ass.

Which is where we come back to the Übersquirrel.

Forth is the most powerful thing I will be able to get running on this chip (don't talk to me about BASIC, ever; I grew up with it). I'm pretty much the only person who is going to read my stuff anyway. And there is an old version of Forth called FIG Forth that has been ported to the 6502 and is freely available.

So what we are going to do now is stop work on Squirrel OS and see what we can do with FIG Forth in 8 kb of ROM. Either we keep Forth as the operating system, or we go back to the monitor program we have been working on.

For those who are interested in Forth -

The book everybody begins with is Starting Forth by Leo Brodie, the one with the famous silly drawings. I would recommend skimming first it to get a feeling for the language, and then read the more philosophical Thinking in Forth as soon as possible to give you the "why" of everything. Then, either go back to Starting for the real work or switch to a modern treatment such as Programming Forth [PDF] by Stephen Pelc. To write actual code, I have been using gforth because it runs on pretty much any platform (including Android 4.4). This is ANS ("ANSI") Forth and quite different from FIG Forth.

Finally, if you are interested in the history of programming languages, Moore has released his reasoning behind Forth from 1970 in Programming a Problem-Orientated Language.

Later I'll show you how to write a program in a forgotten language: machine language. By that I mean sitting at the console and entering absolute, binary instructions with the switches.

That's a bit more basic than even I like it.