Tree-Walking Evaluation

The last two chapters introduced Bridger’s AST and its values. This chapter begins the evaluator: the procedure that maps an AST to a value. It covers the arithmetic, Boolean, string, list, and tuple expressions that Milestone M1 asks you to build, whose semantic rules take the form $e\Downarrow v$: the expression $e$ evaluates to the value $v$. The rest of those rules carry detail that does not bear on this fragment, and this chapter sets it aside.

Tree-walking evaluator

The rules for evaluation are compositional: the value of an expression is defined in terms of the values of its subexpressions. The E-Add rule only fixes the meaning of $e_1+e_2$ once the meanings of $e_1$ and $e_2$ are known.

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2}{e_1+e_2\Downarrow v_1+v_2}(\text{E-Add})$$

This shape of giving meaning is naturally recursive: to evaluate a node, first evaluate its children, then combine their values as the node’s rule prescribes. A leaf (a literal) is the base case: it carries its own value and does not recurse. The little arithmetic language below is fixed by four rules: E-Add above, together with a literal axiom, negation, and multiplication:

$$\frac{}{n\Downarrow n}(\text{E-Lit})\frac{e\Downarrow v}{-e\Downarrow -v}(\text{E-Neg})$$

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2}{e_1\times e_2\Downarrow v_1\times v_2}(\text{E-Mul})$$

The evaluator you develop following this book will recurse over the structure of an Expr. Below is a tree-walking evaluator for the little language above (similar to the one you will be asked to write):

enum Expr {
    Lit(i64),                       // 5
    Neg(Box<Expr>),                 // -e
    Add(Box<Expr>, Box<Expr>),      // e + e
    Mul(Box<Expr>, Box<Expr>),      // e * e
}

fn eval(e: &Expr) -> i64 {
    match e {
        Expr::Lit(n)    => *n,                       // E-Lit
        Expr::Neg(x)    => -eval(x),                 // E-Neg
        Expr::Add(l, r) => eval(l) + eval(r),        // E-Add
        Expr::Mul(l, r) => eval(l) * eval(r),        // E-Mul
    }
}

fn main() {
    // (1 + 2) * 4
    let e = Expr::Mul(
        Box::new(Expr::Add(Box::new(Expr::Lit(1)), Box::new(Expr::Lit(2)))),
        Box::new(Expr::Lit(4)),
    );
    println!("{}", eval(&e)); // 12
}

Each rule became one arm of the match; each premise became a recursive call; each conclusion became the value the arm returns. The calls eval makes on $(1+2)\ast 4$ trace the same tree as the derivation the rules build for it — eval(Mul) waits on eval(Add) and eval(Lit 4), and eval(Add) waits on its two literals — so the call tree and the proof tree have the same shape. Running the program computes the value at the root by the same steps the derivation uses to justify it.

Interpreting a program by a function that recurses over its structure is the oldest way to run one. McCarthy’s LISP defined its own evaluator this way: eval was an ordinary function, written in LISP, that took a program — itself a LISP list — and walked it, dispatching on each form and calling itself on the pieces. An interpreter for a language, written in that same language, is a metacircular evaluator, and the arithmetic walk above is the same idea with the program held as a Rust enum instead of a list.

From rules to match arms

Bridger’s evaluator has the same skeleton, over the real Expr and the real Value. Two things grow past the arithmetic sketch. Evaluation can fail — an operand can have the wrong shape, so the function returns Result<Value, Control> rather than a bare value, and a subexpression’s exit is propagated with ?. And the arithmetic fragment has no variables, so the environment carried by the reference judgment plays no part yet; eval reads only its &Expr, and the rules are read in the store-free, env-free slice $e\Downarrow v$ — the starter’s eval_expr already carries an env parameter, which nothing reads until Part III. The environment enters with let and scope there.

The correspondence is otherwise unchanged: one rule, one arm. The previous chapter wrote the Add arm in full — evaluate both operands, and on two integers return their sum, otherwise raise a TypeError. The rest of eval is built the same way, arm by arm:

fn eval(e: &Expr) -> Result<Value, Control> {
    match e {
        // E-Lit: a literal evaluates to itself
        Expr::Lit(lit, _) => Ok(match lit {
            Lit::Int(n)  => Value::Int(*n),
            Lit::Bool(b) => Value::Bool(*b),
            Lit::Str(s)  => Value::Str(s.clone()),
            Lit::Unit    => Value::Unit,
        }),

        // E-Arith: evaluate both, combine two integers (values.md)
        Expr::Binary(BinOp::Add, l, r, span) => { /* … */ }

        // the remaining forms are the work of Milestone M1
        _ => todo!("Sub, Mul, comparisons, and, or, not, tuples, lists, …"),
    }
}

Most of the remaining arms repeat Add‘s shape with a different operator, string concatenation among them. ++ joins two strings, and E-Concat names both operands’ values exactly as E-Add does:

$$\frac{e_1\Downarrow s_1{e}_2\Downarrow s_2}{e_1++e_2\Downarrow s_1{s}_2}(\text{E-Concat})$$

Its arm is the Add arm with Value::Str in place of Value::Int: evaluate both children, return their concatenation on two strings, and raise a TypeError otherwise. The same ++ also joins two lists, so the arm matches that shape as well — one operator over two value shapes, which is operator overloading; the general mechanism that lets one operator serve many types arrives with traits. Comparing strings for order arrives the same way, through cmp rather than <.

Filling in each arm is the walk applied to one rule at a time. Most arms follow a single pattern — evaluate both children, then combine their values — but two rules depart from that pattern.

When the walk departs from evaluating both

Division carries an extra premise: E-Div fires only when the divisor is nonzero. When it is zero no rule applies, so the expression is stuck, and the interpreter reports it rather than dividing. The arm reads the premise off as a guard:

// E-Div: the divisor must be nonzero, or evaluation is stuck
Expr::Binary(BinOp::Div, l, r, span) => {
    match (eval(l)?, eval(r)?) {
        (Value::Int(_), Value::Int(0)) => Err(Control::Raise(
            RuntimeError::DivByZero { span: *span },
        )),
        (Value::Int(x), Value::Int(y)) => Ok(Value::Int(x.wrapping_div(y))),
        (a, b) => Err(type_error2(Ty::int(), &a, &b, *span)),
    }
}

type_error2 builds the RuntimeError::TypeError the previous chapter wrote out by hand, blaming the first operand that is not an Int (type_error is its one-operand form); here the new case is the zero check, the guard $v_2\ne 0$ in the rule became a match arm. Modulo is the same arm with %.

The boolean connectives depart further. and and or short-circuit: the right operand is evaluated only when the left has not already settled the result. Two rules cover and — a false left operand settles it without touching the right, and a true left operand hands the result to the right — and the walk follows their shape, evaluating the left, then reaching the right on true:

// E-And-False / E-And-True: evaluate the right only when the left is true
Expr::Binary(BinOp::And, l, r, span) => {
    match eval(l)? {
        Value::Bool(false) => Ok(Value::Bool(false)),
        Value::Bool(true) => match eval(r)? {
            b @ Value::Bool(_) => Ok(b),
            other => Err(type_error(Ty::bool(), &other, *span)),
        },
        other => Err(type_error(Ty::bool(), &other, *span)),
    }
}

The arithmetic arm evaluated both children before combining them; the and arm evaluates one and may stop there. What each arm does is dictated by its rule — an axiom is a leaf, a rule with two operand premises recurses twice, a short-circuiting rule recurses once and then decides — so reading the rules off as arms also settles the questions prose semantics left open, such as whether and ever evaluates its right operand. The remaining forms of Expr — the other arithmetic and comparison operators, not, building tuples and lists, prepending to a list with ::, and projecting a tuple component with e.0 — are each one more arm of the same walk, and completing them is Milestone M1. A tuple has positional access because its arity is fixed and the index is a literal.

Beyond tree-walking evaluators

Walking the AST is one way to run a program; however, there are other alternatives when implementing an interpreter. The walk re-inspects the tree every time control reaches a node: each visit dispatches on the node’s variant and follows the Box pointers to its children. For a literal evaluated once is nothing. For the body of a loop that runs a million times — once the language has loops — it is a million repetitions of the same dispatch and the same pointer-chasing over a tree that never changed.

Interpreters that need the speed spend a compile step to remove that repetition.

• A bytecode virtual machine lowers the tree once into a flat sequence of simple instructions, then runs a tight loop that dispatches on one instruction at a time. The instructions sit in an array rather than scattered across the heap, and each is a single indexed step, so the repeated dispatch and pointer-chasing of the walk are gone. The cost is a second representation — the bytecode — to design, produce, and debug alongside the tree. CPython, the JVM, and Lua run this way, and it is the second interpreter Nystrom’s book builds for the same language as its first.
• Closure generation walks the tree once and produces, for each node, a closure that already holds its children’s closures and knows what to do; running the program calls closures and never inspects the AST again. The repeated dispatch is gone without leaving the host language or defining a bytecode, at the cost of a closure allocated per node. Feeley and Lapalme set the approach out in 1987.
• Just-in-time compilation translates the parts of a program that run hot into machine code while the program runs, reaching the speed of compiled code on those parts. It is the most involved and the most machine-specific of the three, and drives the production JavaScript and JVM engines.

A separate choice is the walk’s use of host-language recursion. eval calling itself uses the Rust call stack for the tree’s depth and for every Bridger call in progress, so a runaway recursion would exhaust it. The provided interpreter runs on a large stack and counts the calls in progress, refusing the next one past 100 000 as the stuck state StackOverflow, before the host stack runs out. An interpreter that must bound its memory more tightly keeps an explicit stack of work to do and loops over it instead of recursing, trading the directness of the recursive arms for control over memory.

This book takes the recursive AST-walk. It is the most direct realization of the semantics — one match arm per rule, the call tree the derivation tree — so the evaluator reads as the rules it implements, which is what serves a reader learning what those rules mean.

Further reading

Two interpreters for one language: Robert Nystrom’s Crafting Interpreters (free online) builds a tree-walking interpreter in its first half and a bytecode virtual machine in its second, for the same language, so the two strategies of the last section can be read against each other line for line, with the walk’s “Evaluating Expressions” the direct counterpart of this chapter.

Generating closures instead of walking: Marc Feeley and Guy Lapalme’s “Using closures for code generation” (Computer Languages 12:1, 1987, doi:10.1016/0096-0551(87)90012-9) compiles an expression into a network of closures whose application evaluates it, the middle ground that removes the walk’s repeated dispatch without a bytecode.

A register machine for a scripting language: Roberto Ierusalimschy, Luiz Henrique de Figueiredo, and Waldemar Celes’s “The Implementation of Lua 5.0” describes a production bytecode interpreter in detail, including why its virtual machine passes values through registers rather than a stack.

The evaluator written in its own language: Abelson and Sussman’s Structure and Interpretation of Computer Programs (MIT Press, free online) develops a metacircular evaluator — eval and apply for a Lisp, written in that Lisp — the modern presentation of the walk LISP first ran on.

Concept checks