100 Languages Speedrun: Episode 20: Forth

Stacks are everywhere in programming, behind the scenes.

Whenever you call any function in almost any language, its arguments are pushed onto a stack, as is some information on where the program should return to once it's done with the function. The function pops that data from the stack, and once it's done, it pops up the information of where it should go next. This pushing and popping from stacks is a sizable part of what computers do. However, very few languages expose the stack in any way.

Forth is what happens when stack is the centerpiece of a language.

Hello, World!

Unfortunately we run into our first problem already. Forth was created back in the 1970s, and back then people did not believe in Strings. Forth Stack consists of small cells, each big enough for a number or an address, and a string wouldn't fit there. So instead of fitting in Forth computational model, strings need a lot of special case handling.

#! /usr/local/bin/gforth

." Hello, World!"
cr
bye

There's so many things going on here:

• Forth does not like Unix #! shebang lines, there's a hack to get around it and that involves adding a space after #! to make both Unix and Forth happy.
• cr command prints new line
• bye command exits - you need to do this or Forth will go into repl instead; that's an unusual default.
• ." means "go until next quotation mark and print whatever's there". This string isn't actually an object an any point like in usual programming languages. There's extra space after the .", that's part of the syntax.

You can of course put all that on the same line, line breaks mean nothing in Forth.

Double the number

Let's take baby steps towards building real functions.

#! /usr/local/bin/gforth

( Function to double a number )

: double
  dup +
;

21 double .
cr bye

A few things are happening here:

• ( ... ) is a comment - and again, you need that space after (
• : name ... ; defines a function - functions don't take arguments or return values, they just do stuff to the stack
• The double function does two things: dup duplicates the top of the stack, and + adds the top two numbers on the stack

So let's track what's going on step by step:

• 21 - pushes 21 to stack (stack is now 21)
• double - calls double function
• inside double - dup duplicates top of the stack (stack is now 21 21)
• inside double - + adds top two numbers (stack is now 42)
• double returns (stack is still 42)
• . prints top value from the stack (stack is now empty)
• cr prints new line (stack is still empty)
• bye exits

That might seem really convoluted, but steps like these is what sort of happens behind the scenes in many programming languages.

Fibonacci

Let's do something a bit more complicated, the Fibonacci function.

#! /usr/local/bin/gforth

: fib recursive
  dup 2 <= if
    drop
    1
  else
    dup 1 - fib
    swap
    2 - fib
    +
  endif
;

20 fib . cr
bye

That is a lot! Probably our most complicated Fibonacci function yet.

You can probably understand already what 20 fib . cr bye does - it calls fib with argument of 20, then prints the result, prints new line, and exits.

Let's see what fib function does. It has a big if ... else ... endif, so let's see check both cases. fib will only operate on top parts of the stack, I'll indicate by ... that there could be more stuff below it, but fib won't touch any of that.

If top of the stack is 1:

• fib starts, stack is (... 1)
• dup duplicates top value (... 1 1)
• 2 pushes 2 (... 1 1 2)
• <= compared top two values on stack and pushes 0 for false, or surprisingly -1 for true (... 1 -1)
• if goes to the first branch (... 1)
• drop drops top value of stack (...)
• 1 pushes 1 (... 1)
• function returns, 1 will be treated as return value

And if top of the stack is 20:

• fib starts, stack is (... 20)
• dup duplicates top value (... 20 20)
• 2 pushes 2 (... 20 20 2)
• <= compared top two values on stack and pushes 0 for false, or surprisingly -1 for true (... 20 0)
• if goes to the second branch (... 20)
• dup duplicates top value (... 20 20)
• 1 pushes 1 (... 20 20 1)
• - subtracts top two values (... 20 19)
• fib calls itself with argument of 19 (... 20 4181)
• swap swaps top two values on stack (... 4181 20)
• 2 pushes 2 (... 4181 20 2)
• - subtracts top two values (... 4181 18)
• fib calls itself with argument of 18 (... 4181 2584)
• + adds top two values (... 6765)
• function returns, 6765 will be treated as return value

Loop

On our way to the inevitable FizzBuzz, let's first do a simple loop printing numbers from 1 to 11:

#! /usr/local/bin/gforth

: ten-numbers
  11 1 do i . cr loop
;

ten-numbers
bye

do ... loop is the loop. Top two numbers on stack are limit and start. Limit is where the loop stops, so it needs to be 1 higher than the last index - sort of like Python's range(1,11).

i pushes current loop index onto the stack. Then we print it with . and add a newline with cr.

Forth only supports this inside a function, so we had to wrap it in ten-numbers function. If you try to put this directly into source code or reps, you'd get a cryptic "Interpreting a compile-only word". And same story with if and so on.

FizzBuzz

And finally the FizzBuzz!

#! /usr/local/bin/gforth

: divisible
  mod 0=
;

: fizz-buzz
  dup 15 divisible if
    drop
    ." FizzBuzz"
  else
    dup 5 divisible if
      drop
      ." Buzz"
    else
      dup 3 divisible if
        drop
        ." Fizz"
      else
        .
      endif
    endif
  endif
;

: fizz-buzz-loop
  101 1 do i fizz-buzz cr loop
;

fizz-buzz-loop
bye

• The main program just calls fizz-buzz-loop
• The fizz-buzz-loop is a loop from 1 to 100, calling fizz-buzz with index as argument
• divisible returns true (-1) or false (0) depending on whether the second number on the stack is divisible by the top one
• fizz-buzz is a triple nested if/else/endif - I don't think Forth has any significantly cleaner ways to do this
• dup 15 divisible if takes first branch if top of the stack is divisible by 15, second branch elsewhere (and so on for 5 and 3)
• drop ." FizzBuzz" drops top of the stack and prints "FizzBuzz" instead
• . takes top of the stack and prints it

Should you use Forth?

Forth could be a fun entry point to "esoteric languages". Forth itself is a real serious language that for a while achieved moderate popularity in some niches, primarily in situations where size is at an extreme premium like microcontrollers. Getting some coding practice with stack based language like Forth could prepare you for all kinds of crazy esoteric languages like Befunge, Brainfuck, and so on, as stack-based programming is popular there.

It could also be quite interesting to play with Forth a bit if you want to dive into stack-based virtual machines like JVM (and like most of them) or computer architectures (like pretty much all of them). Even most other stack-based systems are considerably less stack-based than Forth, but it could be useful practice.

For serious programming, absolutely not.

Code

All code examples for the series will be in this repository.

Code for the Forth episode is available here.

Comments

[Gordon Charlton]

I'm going to take issue with your last sentence. "For serious programming, absolutely not."

It should read "For computer scientists, only for context. There is something to concatenative languages (not for everyone, you need an odd shaped head, so to speak, to appreciate postscript notation etc.) and Forth is of historical interest. For serious electrical engineers, yes, absolutely."

I was, for a while, an active and well known part of the Forth community. A little while ago now, but the community is still small and thriving. It is and was, mostly electrical engineers, with some representation from academia.

I owned my third Forth for several years without knowing it, because it was buried deep inside my Mac at the time. Had I known sooner, I would have pressed ⌘ Cmd+⌥ Option+O+F after switching it on, and got the Open Boot Forth prompt.

It existed to talk to firmware on bits of hardware, and tell it "teach me what you do". The firmware would respond with forth text, which the Forth would compile.

Why Forth? Because it was so tiny that it, the compiler and "inner interpreter" (it was a token threaded Forth running on a virtual machine) could exist entirely within the onboard memory of the Motorola 68040 and never be slowed down by having to access the regular RAM. That's how tiny it is. It's creator claimed, when I met him, that it ran faster than the equivalent assembly code (presumably if written in the conventional style, or spat out by a C (or whatever) compiler) because of this.

Other notable uses. It was, for a while, the darling of NASA. I don't know about its current status there. Presumably because of it's history as the language of choice for astronomers wanting to drive their observatory telescopes. And because of its popularity for safety critical systems.

Another notable person within the community that I knew worked in nuclear power. He explained it like this:

You know that long legal disclaimer, the one you click "yes I've read it" without actually reading it? The one that comes with your operating system, your compiler and your business software, and pretty much everything else. It says "we accept zero responsibility for anything bad that happens from using this software. You're on your own, buddy."

I can't do that when I program devices that can kill millions if they go wrong, and that will run continuously for decades, hopefully without crashing. So I build systems, integrated hardware and software, that are so simple at every stage that I can know exactly what they are doing at every moment. The Forth compiler is utterly trivial, I can hold every aspect of it in my head at the same time. The mapping between source code and compiled code is one-to-one. So I know exactly what it compiles. And the environment allows me to rigorously debug code on a line by line basis as I go along. I do 1% coding to 99% testing.

No insurance company will touch me, and I have personal liability, so not only are millions of lives on my line, but if it very goes to court because I wrote buggy code, my livelihood, my savings, my house, and my family are on the line. I will have been responsible for many deaths and destitute.The absolute need for right-first-time makes Forth my language of choice.

Final note. Over in the States, Forth Inc is still a thriving business. Their list of clients is quite impressive, but misses out the really mind-blowing "wtf, THEY use Forth?" clients, because it's their secret sauce. In private conversation with the former head of the company, I learned a few names that I won't be revealing, so you'll just have to take my word that Wow! Really? Them? Oh, yes, very much yes.

[Tomasz Wegrzanowski]

You can check the full tier list of languages I wrote at the end of the series.

The way I rank languages is by "how much I'd recommend a language for a new project". Any historical significance is specifically excluded from consideration.

Forth and Factor are both in "E Tier. Enjoy a weekend with them, then move on", and there's definitely some advantage in trying out a few more exotic languages, even for people who then go back to Python for their day job.