Building an Interpreter

The REPL is the interactive loop that wraps every interpreter: it Reads a textual expression from the user, Evaluates it to produce a value, Prints that value, then Loops back. This pattern is so universal that Python, Node.js, IRB (Ruby), GHCi (Haskell), and Clojure all implement it.

The three phases are cleanly separated:

1. Read — a parser (or reader in Lisp tradition) converts the raw string into an abstract syntax tree (AST), a data structure the evaluator can traverse. In Lisp, this step is trivial because S-expressions already look like tree structure: (+ (* 2 3) 4) is literally a nested list.
2. Eval — the heart of the interpreter. Takes an AST node and an environment, returns a value.
3. Print — converts the returned value back to a string for display.

The separation matters: you can swap out the reader (to parse a different syntax), swap the evaluator (to give different semantics), or swap the printer (to display values differently). The REPL is a composable pipeline, not a monolith.

# Minimal REPL skeleton in Python
def repl():
    env = make_global_env()
    while True:
        try:
            src = input("scheme> ")
            tokens = tokenize(src)      # Read: string -> tokens
            ast   = parse(tokens)        # Read: tokens -> AST
            val   = scheme_eval(ast, env) # Eval: AST -> value
            print(scheme_repr(val))       # Print: value -> string
        except SchemeError as e:
            print(f"Error: {e}")

Before we can evaluate, we must read the program. A lexer (tokenizer) breaks the raw character stream into tokens — the atoms of the language (numbers, symbols, parentheses, strings). A parser then assembles those tokens into an Abstract Syntax Tree (AST), the structured internal representation the evaluator will walk.

In Lisp/Scheme this step is famously simple because the programmer writes S-expressions — the concrete syntax is already a tree. (+ (* 2 3) 4) tokenizes to [( + ( * 2 3 ) 4 )] and parses to the nested list ['+', ['*', 2, 3], 4]. In Python we represent this as actual Python lists.

For other languages the parser is more complex (operator precedence, infix notation, etc.) but the output is always an AST. The evaluator does not see strings; it sees trees. This is crucial: it means eval can simply dispatch on the type of the root node.

Self-evaluating expressions — numbers, booleans, strings — are leaves that evaluate to themselves. Symbols are variables whose values must be looked up in the environment. Lists are compound expressions: their car (first element) determines what kind of form they are.

def tokenize(src: str) -> list[str]:
    # Add spaces around parens so split() isolates them
    return src.replace('(', ' ( ').replace(')', ' ) ').split()

def parse(tokens: list[str]):
    """Recursive-descent parser. Returns nested Python lists."""
    if not tokens:
        raise SyntaxError("Unexpected EOF")
    tok = tokens.pop(0)
    if tok == '(':
        lst = []
        while tokens[0] != ')':
            lst.append(parse(tokens))
        tokens.pop(0)  # discard ')'
        return lst
    elif tok == ')':
        raise SyntaxError("Unexpected )")
    else:
        return atomize(tok)

def atomize(tok: str):
    try: return int(tok)
    except ValueError: pass
    try: return float(tok)
    except ValueError: pass
    return tok  # symbol (string)

An environment is a mapping from names (symbols) to values. But a single flat dictionary is not enough — we also need scope: let bindings, function parameters, and closures each create a new, local scope that should not clobber the outer one.

The solution is a linked chain of frames. Each frame holds its local bindings; if a name is not found locally, the lookup continues in the enclosing frame. This chain terminates at the global environment containing built-in definitions (+, car, cons, etc.).

This model directly implements lexical (static) scope: the meaning of a variable is determined by where it appears in the source code, not where the function was called from. When a function is defined with lambda, the new closure captures a pointer to the environment at definition time, not the current call stack. This is why closures work: the captured environment is still alive even after the outer function returns.

Lookup walks up the chain. Binding (via define or function call) adds a new entry to the current frame. Mutation (via set!) walks up until it finds the frame that owns the variable, then updates it in place.

class Environment:
    def __init__(self, params=(), args=(), outer=None):
        self.frame = dict(zip(params, args))
        self.outer = outer  # enclosing environment

    def lookup(self, name):
        if name in self.frame:
            return self.frame[name]
        if self.outer is not None:
            return self.outer.lookup(name)
        raise NameError(f"Unbound variable: {name}")

    def define(self, name, value):
        self.frame[name] = value   # always in current frame

    def set_bang(self, name, value):
        if name in self.frame:
            self.frame[name] = value
        elif self.outer:
            self.outer.set_bang(name, value)
        else:
            raise NameError(f"set! unbound variable: {name}")

eval is the core of the evaluator. Given an expression (an AST node) and an environment, it returns a value. The key insight is that every expression has a type, and eval dispatches on that type:

The key design principle: if, define, lambda, and quote are special forms — the interpreter handles them directly and does not evaluate all subexpressions eagerly. Everything else is a procedure application: evaluate the operator and all operands, then call apply.

This split between special forms and applications is fundamental to the theory of programming languages.

def scheme_eval(expr, env):
    # Self-evaluating
    if isinstance(expr, (int, float, bool)):
        return expr
    # Variable lookup
    if isinstance(expr, str):
        return env.lookup(expr)
    # Compound expressions (lists)
    if not isinstance(expr, list) or len(expr) == 0:
        raise SchemeError(f"Bad expression: {expr}")

    head = expr[0]
    if head == 'quote':
        return expr[1]
    elif head == 'if':
        _, cond, consequent, *alt = expr
        branch = consequent if scheme_eval(cond, env) else (alt[0] if alt else None)
        return scheme_eval(branch, env)
    elif head == 'define':
        _, name, val_expr = expr
        env.define(name, scheme_eval(val_expr, env))
    elif head == 'lambda':
        _, params, body = expr
        return Closure(params, body, env)  # captures env!
    elif head == 'begin':
        result = None
        for sub in expr[1:]:
            result = scheme_eval(sub, env)
        return result
    elif head == 'set!':
        _, name, val_expr = expr
        env.set_bang(name, scheme_eval(val_expr, env))
    else:
        # Application: eval operator and operands
        proc = scheme_eval(head, env)
        args = [scheme_eval(a, env) for a in expr[1:]]
        return scheme_apply(proc, args)

A closure is a function value that closes over (captures) the environment in which it was defined. It bundles together:

1. The formal parameters — the names the function expects.
2. The body — the expression to evaluate.
3. The defining environment — the lexical scope at creation time.

When lambda is evaluated, no computation happens. The interpreter simply packages these three pieces together and returns a closure object. The magic happens at call time, in apply.

Why does this implement lexical scope? Because when we call the closure, we create a new environment whose outer pointer is the captured defining environment, not the calling environment. Free variables in the body resolve through this chain back to where the function was written, not where it was called.

This model explains: counter closures (each call to make-counter returns a closure with its own private n), mutual recursion (via letrec/define in the same environment), and the fact that define at the top level creates persistent global bindings while let creates ephemeral local ones.

class Closure:
    def __init__(self, params, body, defining_env):
        self.params = params           # e.g. ['x', 'y']
        self.body = body               # AST of the body
        self.env = defining_env        # captured at lambda time

# A factory that returns a closure:
# (define (make-adder n) (lambda (x) (+ x n)))
# (define add5 (make-adder 5))
# (add5 3)  => 8
#
# When (make-adder 5) is called:
#   - a new frame {n: 5} is created with outer=global
#   - (lambda (x) (+ x n)) is evaluated in THAT frame
#   - the closure captures the frame containing n=5
# When (add5 3) is called:
#   - a new frame {x: 3} is created with outer=closure.env
#   - evaluating (+ x n): x=3 from local, n=5 from captured frame
#   - result: 8

apply is the counterpart to eval. Where eval takes an expression and produces a value, apply takes a procedure and a list of already-evaluated argument values, and produces the result.

For primitive procedures (built-ins like +, car, cons), apply just delegates to the underlying host-language function. For compound procedures (closures created by lambda), apply does the following:

1. Create a new environment frame that binds each parameter to the corresponding argument.
2. Set the outer pointer of this frame to the closure's captured environment.
3. Evaluate the body expression in this new environment.

Steps 1-2 are the environment-passing mechanism that implements both parameter passing and lexical scope simultaneously.

The mutual recursion between eval and apply is the most important structural insight of this module. eval calls apply when it sees an application. apply calls eval when it evaluates a closure's body. This ping-pong terminates because each cycle descends into a strictly smaller subexpression of the original program.

def scheme_apply(proc, args):
    if isinstance(proc, Primitive):  # e.g. Primitive(lambda a,b: a+b)
        return proc.fn(*args)
    elif isinstance(proc, Closure):
        # Bind parameters to argument values in a new frame
        if len(proc.params) != len(args):
            raise SchemeError(
                f"Expected {len(proc.params)} args, got {len(args)}")
        # New frame whose outer is the closure's defining env
        new_env = Environment(proc.params, args, outer=proc.env)
        return scheme_eval(proc.body, new_env)  # back to eval!
    else:
        raise SchemeError(f"Not a procedure: {proc}")

The metacircular evaluator (MCE) is the same eval/apply pair, but written in Scheme (or Lisp) to evaluate Scheme. It is called metacircular because the implementation language is the same as the language being implemented.

At first this seems circular and useless: to run Scheme you need Scheme. But the MCE is not meant to bootstrap from nothing — it runs on top of a pre-existing Scheme implementation. Its value is clarity and insight: the MCE is a formal, executable specification of what Scheme programs mean. It is much shorter and clearer than a C implementation of the same semantics.

The MCE reveals something profound: the meaning of every Scheme program is defined by this one short program. If you want to add a new feature — lazy evaluation, new special forms, call/cc — you modify the MCE, not a thousand lines of C. This is the foundation of language-oriented programming.

SICP presents the MCE in Chapter 4. The key procedures are eval, apply, eval-sequence, eval-if, and make-procedure. The environment is a list of frames, each frame a list of (name . value) pairs — a purely functional representation unlike our mutable Python class above, but semantically identical.

;; Simplified MCE in Scheme (as in SICP Ch.4)
(define (my-eval expr env)
  (cond ((self-evaluating? expr) expr)
        ((variable? expr) (lookup-variable expr env))
        ((quoted? expr) (cadr expr))
        ((if? expr) (eval-if expr env))
        ((lambda? expr)
         (make-procedure (lambda-params expr)
                         (lambda-body expr)
                         env))       ; capture env!
        ((begin? expr) (eval-sequence (begin-actions expr) env))
        ((application? expr)
         (my-apply (my-eval (operator expr) env)
                   (list-of-values (operands expr) env)))
        (else (error "Unknown expr" expr))))

(define (my-apply proc args)
  (cond ((primitive-procedure? proc)
         (apply-primitive proc args))
        ((compound-procedure? proc)
         (eval-sequence
           (procedure-body proc)
           (extend-environment
             (procedure-params proc)
             args
             (procedure-env proc))))
        (else (error "Unknown proc" proc))))

A naive recursive eval blows the host-language call stack on deeply recursive Scheme programs. In standard Scheme, tail calls must not grow the stack (R7RS mandates this). This means a Scheme program that tail-recurses ten million times must use O(1) stack space.

The problem: when eval calls itself for the if branch, that call is in tail position — there is nothing for the outer eval to do after it. But Python does not optimize tail calls, so we stack up Python frames.

The solution is trampolining: instead of calling eval recursively in tail position, return a thunk (a deferred computation), and have the outer REPL loop call it. This converts recursive calls into an iterative loop:

while expr is a thunk: expr = expr()

A cleaner Pythonic approach is to convert eval into an iterative loop using an explicit while True that reassigns expr and env for tail positions instead of recursing. This is exactly how production interpreters handle TCO without a trampoline.

def scheme_eval(expr, env):
    """Iterative eval with TCO via 'tail position' loop."""
    while True:
        if isinstance(expr, (int, float, bool)):
            return expr
        if isinstance(expr, str):
            return env.lookup(expr)
        head = expr[0]
        if head == 'if':
            _, cond, consequent, *alt = expr
            # Tail call: don't recurse, just reassign
            expr = consequent if scheme_eval(cond, env) \
                   else (alt[0] if alt else None)
            continue    # loop, no new Python stack frame
        elif head == 'begin':
            for sub in expr[1:-1]:
                scheme_eval(sub, env)  # non-tail: ok to recurse
            expr = expr[-1]            # last expr is tail
            continue
        elif head == 'lambda':
            _, params, body = expr
            return Closure(params, body, env)
        else:
            proc = scheme_eval(head, env)
            args = [scheme_eval(a, env) for a in expr[1:]]
            if isinstance(proc, Closure):
                # Tail call into closure body
                env = Environment(proc.params, args, proc.env)
                expr = proc.body
                continue   # loop!
            return scheme_apply(proc, args)

Not every language construct needs to be a primitive in the evaluator. Many can be reduced (desugared) to simpler primitives before or during evaluation. These are called derived expressions or syntactic sugar.

Examples:

• (and e1 e2) ≡ (if e1 e2 #f) — and is not primitive; eval can transform it.
• (or e1 e2) ≡ (let ((t e1)) (if t t e2)) — note: e1 is evaluated only once.
• (cond ((c1 e1) (c2 e2) (else e3))) ≡ a nested if.
• (let ((x e1) (y e2)) body) ≡ ((lambda (x y) body) e1 e2) — let is literally just an immediately applied lambda!
• (when c body) ≡ (if c (begin body) (void)).

This is powerful: by adding syntax transformations (macros), you can extend the language without touching the evaluator. Scheme's define-syntax / syntax-rules and Common Lisp's defmacro are both systems for writing such transformations in the language itself. The line between built-in and user-defined forms dissolves.

;; let is syntactic sugar for lambda application
;; The interpreter can desugar before eval:
;; (let ((x 3) (y 4)) (+ x y))
;; =>  ((lambda (x y) (+ x y)) 3 4)

(define (let->lambda expr)
  (let ((bindings (cadr expr))
        (body     (cddr expr)))
    (cons (list 'lambda
                (map car bindings)   ; parameter names
                (cons 'begin body))  ; body as begin
          (map cadr bindings))))     ; argument exprs

;; In eval, add before application:
;; ((let? expr) (my-eval (let->lambda expr) env))

Standard Scheme (and Python, Java, C) use applicative-order evaluation: arguments are evaluated before being passed to a function. This is also called call-by-value.

Lazy evaluation (or normal-order / call-by-need) delays the evaluation of arguments until they are actually used. Haskell is the famous example. Lazy evaluation has two remarkable consequences:

1. You can work with infinite data structures (like an infinite list of prime numbers) without evaluating them fully.
2. A function argument that is never used is never evaluated, avoiding potential errors or infinite loops.

SICP Chapter 4.2 shows how to build a lazy evaluator by modifying apply: instead of evaluating arguments eagerly, wrap them in thunks (closures that hold the unevaluated expression and its environment). When the value is actually needed, force the thunk. The first force memoizes the result so it is not recomputed (this is call-by-need, distinguishing Haskell from call-by-name).

This modification is localized to apply — which shows how cleanly the MCE framework allows experimentation with evaluation strategy.

# Lazy evaluation: wrap argument in a thunk
class Thunk:
    def __init__(self, expr, env):
        self.expr = expr
        self.env = env
        self._forced = False
        self._value = None

def force(obj):
    """Force a thunk, memoizing the result."""
    if isinstance(obj, Thunk):
        if not obj._forced:
            obj._value = scheme_eval(obj.expr, obj.env)
            obj._forced = True
        return obj._value
    return obj  # already a value

def lazy_apply(proc, arg_exprs, calling_env):
    """Pass thunks instead of evaluated args."""
    if isinstance(proc, Closure):
        thunks = [Thunk(e, calling_env) for e in arg_exprs]
        new_env = Environment(proc.params, thunks, proc.env)
        return scheme_eval(proc.body, new_env)
    # ... primitives still force their args

The environment representation is a design choice with real trade-offs.

Mutable frame approach (our Python class): each frame is a mutable dict; define adds a key; set! walks up mutating in place. Simple and fast.

Functional (persistent) approach (SICP style): frames are association lists (((x . 3) (y . 4))); extend-environment prepends a new frame to the list without mutating old frames. Enables backtracking evaluators and time-travel debugging (just keep old env references).

Display-environment approach: some evaluators (like MIT Scheme) print environments as nested boxes, making the frame chain visually inspectable — great for teaching.

An important point: the environment is not just a lookup table. It is the model of memory for the program. Mutation (set!, set-car!) is modification of the environment (or heap objects within it). Garbage collection in a Scheme runtime reclaims environment frames (and heap cells) that are no longer reachable from any live closure or the current evaluation. Understanding environments gives you a complete model of object identity and mutation.

;; SICP-style functional environment (association lists)
(define (make-frame vars vals) (map cons vars vals))

(define (extend-env vars vals base-env)
  (cons (make-frame vars vals) base-env))

(define (lookup-var var env)
  (if (null? env)
      (error "Unbound variable" var)
      (let ((binding (assoc var (car env))))
        (if binding
            (cdr binding)
            (lookup-var var (cdr env))))))

;; Usage:
;; global-env = '(((+ . <prim+>) (- . <prim->) ...))
;; after (define x 5):
;; global-env = '(((x . 5) (+ . <prim+>) ...))
;; after (lambda (y) ...) called with 3:
;; call-env = '(((y . 3)) ((x . 5) (+ . <prim+>) ...))

One of the great advantages of building your own interpreter is the ability to experiment with language features. The MCE framework makes it easy to add new special forms.

Adding while: Add a clause to eval that detects (while condition body...) and evaluates the body repeatedly as long as the condition is true. This is 5 lines in Python.

Adding define-record: Parse the record definition, generate make-*, *-ref, and *-set! procedures, and install them in the environment.

Hygienic macros (define-syntax / syntax-rules): Rather than evaluating the arguments, a macro transformer receives the unevaluated syntax and returns a new syntax tree to be evaluated. Adding macro expansion as a phase between read and eval (or inside eval before dispatch) gives you full Scheme macros.

The key lesson: the evaluator is programmable. You are not stuck with the language you start with. This is the root of Lisp's legendary extensibility and is why Paul Graham called Lisp's macros the feature that "other languages are still catching up to."

;; Adding a 'while' special form to our Python interpreter:
# In scheme_eval, add before the application case:
elif head == 'while':
    _, cond_expr, *body_exprs = expr
    result = None
    while scheme_eval(cond_expr, env):
        for b in body_exprs:
            result = scheme_eval(b, env)
    return result

# Usage:
# (define i 0)
# (define sum 0)
# (while (< i 5)
#   (set! sum (+ sum i))
#   (set! i (+ i 1)))
# sum  => 10