100 Languages Speedrun: Episode 20: Forth
Tags: forth
Published: 2021-12-10 17:27:01

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.

```forth
#! /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.

```forth
#! /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.

```forth
#! /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:

```forth
#! /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](https://github.com/taw/100-languages-speedrun).

[Code for the Forth episode is available here](https://github.com/taw/100-languages-speedrun/tree/master/episode-20-forth).