clambda

clambda is lambda compiled at definition time. Part III ended with a discipline — code generation must happen inside the run that will scope it — and clambda is that discipline packaged as a binding form: its handler reifies the body under a staged dictionary inside its own run 0 and hands back a native function.

((clambda (x) (+ x 1)) 41)
;=> 42

The compilation is against the live session: a free name in the body compiles to a read of that name’s session cell, not to the value the cell happens to hold. A clambda bound with define can therefore call itself — the recursive call is a cell read that finds the compiled function once the define completes — and it keeps seeing later set!s to the data it references. What it does not keep seeing is the interpreter, and that is this chapter’s point.

What the residual looks like

Staging the tower is not free the way staging Pink was. Pink’s interpreted language was pure, so the collapse property made the residual be the object program. The tower’s language has cells, and compiled code must preserve every cell effect: the residual of a clambda is a stage-polymorphic function that receives the runtime dictionary of the last chapter and routes cell reads, cell writes, and dynamic applications through it. Arithmetic and other pure operations compile to direct floor operations. The compiled x + 1 above is small; a compiled recursive function is a dictionary-routed loop whose variable reads are cread calls against the session’s cells.

Definition-site semantics

The handlers that compile a clambda body are whatever the meta level holds at definition time — including handlers installed with EM. During compilation each lookup in the body is evaluated by the installed handler; the handler’s own effects on meta-level cells residualize along with everything else. An instrumented interpreter therefore produces instrumented compiled code.

The last chapter’s counting handler, replayed against both an interpreted and a compiled fib. First, the interpreted baseline:

(define fib (lambda (n) (if (eq? n 0) 1 (if (eq? n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))))
(EM (define counter 0))
;=> 'counter
(EM (define old-eval-var eval-var))
;=> 'old-eval-var
(EM (set! eval-var (lambda (e r k) (begin (if (eq? e 'n) (set! counter (+ counter 1)) 0) (old-eval-var e r k)))))
;=> 'eval-var
(fib 3)
;=> 3
(EM counter)
;=> 13

Now compile the same function while the counting handler is installed, and run it:

(define cfib (clambda (n) (if (eq? n 0) 1 (if (eq? n 1) 1 (+ (cfib (- n 1)) (cfib (- n 2)))))))
(EM (set! counter 0))
;=> 'counter
(cfib 3)
;=> 3
(EM counter)
;=> 13

The same thirteen — the counter increments were compiled into the residual at each of the four lookup sites of n, and execution reaches them thirteen times, exactly as often as the interpreted run looked n up. Now restore the stock handler and run both again:

(EM (set! eval-var old-eval-var))
;=> 'eval-var
(EM (set! counter 0))
;=> 'counter
(fib 3)
;=> 3
(EM counter)
;=> 0
(cfib 3)
;=> 3
(EM counter)
;=> 13

Interpreted fib stops counting — it reads the handler cell at every lookup, and the cell holds the original again. Compiled cfib counts thirteen forever: its instrumentation is not a reference to the handler cell but the compiled consequence of the handler that was in force when clambda ran. Redefining the interpreted function after the restore completes the square:

(define fib2 (lambda (n) (if (eq? n 0) 1 (if (eq? n 1) 1 (+ (fib2 (- n 1)) (fib2 (- n 2)))))))
(fib2 3)
;=> 3
(EM counter)
;=> 13

Interpretation binds to the meta level late — the current handlers, at every step. Compilation binds it early — the handlers at definition. lms-black draws the same square, and its test suite pins the same counts. This is also the answer to the µKanren chapter’s closing question: a goal kept behind a clambda boundary is a reusable compiled artifact, staged against the session it was defined in.