clambda

clambda has lambda’s shape and compiles its body against the semantics in force. it answers a floor closure under a tag:

narju> (clambda f (n) (+ n 1))
('cfun . #<closure>)

narju> ((clambda f (n) (* n 2)) 21)
42

the tag matters at a call site and nowhere else. the base environment binds the primitives to floor closures too, and a call site treats the two oppositely: a primitive handed code unfolds into it, a compiled function is called. nothing in the value says which, so clambda says it.

it is an annotation, not a restriction. the same body works either way and callers cannot tell which they got.

(define ifib (lambda fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
(define cfib (clambda fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))

(ifib 22) takes about eight seconds here, (cfib 22) about thirty milliseconds. an interpreted call allocates a frame per level per step, and compiling removes every level between the body and the floor.

What happens to the tower

everything reflective in a compiled body resolves while staging:

(say ((clambda f (n) (+ 1 (call/cc (lambda (k) (+ 100 (k n)))))) 5))

6

the call/cc, the escape and the abandoned (+ 100 _) are gone. the residual is (+ 1 n).

the flip side: an operator that only becomes reflective at run time cannot be recovered, and static-apply throws ('no-call-site . f). that is the whole of what compiling does not preserve.

Interpreted callees get inlined

a call from a compiled region into an interpreted closure unfolds the callee into the code being emitted:

(let ((g (lambda g (x) (+ x 1))))
  (say ((clambda f (n) (g (g n))) 1)))

3

the emitted body is two additions. g is not called at run time.

which is fine until the callee recurses:

(say (attempt (lambda ()
  (let ((g (lambda g (x) (if (< x 1) 0 (g (- x 1))))))
    (clambda f (n) (g n))))))

('throw 'inlines-forever 'g)

unfolding would not stop, so it is refused rather than attempted. the check is not a depth limit. it looks for the same closure reached with statically equal arguments, which is exactly when the next unfolding cannot differ from this one, so a recursion whose static arguments do change still unfolds. that case is the one worth having: an interpreter staged against a static program is precisely it.

a cycle through several functions names them all:

('inlines-forever 'g 'h)

Compiled callees get called

(define down (clambda down (n) (if (< n 1) 0 (down (- n 1)))))
(define go (clambda go (n) (down n)))
(say (go 5))

0

a call to a compiled function is emitted, not unfolded, so its recursion is its own business. the two ways down can reach the call site emit the same thing: staged in the same region as its caller it is still code, and already run it is a cfun reached through a reference. either way go’s residual is one call.

a self-call never needs any of this. lift-fun binds the function’s own name to a code variable before the body is staged, so recursion residualizes as a call by construction.

Static data still unfolds

(let ((walk (lambda walk (xs n)
              (if (nil? xs) n (walk (cdr xs) (+ n 1))))))
  (clambda f (n) (walk '(1 2 3) n)))

the list is known while compiling, so walk runs three times at staging time and the residual is three additions with no list in it. this is the Futamura direction: a general procedure plus static data becomes a specialised one.