⇦

2022-04-29

Smol interpreter

The smallest readable interpreter I could come up with that handles integers, assignments, lexical scope, first class functions.

class Symbol(str): ...
Node = int | Symbol | list["Node"]

def is_whitespace(c: str) -> bool: return c in " \n"
def is_number(c: str) -> bool: return c.isdigit()
def is_symbol(c: str) -> bool: return c not in " \n()"

i = 0
def parse(source: str) -> Node:
    global i
    def gobble(f: Callable[[str], bool]) -> str:
        global i
        value = ""
        while f(source[i]):
            value += source[i]
            i += 1
        return value

    gobble(is_whitespace)
    if is_number(source[i]):
        return int(gobble(is_number))
    if is_symbol(source[i]):
        return Symbol(gobble(is_symbol))
    if source[i] == "(":
        i += 1  # gobble (
        items = []
        while source[i] != ")":
            items.append(parse(source))
            gobble(is_whitespace)
        i += 1  # gobble )
        return items
    raise RuntimeError("Unknown character")

from typing import Callable
Value = int | Callable[..., int]
Scope = dict[Symbol, Value]

def block(scope: Scope, *nodes: Node) -> Value:
    local_scope = scope.copy()
    values = [interpret(local_scope, child) for child in nodes]
    return values[-1]  # blocks evaluate to the final value

def assign(scope: Scope, *nodes: Node) -> Value:
    symbol, node = nodes
    value = interpret(scope, node)
    scope[symbol] = value
    return value

def function(scope: Scope, *nodes: Node) -> Value:
    local_scope = scope.copy()
    *vars, node = nodes
    return lambda *args: interpret(local_scope | dict(zip(vars, args)), node)

macros = {
    Symbol("{"): block,
    Symbol("="): assign,
    Symbol("=>"): function,
}
builtins = {
    Symbol("print"): lambda *args: print(*args),
    Symbol("-"): lambda a: -a,
    Symbol("*"): lambda a, b: a * b,
    Symbol("+"): lambda a, b: a + b,
}

def interpret(scope: Scope, node: Node) -> Value:
    if isinstance(node, int):
        return node
    if isinstance(node, Symbol):
        return scope[node]
    f, *args = node
    if f in macros:
        return macros[f](scope, *args)
    f, *args = [interpret(scope, child) for child in node]
    return f(*args)

Let's run it:

source = """
({
    (= make-adder
        (=> a (=> b (+ a b))))
    (= add-one (make-adder 1))
    (print (add-one 3))

    (= x 5)
    (= f
        (=> a b ({
            (= c (+ a b))
            (* (- c) x)
        ))
    )
    (print (f 1 3))
)
"""
interpret(builtins, parse(source))

Should give you:

4
-20

Heads up - the typing is a bit all over the shop and doesn't actually typecheck..