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.