The metacircular evaluator

Lesson 13 showed that delaying a single stream tail — changing when one expression gets evaluated — bought us back the modularity that assignment had cost. If controlling the evaluation of one tail is that powerful, the full power is to control all evaluation: to write the evaluator itself. This lesson builds an evaluator for a JavaScript-like language in JavaScript. The substitution model (01) and the environment model (10) were descriptions of how evaluation works; here that description becomes running code — two mutually recursive functions, evaluate and apply, that turn the model into a program you can step through.

1 · The central insight: eval and apply call each other

Strip every language down and evaluation is two questions that keep handing off to each other:

That mutual recursion is the engine. evaluate reduces compound expressions toward applications; apply reduces applications back into evaluating a body. Everything else — conditionals, names, literals — is bookkeeping around this cycle. The substitution model (01) was the human-readable sketch of it; the environment model (10) fixed it so state and closures work; this lesson makes that fixed model execute.

2 · Programs are syntax data — dispatch on type

To evaluate a program the evaluator must first read it as a data structure. We assume the source text has already been parsed into tagged objects — a tree where every node carries a type field naming its syntactic kind. This is exactly Lesson 06's symbolic data and Lesson 07's tagged data: a program is just another tree to walk.

// "x * x" parsed into syntax data (an abstract syntax tree node):
{ type: "application",
  fn:   { type: "name", name: "*" },
  args: [ { type: "name", name: "x" }, { type: "name", name: "x" } ] }

// a literal, a name, a conditional, a function definition:
{ type: "literal", value: 7 }
{ type: "name", name: "balance" }
{ type: "conditional", pred: P, then: A, else: B }
{ type: "lambda", params: ["x"], body: BODY }

Now recall Lesson 07's data-directed dispatch: instead of one giant conditional, you look the operation up in a table keyed by type. Here the very same move reappears, but the key is the syntactic type of the expression. evaluate is a dispatch on syntax. Say it plainly: data-directed dispatch from Lesson 07 returns as SYNTAX dispatch — the operation is "evaluate", the type is the kind of expression, and the table maps each syntactic form to the rule that evaluates it.

3 · evaluate — dispatch on the syntactic type

function evaluate(expr, env) {
  switch (expr.type) {
    case "literal":     return expr.value;                 // self-evaluating
    case "name":        return lookup(expr.name, env);     // env model rule 1
    case "lambda":                                          // make a compound fn
      return { kind: "compound", params: expr.params,
               body: expr.body, env: env };                // remembers defining env!
    case "conditional":                                     // evaluate predicate, branch
      return isTruthy(evaluate(expr.pred, env))
        ? evaluate(expr.then, env)
        : evaluate(expr.else, env);
    case "assignment":                                      // x = e
      assign(expr.name, evaluate(expr.value, env), env);
      return undefined;
    case "application": {                                    // the heart of the cycle
      const fn   = evaluate(expr.fn, env);                  // 1. evaluate the operator
      const args = expr.args.map(a => evaluate(a, env));    // 2. evaluate each operand
      return apply(fn, args);                               // 3. hand off to apply
    }
    default: throw new Error("unknown expression type: " + expr.type);
  }
}

Three things deserve emphasis. A literal evaluates to itself — the base case that stops the recursion. A name is looked up in the environment — this is rule 1 of the environment model (10), now a function call. A lambda evaluates to a compound-function value that captures the current env — this single line is what makes closures work: the function object remembers the environment it was born in, exactly as Lesson 10 demanded. And the application case is the cycle: evaluate the operator, evaluate the operands, then call apply.

4 · apply — make a frame, run the body

A function value is one of two kinds. A primitive function is one the evaluator does not implement itself — it borrows the host (real JavaScript) to do arithmetic, comparison, etc. A compound function is one defined by a lambda in the language being interpreted; apply runs its body.

function apply(fn, args) {
  if (fn.kind === "primitive") {
    return fn.impl(...args);                       // borrow the host: e.g. (a,b)=>a*b
  }
  if (fn.kind === "compound") {
    // environment model rule 2: extend the function's DEFINING env with a new frame
    const frame  = bindAll(fn.params, args);       // params -> argument values
    const newEnv = extend(frame, fn.env);          // parent = where the fn was defined
    return evaluateSequence(fn.body, newEnv);      // run the body in the new frame
  }
  throw new Error("not a function");
}

This is the second rule of the environment model made into code: applying a compound function builds a new frame binding parameters to argument values, whose enclosing environment is the function's defining environment (fn.env, captured at the lambda) — not the caller's. Then it evaluates the body there, which loops straight back into evaluate. The cycle closes.

5 · Environments — Lesson 10's model, now as code

The environment is a chain of frames. A frame maps names to values; each frame points to its enclosing frame; the chain ends at the global frame, which holds the primitives. The two operations the evaluator needs are exactly the two rules from Lesson 10.

// a frame is a Map; an environment is { frame, parent } or null at the top
function extend(frame, parent) { return { frame, parent }; }
function bindAll(params, args) {
  const m = new Map();
  params.forEach((p, i) => m.set(p, args[i]));
  return m;
}
function lookup(name, env) {                         // rule 1: search the chain
  for (let e = env; e !== null; e = e.parent)
    if (e.frame.has(name)) return e.frame.get(name);
  throw new Error("unbound name: " + name);
}
function assign(name, value, env) {                  // find the binding, mutate it
  for (let e = env; e !== null; e = e.parent)
    if (e.frame.has(name)) { e.frame.set(name, value); return; }
  throw new Error("unbound name: " + name);
}

lookup walks outward through enclosing frames until it finds the name — that walk is lexical scoping. Because a compound function stored its defining environment, applying it always extends that chain, which is precisely why each bank account from Lesson 10 keeps a private, persistent balance: the closure's frame lives on the chain its lambda captured.

6 · The driver loop, and why "metacircular"

An interpreter is used through a read-eval-print loop (REPL): read a source expression, evaluate it in the global environment, print the result, repeat.

const globalEnv = extend(makeGlobalFrame(), null);   // holds the primitives
function repl() {
  while (true) {
    const expr  = parse(read());                     // text -> syntax data
    const value = evaluate(expr, globalEnv);          // run the cycle
    print(value);
  }
}

The evaluator is called metacircular because it implements a language using that same language's features — it uses the feature to implement the feature. Our evaluator implements function application by performing JavaScript function calls; it implements conditionals with a JavaScript if; it implements arithmetic by borrowing host arithmetic as primitives. It does not explain those mechanisms from scratch — it leans on the host. That is its beauty and, as we will see, its limitation: it is a crisp specification of meaning, not yet a self-sufficient implementation.

evaluate( square(5) , G )                       G = global env
  case "application":
    fn   = evaluate( name "square", G )         -> lookup -> {compound, params:[x], body:(x*x), env:G}
    args = [ evaluate( literal 5, G ) ]         -> [5]
    apply( square, [5] )
      kind == compound
        frame  = { x: 5 }
        newEnv = { frame:{x:5}, parent: G }      <-- new frame, parent is square.env = G
        evaluate( x * x , newEnv )               run body in the new frame
          case "application":
            fn   = evaluate( name "*", newEnv )  -> lookup walks to G -> {primitive, impl:(a,b)=>a*b}
            args = [ evaluate(name x,newEnv),    -> lookup x in newEnv.frame -> 5
                     evaluate(name x,newEnv) ]   -> 5
                 = [5, 5]
            apply( *, [5,5] )
              kind == primitive -> impl(5,5) -> 25     <-- leaves the cycle, host does it
          returns 25
        returns 25
      returns 25
  returns 25

Common mistakes / failure modes

Checkpoint exercise

const add1 = x => x + 1;     // a lambda bound in G
add1(add1(4));               // nested application

Where this points next

The metacircular evaluator is a beautiful specification of meaning — but it is wasteful as an execution strategy. Look again at the trace: every time the body x * x runs, evaluate re-examines its syntactic type, re-discovers it is an application, re-dispatches on each operand. Put add1 in a loop that runs a million times and the evaluator re-traverses the same fixed syntax a million times, paying the dispatch cost on every iteration even though the shape of the code never changes. The syntax analysis and the actual work are tangled together in one pass. That is the precise pressure that forces Lesson 15: separate the analysis of an expression (done once) from its execution (done many times) — the analyzing evaluator.

Interview prompts

• Describe the eval/apply cycle. (§1 — evaluate reduces compound expressions toward applications then calls apply; apply builds a frame and evaluates a body, re-entering evaluate; they are mutually recursive.)
• How does evaluate decide what to do with an expression? (§2–3 — it dispatches on the expression's syntactic type; this is Lesson 07's data-directed dispatch applied to syntax kinds rather than data types.)
• What does evaluating a lambda produce, and why does it capture the environment? (§3 — a compound-function value carrying params, body, and the defining env; capturing the env is what implements closures and lexical scope.)
• Distinguish primitive from compound functions in apply. (§4 — a primitive is implemented by the host and called directly; a compound function is defined by a lambda, so apply makes a frame and evaluates its body, re-entering the cycle.)
• Why must the new frame's parent be the function's defining environment? (§4–5 — that gives lexical scope and makes closures/private state work; using the caller's env would be dynamic scope and break Lesson 10's bank account.)
• What does "metacircular" mean? (§6 — the evaluator implements a feature by using that same feature in the host language: it runs applications via host calls, conditionals via host if, arithmetic via host primitives.)
• Why is the metacircular evaluator a poor execution strategy despite being a good specification? (Where next — it re-traverses and re-dispatches the same syntax on every run; a loop body is re-analyzed every iteration, motivating the analyzing evaluator.)