Stage Polymorphism

The previous chapter passed a parameter l through every handler without explaining it. l is a pair: its cdr is a stage level, and its car is a function the reference calls maybe-lift. The whole difference between interpreting a program and compiling it is what sits in that car.

maybe-lift

Handlers apply (car l) at exactly the points where the interpreter creates a value rather than passing one through: constants (eval-cst), closures (eval-lambda), pairs (eval-cons), and quoted data (eval-quote). Everywhere else — arithmetic, if, application, environment lookup — values flow through the handler untouched.

The session’s two evaluators are the same dispatch closed over two choices of l, built in lib/purple.naj:

(let pink-eval  (pink-tie (cons (lambda _ e e)        0))
(let pink-evalc (pink-tie (cons (lambda _ e (lift e)) 0))

With the identity, created values are ordinary values and the evaluator is the interpreter of the last chapter. With lift, every created value is code — and Part II says what happens next: an operation applied to code residualizes. The handlers do not know which mode they are in. They are stage-polymorphic: one source, two readings, and the reading is picked by a first-class argument.

This is where Part II’s auto-lift convenience earns its place. A handler like eval-plus calls the floor’s + on whatever its subterms produced; under pink-evalc those are code values mixed with the occasional plain number, and the scalar auto-lift keeps the stage-oblivious handler from erroring.

Compiling by interpreting

Under pink-evalc, evaluating a program generates it. The block below boots Pink directly on the floor — the same three moves lib/purple.naj makes at session boot (read the source, trans it, evalms it) — and then evaluates factorial’s source with lift as maybe-lift:

(let pink-poly-src (car (read-file 'lib/pink-forms.naj))
(let pink-tie-src `(let pink-poly ,pink-poly-src
                     (lambda eval l (lambda _ e (((pink-poly eval) l) e))))
(let pink-tie (evalms nil (trans pink-tie-src nil))
(let pink-evalc (pink-tie (cons (lambda _ e (lift e)) 0))
(let fac '(lambda f n (if (eq? n 0) 1 (* n (f (- n 1)))))
  ((pink-evalc fac) (lambda _ y 0)))))))
;=> #<code 25 nodes>

Twenty-five nodes. Part II compiled the same factorial by writing lift into it by hand — explicit (lift 0) and (lift 1) at the constants — and got twenty-five nodes:

(lift (lambda fact n
  (if (eq? n (lift 0))
      (lift 1)
      (* n (fact (- n (lift 1)))))))
;=> #<code 25 nodes>

That agreement is the paper’s Proposition 4.4: compiling a Pink program yields exactly the program itself, in ANF. The interpreter contributes nothing to the output. Its dispatch chain ran — every eq? test on 'lambda, 'if, '+ — but those tests consumed only the program text, which is ordinary data, so they computed away at generation time. What residualized is only what maybe-lift touched: the program’s own constants, closures, and structure. Interpretive overhead is exactly the part of the interpreter that does not pass through maybe-lift, and it vanishes. (narju’s test suite checks the stronger structural claim — the residual contains no symbol nodes, i.e. no fragment of quoted Pink source survives.)

Running the residual confirms it is factorial:

(let pink-poly-src (car (read-file 'lib/pink-forms.naj))
(let pink-tie-src `(let pink-poly ,pink-poly-src
                     (lambda eval l (lambda _ e (((pink-poly eval) l) e))))
(let pink-tie (evalms nil (trans pink-tie-src nil))
(let pink-evalc (pink-tie (cons (lambda _ e (lift e)) 0))
(let fac '(lambda f n (if (eq? n 0) 1 (* n (f (- n 1)))))
  ((run 0 ((pink-evalc fac) (lambda _ y 0))) 5))))))
;=> 120

(Floor forms are closed, so the boot preamble repeats in each block; in the session it happens once. The run 0 wraps the whole generation, for the reason Part II ended on: code values are meaningful only inside the staging context that made them, and the next chapter leans on this.)

At the session prompt

The session offers both readings of any program. interpret is pink-eval behind a convenience signature, and compile runs the generated code immediately (its mechanics are the next chapter’s):

(define fact-src '(lambda f n (if (eq? n 0) 1 (* n (f (- n 1))))))
(define f-int ((interpret fact-src) nil-env))
(define f-com (compile fact-src))
(f-int 5)
;=> 120
(f-com 5)
;=> 120

Same answers; different objects. f-int is a closure that walks fact-src on every call — each recursion re-enters base-eval, re-tests the head symbols, re-extends the environment function. f-com is the twenty-five-node residual, compiled once; the source is gone.