The Futamura Projections

Futamura’s 1971 observation: specializing an interpreter to a source program yields a compiled program (the first projection); specializing the specializer to the interpreter yields a compiler (the second); specializing the specializer to itself yields a compiler generator (the third). The projections are usually stated against a standalone specializer. In Pink there is no such machine — specialization is evaluation under pink-evalc — so the projections become one-liners, and lib/purple.naj runs two of them at every session boot:

(let compiler       (run 0 ((pink-evalc pink-eval-src)  nil-env))
(let evalc-compiled (run 0 ((pink-evalc pink-evalc-src) nil-env))

The previous chapter was the first projection: pink-evalc applied to factorial’s source produced compiled factorial. Here the program being compiled is the evaluator itself. compiler is pink-eval with the interpretive overhead of the evaluator that processed it removed; evalc-compiled is the same treatment applied to pink-evalc — a compiled compiler. The session’s compile helper is a thin wrapper over the latter:

(let compile
  (lambda _ src (run 0 ((evalc-compiled src) nil-env)))

Both artifacts behave like what they were compiled from:

(define fact-src '(lambda f n (if (eq? n 0) 1 (* n (f (- n 1))))))
(define fi ((compiler fact-src) nil-env))
(fi 6)
;=> 720
((compile fact-src) 5)
;=> 120

Measuring collapse

The paper’s title claim is about towers: stack interpreters on interpreters, and staging collapses the whole stack. The witness is the residual code. Compile factorial directly — one level of evaluation:

(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>

Now put an interpreter in the way: run pink-evalc’s source through pink-eval, and apply the resulting (interpreted) compiler to factorial — two levels:

(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-eval (pink-tie (cons (lambda _ e e) 0))
(let pink-evalc-src `(,pink-tie-src (cons (lambda _ e (lift e)) 0))
(let fac '(lambda f n (if (eq? n 0) 1 (* n (f (- n 1)))))
(let nil-env (lambda _ y 0)
  ((((pink-eval pink-evalc-src) nil-env) fac) nil-env))))))))
;=> #<code 25 nodes>

Three levels — an interpreter interpreting an interpreter interpreting a compiler:

(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-eval (pink-tie (cons (lambda _ e e) 0))
(let pink-eval-src `(,pink-tie-src (cons (lambda _ e e) 0))
(let pink-evalc-src `(,pink-tie-src (cons (lambda _ e (lift e)) 0))
(let fac '(lambda f n (if (eq? n 0) 1 (* n (f (- n 1)))))
(let nil-env (lambda _ y 0)
  ((((((pink-eval pink-eval-src) nil-env) pink-evalc-src) nil-env) fac) nil-env)))))))))
;=> #<code 25 nodes>

Twenty-five nodes at every height. Each added interpreter costs evaluation time at generation, and contributes nothing to the residual — the tower collapses to the program at its top. Nothing in the language grows with the height either: the chains above are just longer applications.

Where the run goes

One discipline governs all of this, inherited from Part II’s closing note: code values are meaningful only inside the staging context that made them, so generation must happen inside the run that will execute it. In the floor blocks above, run 0 (or the top-level printer’s implicit reify) encloses the whole pink-evalc application. compile exists to package exactly that enclosure — which is why, at the session prompt, compiling goes through compile rather than through run-compiled applied to code built at the prompt: a code value produced by one prompt input refers to a generation context that is no longer open by the time another input tries to run it.