The Tower

The session evaluator of the last chapter lives in lib/tower.naj, narju’s port of the reflective tower in namin/lms-black (eval.scala; the file’s comments carry the correspondence, structure by structure). Like lib/pink-forms.naj it is one closed floor expression, read as data at boot and animated with trans/evalms; it evaluates to a selector function exporting five names, of which the session uses make-level, make-env, env-define, and ev (clambda-code waits for the clambda chapter, and Part V’s tower-API chapter lists everything precisely).

A reflective tower is the answer to a question about interpreters: the session’s programs run under an evaluator — what does that evaluator run under? In the tower, another copy of itself, and so on upward: level 0 is the program at the prompt, level 1 the interpreter evaluating it, level 2 the interpreter evaluating that. The construction is only useful if a program can reach the levels above it — that is EM, next chapter — and only affordable if the infinite regress costs nothing until it is reached for.

Handlers as environment entries

Each level is a pair m = (menv . slot): an environment for the level’s own machinery, and a lazy slot for the level above. The environment’s one frame holds the evaluator itself, split into fifteen named handlers — base-eval, eval-var, eval-lambda, eval-clambda, eval-let, eval-cst, eval-if, eval-begin, eval-set!, eval-define, eval-quote, eval-EM, eval-application, eval-list, base-apply — each boxed in a mutable cell, followed by the eleven primitives (+ through pair?), bound directly without cells.

Evaluating an expression at level 0 means: look up base-eval in level 1’s frame and apply what the cell currently holds. base-eval dispatches on the expression’s shape and looks up the matching handler the same way. The evaluator is therefore not code but environment state — rebinding eval-var in level 1’s frame changes what variable lookup means for every level-0 program evaluated afterward. That is the entire mechanism EM exploits.

Handlers are values, and the session can ask for one:

(EM eval-var)
;=> ('fn . #<closure>)

('fn . …) is the tower’s tag for a native function — a floor closure obeying the handler calling convention. All fifteen boot handlers are natives, which is what stops the regress: dispatching through a native handler is a direct floor call, no level-2 interpretation required. Only when a handler cell is rebound to an interpreted closure does the level above start doing real work — and level 2 is only constructed (the lazy slot filled) the first time something reaches for it.

Values and environments

The tower’s values are the floor’s numbers, symbols, nil, and pairs, plus four tagged shapes: ('clo params body env . m) for interpreted closures — note the closure records the meta level it was made under, which the clambda chapter makes consequential — ('prim . name), ('fn . fc) for natives, and ('cont . k) for continuations. Floor values that are none of these (the Pink evaluators installed at boot, nil-env, the prelude’s closures) pass through untagged and apply natively, one forced argument at a time — which is why Pink currying like ((pink-eval src) env) works unchanged at the prompt.

An environment is a list of frames; a runtime frame is a cell holding an association list, so define can extend it in place. Mutable bindings are themselves cell-boxed, (name . ('cell . c)); the primitives sit in the frame unboxed. The distinction is a staging decision as much as a mutability one: a read through a cell is an effect the compiler must preserve, a read of an unboxed binding is a constant it can fold. Compiled code keeps its dependence on the session’s cells and constant-folds the primitives away.

Evaluation, concretely

The handlers are written in continuation-passing style — every handler receives an expression, an environment, and a continuation, mirroring lms-black. Threaded through all of it is one more parameter: l, a stage dictionary in exactly the sense of Pink’s maybe-lift, grown to a vocabulary of nine operations (lift, force, cell read/write/new, apply, and friends). At the prompt ev passes the concrete dictionary — identity lifts, real cell operations, real application — and the tower is an ordinary, if elaborately indirect, interpreter:

(+ 1 2)
;=> 3
((lambda (a b) (* a b)) 6 7)
;=> 42

Handing the same handlers a staged dictionary instead turns the tower into a compiler, closure by closure. That is clambda, two chapters from here; EM, the reason the handlers sit in cells at all, comes first.