RSS

Daily Archives: October 17, 2014

The Forth Dimension

Forth

The Forth programming language reached maturity around 1970 after more than ten years of development and experimentation by its creator, Charles H. Moore. Its first practical use was to control a radio telescope at the National Radio Astronomy Observatory, where Moore was employed at the time. From there Forth spread to other telescopes and other observatories, cementing a connection with astronomy and space science that persists to this day; in addition to controlling countless telescopes and planetariums earthside, Forth has been into space many times on probes and satellites of all descriptions. Yet already by the end of its first decade Forth had spread far beyond astronomical circles. It was being used to control the motorized cameras used to film miniature-based special-effects sequences (suddenly a booming business in the wake of Star Wars); to control automotive diagnostic equipment; as the firmware in various medical devices; to control automated agricultural equipment. Closer to our usual interests, Atari had invested a lot of money into developing a version of the language suitable for programming pinball machines and stand-up arcade games, while versions of the language were available for all of the trinity of 1977 within a year or so of their appearance. The key to Forth’s burgeoning popularity was its efficiency: it not only ran faster than just about any language short of assembly, but in the right hands it was also almost unbelievably stingy with memory. Those were good qualities to have in the late 1970s, when the average PC ran at 1 MHz and had no more than 16 K.

We’ll get into why Forth is so efficient in just a bit. But first let’s take a look at the language itself. If you’ve programmed before in just about any other language, Forth will likely seem deeply, deeply weird. Still, there’s also something kind of beautiful about it. If you’d like to follow along with the few examples I’ll give in this article, you have many free implementations of the language to choose from. A good choice, and one that has the advantage of working on Windows, Macintosh, and Linux alike, is Gforth.

Forth is an interactive programming language, like the microcomputer BASICs so many of us grew up with. This means that you can enter commands directly at the Forth console and watch them run immediately.

Forth is also a stack-based programming language, and this is the key to everything else about it. Virtually every programming language uses a stack under the hood; it’s one of the most fundamental mechanisms of computer science. But most other languages try to hide the stack from us, strain to make it so that we need not trouble ourselves over it and, indeed, don’t really need to know much about it at all. The only time many programmers even hear the word “stack” is when an infinite loop or runaway recursion causes a program to crash with a “stack overflow error.” Forth, however, doesn’t hide its stack away like something shameful. No, Forth loves its stack, sets it front and center for all to see. Forth demands that if we are to love it, we must also love its stack. Given this, it would behoove me at this point to explain just what is meant by the idea of a stack in the first place.

A stack is just that: a stack of numbers stored in a special part of memory, used for storing transient data. Adding a number to the stack is called pushing to the stack. It always goes on top. Taking a number from the stack is called popping the stack. It’s always the top number — i.e., the most recently pushed — that’s popped, after which that number is erased from the stack. A stack is, in other words, a first-in-last-out system — or, if you like, a last-in-first-out system. If you haven’t quite wrapped your head around the idea, don’t sweat it. It should become clearer momentarily.

Let’s look at how we can do simple arithmetic in Forth. Let’s say we want to add 2 and 3 together and print the result. In a typical modern language like Java, we’d just do something like this:

System.out.print(2 + 3);

In Forth, we do it a bit differently. If you’ve started up a Forth environment, you can type this in and see the result immediately.

2 3 + .

If you happened to use a Hewlett-Packard scientific calculator back in the day, this notation might look familiar to you. It’s known as “postfix” or “reverse Polish” notation. Let’s unpack this piece by piece to see how exactly Forth is handling this expression.

The first thing to understand here is that Forth reads almost everything as a word — Forthese for a command. A number standing by itself is actually interpreted as a word, a command to push that number onto the stack. Therefore, assuming we started with an empty stack, the stack looks like this after the first two parts of the expression above have been processed:

3
2

Now the interpreter comes to the “+,” which is also read as a command, instructing it to pop two values off the stack, add them together, and push the result back onto the stack. After doing so, the stack looks like this:

5

Finally, the “.” just instructs the interpreter to pop the top value off the stack and print it.

Now let’s consider a more complicated algebraic expression, like “(4 + 5) * (6 + 7).” In Forth, it would be written like this:

4 5 + 6 7 + * .

Let’s walk through this. We push 4 and 5 onto the stack.

5
4

We pop them off, add them together, and push the result to the stack.

9

We push 6 and 7 onto the stack.

7
6
9

We add them together and push the result.

13
9

We pop the top two values on the stack, multiply them together, and push the result.

117

And finally we pop and print the result.

To this point we’ve been working interactively. The key to programming in Forth, however, is to define new words; this is Forth’s nearest equivalent to the function calls common to other languages. Let’s consider a function to cube a number, which would look like this in Java:

int cube (int num) {
   return (num * num * num);
}


In Forth, we might do it by entering the following lines at the console:

: CUBE ( N -> N. Cube a number)
   DUP DUP ( Now there are three copies)
   * * ( Get the cube)
;


Let’s again unpack this piece by piece. The colon is a word which tells the interpreter that what follows will be a new word definition, to be terminated by a semicolon. “CUBE” is the name of the new word we are creating. All text within parenthesis are comments, to be ignored by the interpreter. The “N -> N.” notation within the first parenthesis is not required, but is considered good practice in Forth programming. It tells us that this word will pop and operate on the current topmost word on the stack, and will push a single result onto the stack. Forth words do not take arguments like functions in other languages, but operate only on the current contents of the stack. Thus it’s the programmer’s responsibility to set the stack up properly before invoking a word, and to know what that word will have done to the stack when it finishes. The two lines in the middle are the meat of the word, the actual instructions it represents.

Let’s say we call this new word “CUBE” with a 5 on top of the stack — i.e., by entering “5 CUBE .” at the console. Thus the initial stack looks like this:

5

Now we’re going into the body of the word itself. The two “DUP” statements tell the interpreter to duplicate the top value on the stack twice, without destroying — i.e., without actually popping — the original value. So, we end up with:

5
5
5

Now we pop the top two values, multiply them together, and push the result.

25
5

Then we just do the same thing again.

125

And our work is done.

Next we’ll see how we can use this word within another word. But first let’s see how we would do that as a function in Java.

void cubes10() {
   for (int i = 0; i < 10; i ++) {
      System.out.print("\n");
      System.out.print(i + " ");
      System.out.print(cube(i));
   }
}


Here it is as a Forth word:

: CUBES10 ( ->. Print a table of cubes of 0-9.)
   10 0 ( Indices of loop)
   DO ( Start Loop)
      CR I . I CUBE . ( Print a number and its cube.)
   LOOP ( End of loop.)
;


As the first comment indicates, the “CUBES10” word expects nothing on the stack and leaves nothing there. We begin by pushing 10 and 0 onto the stack. Now Forth’s back-asswordness really comes to the fore: the “DO” word pops the last two words off the stack. It will increment a variable — always known as “I” — from the second of these until it is equal to the first of these, looping each time through the block of words contained between “DO” and “LOOP.” Within the loop, the word “CR” simply causes the cursor to move down to the next line. Keeping in mind that “I” represents the current value of the variable being incremented, which can be pushed and popped just like a constant, the rest should hopefully be comprehensible. The output looks something like this:

0 0
1 1
2 8
3 27
4 64
5 125
6 216
7 343
8 512
9 729

Forth is built entirely from words like the ones we’ve just created. In fact, calling Forth a programming language may be something of a misnomer because virtually every piece of its vocabulary is redefinable. Forth comes with a dictionary of common, useful words, but the programmer is always free to replace these with others of her own devising, to make Forth into whatever she wants it to be. The most basic words are not constructed from other Forth words but rather written as in-line assembly language. The programmer adds words to this base which do ever more complicated tasks, until finally she writes a word that subsumes the entire program. To take an example from Leo Brodie’s classic book Starting Forth (one of Forth’s chief products down through the decades has been horrid puns), a Forth program to control a washing machine might have this as its top-level word:

: WASHER
   WASH SPIN RINSE SPIN
;


Each of the words referenced within “WASHER” would likely call several words of their own. “RINSE,” for instance, might look like this:

: RINSE
   FAUCETS OPEN TILL-FULL FAUCETS CLOSE
;


Each of these words would call still more words of its own, until we come to the level of fundamental assembly-language commands to control the CPU on its most basic level. Forth words can even create new words dynamically, resulting in programs that effectively rewrite themselves as they run to suit their environment.

Especially if you’re a programmer yourself, you may have already formed an impression by now of Forth’s strengths and weaknesses. And yes, contrary to the claims of many Forth zealots, the latter do exist in considerable numbers. Even leaving aside the strange reverse notation, which one can eventually get used to, Forth programs can be incredibly hard to actually read thanks to their reliance on pushing and popping to the stack, with the associated lack of helpful variable names. For this reason Forth has occasionally been called a “write-only” language; Forth code can be well-nigh incomprehensible even to the person who originally wrote it after just a week or so has elapsed. It’s the polar opposite of a contemporaneous language I once wrote about on this blog, Pascal, replacing the latter’s pedantic emphasis on structure and readability above all else with a love of hackerish tricks, sleight of hand, and cleverness that can sometimes come off as sort of facile. Just trying to keep a picture in your head of the current configuration of the stack, something on which absolutely everything you do in Forth depends, can be a nightmare as programs get more complicated and their possible states get more varied. If not quite the last language in the world I’d use to write a complicated modern application, it must be pretty close to it. Its “write-only” qualities make it particularly unsuitable for team projects, a problem given that most useful software long ago got too complicated for solo programmers.

Yet there’s also an uncompromising beauty about Forth that has drawn many people to it, a beauty that has occasionally been compelling enough to override people’s better judgment and make them use the language for purposes to which it really isn’t terribly suited. Whatever else you can say about it, it sticks to its philosophical guns tenaciously. There’s a fascination to building a dictionary of your own, to effectively making a programming language all your own. Grizzled Forth programmers have often replaced virtually everything that comes with the language to create something that is absolutely theirs. That’s a rare experience indeed in modern programming. People who love Forth really love it. This (in Leo Brodie’s words) “high-level language,” “assembly language,” “operating system,” “set of development tools,” and “software design philosophy” has that rare ability, like my old love the Commodore Amiga, to inspire a level of visceral, emotional commitment that smacks more of romance or religion than practicality.

If we do insist on speaking practically, within certain domains Forth excels. It’s still widely used today in extremely constrained environments where every byte and every processor cycle counts, such as, well, the firmware inside a washing machine. To understand what makes Forth so efficient, we need to first understand that those more readable Java functions I showed you above must ultimately be converted into a form pretty close to that we see in the Forth versions. By making us meet the computer halfway (or further), Forth eliminates a whole lot of shuffling about that costs precious processor time. A well-written Forth program can actually be smaller than its pure assembly-language equivalent — much less the same program written in some other high-level language — because Forth so emphasizes reusable words. And it can be surprisingly easy to port Forth programs from computer to computer; one need only re-implement that bottommost layer of words in the new machine’s assembly language, and leave the rest alone.

Of course, all of these advantages that make Forth so attractive to programmers working on embedded systems and device firmware today also made it mighty appealing to programmers of ordinary PCs of the late 1970s and 1980s, working as they were under stringent restrictions of their own. For some early PCs Forth was the only language other than the ROM-housed BASIC or assembly language that made any sense at all. Stripped down to its essentials, Forth can be tiny; for example, Cognetics Corporation, a developer we met in a recent article, worked with a version of Forth that fit into just 6 K. Thus Forth enjoyed considerable popularity, with a fair number of games and other commercial software written in the language. John Draper, the legendary “Captain Crunch” who taught Steve Wozniak and Steve Jobs how to phone phreak amidst myriad other hacking accomplishments, was a particular devotee, distributing a Forth development system for the Apple II which he also used to write the II’s first really usable word processor, EasyWriter. Many of the magazines ran columns or extended series on Forth, which was available, and generally in multiple versions, for virtually every remotely viable machine of the era. One British computer, the ill-fated but fascinating Jupiter Ace, even included Forth in ROM in lieu of BASIC. Tellingly, however, as the 1980s wore on and software got more complex Forth became less common amongst commercial application and game developers, even as it retained a dedicated cult of hobbyists who have persisted with the language to this day. According to Charles Moore, this was as it should be. Forth, he told Jerry Pournelle in Byte‘s March 1985 issue, had never been intended for closed-source commercial software.

Writing big programs to be distributed in object code is a distortion of what Forth is all about. Forth is like a set of craftsman’s tools. You use it to make still more tools that work with whatever you specialize in. Then you use it to solve problems. Forth programs should always be distributed in source code. You should have Forth online at all times. Recompile whenever you want to use a program. Forth programs are tailored, they’re living and dynamic, not static object code.

“Distortion” or not, the most important Forth game, and arguably the most ambitious project ever completed in the language, would appear more than a year after those remarks. I know I’ve been teasing you with it for a while, but, with all the pieces in place at last, we’ll get there next time… really, I promise.

(Probably the best place to look to get an idea of the excitement Forth once generated, as well as a very good picture of the language itself, is the August 1980 Byte, which had Forth as its main theme. My example code in this article has its origins there, as does the picture.)

 
 

Tags: ,