Author: Dave Gauer
Created: 2023-02-02
Updated: 2023-07-21

Note: This page is my personal journey to discover Forth and put it in the context of computing history. It is adapted from my slides for a short talk. I've done everything in my power to make this page scale up and down for various screen sizes. I welcome suggestions and corrections for both the content and display of this page. Here's my contact page.

In the 1990s, Usenet newsgroups (wikipedia.org) were where it was at. For example, Linus Torvalds's initial announcement of Linux was to comp.os.minix in 1991.

The comp.* (wikipedia.org) groups and particularly comp.lang.* were great places to learn about and discuss programming. By the time I got there in the late 90s, Perl was a pretty hot topic, especially as it took a dominant role in the early Web as the dynamic page and form processing programming language via CGI (wikipedia.org).

There were programming resources on the Web, but nothing like what's available now! To actually learn to program, I bought books, and still do.

Usenet was where the community and folklore lived.

(The "Easter egg" in this drawing is alt.religion.kibology, which should get a chuckle from old timers. The rest of you can look it up.)

Sharp-eyed Lisp-lovers and other mutants will perhaps recognize this thing as the Y combinator expressed with lambdas.

The only time I understood this was when I completed the book The Little Schemer by Friedman and Felliesen, which walks you through creating it for yourself. It is a magical book and I implore you to try it.

Mel was real and the Royal McBee RPC-4000 was real. Look at that teletype (aka "teleprinter"). If typewriters and "Royal" together make a little bell in your head go "bing" as your mental carriage hits the end of the page, then you're right: Royal McBee was a merger between the Royal Typewriter Company (wikipedia.org) and McBee, a manufacturer of accounting machines.

For a while, Royal was owned by the Italian typewriter company, Olivetti, who also made some really interesting computers (wikipedia.org).

And then...

Now begins my quest to understand Forth.

Perhaps you've seen postfix or Reverse Polish Notation (RPN) (wikipedia.org) before? The principle is simple: Instead of the usual "infix" notation which puts operators between operands (3 + 4), RPN puts operators after the operands ( 3 4 +).

RPN notation is one of the most visually obvious aspects of the Forth programming language. But it turns out, RPN is not what Forth is about or the reason Forth exists. As we'll see, the situation is reversed.

In fact, as you'll see, my quest is mostly a series of incorrect assumptions I made by looking at the language without the context of history.

By the way, the HP-35 calculator (wikipedia.org) pictured here is really interesting. In the early 1970s, HP had powerful desktop calculators. Actually, what they had were really programmable computers, but they still called them calculators (wikipedia.org) for sales reasons. But these were big desktop machines that ran off of wall current.

Putting all of that power into a "shirt pocket" calculator was an astounding accomplishment at the time. Legend has it that the size of the HP-35 was based on the dimensions of Bill Hewlett's actual shirt pocket. HP-35 calculators have been in space. They killed off the slide rule.

HP calculators are famous for using RPN syntax. If it weren't for these calculators, I suspect it's likely that RPN syntax would be virtually unknown outside of computer science.

RPN is considered to be highly efficient and, being somewhat inscrutable to outsiders, highly geeky.

Let's see a better example...

I'm being cheeky here. Users of bc, are hardly noobs. But it is arguably even geekier to use the much older dc program. bc was once just an infix expression translator for dc to make it more palatable for people who didn't want to use RPN. Thus the gentle teasing.

Besides using RPN syntax, the dc calculator (wikipedia.org) is completely programmable. Oh and it also happens to be one of the very first Unix programs and pre-dates the C programming language!

Anyway, the point here is that RPN syntax lets you express nested expressions without requiring parenthesis to get the order of operations the way you want them. This is one of the reasons RPN fans (including those HP calculator fans I alluded to) are so enamoured with it.

In this example, we input 3, then 4. * multiplies them. Now we have the result (12) available. But first, we input 5 and 6 and multiply them with another * to also store that result (30). The final + adds both stored results (12 + 30) and stores that result (42). Unlike an HP calculator, dc doesn't show us any of the stored results, including the last one until we "print" it with the p command.

As it is known about "ed, the standard text editor" (gnu.org), dc doesn't waste your VALUABLE time (or teletype paper) with output you don't need!

So this relates to Forth how?

As you can see, someone sitting at a Forth interpreter can perform this calculation exactly the same as with the dc calculator (or an HP calculator).

Sharp-eyed readers will note that we print the result with a "." command rather than "p". But that's the only difference.

So Forth is like an RPN calculator? We input values and then operate on them? Well, that statement is not wrong

But does that mean we know what Forth is all about now? If we know how to enter things in postfix notation, we "get" Forth? No! Not even close...

The use of a data stack is probably the second most visible thing about the Forth programming language.

A stack is a data structure often explained with a "stack of plates" analogy. You PUSH a plate on the stack and you POP a plate off the stack. The first item you put on the stack is the last item out of the stack.

Above, we have an illustration of PUSH and two other common stack operations:

• SWAP slides a plate out (very carefully) from the second position and puts it on top.
• DUP takes the top plate and duplicates it using kitchen magic and puts the replica on the top of the stack (in this metaphor, I guess an equal amount of matter is removed somewhere else in the Universe, but we try not to worry too much about that).

As you may have guessed, these four stack words (PUSH, POP, SWAP, DUP) also happen to be Forth words.

Historical note 1: In the old days, people and computers just WENT ABOUT SHOUTING AT EACH OTHER ALL THE TIME IN ALL CAPS BECAUSE LOWERCASE LETTERS WERE TOO EXPENSIVE.

Historical note 2: When a computer asks, "SHALL WE PLAY A GAME?" in all caps, you must answer NO, as we learned in 1983's WarGames (wikipedia.org)

Let's see a stack in action:

Let's revisit our math problem from earlier. This is the Forth code on the left and the results on "the stack" on the right.

Rather than being concerned with the syntax or notation, we're now interested in what these operations are doing with our data stack.

As you can see, entering a number puts it on the stack. The math operators take two values from the stack, do something with them, and put a new value back on the stack.

The '.' (DOT) operator is different since it only takes one value (to print it) and does not put anything back on the stack. As far as the stack is concerned, it is equivalent to DROP. As far as humans are concerned, it has the useful side-effect of letting us see the number.

Now let's see something you probably wouldn't find on an HP calculator. Something non-numerical...

Getting the joke here will require knowing this English idiom (wikipedia.org).

Actually, this isn't just a silly example. Forth's use of the stack can lead to a natural, if somewhat backward use of nouns and verbs. (Kind of like Yoda's speech habits. "Cake you will dup, yes? Have it and eat it you will, hmmm?")

There can, indeed, be some object named CAKE that we have placed on the stack (probably a memory reference) which can be DUPed, and then HAVEd and EATen.

It's up to the Forth developer to make harmonious word choices. It can get far more clever or poetic than my example.

Naming things is great.

But sometimes not naming things is even better.

(Hopefully your answer is "no" or the rhetorical question doesn't work.)

But it's funny how our programming languages often require us to explicitly name intermediate results so that we can refer to them. On paper, we would never give these values names - we would just happily start working on the list.

Imagine, if you will, a factory assembly line in which each person working the line is a hateful fussbudget who refuses to work on the part in front of them until you name it. And each time the part has been worked on it must be given a new name. Furthermore, they refuse to let you re-use a name you've already used.

A lot of imperative languages are like that factory. As your values go down the line, you've got to come up with nonsense names like result2, or matched_part3.

Does your programming language make you do this?

(It's almost as bad as file names used as a versioning system: my_doc_new_v5.4(copy)-final2...)

Working without names (also known as implicit or tacit or point-free programming) is sometimes a more natural and less irritating way to compute. Getting rid of names can also lead to much more concise code. And less code is good code.

Great, so stacks can be a very elegant way to handle expressions.

Have we "cracked" Forth yet? Now we know two things: it uses RPN syntax and it is stack-based.

On this journey of Forth discovery, you'll inevitably run into the term "concatenative programming".

What's that?

An awesome resource for all things concatenative is The Concatenative Language Wiki (concatenative.org). It lists many concatenative languages and has a page about Forth, of course.

For the term "concatenative programming" itself, the Factor programming language website has an excellent page defining the term: Factor documentation: Concatenative Languages (factorcode.org). And, of course, there's the Wikipedia entry, Concatenative programming language (wikipedia.org).

I understand the explanations on these websites now, but it took me a while to get there. Your journey may be shorter or longer. Probably shorter.

Let's see if I can stumble through it...

An applicative language has you apply a function to a value, which returns another value. Using familiar Algol-like (or "C-like", or "Java-like", or "JavaScript-like") syntax, arguments are passed to functions within a pair of parenthesis. In the above example, the parenthesis end up deeply nested as we pass the output of one function to another.

Unlike the math examples, where the infix notation looks more natural to most of us than the postfix notation, the concatenative example of this baking program looks more natural (at least in a human language sense) than the inside-out function application example, right?

(Of course, if you're a programmer used to years of something like C or Java or JavaScript, the inside-out parenthetical form will probably seem pretty natural too. Well, guess what? Your mind has been warped. It's okay, mine has too.)

The point here is that concatenative style has us "composing" functions (which you can think of as verbs) simply by putting them in sequence. Each function will be called in that sequence. The values that are produced at each step are passed along to be consumed as needed.

No names (unless we want them), just nouns and verbs.

But that's just the surface. It turns out this "concatenative language" concept goes way past that...

Can Programming Be Liberated from the von Neumann Style? (PDF) (worrydream.com) This paper is dense with notation and I haven't personally attempted to wade through it, yet. I'm sure it contains many profound ideas.

I know just enough to believe I understand this paragraph from the paper's abstract:

"An alternative functional style of programming is founded on the use of combining forms for creating programs. Functional programs deal with structured data, are often nonrepetitive and nonrecursive, are hierarchically constructed, do not name their arguments, and do not require the complex machinery of procedure declarations to become generally applicable. Combining forms can use high level programs to build still higher level ones in a style not possible in conventional languages."

Perhaps you've heard of "functional programming?" As you can see, that term was being used in 1977.

"Concatenative programming" came after. In fact, Joy is where the "concatenative" description comes from! (von Thun specifically credits Billy Tanksley for creating the term "concatenative notation".)

I can't describe Joy's genesis better than the man himself. Here is von Thun in an interview about Joy:

"Joy then evolved from this in an entirely haphazard way: First I restricted the binary relations to unary functions, and this of course was a dramatic change. Second, to allow the usual arithmetic operations with their two arguments, I needed a place from which the arguments were to come and where the result was to be put - and the obvious place was a stack with a few shuffling combinators, originally the four inspired by Quine. Third, it became obvious that all these combinators could be replaced by unary functions, with only function composition remaining. Finally the very different distinctively Joy combinators emerged, which take one or more quoted programs from the stack and execute them in a specific way. Along the way of course, lists had already been seen as just special cases of quoted programs. This meant that programs could be constructed using list operations and then passed on to a Joy combinator."

From A Conversation with Manfred von Thun (nsl.com), which is a really great read in its entirety.

As you can see, combinators are crucial in Joy. Let's take a moment to dive into those, because this is a pretty fascinating avenue of computer science...

"Higher-order" just means functions that take other functions as input and do things with them.

You can even have functions that take functions that take functions and so on to do powerful things. But you'll need to meditate on them every time you have to re-read that part of your code.

map is one of the more common examples, so I'll use it as an example.

(The second example with the arrow function syntax works exactly the same way, but more compactly. I included it to make the comparison with Joy a little more even-handed. Feel free to pick a favorite and ignore the other one.)

In the first example, we have familiar Algol-like syntax with functions that take arguments in parenthesis.

Perhaps map() is familiar to you. But if not, just know that it takes two parameters like so: map(array, function). The first parameter is implicit in these JavaScript examples, but it's there. The array object, [1, 2, 3, 4] calls its own map() method. The second parameter is a function (named inc in the first example and left anonymous in the second), which will be applied to every member of the list.

The output of map() is a new list containing the result of each application.

Notice how both JavaScript examples have variables such as the parameter n and the result bigger. This is an example of what I mentioned a moment ago when discussing the advantages of stacks: "Traditional" programming languages often make us name values before we can work with them.

The syntax here may require a little explanation. The square brackets ([]) are Joy's quote mechanism. Quotations are a lot like lists, but they can contain programs as well as data.

In this case, the first quotation is the number list, [1 2 3 4].

The second quotation is a program, [1 +].

As in the JavaScript examples, map takes two parameters. The first is the function (or "program" in Joy) to apply, and the second is the list to apply it to.

(It's kind of confusing to talk about "first" and "second," though because that's the opposite order in which we supply those arguments on the stack...)

Note the lack of variables bigger or n. Intermediate values just exist.

It looks pretty nice and neat, right?

This "point-free" style can be a blessing... or curse. Unlike computers, human brains have a hard time juggling too many things on the stack.

There seems to be a happy medium between named and unnamed. Also, the point-free style seems to benefit greatly from short (even very short) definitions to avoid mental juggling and greater composibility.

If you have the slightest interest in Joy, I highly recommend reading or skimming this delightful tutorial by Manfred von Thun himself: An informal tutorial on Joy (hypercubed.github.io).

Note: I had a bit of a time actually running Joy to test out these examples. Thankfully, I eventually ran into Joypy (github.com), a Joy written in Python. My Linux distro comes with Python installed, so the whole process for me was:

git clone https://github.com/calroc/joypy.git
cd joypy
python -m joy
...
joy? [1 2 3] [1 +] map
        

Okay, that's a glimpse.

But we've barely touched the conceptual power of combinators with our map examples. Let's go a little deeper on this fascinating subject:

Here's something from my bookshelf. It's To Mock a Mockingbird by mathematician and puzzle-maker Raymond Smullyan. It uses puzzles involving birds to solve logic problems and classify some well-known combinators.

It would be impossible to write a complete catalog of combinators just as it would be impossible to write a complete catalog of integers. They're both infinite lists. Nevertheless, some well-known combinators have been identified as having special properties. In the book above, many of these have been given the names of birds.

Remember, combinators are just "higher-order" functions that take functions as input. Well, it turns out these are all you need to perform any computation. They can replace logical operators and even variables.

What?!

Yeah, you can re-work any expression into a combinatorial expression and completely replace everything, including the variables, with combinators.

It's kind of hard to imagine at first. But you can see it happen right before your very eyes. The mind-blowing tool on this page by Ben Lynn: Combinatory Logic (stanford.edu) takes a term expressed in lambda calculus and replaces everything with just two combinators, K and S. (We'll talk more about those two in just a moment because they are super special.)

(Ben Lynn's whole website is full of neat stuff like this. If you're looking to entertain yourself for any amount of time from an afternoon to the rest your life, Lynn has you covered.)

So combinators share something in common with lambda calculus and Turing machines. These systems provide all of the building blocks you need to perform any possible computation in the sense of the Church-Turing thesis (wikipedia.org) or "computability thesis". (We've also discovered some problems that are not computable and no system can compute them like "the halting problem," but these are pretty rare.)

It turns out that computation is a fundamental feature of the Universe. As far as we can tell, any universal system of computation is equally capable of solving any computational problem. And once you realize how little is required, you can invent a universal computer yourself!

Electronically speaking, this is the same principle that allows a NAND gate to simulate all other gates. NAND gates are a fundamental computational building block. You can make an entire computer with nothing but NAND gates and that computer can (slowly) solve any computable problem you can imagine.

Anyway, when we use combinators, this particular flavor of universal computation is called combinatory logic (wikipedia.org).

What do the building blocks of combinatory logic look like?

Let's start small:

The simplest of all combinators is I, the "identity combinator". There are a ton of different ways to write this. In lambda calculus, it looks like this: I = λx.

The way to read "(I x) = x" is: "I applied to some object x results in...x."

We say "object x" rather than "value x" because, being a combinator, I could take a function as input as well as a value. In fact, "object" is intentionally very abstract, so x could contain a scalar value, or list, or function, or another combinator, or anything. Whatever that object is, I returns it.

Both of these take more than one parameter of input. But if you're used to Algol-like function syntax, the way this works may be surprising.

Since it's the simpler of the two, let's use the K combinator as an example:

The way to read "(K x y) = x" is: "K applied to x yields a combinator, which, when applied to y always evaluates to x."

(Programmers familiar with the concept of currying will see that this is like the partial application of a function, where a new function is "pre-baked" with the argument x. The term "currying" is named in honor of mathematician Haskell Curry (wikipedia.org), after whom the Haskell programming language is also named.)

The result is that K makes a combinator that throws away any input and just returns x. Weird, right? But it turns out to be useful.

K is super easy to write in a language like JavaScript, which is also a nice choice because you can play with it right in the browser console like I just did:

K = function(x){
  return function(y){
    return x;
  }
}

K("hello")("bye")

> "hello" 
        

See how the result of K("hello") is a function that returns "hello" no matter what you give it as input?

How about S? I'll leave implementing that in JavaScript as an exercise for the reader. It's clearly much more complicated since it has three levels of "function that yields a combinator" on the left and the result is an equally complicated combinator that first applies parameter z to combinator y.

(By the way, the y combinator above should not be confused with the Y combinator. Do you remember that arcane lambda calculus artifact projected over that head with the third eye way up near the beginning of this page? That thing was the Y combinator! It turns out, it's all, like, connected, you know?)

But the real point is this: S and K are special for one very interesting reason. Together with I, they form the "SKI calculus" and just these three combinators are all you need to perform any computation in the known universe.

Actually, it's even crazier than that. You don't even need I because that, too, can be created with S and K.

That's right, the S and K definitions above are a complete system for universal computation.

The book shown here is another from my bookshelf. It's Combinators: A Centennial View by Stephen Wolfram.

It starts with a (much too) terse introduction to the SKI combinator calculus and then launches into page after page of visualizations of S and K combinators being fed into each other. Like fractals or automata, simple inputs can produce patterns of surprising sophistication.

Wolfram demonstrates combinators that keep producing different output for a gazillion iterations and then get stuck in a loop. Some of them produce regular patterns for a while and then start producing different patterns. Some just loop forever at the outset. As in other universal systems, there is no end to the complexity produced by these two simple constructs. It is infinite. And all of this is just S and K combinators taking combinators as input and returning combinators as output.

I think it is wild and fun to see someone play with a subject like Wolfram does in this book. Each page is saying, "Look at what is possible!"

Combinators is also Wolfram's ode to the discoverer of combinatory logic, Moses Schönfinkel (wikipedia.org) who, like so many of the giants in the field of computer science, did his work on paper decades before the first digital electronic computers beeped their first boops.

Figuring out the output of the S combinator once was enough to keep me occupied for a while. It boggles my mind to imagine feeding it another S as input on paper, let alone discovering these particular combinators in the first place.

Okay, we get it, combinators are a crazy way to compute.

But are they worth using in "real" programs? In limited doses, absolutely!

Both of those pieces of JavaScript give us the result of applying the function bar() to an array foo.

I think map() is a great example of the power of combinators to clean up a program with abstraction. Once you start using simple combinators like this to abstract away the boilerplate logic of yet another loop over a list of items, it's hard to go back.

My personal history with exploring higher order functions in a production setting is through the Ramda (ramdajs.com) JavaScript library, which I discovered from the talk Hey Underscore, You're Doing It Wrong! (youtube.com) by Brian Lonsdorf, which is fantastic.

Once I started discovering how combinators and curried functions could eliminate big old chunks of code, I was hooked! The old, dreary procedural code became a new fun puzzle!

Mind you, it's very easy to go overboard with this stuff and write something far less readable than some simple procedural code. (Gee, ask me how I know this.)

But in limited doses, it's super powerful and compact.

Computing the factorial of a number is often used as an example of recursion. The final answer is the input number multiplied by the previous number multiplied by the previous number multiplied by... the rest of the numbers all the way down to 1.

Computing a factorial requires a cumulative result. Without recursion, you need an explicit variable to hold the intermediate result as you loop through the numbers.

As shown in the Joy factorial definiton above, linrec is a "linear recursion" combinator. It takes takes 4 parameters, each of which is a quoted program. null is a predicate which tests for zero. dup is the same as in Forth. pred is an operator which yields a number's predecessor (given 4, yields 3). "*" multiplies two numbers, just like you'd expect. Given these pieces, perhaps you can take a guess at how linrec works?

For comparison, here is a recursive JavaScript solution:

function factorial(n) {
    if (n <= 1) {
        return 1;
    }

    return n * factorial(n - 1);
 }
        

Note that the Joy example is not just shorter and has no variable names but it has abstracted away the mechanics of recursion. All we're left with is the logic specific to the factorial problem itself.

It's debatable which of these two are more readable because the measure of readability is in the eye of the beholder. But I think you can imagine getting good at reading the Joy example.

Okay, so we've gone pretty deep into this concatenative programming and combinator thing. How does this actually relate to Forth?

First of all, Forth does have facilities for dealing with combinators:

First, let's see how EXECUTE works. The syntax will be alien to non-Forth programmers, but the concept will be no problem for anyone used to using first class functions.

First, let's make a new word:

: hello ." Hello" ;
        

This is Forth for, "Compile a word called hello that prints the string Hello."

(We'll learn how compiling words actually works later. For now, please just gracefully accept what you're seeing.)

Next:

 
VARIABLE hello-token
        

This creates a new variable called hello-token which will store the "execution token" for the hello word.

This part will look super cryptic if you're new to Forth:

 
' hello hello-token !
        

Let's examine this one piece at a time:

• "'" gets the address of the word "hello" and puts it on the stack.
• "hello-token" is a variable, which just leaves its address on the stack when called.
• "!" stores a value from the stack (the address of hello) at an address from the stack (the address of variable hello-token).

So the code above simply reads, "Store the address of hello in the variable hello-token."

Now let's use EXECUTE to call this "execution token":

 
hello-token @ EXECUTE
Hello
        

Behold, it printed the "Hello" string!

Remember, the variable hello-token leaves its address on the stack when it is called.

"@" is a standard Forth word that loads the value from the given address and puts that value on the stack.

EXECUTE gets an address from the stack and runs whatever word is found at that address.

Perhaps it would be helpful to see that this silly statement:

' hello EXECUTE
        

hello
        

Anyway, now we're armed with Forth's combinatorial ability: Treating functions ("words") as values so other functions can take them as input. This allows us to define combinators in Forth.

For some compact higher-order function definitions in Forth, check out this Gist by Adolfo Perez Alvarez (github.com).

While both languages share a cosmetically similar syntax, and both produce the same result for this expression, there is a fundamental difference between how the two languages "think" about the expression because they arrived at this place in completely different ways.

Forth's only concern (as a language) is to process these three tokens and act upon them according to some simple rules. (If the token is in the dictionary, execute it. If it's a number, put it on the stack.)

To Joy, it may be the same mechanical process under the hood, but the language itself sees these tokens more like a mathematical expression. It's a much more abstract outlook.

The point I'm making is that Forth may accomodate the abstract point of view, if the developer chooses to take it. But Forth is not based on abstract concatenative computing principles or combinatory logic.

Let's look at this from a historical perspective. First, the notions of postfix syntax (RPN) and a data stack for the basis of the language:

Hold that thought, here's a fun aside:

The drawing of the computer labeled "Z3" on the right is of the Z3 computer (wikipedia.org) designed by engineer and computer scientist Konrad Zuse. This is widely considered to be the first programmable digital computer! It used electro-mechanical relays like the telegraph networks of the day.

(By the way, a certain amount of electro-mechanical logic is still used in modern nuclear reactor safety systems because the big mechanical components are not as vulnerable to nuclear radiation as semiconductors!)

The Z3 could do addition in less than a second and multiplication in three seconds. It had 64 words of 22 bits each and worked with the equivalent of modern floating-point numbers.

As mentioned above, it can be said to use RPN, though there are only two registers and nine instructions. Opcodes were encoded in eight bits. The computer is programmable via punched paper tape (you can see the tape device to the right of the control console, though it's a bit of a scribble in my drawing).

It is also a stack machine. Again, this is with a mere two registers, which get juggled in a particular sequence as you load and store values.

Fun fact: The control unit used special control wheels to encode microsequences. If the microsequence wasn't programmed correctly, it could short-circuit the machine and destroy the hardware!

I got most of this information from this excellent paper by Raul Rojas: Konrad Zuse's Legacy: The Architecture of the Z1 and Z3 (PDF) (ed-thelen.org).

Anyway, so the simple mechanics of RPN and stack-based operation are very natural for digital computing machines and their use goes back to the very beginning.

Uh oh.

While the ideas of combinators and other types of universal computation were well known in certain mathematical and computational circles, I would argue they were not very amenable to existing computer hardware until much later when computers became fast enough to support "functional programming" styles and abstractions.

Until then, programming was "close to the metal." Even the idea of "structured programming" with programming language concepts like if/else or while/for loops was once considered novel! Until then, everything was done with address jumps or GOTO.

It's important to remember that "coding", the actual act of turning an abstract program into machine code, was long ago considered to be a mere secretarial skill, not far removed from typing and other forms of data entry. This is why some people (including myself) refer themselves as "programmers" rather than "coders".

Concatenative programming, with its emphasis on combinators (and immutable data structures, which we haven't talked about), doesn't have the same historic grounding for Forth the way that RPN syntax and stack-based programming do.

So I must conclude that understanding concatenative programming is super cool, but it doesn't actually help us understand the true nature of Forth because it doesn't describe how Forth came to be. It is not part of Forth's "origin story."

As we'll soon see, Forth really is about the "nuts and bolts". You bring your own theories with you.

There's nothing wrong with thinking about Forth in these terms, but it doesn't answer the "why" questions:

"Why does Forth have this syntax?"

"Why does Forth work this way?"

I think the answers to the "why" questions are best answered by looking at when.

What is Forth's history, anyway?

If this image doesn't make any sense to you, citizen of the future, it's from the iconic movie poster by Drew Struzan for Back to the Future (1985) (wikipedia.org).

In Forth - The Early Years (PDF) (worrydream.com), Chuck Moore recites a fairly terse history of Forth, from the earliest pre-Forths to the creation of the language standard.

(Note: Chuck mentions the Smithsonian Astrophysical Observatory (SAO) and the Massachusetts Institute of Technology (MIT) in roughly the same time period, and it's a bit difficult to be entirely sure which part is talking about which organization. But if you look at a map, SAO is at Harvard University. Harvard and MIT are about a mile apart in Cambridge, Massachusetts. It's basically a singular point if you zoom out a bit. So that helps explain the overlap.)

The computer in question is the IBM 704 (wikipedia.org) It was one of those room-filling vacuum-tube computers with tape drives the size of refrigerators.

The 704 was a fully programmable "modern" computer with magnetic-core memory, multiple registers, a 36-bit instruction set, and 36-bit words ("word" as in native memory size for the processor, not "word" as in Forth functions).

There were switches for each register on the control console, but programs could be written to and read from paper punch cards.

It was very modern for the time, but...

"In its day, the 704 was an exceptionally reliable machine. Being a vacuum-tube machine, however, the IBM 704 had very poor reliability by today's standards. On average, the machine failed around every 8 hours, which limited the program size that the first Fortran compilers could successfully translate because the machine would fail before a successful compilation of a large program."

It's difficult to imagine now, but changing parameters for a program, re-compiling it, and running it again could take a day (assuming you didn't make any mistakes).

So Chuck solved that irritation with an extremely clever solution:

Here's a quote from The Evolution of Forth (forth.com):

"Moore's programming career began in the late 1950s at the Smithsonian Astrophysical Observatory with programs to compute ephemerides, orbital elements, satellite station positions, etc. His source code filled two card trays. To minimize recompiling this large program, he developed a simple interpreter to read cards controlling the program. This enabled him to compose different equations for several satellites without recompiling..."

His free-form input format turned out, ironically, to be more reliable for human use than Fortran, which required formatted columns. (At the time, any mis-aligned columns in Fortran punchcard input would require a re-run of the program!)

It was also faster and more compact.

These "programming the program" statements in Moore's simple interpreter did not use keywords. They were statement numbers encoded on a punchcard.

So, at last, we have discovered the true origin of the Forth language: Moore wrote a simple interpreter to reduce waste and tedium.

Already, Moore has exhibited the defining combination of traits shared by great programmers around the world: Inventive and allergic to tedium.

If it had stopped there, it would have been a clever trick and perhaps worthy of a footnote in history.

But Chuck Moore did not stop there.

Now we head from Massachusetts to California where Moore found himself at Stanford University where he received his BA in Physics and started graduate school. He worked with Stanford's Burroughs B5500.

Let's talk about the computer first:

The B5500 (or "B 5500" - the official manual puts a space between the B and the number) was a solid-state computer. It was part of the "second-generation" of computers (wikipedia.org). These computers had discrete transistors on circuit boards. By contrast, the first generation before them used vacuum tubes (like the aforementioned IBM 704) and the third generation after them used integrated circuits.

In fact, the Burroughs Large Systems engineers were transistor computer pioneers. And the B5000 series was a pioneering system.

Here's some more resources:

• Burroughs B5000 / B5500 / B5700 gallery (retrocomputingtasmania.com) - an awesome illustrated guide including a picture of the actual Stanford B5500.
• Burroughs B5500 Reference Manual (PDF) (bitsavers.org) - The entire 224 page manual that came with the computer.
• Early Computers at Stanford (stanford.edu) - a description of the computer itself and a brief summary of its use at Stanford.

And what exactly did Chuck Moore do with that B5500 machine?

(As we'll see, symbols like "+" and "-" are words in Forth.)

Moore worked on the Stanford Linear Accelerator as a programmer. His focus was on steering the beam of the electron accelerator.

The CURVE program was even more "programmable" than his Fortran program at SAO. He took those ideas and expanded them to include the idea of a parameter stack and the ability to define new procedures.

This made the interpreter much more flexible and capable.

Aside: At this point, I also think it's interesting to compare Moore's budding interpreter language with another interpreter created specifically to be embedded in larger programs for controlling them: The Tcl programming language (wikipedia.org). 27 years after Moore started his work, John Ousterhout created Tcl out of frustration with ad-hoc, half-baked solutions 1988 at Berkeley. The name comes from "Tool Command Language". But the comparison goes deeper than just the shared motivation. Tcl and Forth have similar levels of syntactical purity and flexibility. Everything in Tcl is a string! Both languages give the user the power to define fundamental parts of the system, such as new control structures, in the language itself. If this sounds interesting, you owe it to yourself to play with Tcl for a while. It is extremely clever and extremely capable. The main implementation has been well cared-for and can be found on most Unix-like systems, often installed by default.

As Moore demonstrated with CURVE, a powerful, extensible interpreter is a huge time-saver (certainly when compared to re-compiling the program!) and allows the user of the program to add to the program's functionality on the fly. It's difficult to overstate how powerful this can be.

Truly, now we have the beginnings of a fully-fledged programming language. It's not named Forth yet, but we're getting closer.

First, let's talk about what "TTY" means in 1965. Teleprinters (wikipedia.org) or "teletypewriters" or just "teletype" were all printer devices. They printed to continuous sheets of paper fan-folded to fit into boxes.

The Latin "tele-" prefix means "far" or "at a distance". These machines trace a direct lineage from telegraphs and Morse code.

In the late 1800s, the concept of a typewriter which operated over telegraph lines had been explored and existed in a variety of forms. But the transmission code, paper tape, and typewriter system devised by Donald Murray (oztypewriter.blogspot.com) is the one that won out. And it was arguably Murray's choice of QWERTY keyboard that cemented it as the standard around the world.

The existing Baudot code (from which we also get the term "baud") was modified by Murray into something that very much resembles what we still use today. Murray also introduced the concept of control characters, which still clearly retain their typewriter origins in the names: CR (carriage return) and LF (line feed).

Teletype machines started as point-to-point text communication tools (like the telegraph), but they were later used over switched networks like the world-wide Telex system which used pulse dialing to automatically route a connection through the network.

The Teletype Model 33 (wikipedia.org) I drew above was one of the most popular teletypes used with computers. It was created by The Teletype Corporation in 1963, which means it shares a birth year with the ASCII standard! It remained popular until the mid-1970s when video terminals finally came down in price enough to push printer teletypes aside. In fact, Teletype Co. made the Model 33 until 1981, which is much later than I would have guessed!

As for paper-tape (wikipedia.org), I'll just quote Wikipedia directly:

"Punched tape was used as a way of storing messages for teletypewriters. Operators typed in the message to the paper tape, and then sent the message at the maximum line speed from the tape. This permitted the operator to prepare the message "off-line" at the operator's best typing speed, and permitted the operator to correct any error prior to transmission. An experienced operator could prepare a message at 135 words per minute (WPM) or more for short periods."

Donald Murray didn't invent the concept of perforated paper tape for data storage, but his system used it for the encoding of transmitted messages from the keyboard. It doesn't seem like a stretch to trace the origins of this storage method to Murray's system.

The computers of this era and earlier were paper manipulators. They were kind of like really complicated typewriters. They displayed their output on paper, they were programmed with paper, and they kept long-term storage on paper!

But as time went on, computer interactivity increased. They became less like typewriters and more like the machines we use today.

As each new ability emerged, Forth became increasingly interactive.

In the mid-1960s, "mini-computers" came out. They were still huge by today's standards, but no longer required a large room of their own.

In addition to the reduction in size, the other emerging change was direct interactive use of a computer via teletype.

Specifically, the invention of timesharing (stanford.edu) was a huge shift away from the "batch processing" style of computing that had come before (like with input via punchcard).

(Fun fact: A "second generation" time-sharing operating system called Multics (multicians.org) was the spiritual ancestor of and name from which Brian Kernighan made the joke name Unix: "One of whatever Multics was many of".)

Moore's evolving pre-Forth language also gained completely interactive editing and executing of programs.

This would have been right around the time that the original LISP REPL (Read-eval-print loop) (wikipedia.org) was created in 1964 on a PDP-1.

If not pre-saging, Moore was certainly on the bleeding edge of interactive computer usage!

Aside: If you want to see an awesome demonstration of interactive computer usage on paper, check out this demonstration by Bob Spence: APL demonstration 1975 (youtube.com). Bob Spence (wikipedia.org) is best known for his own contributions, including a number of early clever computer interaction ideas that are worth re-examining today. Bob's demo is extremely pleasant to watch and brilliantly presented in split screen. Notice how paper output lets you mark up stuff with a pen - pretty nice feature! And APL (wikipedia.org) is a whole other rabbit hole which has interesting intersections with the point-free and higher-order function programming we've encountered earlier.

Then this happens...

Yup, this really is the origin of the name, "Forth". Funny how temporary things tend to stick and last forever, isn't it?

The IBM 1130 (wikipedia.org) is one of those new-fangled "minicomputers" we've talked about. Gosh, it was so small, the CPU weighed less than a car!

And it was affordable! The base model was as low as $32,000. Compare that to $20,000, the median price for a house in the U.S. in 1965. Just think of that: If you could afford a house, you were well on your way to being able to afford a computer!

As noted, the unit Chuck Moore worked on had a disk drive, which would have bumped up the price an additional $9,000. That would be the equivalent of buying an above-average house and adding a couple brand-new 1965 cars in the driveway.

But, wow, imagine having disk drive cartridges with 512 KB of storage at your disposal. What would you do with all that space?

As mentioned, at this time, we're still interacting with the computer (mostly) via paper, but these minis brought the idea of interactive computing to "the masses" because they were so much smaller, cheaper, and more reliable than the sorts of computers that had come before.

Quoting The Evolution of Forth (forth.com):

"Newly married and seeking a small town environment, Moore joined Mohasco Industries in Amsterdam, NY, in 1968. Here he developed computer graphics programs for an IBM 1130 minicomputer with a 2250 graphic display. This computer had a 16-bit CPU, 8k RAM, his first disk, keyboard, printer, card reader/punch (used as disk backup!), and Fortran compiler. He added a cross-assembler to his program to generate code for the 2250, as well as a primitive editor and source-management tools. This system could draw animated 3-D images, at a time when IBM's software for that configuration drew only static 2-D images. For fun, he also wrote a version of Spacewar, an early video game, and converted his Algol Chess program into the new language, now (for the first time) called FORTH. He was impressed by how much simpler it became."

As you may have gathered by now, Chuck Moore is a pretty extraordinary computer programmer.

It turns out the IBM 1130 was hugely influential to a bunch of early big-name programmers in addition to Moore. Something was in the air.

In addition to its funny new name, Forth had also gained new abilities:

It's not just the name that makes this the first real Forth: A dictionary of named words which can be called interactively or recursively in the definitions of other words is one of the defining features of Forth. The ability to use words as building blocks is the Forth language's primary abstraction.

In the example above, we've defined a word called DOUBLE which duplicates the number on the top of the stack and adds the two numbers together.

A second word called QUAD uses the previous definition by calling DOUBLE twice, quadrupling the number in a rather amusing way.

A return stack makes this possible. Without a return stack, we have no way of telling the computer how to "get back" to the place in QUAD where we left off after DOUBLE is done.

(We'll get to the specifics of the syntax soon. That's another vital part of understanding Forth.)

First of all, the UNIVAC 1108 (wikipedia.org) is a great example of the awesome "retro-futuristic" design of these old machines. Just look at the sweeping angles in my drawing of the console. That's a cool computer console!

When these computers cost more than a house, it makes perfect sense that they were constructed into beautiful custom furniture that made them look like space ships.

You have to wonder: Did the sci-fi art of the time drive the design of these computers or did the computers and industrial design of the time inform the art? Or, more likely, did they both feed off of each other in the classic cycle of, "life imitates art imitates life?"

That's a teletypewriter built into the desk of the console. I presume the tractor-feed paper would have spooled to and from containers behind the sleek facade.

Anyway, the UNIVAC 1108 is an even more modern computer than the IBM 1130. Now we're moving into using integrated circuits for everything, including the register storage. (Speaking of registers, the 1108 had 128 of them and must have been interesting to program!)

As was also the trend at the time, the CPU was constructed of discrete cards connected together by a wire-wrapped backplane.

If you're not familiar with the technique, you should know that wire-wrapped (wikipedia.org) connections are extremely high quality. Wire is wrapped with great force around a post, making a gas-tight connection that will not corrode (corrosion can occur outside the connection, of course). A little bit of the insulation gets wrapped in the last turns, which provides flexibility and strain relief. There are NASA guidelines for making a perfect wire-wrap connection.

Anyway, the Univac was even more powerful and modern than Moore's previous computer and he took advantage of it.

You don't have to read between the lines to see Moore's obvious distaste of COBOL (wikipedia.org), the COmmon Business-Oriented Language. What's impressive is that he managed to still use Forth while also using the required COBOL modules.

When this project was abandoned by the employer, Moore was upset by the whole situation, particularly the way business software was increasing in complexity. This won't be the last time we see this theme crop up.

He also wrote a book (unpublished) at this time called Programming a Problem-Oriented Language. It's written in typical Moore fashion, without superfluous words or exposition. Feel free to contrast this with the article you're reading now.

(This book will be mentioned again later.)

Radio telescopes are like visual telescopes, but they collect lower frequency waves. Thanks to the magic of computers, we can process these signals to see what the radio telescopes see.

Radio telescopes can work with everything from 1 kHz, which is just below the uses of "radio" as we think of it for navigation, communication, and entertainment, to 30 GHz, which is still well under the visible portion of the electromagnetic spectrum. Consumer microwave ovens operate at about 2.45 GHz.

(Speaking of Gigahertz, apparently Intel Core i9 processors can run at clock speeds up to 6 Ghz, but most CPU designs top out at around 4 Ghz. This may be important for Forth for reasons I explain later.)

The visible part of the spectrum is very small by comparison. It starts at 420 THz (terahertz) and ends at 720 THz. The familiar rainbow of colors captured in the mnemonics "Roy G. Biv" or "Richard of York Gave Battle in Vain" (ROYGBIV) lists colors in order of lowest frequency (Red) to highest (Violet).

Here is the official website of the National Radio Astronomy Observatory (nrao.edu). But for a better summary, the Wikipedia entry (wikipedia.org) is the way to go. Be sure to scroll down to the incredible image and description from 1988 of the collapsed 300ft radio telescope:

"The telescope stood at 240ft in height, wieghed 600-tons, had a 2-min arc accuracy, and had a surface accuracy of ~1 inch. The collapse in 1988 was found to be due to unanticipated stresses which cracked a hidden, yet weight and stress-supporting steel connector plate, in the support structure of the massive telescope. A cascade failure of the structure occurred at 9:43pm causing the entire telescope to implode."

The 300ft dish had been the world's largest radio telescope when it went active in 1962 at the NRAO site in West Virginia.

My drawing above is of the Very Large Array (wikipedia.org) in New Mexico. NRAO is also a partner in a huge international array in Chile.

By using radio interferometry, arrays of telescopes can be treated as essentially one huge telescope with the diameter of the array (missing the sensitivity a dish of that size would have).

But the scope for which Moore wrote software was a single 36ft (11 meter) dish at Kitt Peak in Arizona called The 36-Foot Telescope. It was constructed in 1967 and continued working until it was replaced with a slightly larger and more accurate dish in 2013.

The 36ft scope was used for millimeter-wavelength molecular astronomy. This is the range above "microwaves" and these telescopes pretty much have to be constructed at dry, high altitude sites because water vapor in the air can interfere with the radio waves.

(Note that Moore stayed at the NRAO headquarters in Virginia and was not on-site at Kitt Peak.)

NRAO had a policy of using Fortran on its minicomputers, but based on the success of his previous work, Moore was begrudgingly given permission to use Forth instead. I couldn't possibly do justice to summarizing it, so here's Chuck's own words describing the software he wrote for the NRAO (also from Forth - The Early Years):

"There were two modes of observing, continuum and spectral-line. Spectral-line was the most fun, for I could display spectra as they were collected and fit line-shapes with least-squares."

It did advance the state-of-the-art in on-line data reduction. Astronomers used it to discover and map inter-stellar molecules just as that became hot research."

Here is a photo (nrao.edu) of the 36-foot telescope. And here is a photo of the control room in 1974 (nrao.edu) with what appears to be a PDP-11 in the background.

As you can see, the work itself was extremely interesting and cutting-edge. But how Moore went about it was also very interesting, which a series of computer drawings will demonstrate in a moment.

But on the Forth language front, there was another development...

We take it for granted now that "free" or "open" software unencumbered by patents and restrictive corporate licenses is a good thing. But this was absolutely not a mainstream position in the early 1970s.

To put things in context, in the summer of 1970, Richard Stallman (wikipedia.org) was just out of high school and was writing his first programs in Fortran (which he hated) and then APL.

It wasn't until 1980 that Stallman finally got fed up enough with the state of proprietary and legally encumbered software to start the "free-as-in-freedom" software revolution. Companies were increasingly using copyright to prevent modification, improvement, or duplication by the end user. Stallman, being a pretty incredible programmer, wrote free clones of such programs. He announced the GNU project (wikipedia.org) in 1983.

Aside: I believe Stallman was right. There's absolutely nothing wrong with writing programs for money or selling software. But using the law to prevent people from truly owning that software by limiting how or where to run it, or even preventing people from writing their own similar software, if they are capable, is an abominable practice and should be countered at every step.

I think that when you get to the heart of what Forth is all about, Moore's displeasure with the ANSI standardization suddenly makes tons of sense. In short, the whole point of Forth is to create your own toolkit. Having an all-inclusive language standard is great for making sure Forths are interchangeable. Unfortunately, it's also antithetical to adapting the language to your specific hardware and software needs.

Alright, enough philosophizing. Let's get back to the computer stuff!

While Moore was at NRAO, he also wrote software to point the telescope. Elizabeth Rather (Moore credits her as Bess Rather in his paper) was hired for support and they worked together on at least one port. The Forth system migrated across multiple machines at NRAO which, as we'll see, highlights one of the technological strengths of the standard Forth implementation.

By the way, after her initial reaction of shock and horror, Elizabeth Rather embraced Forth. From The Evolution of Forth (forth.com):

"After about two months, Rather began to realize that something extraordinary was happening: despite the incredibly primitive nature of the on-line computers, despite the weirdness of the language, despite the lack of any local experts or resources, she could accomplish more in the few hours she spent on the Forth computers once a week than the entire rest of the week when she had virtually unlimited access to several large mainframes."

Rather went on to write the first Forth manual in 1972 and write papers about it for the NRAO and other astronomical organizations.

Later, Elizabeth "Bess" Rather (wikipedia.org) became the co-founder of FORTH, Inc with Chuck and remained one of the leading experts and promoters of the Forth language until her retirement in 2006.

There's a great overview paper of the whole NRAO system by Moore and Rather in a 1973 Proceedings of the IEEE: The FORTH Program for Spectral Line Observing (PDF) (iae.nl).

It includes a high-level description of the system with examples of interactive Forth usage and a neat diagram on the first page, which you can see in the screenshot.

As mentioned, Forth was ported to a bunch of different computers at NRAO.

Let's take a look:

Moore mentions first having ported his Forth system to the IBM 360/50 (wikipedia.org).

The System/360 (or S/360) computers were extremely successful, largely because of availability, longevity, and compatibility. IBM claims to be the first company to use microcode (wikipedia.org) to provide a compatible instruction set across all S/360 computers despite the hardware differences between models.

The cheaper 360 computers used microcode while the more expensive and powerful machines had hard-wired logic. NASA even had some one-off models of IBM 360 made just for them.

Until microcode came along, if you bought a "cheap" computer to get started and then upgraded to a more powerful computer, you would have to re-write your programs in a new instruction set. (If you happen to have written your programs in a high-level language like Fortran, you would still have to re-compile your programs from punchcards, and you would need the Fortran compilers on both computers to be perfectly compatible!) It's easy to see why being able to upgrade without changing your software would have been appealing.

System/360 computers were a "big bet" (5 billion dollars according to IBM themselves: System 360: From Computers to Computer Systems (ibm.com)) that nearly destroyed the company. The bet clearly paid off because they made these machines from 1964 to 1978.

Oh, and it wasn't just the instruction set that was compatible. The 360 computers also had standardized peripheral interfaces, which were compatible between machines. There was a huge market for peripheral devices. IBM themselves made 54 different devices such as memory, printers, card readers, etc. The 360 also spawned a whole third-party peripheral industry, much like the IBM PC-compatible era that started in 1981 and continues to the desktop computer I'm typing on right now in 2023.

Moore wrote Forth from scratch in S/360 assembly.

Then...

I drew Chuck behind the system in this one because I couldn't bring myself to obscure an inch of that glorious pedestal console.

You can see the Honeywell 316 (wikipedia.org) and the brochure (wikimedia.org) image from which I made my drawing.

Just look at the space-age lines on that thing! It looks straight out of a Star Trek set. Sadly, there's basically no chance the one Moore actually worked on had this console. Less than 20 of them were sold. But thanks to my drawing, we can pretend.

Beyond just its appearance, this particular console has a really wild history. The extravagant gift company, Neiman Marcus, actually offered the Honeywell H316 with this pedestal as a "kitchen computer". It cost $10,000 and would have come with a two-week course to learn how to input recipes and balance a checkbook using toggle switches and lights to indicate binary data! (As far as anyone knows, none of these were actually sold.)

The ad for the Honeywell Kitchen Computer was in full "Mad Men" mode and was extremely patronizing, as was unfortunately typical for the time. But if you can look past that, the whole thing is quite funny:

"Her souffles are supreme, her meal planning a challenge? She's what the Honeywell people had in mind when they devised our Kitchen Computer. She'll learn to program it with a cross-reference to her favorite recipes by N-M's own Helen Corbitt. Then by simply pushing a few buttons obtain a complete menu organized around the entree. And if she pales at reckoning her lunch tabs, she can program it to balance the family checkbook..."

You can see a tiny scan of the original ad with a woman admiring her new Honeywell Kitchen Computer that barely fits in her kitchen here (wikipedia.org).

But moving on from the pedestal...

The implementation of Forth on the H316 is considered to be the first complete, stand-alone implementation because it was actually programmed on the computer itself and was used to create other Forths. It is at this point that Moore has achieved a fully ascendant system.

But wait, there's moore...er, sorry, more!

As is typical for a Chuck Moore endeavor, this telescope application pushed other new boundaries: The system actually ran across two computers (we're about to see the second one) and gave real-time access to multiple astronomers. Because it spread the load the way it did, there were no issues with concurrency, which is something we programmers struggle with to this day.

This real-time control and analysis was basically a luxury available on no other system at the time. Even Honeywell, the creator of these computers, had only been able to achieve the most primitive concurrency for them and it was nothing like this.

As usual, Moore was right on the very crest of computing with his ultra-flexible Forth system.

As mentioned above, the Forth system was also ported to the DDP-116 (t-larchive.org). and used with its "parent" system on the H316 featured above.

(The DDP-116 was originally manufactured by Computer Control Company in 1965, but CCC was sold to Honeywell in 1966 and became its Computer Controls division.)

The DDP-116 was a 16-bit computer (the first available for purchase), but still part of that "second generation" of computers we've mentioned before, with individual transistors and components wire-wrapped together on huge circuit boards. (Check out the pictures on the DDP-116 link above for all sorts of excellent views of the insides and outsides of an example machine and its peripheral devices!) It happens to have also been a pretty rare computer. It didn't sell in vast quantities like the IBM systems.

As you can see in the drawing, Chuck Moore began to grow in power as his system evolved and this manifested in additional arms! Or maybe I started to get a little loopy while drawing old computers for these slides in the final evenings before I was due to give my talk? I'll let you decide what is real.

But wait, there's one more!

The PDP-11 (wikipedia.org) was by some measures the most popular minicomputer ever.

It was a 16-bit machine and had an orthogonal instruction set (meaning the same instruction could be used in multiple ways depending on the operand. This makes the mnemonics of the instruction set smaller and more logical and much easier to memorize). This was even more powerful because I/O was memory-mapped, so the same instructions used to move values around in memory and registers could also be used to transfer data to and from devices.

All told, these conveniences made the PDP-11 fun to program! Assembly language programmers rejoiced. The ideas in the PDP-11 spread rapidly and are to be found in the most popular architectures in use today. Compared to what came before it, PDP-11 assembly language will look surprisingly familiar to modern assembly programmers.

The original machines were made starting in 1970 with wire-wrapped backplanes and discrete logic gates. Later models introduced "large-scale integration," which is a term we'll see later, so hold that question! These later versions of the PDP-11 were still being made twenty years later in 1990! There are apparently still PDP-11s performing crucial tasks today, with nuclear power plants being one of the most prominent examples.

It's hard to see in my drawing, but the PDP-11 front panel is one of the most iconic computer interfaces ever made. Hobbyists make working models, including ridiculously cute and awesome miniature versions. Here are two model versions - click on them to go to the original wikipedia.org files, where you can admire their full beauty:

It would be difficult to overstate the impact of this machine. Probably the most famous piece of software released on the PDP-11 was the first version of Unix (wikipedia.org) that actually bore the name "Unix".

It was also the birthplace of the C (wikipedia.org) programming language. Dennis Ritchie ported Ken Thompson's B language to the PDP-11 to take advantage of its abilities. Unix was then re-written in C starting with Version 4. So the Unix we know today and a large portion of the command line utilities that are standard with a Unix-like system were programmed on the PDP-11. (And you can thank Richard Stallman's GNU project for freeing those for the masses. GNU stands for "GNU's Not Unix!")

You'll also note that Chuck Moore has gained his fourth and final arm in my drawing above ("fourth," ha ha). This may or may not reflect actual events. Also, I'm not sure if Moore would have been using a video terminal at that time. It's possible. DEC's first video terminal was the VT05 (columbia.edu), which came out in 1970.

Wait, aren't most programs composed of calls to subroutines?

That's true. The big difference is that threaded code (wikipedia.org) in this sense doesn't actually contain the instructions to call the subroutines. It stores just the addresses. Therefore another routine is responsible for advancing a pointer over the address list and executing the subroutines.

Huh?

Yeah, there's no way around it, threaded code is complicated.

And indirect threaded code is even more complicated (and harder to explain).

"Hey, wait!" I hear you saying. "If Chuck hates complexity so much, why did he use such a complex method for Forth?"

That's completely fair.

But before we address that, I'll try to briefly explain how threaded code is stored and executed.

First, here's how normal machine code might be written:

This is the simplest type of "call" to store in a program. We simply have the jmp (jump) instruction followed by the address to jump to. Here I show both a hard-coded address (0x0804000) and a register (eax). Both of these are "direct" for our purposes.

Alternatively, many processors have a more advanced call instruction. A call is more complicated because it has to do additional work behind the scenes. It must store a return address on "the stack" before jumping to the specified address. Then a ret (return) instruction at the end of the called routine can use the stored address to resume the execution just after the "call site" where the call was first made. Why are return addresses stored on a stack? That's because you can nest calls. Pushing addresses as you jump and popping them in reverse order as you return keeps things nice and neat. This "the stack" is not what Forth refers to as "the stack". Forth's main stack is better known as "the parameter stack". Many Forth implementations also have a return stack!

Anyway, this is direct and it's not threaded. Just jump to an address.

The first step of complication is adding indirection.

For this example to make sense, you need to know that the square brackets around the register ([eax]) is a common assembly language convention that means "the value at the memory address that is stored in register eax".

So jmp [eax] means "jump to the address stored at the address stored in register eax."

That's indirect.

So now we have the "indirect" part of "indirect threaded code." But what's the "threaded" part?

Instead of containing the actual instructions to jump or call subroutines:

jmp 0x0804000
jmp 0x080A816
jmp 0x08C8800
jmp 0x08C8DD0
        

Threaded code stores just the list of addresses:

0x0804000
0x080A816
0x08C8800
0x08C8DD0
        

There are two consequences of storing code like this:

• The address list takes up less memory than the full code to make the jump. (In fact, it takes a lot less on some historic machines.) This is good.
• Some sort of "code interpreter" will need to be written to execute this list. You can't just send a list of addresses to a processor and expect it to work. This could be good or bad.

Another way to look at the list of addresses above is that, conceptually, threaded code is basically a list of subroutines.

To complete our definition of "indirect threaded" code, we just need to put both concepts together:

This is where it gets pretty crazy. So now we've got a second level of indirection. Why on Earth would we do this?

Well, this allows us to store a separate "code interpreter" (or "inner interpreter") for different kinds of subroutines!

Instead of pointing directly at subroutines, these addresses point at interpreters. Talk about ultimate flexibility - every subroutine in an indirect threaded program can have its own custom interpreter for the rest of its instructions...each of which can also be threaded...or indirectly threaded!

But what calls all of these inner interpreters? An outer interpreter, of course! The outer interpreter is the part we actually interact with when we sit down to type at a Forth terminal.

In Forth, indirect threaded code is a list of addresses pointing to the "inner interpreter" portions of words, which execute the rest of the word. What types of inner interpreters could we have, anyway? Well, for example, we might have one kind of word that stores a string in memory and another that executes machine code. But the only limit is your imagination.

Make sense?

I personally would not have understood that explanation at all until much later in my journey (I know this because similar - probably better - explanations flew right over my head). No doubt you're faster than me at apprehending this stuff and are already halfway through implementing your own Forth based on these descriptions.

None of the rest of the material requires understanding any of the above, so please don't feel you need to fully grok (wikipedia.org) it before continuing. Indirect threading is an important part of Forth's history, but there are plenty of Forths that do not use it.

In addition to its compact storage, threaded code would have been even more efficient on the contemporary machines during Forth's gestation because calling subroutines often wasn't as simple as the call instruction found on "modern" architectures.

Subroutine and procedure call support (clemson.edu) by Mark Smotherman explains:

"1963 - Burroughs B5000 - A stack-based computer with support for block-structured languages like Algol. Parameters and return address are stored on the stack, but subroutine entry is a fairly complex operation."

So the memory and performance improvements of this style of subroutine call were potentially very great indeed. This is one of the reasons for Forth's legendary reputation for high performance.

We'll revisit this topic from another angle soon. But if you're interested in these mechanics (and want to see the origin of the boxes and arrows drawings at the top of this section), check out this multi-part article series for The Computer Journal, MOVING FORTH Part 1: Design Decisions in the Forth Kernel (bradrodriguez.com), by Brad Rodriguez.

The important thing is that we've now fully traced the origins of Forth from a simple command interpreter to the full-blown interactive language, editor, operating system, and method of code storage and execution it became.

At last! Now we can put it all together:

Forth is postfix because that's a natural order for the computer and lends itself to an incredibly minimalistic interpreter implementation: get the values, operate on them;

Forth is stack oriented because that's a compact and convenient way to store values without needing to add variables or name things;

Forth is concatenative because building a language that can operate as a string of words is incredibly flexible and can adapt to just about any programming style without any help from the language itself. (And it turns out this is especially true when you throw in higher-order functions);

Forth is interpreted because that is interactive and allows the programmer to make fast changes on the fly or simply "play" with the system. This is part of Forth's adaptability and flexibility;

Forth is self-hosting because you can bootstrap a Forth implementation from a handful of words implemented in assembly and then write the rest in Forth;

Forth is extremely compact because machines at the time had limited memory and this gave Forth an edge on other interpreters (and even compiled languages!) on mainframes and mini-computers.

Now that we have everything in historical context, I think it's much clearer why Forth exists and why it takes the peculiar form that it does.

None of this was planned. Chuck didn't sit down at a terminal in 1958 and conjure up Forth. Instead, he grew a system to serve his needs and to make use of new hardware as it was made available.

Reading about Forth's history is a wonderful way to understand what makes Forth special and what it's about.

But even knowing all of this, I was still a long way off from a true understanding of how this all comes together in an actual working system. I didn't really understand how it worked. And I didn't understand what Forth was actually like to use In other words, I still didn't understand Forth as a programming language.

I've mentioned it before, but I'll point it out again. Notice the phrasing "implement a Forth."

As we've established, Chuck Moore believes a Forth system is best when it is custom-tailored to the system and task at hand. So it should come as little surprise that writing your own Forth or Forth-like is entirely "par for the course" in any would-be-Forther's quest to discover the True Meaning of the language and enter the mystical realm where All is Revealed.

Well, what else could I do?

Having no other clear course of study, I decided to heed the wisdom of the crowd.

Presenting...

To really get to know it, I took Forth to bed with me.

I wrote Assembly Nights when I realized how much I was enjoying myself:

"Over the last three months, I've developed an unusual little nighttime routine..."

I prepared myself for dealing with the JonesForth source (i386 assembly language in the GNU GAS assembler) by learning some assembly and Linux ABI basics. JonesForth is 32-bit only and uses the Linux system call ("syscall") ABI directly.

Then I spent roughly a year porting JonesForth into a complete working copy in NASM assembler. (Yes, that's a "port" from one flavor of i386 asm to another.)

I did a tiny bit almost every night. A lot of it was debugging in GDB.

Here's the nasmjf web page

In the process of writing the port, I learned how a traditional indirect threaded Forth works.

And I learned that it takes time to absorb such a twisty-turny method of code execution.

Especially if the x86 assembly language tricks are new to you like they were for me.

One of the first things you encounter when you open up the jonesforth.S (a single file which contains the assembly language portion of JonesForth) are many ASCII art diagrams.

Richard W.M. Jones does an excellent job of walking you through the workings of the interpreter and explaining the i386 instruction set features he uses.

If the diagram above seems bewildering, I agree.

So, of course, I thought maybe I could do better...

After I was done with my port, I tried to make an ASCII art diagram of my own to capture my new understanding. In fact, this is one of several.

With the benefit of the distance of time, it is clear to me that these things only make sense once you already understand them to some degree. But the act of making them is extremely useful for solidifying your understanding.

But wait, there's more!

Both ASCII art diagrams above are just part of the complete indirect threaded execution system. They're just showing how the "inner interpreter" works to execute Forth words.

Perhaps you recall from the section about indirect threaded code above that the second level of indirection allows different "interpreter" routines to execute different types of threaded subroutines? Well, that's all those two ASCII diagrams are trying show.

But when we say that Forth is an interpreted language, this is not what we're talking about. There's also the "outer interpreter" that the programmer interacts with.

In the vector image I made above for nasmjf, I attempted to map out the whole thing in my own words.

If you take anything from this image, it's that INTERPRET looks up words (functions) by name and calls them by executing the interpreter routine whose address is stored in the word (again, this is the indirect threading part). In turn, there may be any number of interpreters, but the three main types used in JonesForth are:

• Pure assembly language routines are their own interpreters.
• "Regular" Forth words use the DOCOL interpreter. DOCOL executes the rest of the threaded code in the word, most of which is just a list of addresses, but some of which will be data. This is the "normal" kind of threaded subroutine.
• Numeric literals have a tiny interpreter routine inline with the data that just pushes their value to the stack. Numeric literals don't have to be words, though, in JonesForth, they're just a bit of inlined machine code.

But even knowing this only helps to explain how code starts executing. How does this type of Forth know what to run after a word is complete?

Ah, for that we have this:

Notice the term "code word". That's the Forth term for words written in pure assembly language.

Every code word has this macro at the end. (Some Forths actually call a subroutine for this. JonesForth uses this two-line macro because the action is so efficient in i386 machine code.)

Remember the list of addresses in the explanation of "indirect threaded" code? This is how we execute them sequentially.

This implementation uses the i386 lodsd instruction to take care of two operations in one: move a "double word" from memory into a register, and then update another register so that it points to the next "double" spot in memory.

(Rant: And a "double" is 32 bits on Intel chips for the really annoying reason that they kept the definition of "word" at 16 bits even as the platform moved to 32 and then 64-bit architecture. So "word" on Intel architectures is a completely meaningless thing that you just have to memorize as "16 bits" even though "word" is supposed to be the native data size of the architecture. And what's worse is that the tools for working with programs on Intel chips like GDB then refer to everything with the corresponding C names for everything, which naturally assumed that the architecture names would be based on reality. But they aren't. So terms like "double" and "long" are basically just absolutely worthless legacy garbage to memorize and useful only to C and Intel architecture veterans.)

Okay, so now the eax register points to the next threaded subroutine address in memory. The jmp starts executing whatever that points to, which will be the "inner interpreter" for that subroutine.

Got that?

A lot of moving parts, right?

There's more:

Remember, there's two fundamental types of words in a traditional Forth like JonesForth: "Code" words and "colon" words. Code words are primitives written in machine code. Colon words are the "regular" words actually written in the Forth language.

These "colon" words (so-named because they are assembled via the "COLON" compiler, which we'll talk about in a moment), all end in the so-called EXIT macro.

The EXIT macro handles the return stack. Then there will be a NEXT after that to conclude whatever code word primitive we were in (we're always in at least one because the "outer-most" interpreter is a code word primitive!), so the process we described above will automatically start where we left off at the "call site" of the word we just finished executing.

If you weren't lost before, surely this will do the trick?

I do have another attempt to explain how this all nests in a sort of indented pseudocode:

This nested view of the process is as close as I've ever been to explaining (to myself) what the entire execution flow looks like at a high level.

I'm sure every Forth implementer has their own mental model.

You'll notice we didn't even talk about QUIT. Other than the name, that one's not nearly as bad - it's really just the end of the outer interpreter loop.

(So, yeah, we have EXIT and QUIT, neither of which leave Forth... Hey, it was the 1960s. Things were different then.)

Historical note: The above "Crazy Chuck" drawing is a parody of a popular meme with actor Charlie Day's character in the episode "Sweet Dee Has a Heart Attack" from the show It's Always Sunny in Philadelphia:

"Every day Pepe's mail's getting sent back to me. Pepe Silvia, Pepe Silvia, I look in the mail, this whole box is Pepe Silvia!"

You, citizen of the distant future, will not have recognized this parody, but at least now you can look it up.

I'll repeat your question from before so you don't have to:

"Hey, wait! But if Chuck hates complexity so much, why did he use such a complex method for Forth?"

This is where the historical context is, once again, very revealing:

As we've seen, Charles H. Moore did not create Forth all at once in a single lightning bolt of inspiration. It began as a simple command interpreter and executor and grew from there. It has always consisted of tiny little parts, working together.

Each of these tiny parts is extremely simple on its own.

And each was added over a period of time as the need arose.

I think that's the genius of Forth: That all of these little pieces can work together to make a running system and yet still remain independent. You can learn each of these in isolation. You can replace them in isolation.

Ultimate flexibility and simplicity at the lowest level of the implementation comes at the cost of easy understanding at higher levels.

When growing a system like this, most of us would have thought bigger, Moore thought smaller.

Let's do the same. I've thrown the terms "code word" and "colon word" around a lot. I've explained them a bit, but we've never given a proper introduction.

Let's go small:

Again, Code words are primitives written in machine language supplied by the Forth implementation.

Let's see some real code words so we can de-mystify them once and for all. These are extremely simple and extremely concrete examples of actual NASM assembly language source from my nasmjf port of JonesForth:

Is that really SWAP? Yes, it really is! We're just telling the CPU to pop the two most recent values from the stack and then push them back in the opposite order.

(JonesForth uses the i386 call/return stack as a Forth parameter stack so we can use the native "pop" and "push" to make these operations easy. In exchange, we lose the ability to use "call" and "ret" for subroutines.)

The DEFCODE macro is housekeeping - it creates the entry's header in the Forth word dictionary.

Notice the NEXT macro we talked about previously? Remember, that's just another two lines of assembly pasted at the end of this routine.

We're down to just two instructions now! We move the value pointed at by the esp register into eax and then push it onto the stack.

To understand why this duplicates the top item on the stack, you need to know how the esp register is used. Here's the relevant comment from the JonesForth source:

"In this FORTH, we are using the normal stack pointer (%esp) for the parameter stack. We will use the i386's "other" stack pointer (%ebp, usually called the "frame pointer") for our return stack."

Which means that esp points to the current top of the parameter stack. So pushing that value on the stack duplicates the top value. (This could also have been written more clearly with three instructions: one "pop" and two "push"es.)

Now we have an entire Forth word defined as a single instruction! DROP just "removes" the top value from the stack. In this case, we pop it into the eax register and then don't do anything with it, essentially throwing it away. (Alternatively, we could have decremented the esp register, but in this case, the "pop" is both shorter and clearer.)

Now let's see these three words in action in a real Forth program that moves some real numbers around in memory...

The code word primitives we've just defined are used by the rest of the Forth implementation to define colon words in the language itself. If you write Forth applications, your own colon words will probably use these heavily.

You can also call them interactively in the interpreter.

The above example shows what it might be like to use these three primitives right at the keyboard. The column on the right shows the state of the parameter stack after each line of input.

Apart from pushing the two numbers on the stack (8 7) , we've now seen the assembly language code for the entire program shown above. That makes this pretty "bare metal" stuff, right?

Here's the walk-through:

• We start with 8 and then 7 on the top of the stack.
• SWAP reverses the order of the stack so 8 is now on the top.
• DROP pops the 8 and throws it away. Now only 7 remains.
• DUP pushes a second copy of 7 onto the top of the stack.

Again, these instructions could exist in the definition of a word or you could type them interactively in the running Forth interpreter. The result is the same.

I think there's something pretty magical about realizing that typing these instructions is running specific machine code sequences exactly as they were entered. In this implementation, there's no optimizing compiler or virtual machine acting as middle-man. You really are communicating directly with the processor.

If you weren't already wondering, perhaps you are now: How many Forth words need to be defined in machine code to have a "bootstrappable" Forth system?

There are some theoretical minimums. But as you get down to an absurdly small number of instructions, the Forth code written with the primitives (to implement the rest of the language) approaches absurdly large amounts of convolutions that test the limits of both programmer ergonomics and computational inefficiency.

Check out this amazing article by Frank Sergeant: A 3-INSTRUCTION FORTH FOR EMBEDDED SYSTEMS WORK (utoh.org).

"How many instructions does it take to make a Forth for target development work? Does memory grow on trees? Does the cost of the development system come out of your own pocket? A 3- instruction Forth makes Forth affordable for target systems with very limited memory. It can be brought up quickly on strange new hardware. You don't have to do without Forth because of memory or time limitations. It only takes 66 bytes for the Motorola MC68HC11. Full source is provided."

You read that right: 66 bytes.

And later:

"The absolute minimum the target must do, it seems to me, is fetch a byte, store a byte, and call a subroutine. Everything else can be done in high-level Forth on the host."

Which reminds me, did you know there is such a thing as a one-instruction set computer (wikipedia.org)? And of course you can run Forth on them: 16-bit SUBLEQ eForth (github.com).

But that's nuts.

How about something a little more realistic?

Cesar Blum's sectorforth (github.com) is:

"...a 16-bit x86 Forth that fits in a 512-byte boot sector. Inspiration to write sectorforth came from a 1996 Usenet thread."

See? There's Usenet again. It wasn't just me reading all that lore.

The author's posting of the project to the Forth sub-reddit (reddit.com) has additional insight:

"I've always been fascinated by the idea of having a minimal kernel of primitives from which "everything" can be built. Before Forth, I had only seen that in the form of Lisp's "Maxwell equations of software", which is cool, but always left me a little disappointed because it is too abstract to build something that you can actually interact with - you can't break out of its esoteric nature...

With Forth, however, you can start from almost nothing, and start adding things like ifs, loops, strings, etc., things that look more like your day-to-day programming. I find that there's a lot of beauty in that."

Note: The statement about Maxwell's equations surely refers to Alan Kay's famous quote about LISP from A Conversation with Alan Kay (acm.org):

"Yes, that was the big revelation to me when I was in graduate school - when I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were "Maxwell's Equations of Software!" This is the whole world of programming in a few lines that I can put my hand over."

Okay, so we've talked about code words that are just chunks of machine code that can be called upon at any time.

Now let's see what colon words are all about...

A colon word is so-named because its definition begins with the ":" character.

The example colon word definition above creates a new word called SDD that is a composition of the three code words we defined earlier: SWAP, DROP, and DUP. Perhaps the word "composition" brings to mind the concatenative terminology we explored earlier in this quest?

As this example demonstrates, colon words are defined entirely by other words, which may be code words or other colon words. You can also have numeric values, e.g. 8 and 7, which are handled by the interpreter.

(You can also have strings, which looks like data...but those are just input that happens to follow one of the special words, e.g. ." (dot quote), that knows how to handle the input!)

Let's see it in action:

In indirect threaded code terms, this colon word has been "compiled" into the addresses of the "inner interpreters" for each of the three code words. But feel free to ignore this detail!

Let's demystify this further because the Forth "compiler" is probably much, much simpler than you'd think: