FORTH interpreter in 130* lines of Python

Get the code on GitHub

Introduction

FORTH is a simple stack-based language. It is a good way to learn compilers and interpreters. I will show you how to write a FORTH compiler and interpreter in 130* lines of Python.

Some disclaimers

First, this is not a perfect, standards-compliant FORTH. It is a small project for learning compilers and interpreters.
Second, this is a rough guide, not a full tutorial. I will not explain every detail. I will show you how to get it working. If you want more depth on compilers and interpreters, read Crafting Interpreters.
Finally, the full project is about 480 lines. Most of that defines primitives you could add at runtime, so the core stays small. The extras are nice starting points :)

A language in two parts

Our FORTH implementation has two stages: compile and interpret. In the compile stage, we collect words to run later. In the interpret stage, we run those words.

Start with a file called state.py. This file holds two dataclasses for the two states of our FORTH system.

First, import what you need from the dataclasses module.

from dataclasses import dataclass, field

Then define the two states.

If you do not know dataclasses yet, they are a clean way to make classes that only hold data. They work well for simple classes with no methods. You can read more in the Python docs.

@dataclass
class CompileState:
    tokens: list        = field(default_factory=list)
    codes: list         = field(default_factory=list)
    branchStack: list   = field(default_factory=list)
    variables: dict     = field(default_factory=dict)
    words: dict         = field(default_factory=dict)
    pos: int            = 0
    last_return: int    = 0
    end: bool           = False

@dataclass
class InterpretState:
    codes: list         = field(default_factory=list)
    dataStack: list     = field(default_factory=list)
    branchStack: list   = field(default_factory=list)
    variables: list     = field(default_factory=list)
    pos: int            = 0
    end: bool           = False

We all need a little help

Next, define a few helper functions. Put them in helpers.py.

from typing import List

def tokenize(code:str) -> List[str]:
    tokensOut : List[str] = []
    tokensOut = code.split()
    return tokensOut

def isInt(lexeme:str) -> bool:
        try:
            int(lexeme)
        except ValueError:
            return False
        return True

These two functions split code into tokens and check whether a lexeme is an integer.

Getting primitives

Next, define some primitives. These are the basic building blocks of the language. Put them in primitives.py.

Start by importing what you need.

from __future__ import annotations
from typing import Dict, Callable
from state import InterpretState, CompileState
from getch import getch

getch is a bit special. It lets you read one character without waiting for Enter. It is not in the standard library, so install it with pip install getch.

Next, define a dictionary to hold all primitives. Call it Primitives.

Primitives : Dict[str, Dict[str,function]] = {} #The main export of this file.

Now define two decorators. They let you write primitives with less boilerplate. The first is primitive(). It takes a function, reads the lexeme from the docstring, and adds it to Primitives. The rest of the logic tags which lexemes are compile-only, interpret-only, or both.

def primitive(func) -> None:
    """
    Decorator which automatically adds a primitve word to the Primitives dictionary.
    It creates a default compile-time behavior for the primitive if none is provided.
    Lexemes for the primitives must be provided in the docstring of the function.
    """
    docstring = func.__doc__
    specialCompile : bool = docstring.find(" | (Function Implements Special Compile-Time Behavior)") != -1
    lexeme = docstring[docstring.find("Lexeme: ") + 8:].split()[0].strip()
    funcs = Primitives.get(lexeme, {"compile": None, "execute": None})
    if specialCompile:
        funcs["compile"] = func
    else:
        defaultCompile : Callable[[CompileState], None] = lambda state: state.codes.append(lexeme)
        funcs["compile"] = defaultCompile
        funcs["execute"] = func
    Primitives[lexeme] = funcs
    return func

The second decorator is compileTime(). It adds a marker to the docstring to show special compile-time behavior. Use it for primitives that need custom work at compile time and at run time.

def compileTime(func) -> function:
    """
    Decorator to mark a primitive as having a non-default compile-time behavior.
    """
    func.__doc__ = func.__doc__ + " | (Function Implements Special Compile-Time Behavior)"
    return func

Last in primitives.py, define some primitives. Start with simple ones that need no special compile-time behavior. You can stop early, but I suggest you use all of them so you can see how they work.

Arithmetic and comparisons:

@primitive
def plus(state:InterpretState) -> None:
    """Lexeme: +"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(a + b)
    state.pos += 1

@primitive
def minus(state:InterpretState) -> None:
    """Lexeme: -"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(b - a)
    state.pos += 1

@primitive
def star(state:InterpretState) -> None:
    """Lexeme: *"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(a * b)
    state.pos += 1

@primitive
def slash(state:InterpretState) -> None:
    """Lexeme: /"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(b // a)
    state.pos += 1

@primitive
def mod(state:InterpretState) -> None:
    """Lexeme: MOD"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(b % a)
    state.pos += 1

@primitive
def slashMod(state:InterpretState) -> None:
    """Lexeme: /MOD"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(b % a)
    state.dataStack.append(b // a)
    state.pos += 1

@primitive
def lessThan(state:InterpretState) -> None:
    """Lexeme: <"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    if a < b:
        state.dataStack.append(-1)
    else:
        state.dataStack.append(0)
    state.pos += 1

@primitive
def greaterThan(state:InterpretState) -> None:
    """Lexeme: >"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    if a > b:
        state.dataStack.append(-1)
    else:
        state.dataStack.append(0)
    state.pos += 1

@primitive
def equal(state:InterpretState) -> None:
    """Lexeme: ="""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    if a == b:
        state.dataStack.append(-1)
    else:
        state.dataStack.append(0)
    state.pos += 1

Bitwise operations:

@primitive
def bitwiseAnd(state:InterpretState) -> None:
    """Lexeme: AND"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(a & b)
    state.pos += 1

@primitive
def bitwiseOr(state:InterpretState) -> None:
    """Lexeme: OR"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(a | b)
    state.pos += 1

@primitive
def bitwiseNot(state:InterpretState) -> None:
    """Lexeme: INVERT"""
    a = state.dataStack.pop()
    state.dataStack.append(~a)
    state.pos += 1

Stack manipulation:

@primitive
def swap(state:InterpretState) -> None:
    """Lexeme: SWAP"""
    a, b = state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(a)
    state.dataStack.append(b)
    state.pos += 1

@primitive
def dup(state:InterpretState) -> None:
    """Lexeme: DUP"""
    a = state.dataStack.pop()
    state.dataStack.append(a)
    state.dataStack.append(a)
    state.pos += 1

@primitive
def drop(state:InterpretState) -> None:
    """Lexeme: DROP"""
    state.dataStack.pop()
    state.pos += 1

@primitive
def over(state:InterpretState) -> None:
    """Lexeme: OVER"""
    state.dataStack.append(state.dataStack[-2])
    state.pos += 1

@primitive
def rot(state:InterpretState) -> None:
    """Lexeme: ROT
    ( n1 n2 n3 -- n2 n3 n1 )
    """
    a, b, c = state.dataStack.pop(), state.dataStack.pop(), state.dataStack.pop()
    state.dataStack.append(b)
    state.dataStack.append(a)
    state.dataStack.append(c)
    state.pos += 1

Input and output:

@primitive
def key(state:InterpretState) -> None:
    """Lexeme: KEY"""
    keypress = getch()
    state.dataStack.append(ord(keypress))
    state.pos += 1

@primitive
def period(state:InterpretState) -> None:
    """Lexeme: ."""
    print(state.dataStack.pop(), end='\n')
    state.pos += 1

@primitive
def emit(state:InterpretState) -> None:
    """Lexeme: EMIT"""
    print(chr(state.dataStack.pop()))
    state.pos += 1

@primitive
def cr(state:InterpretState) -> None:
    """Lexeme: CR"""
    print()
    state.pos += 1

Compile-time words for definitions, branches, and loops:

@primitive
@compileTime
def colon(state:CompileState) -> None:
    """Lexeme: :"""
    word = state.tokens[state.pos+1]
    state.words[word] = len(state.codes)
    state.pos += 1

@primitive
@compileTime
def semicolon(state:CompileState) -> None:
    """Lexeme: ;"""
    state.codes.append(";")
    state.last_return = len(state.codes)

@primitive
@compileTime
def prim_if(state:CompileState) -> None:
    """Lexeme: IF"""
    state.branchStack.append(len(state.codes) + 1)
    state.codes.extend(("IF", None))

@primitive
@compileTime
def prim_else(state:CompileState) -> None:
    """Lexeme: ELSE"""
    ifPos = state.branchStack.pop()
    state.codes[ifPos] = len(state.codes) + 2
    state.branchStack.append(len(state.codes) + 1)
    state.codes.extend(("ELSE", None))

@primitive
@compileTime
def prim_then(state:CompileState) -> None:
    """Lexeme: THEN"""
    elsePos = state.branchStack.pop()
    state.codes[elsePos] = len(state.codes)

@primitive
@compileTime
def do(state:CompileState) -> None:
    """Lexeme: DO"""
    state.branchStack.append(len(state.codes) + 1)
    state.codes.append("DO")

@primitive
@compileTime
def loop(state:CompileState) -> None:
    """Lexeme: LOOP"""
    doPos = state.branchStack.pop()
    state.codes.extend(("LOOP", doPos))

(For brevity, a few interpret-time twins of the branching words are omitted here. The full runnable set lives on GitHub.)

Interpreter

The interpreter itself is small. It is a loop that runs until the program ends. For each token, it looks up the word in the primitives dictionary and calls that function. If the token is not in the dictionary, treat it as a number and push it onto the data stack.

There is more here for variables and calling "functions", but again, this is not a tutorial.

from state import InterpretState, CompileState
from primitives import Primitives
from helpers import isInt

class Interpreter:
    def __init__(self):
        self.compileState = CompileState()
        self.interpretState = InterpretState()

    def run(self, tokens): self.compile(self.compileState, tokens)

    def compile(self, state:CompileState, tokens):
        state.tokens.extend(tokens)
        if state.codes:
            state.codes.pop()
        state.end = False

        while not state.end:
            if state.pos == len(state.tokens):
                state.codes.append('END')
                state.end = True
                break

            token = state.tokens[state.pos]
            if isInt(token):
                state.codes.extend(('PUSH', int(token)))
            elif token in Primitives:
                Primitives[token]['compile'](state)
            elif token in state.variables:
                state.codes.extend(('PUSH', state.variables[token]))
            elif token in state.words:
                state.codes.extend(('CALL', state.words[token]))
            else:
                print('Unknown word:', token)
            state.pos += 1
        self.interpret(self.interpretState, state.codes, len(state.variables), state.last_return)

    def interpret(self, state: InterpretState, codes, var_count, start):
        state.codes = codes
        state.variables.extend([0] * (var_count - len(state.variables)))
        state.pos = max(start, state.pos)
        state.end = False

        while not state.end:
            code = state.codes[state.pos]
            Primitives[code]['execute'](state)
            # PUSH, CALL, and variable handling omitted — see the repo

Making it interactive

The interpreter is ready to use. I added a simple REPL so you can try it. It is not fancy, but it is short and it works.

Add this code to a file called pyforth.py:

#! /usr/local/bin/python3
import helpers, interpreter, argparse, readline # Readline magically makes input history work.

# Get command line arguments.
parser = argparse.ArgumentParser(description='Forth Interpreter')
parser.add_argument('file', nargs='?', type=argparse.FileType('r'))
args = parser.parse_args()

# Decide if we're reading from a file or stdin.
if not bool(args.file):
    forth = interpreter.Interpreter()
    while True:
        try: line = input('> ')
        except (EOFError, KeyboardInterrupt): break
        forth.run(helpers.tokenize(line))
else:
    forth = interpreter.Interpreter()
    forth.run(helpers.tokenize(args.file.read()))

Woo! It's done!

Set the shebang at the top to your Python path. Then run ./pyforth.py and you should be good to go!