Build Your Own Forth Interpreter
This challenge is to build your own Forth-like interpreter. Forth is a stack-oriented programming language that was designed by Charles H. "Chuck" Moore and first used by other programmers in 1970. It gained an official standard in 1994. Although it’s not an acronym, for much of it like Forth was referred to as FORTH. Why Forth and not Fourth? Here’s why:
“The first time I combined the ideas I had been developing into a single entity, I was working on an IBM 1130, a “third-generation” computer. The result seemed so powerful that I considered it a “fourth-generation computer language.” I would have called it FOURTH, except that the 1130 permitted only five-character identifiers. So FOURTH became FORTH, a nicer play on words anyway.”
— Charles H. Moore, creator of Forth
Forth has been used to write bestselling computer games, firmware, spaceflight software and various embedded systems. For us it’s a fun language to implement an interpreter for and it gives you a chance to learn about Reverse Polish Notation (RPN), stack oriented-programming and writing interpreters.
The Challenge - Building A Forth Interpreter
This challenge is to build your own Forth-like interpreter. That is an interpreter for a subset of the Forth language, sufficient for you to write and run code to generate the Fibonacci sequence and the coding interview favourite, FizzBuzz.
You can build a Forth-like interpreter in any programming language or stack. You could build it as a CLI tool or as an in-browser interpreter with a web based IDE. So this coding challenge will suit frontend, backend, fullstack, data engineer, system, or whatever type of software engineer you consider yourself to be.
Me, I built it as a CLI tool just like the other compilers and interpreters I’ve built.
Step Zero
As always, in a throwback to the days when I wrote C, Coding Challenges is zero indexed. In this step your goal is to:
- Decide if you’re building:
- A web-based solution and if so, is it frontend only or fullstack?
- Decide if you’re building a desktop or mobile application complete with a GUI.
- Decide if you’re building a CLI tool, like me. 🙂
- Decide what programming language you’re going to build your solution in.
- Learn some Forth!
When it comes to learning Forth, there are two good places to start:
- Starting FORTH, the classic FORTH tutorial by Leo Brodie.
- Easy Forth an online ebook with integrated interpreter letting you try out the code right there in the book.
N.B.: If you want to go deeper there is a more in depth set of resources on the Coding Challenges blog post: learning Forth.
Step 1
In this step your goal is to build a simple REPL (Read-Eval-Print Loop) and allow the user to terminate the REPL by entering the Forth word: bye. In Forth, subroutines are referred to as ‘words’.
The typical Forth prompt in the REPL is: ok>
So when you’ve completed this step, using your interpreter will look something like this:
% ./ccforth
ok> bye
Not very exciting is it, so let’s add enough Forth for us to do simple calculations.
Step 2
In this step your goal is to handle the user entering integers and some basic mathematical operations. To enable that you need to handle entering an integer. The integer should then be pushed onto the interpreter’s data stack - remember Forth is stack based.
In Forth, anything between brackets is a comment, so words are often described using comments, for example:
| Word | Comment | Description |
|---|---|---|
| + | ( n1 n2 -- sum ) | Pops the top two elements (n1 and n2) on the stack, pushes the sum on to the top of the stack |
| - | ( n1 n2 -- diff ) | Pops the top two elements on the stack, subtracts n2 from n1 stores the result on the top of the stack |
| * | ( n1 n2 -- multiplied ) | Pops the top two elements on the stack, pushes the product on to the top of the stack |
| / | ( n1 n2 -- divided ) | Pops the top two elements on the stack, pushes the result of n2 / n1 on to the top of the stack |
| mod | ( n1 n2 -- modulus ) | Pops the top two elements on the stack, pushes the remainder of n2 / n1 on to the top of the stack |
You should add support for all these operations. To test them you’ll need to also implement a feature of most Forth REPLs, showing the stack from bottom to top before the prompt. For example:
% ./ccforth
ok> 1 2 2 + +
5 ok>
Here the integers 1,2, and 2 are pushed onto the stack, then the operations + and + are run. The result of each addition is pushed onto the stack, resulting in the stack containing 5. This could also have been done in stages:
% ./goforth
ok> 1
1 ok> 2
1 2 ok> 2
1 2 2 ok> +
1 4 ok> +
5 ok>
Leaving the result, 5 on the top of the stack.
Step 3
In this step your goal is to add support for several Forth words used to manipulate the stack: dup, drop, rot, over and swap:
| Word | Comment | Description |
|---|---|---|
| swap | ( n1 n2 -- n2 n1 ) | Swaps the top two elements on the stack |
| dup | ( n -- n n ) | Duplicates the top element on the stack |
| over | ( n1 n2 -- n1 n2 n1 ) | Duplicates the second from top element and pushes it on to the top of the stack |
| rot | ( n1 n2 n3 -- n2 n3 n1 ) | Rotates the top three elements on the stack |
| drop | ( n1 -- ) | Pops the top element off the stack |
Be sure to test them.
Step 4
In this step your goal is to implement support for four new words:
| Word | Comment | Description |
|---|---|---|
| . | ( n1 -- ) | Prints and pops the top of the stack |
| emit | ( n1 -- ) | Prints the top of the stack as n ASCII character and pops the top of the stack |
| cr | ( -- ) | Prints a newline |
| ." | ( -- ) | Prints the string from after the space to the ending quote, i.e. ." hello" prints "hello" |
Using them looks like this:
ok> 5 . cr
5
ok> 78 72 79 74 emit emit emit emit cr
JOHN
ok> ." Hello, Coding Challenges" cr
Hello, Coding Challenges
ok>
Step 5
In this step your goal is to implement support for defining new words. In Forth words are defined between : and ; and then called using the word, for example to define a new word say-hi, and then call it:
ok> : say-hi ." Hi, John" cr ;
ok> say-hi
Hi, John
ok>
You should also handle calling a word that doesn’t exist. For that simply print the word and a question mark:
ok> say-bye
say-bye ?
Finally add support for comments. Comments are any text between brackets and are not interpreted:
ok> ( this is a comment )
ok> : hi ( says hi ) ." Hi!" cr ;
ok> hi
Hi!
ok>
Step 6
In this step your goal is to add support for conditionals and loops. The conditionals are:
| Word | Comment | Description |
|---|---|---|
| < | ( n1 n2 -- -1/0 ) | Pops the top two elements on the stack, checks if n1 is less than n2, pushes -1 if it is otherwise 0 |
| > | ( n1 n2 -- -1/0 ) | Pops the top two elements on the stack, checks if n1 is greater than n2, pushes -1 if it is otherwise 0 |
| = | ( n1 n2 -- -1/0 ) | Pops the top two elements on the stack, checks if n1 is equal to n2, pushes -1 if it is otherwise 0 |
| <> | ( n1 n2 -- -1/0 ) | Pops the top two elements on the stack, checks if n1 is not equal to n2, pushes -1 if it is otherwise 0 |
| and | ( n1 n2 -- -1/0 ) | Pops the top two elements on the stack and if both are true pushes -1, otherwise 0 |
| or | ( n1 n2 -- -1/0 ) | Pops the top two elements on the stack and if either is true pushes -1, otherwise 0 |
| invert | ( n1 -- -1/0 ) | Pops the top element on the stack and pushes the boolean negation |
Once you have them you should be able to implement if then blocks:
: buzz 5 mod 0 = if ." Buzz" then ; 5 buzz
And if else then blocks:
5 3 = if ." Equal" else ." Not Equal" then
Then move on to adding support for do loop:
ok> : loop5 5 0 do ." Test" cr loop ; loop5
Test
Test
Test
Test
Test
ok>
Don’t forget to refer to the Forth book for full details of the syntax if you need clarification.
Step 7
In this step your goal is to support running Forth-like code from a script file, with the name provided as an argument to the interpreter. Here are two scripts you should be able to run with the language features built so far:
: fib over over + ; ( generate the next number in the Fibonacci sequence )
: fibn 10 1 do fib dup . loop ;
0 dup . 1 dup . fibn ( generate the next 10 numbers )
cr
To generate the Fibonacci sequence and FizzBuzz:
: fizz 3 mod 0 = dup if ." Fizz" then ;
: buzz 5 mod 0 = dup if ." Buzz" then ;
: fizz-buzz dup fizz swap buzz or invert ;
: do-fizz-buzz 25 1 do cr i fizz-buzz if i . then loop ;
do-fizz-buzz
Once that works, have some fun writing your own Forth code to run in your interpreter!
Going Further
If you’d like to take this further, work through the resources on learning Forth and read the Forth standard, then add the new features that would be of interest to you. You could also explore compiling the code, either directly or leveraging the LLVM backend.
Help Others by Sharing Your Solutions!
If you think your solution is an example other developers can learn from please share it, put it on GitHub, GitLab or elsewhere. Then let me know - ping me a message on the Discord Server, via Twitter or LinkedIn or just post about it there and tag me. Alternately please add a link to it in the Coding Challenges Shared Solutions Github repo.
Get The Challenges By Email
If you would like to receive the coding challenges by email, you can subscribe to the weekly newsletter on SubStack here: