Lazy evaluation

Lesson 15 split the evaluator into analyze (done once) and execute (done many times) and ended on a claim that sounds almost dangerous: once you own the evaluator, you own the semantics. Change one rule and the language changes underneath every program. This lesson cashes that claim for the first time. We take the exact same evaluator from Lesson 14 and change one thing — when an argument is evaluated — and a different programming model falls out: normal-order (lazy) evaluation. Programs that diverged now terminate; the hand-built streams of Lesson 13 reappear as ordinary pairs, for free.

1 · Two orders, defined precisely

Every evaluator for a call f(arg1, arg2, …) must answer one question: do you evaluate the argument expressions before entering the body, or only when the body actually needs their values? There are two disciplined answers.

The names come from the lambda calculus: normal order reduces the outermost (leftmost) application first; applicative order reduces the arguments (the inner redexes) first. The key theorem behind this lesson: if any reduction order terminates with a value, normal order does too. Applicative order can loop forever on expressions normal order would finish — never the reverse. So normal order strictly terminates more often; the cost is that an argument used twice may be computed twice, and that effects fire at surprising moments. The next sections make both halves of that trade concrete.

2 · An expression that diverges one way and terminates the other

Define a function that ignores its second argument, and call it with a second argument that loops forever:

function loop() { return loop(); }          // never returns
function constant(x, y) { return x; }        // ignores y entirely

constant(42, loop());

APPLICATIVE ORDER (eager — stock JS, Lesson 14's apply)
  evaluate constant(42, loop())
   -> evaluate operands first:  42 -> 42,  loop() -> evaluate loop()
        -> loop() -> loop() -> loop() -> ...        DIVERGES
   the body is never entered; the answer 42 is never reached.

NORMAL ORDER (lazy)
  evaluate constant(42, loop())
   -> enter body immediately, bind  x := <thunk 42>,  y := <thunk loop()>
   -> body is  return x;   it forces x -> 42
   -> y is never forced, so loop() is never run.        RETURNS 42

This is also the precise reason the substitution model in Lesson 01 quietly assumed eager order: it reduced f(arg) by first reducing arg. Normal order is the other legal substitution discipline, and it is the one that matches lambda-calculus "fully expand, then reduce."

3 · Laziness as surgery on apply

We do not write a new evaluator. We take Lesson 14's and change how arguments cross the boundary into a function body. A thunk is the device: a delayed computation — the unevaluated argument expression packaged with the environment it must be evaluated in. Forcing a thunk means finally evaluating it to a real value.

// A thunk: expression + environment, not yet evaluated, plus a memo slot.
function makeThunk(expr, env) {
  return { thunk: true, expr, env, evaluated: false, value: undefined };
}

// force: turn a thunk into a real value, recursively (a thunk may force to a thunk).
function force(obj) {
  if (!isThunk(obj)) return obj;                 // already a value
  if (obj.evaluated) return obj.value;           // MEMO: computed before? reuse it
  const result = force(evaluate(obj.expr, obj.env));
  obj.evaluated = true;                          // <-- the one change that makes it
  obj.value = result;                            //     a MEMOIZING (call-by-need) thunk
  return result;
}

Now the two surgical edits to the eval/apply cycle. First, apply must not pre-evaluate operands — it binds each parameter to a thunk. Second, the few places that genuinely need a real value (a primitive operation, the predicate of a conditional, the final answer to print) must force first.

// In evaluate(): an application no longer evaluates its operands.
function evalApplication(expr, env) {
  const fn = force(evaluate(expr.operator, env));        // operator: need a real fn -> force
  const args = expr.operands.map(o => makeThunk(o, env)); // operands: DELAY them, don't run
  return apply(fn, args);
}

// apply binds parameters to thunks; primitives force, compound bodies don't.
function apply(fn, args) {
  if (isPrimitive(fn)) return fn.impl(...args.map(force));   // primitives need values
  const frame = extendEnv(fn.params, args, fn.env);         // bind params to THUNKS
  return evalSequence(fn.body, frame);
}

// conditionals must force the predicate (you cannot branch on a thunk):
function evalIf(expr, env) {
  return isTruthy(force(evaluate(expr.predicate, env)))
       ? evaluate(expr.consequent, env)
       : evaluate(expr.alternative, env);
}

The two lazy disciplines differ only by the four lines that set evaluated/value. Drop the memo slot and a reused argument is recomputed on every use (call-by-name); keep it and the result is cached (call-by-need). For pure programs both give the same answers; with effects they differ, which is exactly why the cost in §5 bites.

4 · Streams fall out for free — as ordinary pairs

Recall the labor of Lesson 13: to get an infinite list we hand-built a pair whose tail was wrapped in an explicit delay and unwrapped with force, and we needed special stream_map/stream_filter that knew about the wrapping. In a lazy evaluator that entire apparatus vanishes, because every argument is already delayed. An ordinary pair built by an ordinary constructor already has a delayed tail.

// Plain pairs in the LAZY language — no delay/force anywhere in sight:
function pair(a, b) { return f => f(a, b); }   // ordinary pair from Lesson 04
const head = p => p((a, b) => a);
const tail = p => p((a, b) => b);

// An INFINITE list of integers — an ordinary recursive definition:
function integersFrom(n) { return pair(n, integersFrom(n + 1)); }
const integers = integersFrom(1);

head(integers);              // 1     (forces only the head)
head(tail(integers));        // 2     (the tail thunk fires only now)
head(tail(tail(integers)));  // 3

Why does integersFrom(n + 1) not loop forever? Because in the lazy language pair is just a function call, so its second argument is thunked, not run. The recursion unrolls exactly one step per tail you actually take. The Lesson 13 stream was a local patch — delay this one tail by hand. Lazy evaluation is the same idea lifted into the evaluator: delay every argument, always. Same generality, none of the bespoke combinators.

5 · The bill: you can no longer see when things run

Laziness is not free lunch. The eager evaluator gave you a reliable mental model: arguments run left to right, before the call, exactly once. Lazy evaluation shatters that, and the casualties are mostly about order and effects.

Common mistakes / failure modes

Checkpoint exercise

// a
function unless(cond, usual, exceptional) { return cond ? exceptional : usual; }
unless(false, 1, divideByZero());   // does divideByZero() run?

// b  (memo on)  vs  (memo off)
function twice(x) { return x + x; }
twice(sideEffectReturning7());      // how many times does the side effect fire?

// c
function ones() { return pair(1, ones()); }   // does defining `ones` loop?
head(tail(tail(ones())));                       // what does this return?

Where this points next

We changed one rule — when arguments evaluate — and got a new language. That proves the method, so now we ask: what other single rule, changed, buys the most power? Lazy evaluation still computes one answer per expression. Lesson 17 changes the evaluator so an expression may legitimately yield many answers: we add amb, a choice operator, and the evaluator gains automatic backtracking. Where laziness asked "evaluate this argument later," nondeterminism asks "evaluate this expression every possible way, and back up when a constraint fails." The mechanism is a second pair of continuations threaded through the evaluator — and it turns search from a thing you hand-code with loops (or Lesson 13 streams) into a primitive of the language itself.

Interview prompts

• Define applicative order and normal order precisely. (§1 — applicative: evaluate all operands to values, then apply; normal: substitute unevaluated operands, reduce only when needed; lambda-calculus inner-redex-first vs outermost-first.)
• Give an expression that terminates under normal order but diverges under applicative. (§2 — constant(42, loop()): eager evaluates loop() first and never halts; lazy returns 42 because the ignored argument is never forced.)
• What exactly do you change in the metacircular evaluator to make it lazy? (§3 — stop pre-evaluating operands in the application rule, bind parameters to thunks in apply, and force only at primitives, predicates, and the REPL output.)
• What is a thunk, and what is memoization's role? (§3 — a thunk packages an unevaluated expression with its environment; forcing evaluates it; memoizing caches the result so reused arguments are computed once — the call-by-need vs call-by-name distinction.)
• Why do streams become ordinary pairs under lazy evaluation? (§4 — every argument is already delayed, so pair(n, integersFrom(n+1)) has a thunked tail with no explicit delay; the Lesson 13 stream operators become redundant.)
• What does laziness cost? (§5 — unpredictable effect timing, space leaks from retained thunks, call-by-name vs need diverging under effects, and non-local error reporting; it changes termination/what-is-computed, not speed.)
• Why is laziness evidence that "owning the evaluator means owning the semantics"? (§intro, §2 — one rule changed in apply alters termination behavior for every program, with no program edits — the metalinguistic thesis made concrete.)