Lift and Run

Part I covered an ordinary Lisp. The two forms in this chapter are the part that is not ordinary, and everything after this chapter is built from them.

lift takes a value and produces code — a program fragment that, when executed, produces that value:

(lift 3)
;=> #<code 1 nodes>
(lift 'a)
;=> #<code 1 nodes>

Code is a value like any other: it can be bound, passed, consed, and inspected. The printer shows only its size — residual programs get large — but the structure is a real expression tree.

run executes code. Its first operand is a stage dispatch, like log’s in Part I; with 0 there, run compiles its second operand and executes the result now:

(run 0 (lift 3))
;=> 3
(run 0 (* (lift 6) 7))
;=> 42

The pair of forms is the language’s entire compiler interface. base.scm gives them one line each in the expression grammar, and the paper’s claim is that they suffice: with lift and run, an interpreter can be turned into a compiler by the language itself, with no compiler infrastructure outside it (Part III does exactly this).

Operations on code residualize

The interesting behaviour is not lift on literals — it is what the rest of the language does when code shows up as an operand. An operation applied to code cannot compute, so it emits itself into the program under construction and hands back code standing for its result:

(+ (lift 1) (lift 2))
;=> #<code 5 nodes>

Nothing was added. Instead, a residual program was built — in this case (let x0 (+ 1 2) x0), five nodes — which performs the addition when it runs:

(run 0 (+ (lift 1) (lift 2)))
;=> 3

Every primitive follows the pattern: car, cons, eq?, the predicates, application itself. Evaluation in the presence of code is code generation; there is no separate staging interpreter, just the same dispatch answering “compute now” for values and “emit” for code.

The lift discipline

Staging is explicit. A plain value does not become code by being near code; it becomes code when lifted, and the boundary shows as soon as a staged construct needs code and finds something else. A staged if — one whose condition is code — must residualize both branches, so both branches must produce code:

(if (lift 1) 'yes 'no)
;! staging error: force-code: expected code, not Sym("yes")

(run 0 (if (lift 1) (lift 'yes) (lift 'no)))
;=> 'yes

Likewise lift of a pair expects the components to be code already — lift reifies one layer, it does not deep-lift:

(lift (cons 1 2))
;! staging error: lift Tup: car must be Code, got Cst(1)

(lift (cons (lift 1) (lift 2)))
;=> #<code 5 nodes>

One convenience softens the discipline, taken from lms-black: the scalar operands of arithmetic and eq? auto-lift when the other side is code — (+ x 2) inside staged code means (+ x (lift 2)):

(run 0 (+ (lift 1) 2))
;=> 3

This keeps stage-oblivious code — code written without knowing whether its inputs are values or code — from erroring on literals. Part III leans on it.

Staging a function

lift of a closure produces a residual lambda (the mechanics are the next chapter’s subject). Compile one and apply it:

((run 0 (lift (lambda _ x (* x x)))) 7)
;=> 49

Recursive functions stage too, provided their bodies respect the lift discipline — here with (lift 0) and (lift 1) marking the constants that must live in the generated program:

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

Twenty-five nodes — finite, although the function is recursive; the next chapter explains why the unfolding stops. It executes as factorial:

((run 0 (lift (lambda fact n
  (if (eq? n (lift 0))
      (lift 1)
      (* n (fact (- n (lift 1))))))))
 5)
;=> 120

code?

(code? d e) tests whether e is code, answering 1 or 0; the first operand is the stage dispatch (when it is code, the test itself residualizes):

(code? 0 (lift 3))
;=> 1
(code? 0 3)
;=> 0

Deferred run

run with a code first operand does not execute — it residualizes the run itself, producing code that will do the running at the next stage:

(run (lift 0) (lift 3))
;=> #<code 5 nodes>

This matters for towers: a level that is itself being compiled must emit its runs rather than perform them. The pattern recurs in Part IV.