Build a Tree-Walk Interpreter

Learning Objectives

Define a small language's feature set, lexical rules and grammar, and implement its lexer, parser and AST.

Implement expression evaluation and statement execution with environments, declarations, assignment, arithmetic, comparison, Boolean logic with short-circuiting, printing, blocks and nested scopes.

Define runtime type checks, truthiness, equality and numeric conversion rules; report runtime errors with source locations; recover in an interactive shell; test and debug the interpreter; plan for functions and extensions.

Plain-Language Explanation

A tree-walk interpreter is a function that looks at an AST node and does what it says: for a number node it returns the number; for an addition node it evaluates both sides and adds them; for a print node it evaluates the expression and prints it. Variables live in an environment — a table from names to values — and each block gets its own table linked to the one outside it.

Precise Technical Explanation

Define the language feature set Start with the specification's initial subset: let, print, arithmetic, comparison, equality, unary operators, literals, variables and grouping. Later add assignment, blocks, if, while, functions and closures. Writing the feature list first prevents accidental semantics.

Design lexical rules Identifiers, numbers, strings with escapes, operators, // comments — exactly as in Module 3.

Implement the lexer A handwritten scanner producing tokens with spans (Module 3's tokenize).

Define the grammar The initial grammar from the specification:

Each production is one parser function. Precedence follows the layering (equality lowest, unary highest); all binary operators are left-associative; unary operators are right-associative (!!x).

Implement the parser Recursive descent with panic-mode recovery (Module 4).

Define AST classes or tagged unions One node type per production that carries meaning (Module 5).

Implement expression evaluation evaluate(node, env) switches on the node kind and returns a value. The specification's illustrative version:

This is illustrative pseudocode using Python syntax; a real implementation needs operator validation, source-aware errors and short-circuit handling for logical operators — as the complete interpreter below has.

Implement statement execution execute(stmt, env) performs effects and returns nothing: Let defines, Print prints, Expression evaluates and discards.

Environment and variable lookup An environment maps names to values and points to its enclosing environment; lookup walks outwards and fails with "Undefined variable" at the global end.

Variable declaration and assignment Declaration creates a binding in the *current* environment; assignment updates the *nearest existing* binding (and fails if there is none — MiniLang does not create globals implicitly).

Arithmetic and comparison operators Apply only to numbers (and + to two strings); anything else is a runtime type error.

Boolean logic and short-circuit evaluation a and b does not evaluate b when a is falsy; a or b does not evaluate b when a is truthy. The result is one of the operand values, not necessarily a Boolean (nil or "default" is "default").

Print/output statements Convert a value to text with defined formatting (integers without .0), then write it.

Blocks and nested scopes Executing a Block creates a new environment whose parent is the current one, runs the statements, and restores the previous environment even if an error occurs (try/finally).

Runtime type checking Every operator checks its operands' runtime types before acting.

Runtime errors and source locations Errors carry the node's span: Runtime error [line 1:9]: Operands of '+' must be two numbers or two strings (got number and string).

MiniLang: nil and false are falsy, everything else truthy. (Python and JavaScript also treat 0 and "" as falsy — a deliberate difference to discuss.)

Same type and value; no conversion; functions compare by identity.

Numeric conversion rules None: MiniLang never converts strings to numbers implicitly; str(x) converts explicitly to a string.

Error recovery in an interactive shell A REPL catches each error, reports it, keeps the global environment, and reads the next line.

Testing and debugging the interpreter Golden tests of programs and outputs, error tests, and — once a second back end exists — differential tests (this course runs every MiniLang program on both back ends).

Add functions in later modules Functions need call frames (environments per call), return (non-local exit), arity checks and closures (Modules 11–12).

Design limitations and extensibility A tree-walker is slow on deep recursion and allocates environments as hash maps; but it is the clearest specification of semantics and a reference for testing faster back ends.

Language example Expected output: 32. Trace: lexer → parser → AST → environment lookup → evaluation → output (below).

program        = { statement } ;
statement      = letDecl | printStmt | expressionStmt ;
letDecl        = "let", IDENTIFIER, "=", expression, ";" ;
printStmt      = "print", "(", expression, ")", ";" ;
expressionStmt = expression, ";" ;
expression     = equality ;
equality       = comparison, { ("==" | "!="), comparison } ;
comparison     = term, { (">" | ">=" | "<" | "<="), term } ;
term           = factor, { ("+" | "-"), factor } ;
factor         = unary, { ("*" | "/"), unary } ;
unary          = ("!" | "-"), unary | primary ;
primary        = NUMBER | STRING | "true" | "false" | "nil" | IDENTIFIER | "(", expression, ")" ;

def evaluate(node, environment):
    if node.kind == "number":
        return node.value
    if node.kind == "binary":
        left = evaluate(node.left, environment)
        right = evaluate(node.right, environment)
        return apply_operator(node.operator, left, right)
    raise RuntimeError(f"Unsupported expression: {node.kind}")

let x = 10;
let y = x * 3 + 2;
print(y);

Why It Matters in Real Systems

Many configuration, rule and template languages are tree-walk interpreters; and every serious language implementation keeps a simple reference evaluator for testing.

Key Terms

Mapping from names to values with a parent link Evaluate / execute

Produce a value from an expression / perform a statement Skipping the right operand when the left decides

Which values count as true in conditions

Syntax or Instruction Format

MiniLang source (grammar above); the interpreter's API is interpret(source) → { output, error }.

Complete Example

A complete tree-walk interpreter for the specification's initial MiniLang subset, independent of the course implementation (CPython 3.13.1). It includes a lexer, a recursive-descent parser, runtime type checks, short-circuit-free core operators and errors with positions:

The course's MiniLang interpreter on the same program, showing each environment change and lookup (treetrace mode):

Short-circuit evaluation, blocks and runtime errors with positions (both back ends):

import re

TOKEN = re.compile(r"\s*(?:(\d+(?:\.\d+)?)|(\"[^\"]*\")|([A-Za-z_]\w*)|(==|!=|>=|<=|[-+*/()<>=!;]))")


def lex(src):
    pos, out = 0, []
    while pos < len(src):
        if src[pos:].strip() == "":
            break
        m = TOKEN.match(src, pos)
        if not m:
            raise SyntaxError(f"unexpected character {src[pos]!r} at offset {pos}")
        num, string, name, op = m.groups()
        if num:
            out.append(("num", float(num)))
        elif string:
            out.append(("str", string[1:-1]))
        elif name:
            out.append(("kw", name) if name in ("let", "print", "true", "false", "nil") else ("name", name))
        else:
            out.append(("op", op))
        pos = m.end()
    return out + [("eof", None)]


class Parser:
    def __init__(self, tokens):
        self.t, self.i = tokens, 0

    def peek(self):
        return self.t[self.i]

    def take(self, kind=None, value=None):
        tok = self.t[self.i]
        if (kind and tok[0] != kind) or (value and tok[1] != value):
            raise SyntaxError(f"expected {value or kind}, found {tok[1]!r}")
        self.i += 1
        return tok

    def program(self):
        stmts = 
…

['32']
['concat', 'true', 'true']
["RuntimeError: Operands of '+' must be numbers."]
['RuntimeError: Division by zero.']
["SyntaxError: expected name, found '='"]

let x = 10;
let y = x * 3 + 2;
print(y);

define  define x = 10 in global scope   env: global{x=10}
lookup  look up 'x' → 10
define  define y = 32 in global scope   env: global{x=10, y=32}
lookup  look up 'y' → 32
print   print → 32

let name = nil;
print(name or "anonymous");
print(false and undefinedName);     // right side never evaluated
{
  let name = "inner";
  print(name);
}
print(name == nil);
print("total: " + 3);

anonymous
false
inner
true
Runtime error [line 9:7]: Operands of '+' must be two numbers or two strings (got string and number).

Line-by-Line Explanation

Python interpreter: lex uses one regex with groups per token class; the parser's binary helper builds left-associative chains; evaluate checks runtime types before every operator and keeps == type-strict; run catches errors per program, like a REPL does per line.

Trace: define lines show the global environment growing; lookup shows x read during x * 3 + 2.

Semantics: or returns its right operand's value; false and undefinedName never touches the undefined name; the block's name shadows the global only inside the block; the last line fails at run time, and the error points at the start of the failing + expression (line 9, column 7).

Expected Output

32 for the specification example; the rest as shown.

Step-by-Step Runtime Behavior

let y = x * 3 + 2; → evaluate Binary(+) → evaluate Binary(*) → look up x (10) → literal 3 → 30 → literal 2 → 32 → bind y = 32 in the global environment.

Common Misconceptions

"and/or return Booleans." In MiniLang, Python and JavaScript they return an operand value.

"Blocks copy the environment." They link to it; assignments to outer variables are visible after the block.

Common Bugs and Failure Modes

Evaluating both operands of and/or; restoring the environment only on success (leaking scopes after an error); implicit global creation on assignment typos; comparing values with host-language equality that converts types.

Corrected or Safer Patterns

Use try/finally when switching environments; make assignment to undeclared names an error; implement equality explicitly.

Debugging and Inspection Techniques

Trace mode (as above), AST dumps, a REPL that prints values, and breakpoints on AST nodes (the interpreter tracer visualizer).

Performance Considerations

Each variable access walks the environment chain with hash lookups; each node dispatch is a branch. Module 7 resolves locals to indices; Modules 8–9 replace the tree with bytecode.

Security Considerations

Interpreters of untrusted code need step budgets (MiniLang: 100,000 steps), recursion limits and no access to host functions beyond an allow-list.

Portability and Version Caveats

The interpreter's semantics are what you define — write them down (as the MiniLang semantics table does) instead of inheriting the host language's quirks (Python's 0 == False is True; MiniLang's is false).

Real-World Use Cases

Template languages, rule engines, configuration DSLs, query filters, calculators, educational languages.

Best Practices

Specify semantics first, check types explicitly, attach spans to errors, keep a reference interpreter for differential testing.

Exercises

E1 · Beginner. Predict MiniLang's output: print(0 or 5); print(nil or 0);

Answer: 0 then 0 — 0 is truthy in MiniLang, so 0 or 5 returns 0; nil or 0 returns 0.

E2 · Intermediate. Add the % (remainder) operator to the Python interpreter.

Answer: Add % to the factor operator tuple, and in evaluate add "%": math.fmod(left, right) (or Python's %, whose sign follows the divisor — choose and document one), raising "Division by zero" for a zero divisor.

E3 · Advanced challenge. Make the Python interpreter report runtime errors with line and column.

Answer: Make the lexer record each token's offset and compute line/column; store the operator token's position in each binary/unary node; raise RuntimeError with that position and format it as [line L:C].

Quiz

? What does `print(false and undefinedName);` do in MiniLang?
+ Prints false without evaluating undefinedName. :: `and` short-circuits on a falsy left operand.
- Raises "Undefined variable". :: The right operand is never evaluated.
- Prints nil. :: The result is the left operand, false.
- Is a syntax error. :: It is valid syntax.

? Where does `let` inside a block create its variable?
+ In the block's new environment. :: It is gone after the block.
- In the global environment. :: Only top-level lets are global.
- In the enclosing function's environment. :: Blocks have their own scope.
- Nowhere until it is assigned. :: Declaration creates the binding.

? Which are good interpreter design choices? (select all that apply)
+ Restore the previous environment in a `finally` block :: Errors must not leak scopes.
+ Check operand types before applying an operator :: Clear runtime errors.
- Let the host language's equality decide `==` :: Host rules may convert types.
+ Attach source spans to runtime errors :: Users can find the failing code.

Summary and Key Takeaways

A tree-walk interpreter is a recursive evaluator over the AST plus a chain of environments. Defining truthiness, equality, conversions and error behaviour explicitly — and testing them — turns it into a precise, executable specification of the language.