Analyzer, data as programs, and declarations

Lesson 14's metacircular evaluator was a faithful specification of meaning — but the closing trace exposed a waste: every time a body runs, evaluate re-examines its syntactic type, re-dispatches on each operand, and re-discovers facts about the code that never change. A loop body run a million times is analyzed a million times. This lesson removes that waste with one structural change: split syntactic analysis (done once, the moment we first see an expression) from execution (done many times, against many environments). analyze(expr) walks the syntax once and returns an execution function of env. Along the way we confront the idea that made all this possible — programs and data are the same stuff — and handle internal declarations at analysis time.

1 · The waste, and the factoring that removes it

Recall Lesson 14's evaluate: a single function that does two unrelated jobs on every call. It analyzes — "what kind of expression is this? an application? then which subexpression is the operator?" — and it executes — "do the work in this environment." The first job depends only on the syntax, which is fixed. The second depends on the environment, which changes call to call. Bundling them means re-doing the fixed work every time the variable work runs.

The fix is to factor those two jobs into two phases:

The key identity is evaluate(expr, env) === analyze(expr)(env). We have simply split a two-argument function into a sequence of two one-argument applications (currying it on the syntax). The win comes because analyze(expr) can be computed once and its result reused for every env.

2 · The analyzing evaluator, case by case

Every case now returns a closure over env instead of doing the work immediately. Read each return env => … as "the work to do later"; everything outside that arrow is the analysis, done once.

function analyze(expr) {
  switch (expr.type) {
    case "literal": {
      const v = expr.value;                       // read the value ONCE, at analysis
      return env => v;                            // exec: just hand it back
    }
    case "name": {
      const n = expr.name;
      return env => lookup(n, env);               // exec: only the lookup is per-call
    }
    case "conditional": {
      const aPred = analyze(expr.pred);           // analyze all three branches ONCE
      const aThen = analyze(expr.then);
      const aElse = analyze(expr.else);
      return env => isTruthy(aPred(env)) ? aThen(env) : aElse(env);
    }
    case "lambda": {
      const params = expr.params;
      const aBody  = analyzeSequence(expr.body);  // body analyzed ONCE, not per call!
      return env => ({ kind: "compound", params, body: aBody, env });
    }
    case "application": {
      const aFn   = analyze(expr.fn);             // analyze operator ONCE
      const aArgs = expr.args.map(analyze);       // analyze each operand ONCE
      return env => executeApply(aFn(env), aArgs.map(a => a(env)));
    }
    default: throw new Error("unknown expression type: " + expr.type);
  }
}

function executeApply(fn, args) {
  if (fn.kind === "primitive") return fn.impl(...args);
  if (fn.kind === "compound") {
    const newEnv = extend(bindAll(fn.params, args), fn.env);
    return fn.body(newEnv);        // body is ALREADY an exec function — just call it
  }
  throw new Error("not a function");
}

The decisive line is the lambda case: analyzeSequence(expr.body) runs once, at analysis time, no matter how many times the function is later called. In Lesson 14 the body's syntax was re-walked on every single application. Here it is walked once; what gets stored in the compound-function value is not syntax but a ready-to-run execution function. executeApply then just calls it.

3 · Counting the dispatch you eliminate

Numbers make the win concrete. Take a loop body — modeled here as a function applied N times — that computes x * x + 1:

const f = x => x * x + 1;        // body: (x * x) + 1
// applied N times, e.g. mapping over a list of length N

The body parses into nested applications: +( *(x, x), 1 ). That is 2 application nodes, 1 literal (the 1), and 4 name references (the two xs plus the operator names + and *) — call it roughly 7–8 syntax-dispatch decisions to fully walk the body once. Now compare the two evaluators when this body runs N times:

The per-call work that genuinely depends on the environment — the variable lookups for x, the two primitive calls — still happens N times in both; that work is irreducible. What the analyzing evaluator deletes is the repeated structural re-discovery: "this is an application, its operator is +, it has two operands, the first is itself an application…". That is computed once and frozen into closures. For a body run a million times, you pay the syntax tax once, not a million times.

L14 metacircular — evaluate(f(5)):
  evaluate sees "application"      <- dispatch
    evaluate name f                <- dispatch + lookup
    evaluate literal 5             <- dispatch
    apply: make frame {x:5}
      evaluate body (x*x)+1 in frame
        "application" for +        <- dispatch
          "application" for *      <- dispatch
            name x, name x         <- 2 dispatch + 2 lookup
          literal 1                <- dispatch
  ... and on evaluate(f(6)) EVERY ONE of those dispatch steps happens AGAIN.

L15 analyzing — done in two phases:
  PHASE 1 (once):  analyze(f's body) walks (x*x)+1, builds nested exec closures.
                   The compound value of f stores exec, not syntax.
  PHASE 2 (per call):
    f(5): executeApply -> newEnv{x:5} -> body_exec(newEnv)
            body_exec just calls: mul_exec(env) then add 1   (NO re-dispatch)
    f(6): executeApply -> newEnv{x:6} -> body_exec(newEnv)   (SAME exec reused)
          phase 1 is NOT repeated.

4 · Data as programs — programs and data are the same stuff

Step back. To build either evaluator we represented a program as a tree of tagged objects (Lesson 14, §2) and then wrote ordinary functions — evaluate, analyze — that consume that tree the way Lesson 05's procedures consumed lists. A program, to the evaluator, is just data. And conversely, the data the evaluator returns — a compound-function value carrying a body — is a packaged-up program. There is no firm wall between code and data: code is data a particular processor (the evaluator) happens to know how to run, and data is inert code awaiting a processor.

This is not a slogan; it is the load-bearing fact of Part IV. Because a program is just a data structure we can write functions over it — and those functions are evaluators, analyzers, optimizers, compilers. Lesson 16 will change argument handling by editing a few lines of analyze; Lesson 17 will add backtracking; Lesson 22 will compile the tree to machine instructions. Every one of those is "a function over the program-as-data." The analyzing evaluator is the first taste: it is a function that transforms a program (syntax tree) into a faster program (a tree of execution closures) before running it. That transform-then-run shape is exactly what a compiler does — analysis once, execution many times — which is why the brief calls this the first step from interpreter-as-specification toward an implementation strategy.

5 · Internal declarations, handled at analysis time

A function body may declare local names before using them — const u = …; const v = …; return u + v;. For these to mutually refer to each other (and for forward references to work), the body needs all its declared names in scope throughout the body, not only from the textual point of declaration onward. The clean way is to scan the body for declarations once, at analysis time, and arrange that the frame created on each call already reserves slots for every declared name.

// analysis pass over a body: collect declared names, build exec that
// (1) reserves slots for them in the call frame, (2) runs the declarations,
// (3) runs the rest. The SCAN happens once during analyze, not per call.
function analyzeSequence(body) {
  const names = scanDeclarations(body);     // once: which locals does this body declare?
  const aStmts = body.map(analyze);         // once: analyze every statement
  return env => {                            // per call:
    names.forEach(n => declare(n, env));     // reserve slots so refs resolve
    let result;
    for (const s of aStmts) result = s(env); // run the already-analyzed statements
    return result;
  };
}

Notice the division of labor that defines this whole lesson: scanning the body for its declared names is structural, depends only on the syntax, and is done once inside analyze. Reserving the slots and running the statements is environment-dependent and done per call. Putting the scan in the analysis phase is the same optimization as everything above — do the syntax work once — applied to scope.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

We have proven the deeper point operationally: if you own the evaluator, you own the semantics. The analyzing evaluator changed nothing about what programs mean — it only changed how fast they run, by moving syntax work earlier. But the same control lets you change meaning itself. Look at the application case: it evaluates every operand before calling the function (aArgs.map(a => a(env))). That eager step is a choice in our code, not a law of nature. Change just that handful of lines — pass operands unevaluated, as thunks the function forces only if it needs them — and the language stops being applicative-order and becomes normal-order (lazy). Same surface syntax, different language, because we edited the evaluator. That is the precise pressure that forces Lesson 16: having the evaluator in our hands, we change how arguments are handled, and lazy evaluation falls out — with infinite lazy lists coming for free.

Interview prompts

• What does the analyzing evaluator separate, and why does it matter? (§1 — syntactic analysis (once) from execution (many times); the structural dispatch on fixed syntax is computed once and reused, so repeated execution gets cheaper.)
• State the identity relating analyze to evaluate. (§1 — evaluate(expr, env) === analyze(expr)(env); it curries on the syntax so analyze(expr) can be computed once and reused for every env.)
• In the analyzer, what work goes outside the env => arrow vs inside it? (§2 — syntax-dependent work (type dispatch, structural decomposition, scanning declarations) outside, once; env-dependent work (lookups, applications) inside, per call.)
• Quantify the savings for a loop body run N times. (§3 — the metacircular evaluator pays the body's syntax dispatch (~k decisions) on all N calls (~kN); the analyzer pays it once (~k), leaving only irreducible per-call lookups/primitive calls.)
• What is the "data as programs" idea, and why is it load-bearing? (§4 — programs are represented as data trees, so evaluators/analyzers/compilers are just functions over that data; it is what lets us transform and reinterpret programs at all.)
• How are internal declarations handled, and which phase does the scan belong to? (§5 — scan the body for declared names once at analysis time so refs resolve throughout the body; reserve slots and run statements per call.)
• Why does the analyzer demonstrate that "owning the evaluator means owning the semantics"? (Where next — analysis changed speed without changing meaning, but the same code controls meaning: editing the eager operand step in the application case turns the language lazy, motivating Lesson 16.)