Coding Challenge #95 - Forth Interpreter

This challenge is to build your own interpreter for a Forth-like programming language and learn some Forth.

Hi this is John with this week’s Coding Challenge.

🙏 Thank you for being one of the 88,421 software developers who have subscribed, I’m honoured to have you as a reader. 🎉

If there is a Coding Challenge you’d like to see, please let me know by replying to this email📧

Coding Challenge #95 - 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.

If You Enjoy Coding Challenges Here Are Four Ways You Can Help Support It

1. Refer a friend or colleague to the newsletter. 🙏

2. Sign up for a paid subscription - think of it as buying me a coffee ☕️, with the bonus that you also get 20% off any of my courses.

3. Buy one of my self-paced courses that walk you through a Coding Challenge.

4. Join one of my live courses where I personally teach you Go by building five of the coding challenges or systems software development by building a Redis clone.

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:

1. Decide if you’re building:

   1. A web-based solution and if so, is it frontend only or fullstack?

   2. Decide if you’re building a desktop or mobile application complete with a GUI.

   3. Decide if you’re building a CLI tool, like me. 🙂

2. Decide what programming language you’re going to build your solution in.

3. 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, the + word is documented using a comment ( n1 n2 -- sum ).

Here is the full list of mathematical operations:

+ ( 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:

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:

. ( 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:

< ( 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.

Two Other Ways I Can Help You:

1. I write another newsletter Developing Skills that helps you level up the other skills you need to be a great software developer.

2. I have a YouTube channel sharing advice on software engineering.

Share 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 via Bluesky 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

Request for Feedback

I’m writing these challenges to help you develop your skills as a software engineer based on how I’ve approached my own personal learning and development. What works for me, might not be the best way for you - so if you have suggestions for how I can make these challenges more useful to you and others, please get in touch and let me know. All feedback greatly appreciated.

You can reach me on Bluesky, LinkedIn or through SubStack

Thanks and happy coding!

John