Introduction 🐱

narju gismu — x₁ is orange [color] in shade x₂ [medium red-yellow].

The reference implementations of this family of collapsible-tower languages are named Pink and Black. Following that tradition, narju takes its name from the Lojban word for orange — after a handsome orange cat. 🐱

narju is a multi-stage Lisp and a collapsible tower of interpreters. It implements the language of Amin and Rompf’s Collapsing Towers of Interpreters (POPL 2018), a small Lisp — called λ↑↓ in the paper — extended with two staging operators: lift, which turns a value into code that produces it, and run, which evaluates code. Everything else in the system is built out of those two operators.

The system has three layers, and only the first is Rust:

• The floor. A CK-machine interpreter for λ↑↓. Evaluating a program that uses lift produces a program: staging is the language’s compilation mechanism, and there is no other compiler anywhere in the system.
• Pink. A metacircular evaluator for λ↑↓, written in λ↑↓ — and written stage-polymorphically, so the same source text is an interpreter when run directly and a compiler when staged. Staging the interpreter with respect to a program is the first Futamura projection; the book carries the construction through the third.
• Purple. An interactive session running on a tower of such evaluators, where each level interprets the one above and the EM operator lets a program reach down and rebind the machinery of the level interpreting it. Because the levels are stage-polymorphic, the tower collapses: the whole stack compiles down to floor code, and a program modified by EM pays for its modification exactly once.

The title of the paper is a literal description. An interpreter imposes a per-instruction overhead; a tower of interpreters multiplies those overheads together; a tower of stage-polymorphic interpreters can be collapsed by staging until the overhead is gone. The point of narju is to make that construction concrete enough to type at.

Acknowledgments

narju is an implementation of Nada Amin’s language, and this book is an extended commentary on her work. The design follows the paper — Amin and Rompf, Collapsing Towers of Interpreters, POPL 2018, https://doi.org/10.1145/3158140 — and the two reference implementations: namin/pink (Pink and the base language, in Scheme and Scala) and namin/lms-black (the reflective tower, in Scala). Where the book states what “the paper” or “the reference” does, those are the sources meant. Thanks to Nada Amin for the language and for keeping the reference implementations public and readable.

One disclaimer: narju is an independent implementation, and where it deviates from the references — by accident or by necessity — the deviation is narju’s, not the paper’s. Nothing here should be read as authoritative about the reference systems.

How to read this book

The parts are ordered so that no Lisp background is assumed at the start. Part I covers the floor language form by form: values, binding, functions, lists, and the small set of effects. Part II introduces the staging operators and the machinery that builds residual code. Part III builds Pink, the metacircular evaluator, and walks the Futamura projections. Part IV assembles the tower and the Purple session. Part V is reference material: the command-line interface, the library files, and a map into the Rust implementation.

Every example in this book is executed when the book is built. Result lines, marked ;=>, and printed output, marked ;; prints:, are injected by the build from a live narju session — they are not transcribed by hand, and a build whose examples fail is a failed build. Examples within a chapter share a session, so a chapter reads as a transcript.

Getting Started

narju is a single Rust crate. Build and run it with cargo:

$ cargo run --release

or, with nix, nix develop provides the toolchain. The binary is narju.

Two REPLs

Run with no arguments, narju boots the full Purple session: it reads lib/purple.naj, which constructs the Pink evaluator, runs the Futamura projections, and starts a REPL on top of the tower. That session is the subject of Part IV, and it is the more comfortable place to live — it has define, a prelude, and error recovery.

This part of the book is about the language underneath, so it uses the other REPL:

$ cargo run --release -- --raw

--raw skips the Purple boot and drops into the floor REPL — a direct line to the λ↑↓ interpreter, with nothing loaded. Every form you type is parsed, checked, and evaluated by the CK machine; the result is printed with its kind. There is no define here and no prelude: each top-level form is a closed program, and nothing persists from one form to the next except the staging context (Part II) and the cell store (chapter on mutable cells).

Throughout Part I, examples are floor forms. The ;=> line under each form is its value, and ;; prints: lines are its output — both are produced by evaluating the form when this book is built, not written by hand:

(+ 1 2)
;=> 3

The command line

narju                      boot the Purple session (default)
narju --raw                floor REPL, no boot
narju file.naj [more...]   load files, then floor REPL
narju -e '(+ 1 2)'         evaluate an expression, then floor REPL
narju --run file.naj       run a file, print results, exit
narju --script file.naj    run a file silently, exit
narju --purple FILE        boot an alternative Purple script
narju --quiet              suppress the banner

REPL commands

The floor REPL accepts a small set of colon-commands alongside expressions:

:help          show the command list
:q, :quit      exit
:env           list bindings with types and values
:env <name>    inspect one binding
:ctx           show the staging context (fresh counter, block depth)
:load <file>   load a file
:reset         clear the environment and staging context

:ctx will not mean much until Part II; :env will not show much until you load a file, since the floor has no define.

Atoms and Values

The reader is small. Source text is made of parenthesized lists, atoms, comments (; to end of line), and four prefix characters covered in later chapters (', `, ,, ,@). An atom is a maximal run of symbol characters — alphanumerics plus + - * / ? ! < > = _ # . — classified after the fact: the token nil is nil, a token matching -?[0-9]+ is an integer, and anything else is a symbol.

Numbers

Integers are 64-bit and signed. They evaluate to themselves:

42
;=> 42
-7
;=> -7

Booleans are numbers

There is no boolean type. The reader takes #t to the literal 1 and #f to the literal 0, and every predicate in the language answers 1 or 0:

#t
;=> 1
#f
;=> 0
(number? #t)
;=> 1

if (later chapter) treats 0 as false and any other number as true. The practical consequence is that logic is arithmetic — a habit the library code leans on, and one worth acquiring early.

Symbols

A symbol is an interned name. Evaluating one looks it up as a variable, so to get the symbol itself it must be quoted:

'hello
;=> 'hello
'two-words?
;=> 'two-words?

Quotation gets a full treatment in the chapter on pairs and lists; for now, 'x is the datum x, not the value of a variable named x. Note the printer preserves the convention: symbols display with their quote, so what you see can be typed back in.

nil

nil is the empty list, and the terminator of every proper list. It is a distinct value — not a number, not a symbol, and notably not false: if rejects it as a condition. It evaluates to itself:

nil
;=> nil
(null? nil)
;=> 1

The value kinds

Everything a floor program can compute is one of seven kinds of value. Three have appeared already: numbers, symbols, and nil. The rest, with their printed forms, are:

• Pairs, printed (1 2 3) or (1 . 2) — the chapter on pairs and lists.
• Closures, printed #<closure> — the chapter on functions.
• Code, printed #<code N nodes> — a program fragment held as a value, the subject of Part II. N counts expression nodes, since residual programs get too large to print in full.
• Cells, printed #<cell N> — mutable references, the last chapter of this part.

There are no strings, no characters, and no floats. Symbols do the work strings would do elsewhere; the reference implementations make the same economy.

Naming: let

let is the only way to name an ordinary value:

(let name init body)

It evaluates init, binds the result to name, and evaluates body in the extended scope. One binder per let — there is no binding list, so multiple names take nested lets:

(let x 10
  (let y 20
    (+ x y)))
;=> 30

Inner bindings shadow outer ones:

(let x 1
  (let x (+ x 1)
    x))
;=> 2

Names are resolved before evaluation

The parser resolves every name to an environment position at parse time; the evaluator never sees a name, only an index. Two consequences are worth knowing about.

First, an unbound name is a parse error, reported before any part of the form runs:

(let x 1 (+ x y))
;! parse error: unbound variable: y [in list starting with Sym("+")] [in list starting with Sym("let")]

Second, since names are positions, scope is entirely static — a closure captures the environment it was built in, and no later binding can reach into it.

No top-level define

The floor has no define. A let scope closes with its body, and when a top-level form finishes, its bindings are gone:

(let x 42 x)
;=> 42
x
;! parse error: unbound variable: x

Each top-level form is a closed program. This is not an oversight but a division of labour: the floor is the machine the rest of the system is built on, and the interactive conveniences — define, a prelude, a persistent environment — are provided by the Purple session (Part IV), in the language itself. When a floor program needs many definitions in scope at once, it nests lets; lib/mk.naj binds an entire µKanren library around a program that way, seventeen lets deep.

Functions

A lambda takes exactly one argument, and names itself:

(lambda self arg body)

The first symbol is the function’s name for its own body; the second is the parameter. Application is juxtaposition:

((lambda _ x (+ x 1)) 41)
;=> 42

When the self-name is not needed, the convention is to write _ for it — _ is an ordinary symbol, not special syntax, and the convention is inherited from the reference implementation.

Recursion

When a closure is applied, its environment is extended with the closure itself and then the argument, so the body reaches its own function under the self-name. Recursion therefore needs no fixpoint combinator and no top-level definition:

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

fact is in scope only inside the body. This is the language’s whole story about recursion, and it is enough: every recursive function in the system’s libraries — append, map, the Pink evaluator itself — is written this way.

Currying

One argument per lambda means multi-argument functions are curried: a function of two arguments is a function returning a function.

(let add (lambda _ a (lambda _ b (+ a b)))
  ((add 2) 3))
;=> 5

Application sugar makes the call sites bearable: (f a b) reads as ((f a) b), associating left, for any number of arguments.

(let add (lambda _ a (lambda _ b (+ a b)))
  (add 2 3))
;=> 5

There is no corresponding sugar on the binding side — a two-argument function is written as two nested lambdas, and only the outer one can usefully carry a self-name (an inner lambda’s self-name rebinds on every call, capturing the partial application rather than the whole function). The library convention is to name the lambda that drives the recursion and write _ for the rest; lib/prelude.naj is a compact style guide.

Partial application falls out for free:

(let add (lambda _ a (lambda _ b (+ a b)))
  (let increment (add 1)
    (increment 41)))
;=> 42

Closures print as #<closure>:

(lambda _ x x)
;=> #<closure>

Conditionals and Predicates

if is the one branching form:

(if condition then else)

Both branches are always present. The condition must evaluate to a number: 0 is false, anything else is true.

(if 1 'yes 'no)
;=> 'yes
(if 0 'yes 'no)
;=> 'no
(if (- 3 3) 'zero 'nonzero)
;=> 'nonzero

The condition may not be nil, a symbol, or a pair — only numbers branch (and code values, which residualize the if; Part II):

(if nil 'yes 'no)
;! type error in if: expected Cst or Code, got Nil

This is stricter than most Lisps, where anything non-false is true. The discipline is inherited from the reference base.scm, and it composes with the boolean encoding: predicates answer 1 or 0, so predicates are exactly the things if accepts.

The type predicates

Four predicates classify a value by kind, answering 1 or 0:

(number? 3)
;=> 1
(symbol? 'a)
;=> 1
(null? nil)
;=> 1
(pair? (cons 1 2))
;=> 1

Each answers 0 for everything outside its kind — there is no error case:

(number? 'a)
;=> 0
(null? 0)
;=> 0

(A fifth, code?, tests for staged code; it takes an extra stage-dispatch operand and is covered with the rest of the staging forms in Part II.)

eq?

eq? is the equality test, answering 1 or 0. On numbers, symbols, and nil it is the obvious comparison; on pairs it is structural, comparing recursively:

(eq? 'a 'a)
;=> 1
(eq? '(1 (2 3)) '(1 (2 3)))
;=> 1
(eq? '(1 2) '(1 3))
;=> 0

Values of different kinds are unequal, never an error:

(eq? 0 nil)
;=> 0

Closures compare structurally too — two separately written but identical lambdas are eq?. Cells compare by identity: two cells are eq? only if they are the same cell, no matter their contents (see the cells chapter). Code operands do not compare at all — like every operation on code, the eq? residualizes (Part II), which is how generated programs get to contain equality tests.

Testing numbers for equality

There is no = primitive; eq? covers numbers. Library code sometimes exploits the boolean encoding instead — lib/mk.naj defines its own numeric equality as

(let = (lambda _ a (lambda _ b (if (- a b) 0 1)))
  (= 3 3))
;=> 1

reading (- a b) as “true iff a ≠ b”. Arithmetic-as-logic is idiomatic here.

Pairs, Lists, and Quotation

cons builds a pair; car and cdr take it apart:

(cons 1 2)
;=> (1 . 2)
(car (cons 1 2))
;=> 1
(cdr (cons 1 2))
;=> 2

A pair whose second component is another pair, ending in nil, prints as a list:

(cons 1 (cons 2 (cons 3 nil)))
;=> (1 2 3)

An improper tail falls back to dotted notation, as (1 . 2) above. Lists are nothing but this: nil-terminated chains of pairs. car of a list is its first element; cdr is the rest; null? detects the end.

Dotted notation is print-only. . is an ordinary symbol character, so '(1 . 2) does not read back as a pair — it reads as a three-element list whose middle element is the symbol .:

(cdr '(1 . 2))
;=> ('. 2)

Improper pairs are written with cons, never quoted.

car and cdr are for pairs only:

(car 5)
;! type error in car: expected Tup, got Cst(5)

Quotation

Building lists element by element with cons gets old. quote takes a datum — the source text itself, unevaluated — and produces it as a value; 'x is reader shorthand for (quote x):

'(1 2 3)
;=> (1 2 3)
'(a (b c) 4)
;=> ('a ('b 'c) 4)
(car '(a b c))
;=> 'a

Under a quote, symbols are data rather than variable references — which is why 'a is how the symbol a is written, and why quoted structure can mention names that are bound nowhere. This matters more here than in most Lisps: Pink programs are quoted data, and Part III consists largely of handing quoted λ↑↓ source to an evaluator that is itself a floor program.

The empty list is written 'nil in quoted contexts by convention (a quoted nil is still nil):

'nil
;=> nil
(null? 'nil)
;=> 1

Quasiquotation

A quasiquote `datum is a quote with holes. Inside it, ,expr splices the value of expr into the datum:

`(1 ,(+ 1 2) 3)
;=> (1 3 3)
(let x 'mid `(a ,x b))
;=> ('a 'mid 'b)

Everything outside an unquote is data, exactly as under quote. Two reader notes: ,@ (splicing unquote in Scheme) is read as a plain , — there is no list splicing — and in loaded files quasiquote is expanded at read time into plain cons/quote source, so library code can use templates without the evaluator knowing about them (lib/mk.naj is one big quasiquote template over an object program).

The cadr family

cadr, caddr, and cadddr — second, third, fourth element — are surface sugar, rewritten to car/cdr chains before evaluation:

(cadr '(a b c))
;=> 'b
(caddr '(a b c))
;=> 'c

Following the reference implementation’s sug pre-pass, the rewrite applies to the whole source tree including quoted data:

'(cadr x)
;=> ('car ('cdr 'x))

The quoted form arrives as (car (cdr x)) — because Pink source is quoted data, and the Pink evaluator only understands the desugared forms. Sugar that stopped at quotation would leave every quoted program to desugar itself.

Arithmetic

Three operators, all binary, all on 64-bit signed integers:

(+ 2 3)
;=> 5
(- 2 3)
;=> -1
(* 2 3)
;=> 6

There is no division, no modulo, no comparison other than eq?, and no numeric tower — the reference base.scm has exactly these three, and narju follows it. What the set lacks in convenience it recovers in composability with the boolean encoding:

(* (number? 3) (null? nil))
;=> 1

* is conjunction, + (on 0/1 values) is close to disjunction, and (if (- a b) 0 1) is numeric equality, read as “false iff the difference is nonzero”. Ordering comparisons, where needed, are written recursively — count both numbers down together and see which reaches zero first:

(let less?
  (lambda less? a
    (lambda _ b
      (if (eq? b 0) 0
        (if (eq? a 0) 1
          ((less? (- a 1)) (- b 1))))))
  (less? 3 5))
;=> 1

Operators are special forms, not values — + cannot be passed to a function. Where a library needs a first-class operation it wraps one:

(let add (lambda _ a (lambda _ b (+ a b)))
  (add 20 22))
;=> 42

The operands must both be numbers (or code, staging the operation — Part II):

(+ 1 'a)
;! type error in +: expected matching Cst or Code, got (Cst(1), Sym("a"))

Effects

The floor has four effectful primitives: print, read, read-file, and log. All I/O goes through a single boundary — the evaluator owns an I/O implementation, which is a terminal at the REPL and a script harness in tests and in this book’s build. Nothing else in the language touches the world.

print

(print e) writes the value of e and returns nil:

(print (cons 1 (cons 2 nil)))
;; prints: (1 2)
;=> nil

Because the result is nil, print sits in the effect slot of a sequencing let rather than in the middle of an expression — for the latter, log below returns its value.

read

(read prompt) prints the prompt, reads one line from the evaluator’s input, and parses it as a datum — a value, not an expression: no evaluation, no name resolution. End of input and blank lines read as nil. The book’s build harness supplies no input, so here it reaches end-of-input at once:

(read 'ready?)
;=> nil

Under the Purple session this primitive is the REPL: the read–eval– print loop at the top of the tower is a floor program calling read (Part IV).

read-file

(read-file 'path) reads a source file and parses it into a list of forms-as-data — again values, not expressions, one list element per top-level form. The path is a symbol, resolved relative to the process working directory (with $NARJU_LIB as a fallback root, so installed builds find their libraries from anywhere):

(car (car (read-file 'lib/prelude.naj)))
;=> 'define

The first form in the prelude is a define, and its head arrives as the symbol define — plain data. define means nothing to the floor; it is the Purple session that reads this file and decides what to do with each form. read-file is the floor’s entire filesystem: the Pink-level load, the tower boot, and the prelude all come through it.

Because the file is source, the read-time transforms from earlier chapters apply: the cadr family is desugared and quasiquote is expanded before the data reaches the program.

log

(log b v) is a stage-aware debug print: with b a plain value it prints v tagged [log] and — unlike print — returns it, so it can wrap any subexpression without changing the program’s result:

(log 0 'checkpoint)
;; prints: [log] 'checkpoint
;=> 'checkpoint

The first operand is a stage dispatch, a pattern that recurs throughout the staging forms: when b is code, the log is not performed now but residualized — emitted into the program being generated, to run when that program runs. Part II gives this pattern its proper treatment; log is worth meeting early because it is the tool for watching staged programs execute.

Errors

An error aborts the current top-level form: the machine unwinds, the REPL reports, and the next form starts fresh. Part I has already met the main kinds —

• parse errors, including unbound variables, caught before evaluation starts;
• type errors, a primitive applied to the wrong kind of value;
• staging errors, violations of the staging discipline (Part II).

(cdr 'a)
;! type error in cdr: expected Tup, got Sym("a")

throw

(throw v) raises the value of v as an error with a first-class payload — any value, typically a symbol or a structured list saying what went wrong:

(throw 'out-of-cheese)
;! uncaught throw: 'out-of-cheese

The payload rides the unwind intact, which makes throw a signalling mechanism rather than just a panic: a program can throw structured data and something below can take it apart.

catch

The something below is catch. (catch e) evaluates e and returns a tagged list either way: (ok value) if no error escapes, (error payload) if one does — a result the caller can dispatch on with car and eq?:

(catch (+ 1 2))
;=> ('ok 3)
(catch (throw 'boom))
;=> ('error 'boom)
(catch (throw (cons 'unbound (cons 'x nil))))
;=> ('error ('unbound 'x))

A thrown payload arrives structurally. Any other error inside a catch — a type error, say — arrives with its report flattened into a single symbol:

(catch (car 5))
;=> ('error 'type error in car: expected Tup, got Cst(5))

catch exists for one caller: the Purple REPL loop, which wraps each evaluation in it so that a user error prints a message instead of killing the session, and so that a base environment can report an unbound variable loudly as (unbound . name) rather than returning a silent default. It is deliberately minimal — no handler argument, no filtering, no rethrow — and user code is expected to reach for the session-level error handling of Part IV rather than call it directly. The floor takes the same view of catch as of its other effects: provide the smallest primitive the layer above needs, and let the layer above build the ergonomics.

Mutable Cells

Everything so far has been immutable: cons builds a new pair, let binds a name once, and no operation changes a value after it exists. Mutation enters through exactly one door — the cell, a first-class mutable reference:

(cell-new 42)
;=> #<cell 0>

cell-new allocates a cell holding a value; cell-read fetches the current contents; cell-set! replaces them, returning the new value:

(let c (cell-new 0)
  (let _ (cell-set! c (+ (cell-read c) 1))
    (cell-read c)))
;=> 1

(The (let _ effect body) shape is the idiom for sequencing — there is no begin.)

Identity

A cell is a reference: copies alias, and a write through one alias is visible through all. eq? on cells compares identity, not contents — two cells holding the same value are still different cells:

(eq? (cell-new 5) (cell-new 5))
;=> 0
(let c (cell-new 5) (eq? c c))
;=> 1

The printed form #<cell N> shows the cell’s index in the evaluator’s store, which is exactly its identity. The store belongs to the evaluator instance, and persists across top-level forms — the one exception to the rule that nothing outlives a form. A closure over a cell is therefore the floor’s object: state plus behaviour,

(let c (cell-new 100)
  (let counter (lambda _ _ (cell-set! c (+ (cell-read c) 1)))
    (let _ (counter 0)
      (let _ (counter 0)
        (cell-read c)))))
;=> 102

Cells never fold

One rule about cells reaches forward into everything after this chapter: cells never fold under staging. lift of a cell is an error — a residual program cannot capture a live mutable reference as syntax — and staged cell operations always residualize as operations, never evaluate away to the cell’s current contents. A generated program that reads a cell reads it when it runs, not when it was generated.

The rule is why the tower of Part IV works at all: each level of the tower keeps its machinery — its evaluation handlers, its environment — in cells, and a collapsed tower must still see a handler rebinding (via EM) take effect afterward. Fold the cell and the rebinding would be compiled away; keep it a cell and the compiled tower stays honestly reflective. The full mechanics are in Parts II and IV; what to remember from this chapter is that a cell is a promise the compiler keeps.

Floor Reference

Every form the floor understands, in one place. Entries marked staging are covered properly in Part II; they are listed here so the reference is complete. Special forms are recognized by head symbol and arity — a special-form name applied at the wrong arity falls through to ordinary application and, since none of these names is a bound variable, fails as unbound (let is the one exception, with its own arity error). Following the reference implementation, operator names are not values: car can head a form but cannot be passed to a function.

Literals and atoms

Numbers — 42, -7

64-bit signed integers, self-evaluating. Also the boolean encoding: predicates answer 1/0 and if branches on 0/nonzero.

#t, #f

Read-time aliases for 1 and 0. Not distinct values.

nil

The empty list. Self-evaluating; terminates proper lists; not a valid if condition; tested with null?.

Symbols — x, two-words?

A bare symbol is a variable reference, resolved at parse time to an environment position — unbound names are parse errors. A quoted symbol is data. Symbol characters: alphanumerics and + - * / ? ! < > = _ # ..

Comments — ; …

Semicolon to end of line, discarded by the reader.

Binding and control

(lambda f x body)

The unary, self-naming function. f names the closure in its own body (write _ when unused); x names the argument. Application extends the closure environment with the closure itself, then the argument — recursion without a fixpoint operator. Evaluates to #<closure>.

(f a), (f a b …)

Application. Strictly unary; (f a b) is sugar for ((f a) b), associating left. Applying a non-closure is a type error; applying code residualizes (staging).

(let x e body)

Evaluate e, bind the result to x, evaluate body. One binder; nest for more. Also the sequencing idiom: (let _ effect body).

(if c t e)

Branch on a number: 0 false, anything else true. Both branches required; nil and other non-numbers are type errors. A code condition reifies both branches and residualizes the if (staging).

Data

(cons a b) / (car p) / (cdr p)

Build a pair; take its first / second component. car/cdr of a non-pair is a type error. Lists are nil-terminated cons chains, printed (1 2 3), with (1 . 2) for improper tails.

(quote d), 'd

The datum d as a value, unevaluated. Symbols inside are data, not variables.

(quasiquote d), `d, (unquote e), ,e

A quote with holes: ,e inside a template splices the value of e. ,@ is read as plain , — no splicing. In loaded files, quasiquote is expanded at read time into cons/quote source.

(cadr p) / (caddr p) / (cadddr p)

Second / third / fourth element. Surface sugar, rewritten to car/cdr chains over the whole source tree — including quoted data, so Pink source never contains them.

Predicates

(number? e) / (symbol? e) / (null? e) / (pair? e)

Kind tests, answering 1 or 0. Never an error.

(eq? a b)

Equality, answering 1 or 0. Structural on numbers, symbols, nil, pairs, and closures; by identity on cells. Different kinds are unequal. Code operands residualize the comparison (staging); a code operand against a non-scalar raises a stage error.

(code? d e) — staging

1 if e’s value is staged code. d is a stage dispatch: when it is code, the test itself residualizes.

Arithmetic

(+ a b) / (- a b) / (* a b)

Addition, subtraction, multiplication on integers. Binary only; no division. Code operands residualize the operation (staging).

Staging

(lift e) — staging

Reify the value of e as next-stage code: numbers and symbols become literals, pairs of code become cons nodes, closures η-expand into staged lambdas (memoized, so a recursive function lifts to one residual definition). Lifting a cell is an error.

(run b e) — staging

Stage dispatch on b: non-code b compiles e — evaluates it in a fresh scope, expecting code — and immediately executes the result; code b residualizes the run.

(lift-ref name v) — staging

Cross-stage persistence: embed the live value of v in residual code as a reference, not a syntactic copy. With a code first operand, residualizes.

(evalms env-list e) — staging

Evaluate a code value under an explicit environment given as a list of values. The reference base.scm’s evalms, exposed as a primitive; back half of the trans/evalms pipeline the Purple boot uses to animate source-as-data.

(trans e env) — staging

Translate an s-expression value into a code value, resolving names positionally against env — a list of symbols, or (name . code) pairs that splice code in place of a variable. base.scm’s trans as a primitive.

Effects

(print e)

Write the value; return nil. (log is the value-returning variant.)

(read prompt)

Print the prompt, read one input line, parse it as a datum (a value — no evaluation). End of input and blank lines read as nil.

(read-file 'path)

Parse a source file into a list of forms-as-data, one element per top-level form, with read-time transforms (cadr sugar, quasiquote) applied. The floor primitive underneath load and the tower boot.

(log b v) — stage-aware

With non-code b: print v tagged [log], return it. With code b: residualize the log, persisting a non-code v as a cross-stage reference.

Errors

(throw v)

Raise the value of v as an error with a first-class payload. Unwinds to the nearest catch; uncaught, aborts the top-level form.

(catch e)

Evaluate e to a tagged list: (ok value) on success, (error payload) on error. A thrown payload arrives structurally; any other error arrives as a single symbol holding its report. Written for the Purple REPL loop; deliberately minimal.

Cells

(cell-new v) / (cell-read c) / (cell-set! c v)

Allocate a mutable cell / read it / overwrite it (returning the new value). Identity semantics: copies alias, eq? compares identity, printed #<cell N>. Cells never fold under staging: lift of a cell errors, staged cell operations residualize.

No surface syntax

One expression form exists only inside generated code, with no way to write it in source: the cross-stage persisted value (the reference’s proc), produced when staged log or lift-ref embeds a live value in residual code. Residual programs are otherwise ordinary source — which is what lets run execute them and Part III print them.

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.

How Residual Code Is Built

The previous chapter treated code generation as a black box: staged operations “emit themselves”. This chapter opens the box. None of it is needed to use staging, but Part III reads differently once the shape of the generated programs is familiar.

Let-insertion

The generator keeps an open block — a list of statements emitted so far. When an operation residualizes, it does not build an expression tree in place; it appends the operation to the block as a statement and returns a fresh residual variable standing for the result. When the enclosing scope closes, the block is drained into a chain of lets ending in the final expression.

(+ (lift 1) (lift 2)) therefore compiles not to the expression (+ 1 2) but to

(let x0 (+ 1 2)
  x0)

— five nodes, matching the count the printer reported. Every intermediate result gets a name; compound expressions never nest. The output is in administrative normal form (ANF), and the discipline buys two things: generated programs never duplicate work (a shared result is a shared variable, not a recomputed expression), and effects in generated code stay in the order they were emitted, since statement position is evaluation order.

The fresh-variable counter and the open block are the staging state — what base.scm keeps in globals and narju keeps in the evaluator context. The floor REPL’s :ctx command shows both.

Reify scopes

Some constructs need a complete program for a subterm, not a variable into an open block: both branches of a staged if, the body of run, the body of a staged function. These open a reify scope — save the staging state, start an empty block, evaluate the subterm, drain the new block into a let-chain around the result, restore the state. A staged if reifies each branch this way, so branches keep their effects to themselves; run 0 reifies its operand to get the closed program it executes.

Scopes nest arbitrarily — a staged if inside a staged function inside run is three saved-and-restored staging states — and the machine keeps them on its own explicit stack, so nesting depth is bounded by memory, not by the Rust call stack.

Lifting a closure

lift on numbers and symbols makes literals. On a closure there is nothing syntactic to copy — a closure is a captured environment and a body, not source — so lift η-expands: it opens a reify scope, applies the closure to a fresh code variable, and lets the body generate itself. Whatever the body does with an ordinary argument, it now does with code, emitting its operations into the new block; the drained result becomes the body of a residual lambda.

This is the move that makes an interpreter compilable in Part III: the interpreter is a function, functions are lifted by running them on code, and running an interpreter on code is compiling.

Memoization, or why recursion terminates

η-expansion of a recursive function looks like it should diverge: the body of fact contains a call to fact, generating that call re-enters the closure, and so on. The generator memoizes instead — the reference’s stFun registry. Before η-expanding, lift checks whether a structurally identical closure has already been lifted in this scope; if so, it reuses the existing residual definition rather than expanding again.

The recursive call inside fact’s body is a call to the same closure, so the check fires on the first recursion and the unfolding stops at depth one. The result is a single residual lambda that calls itself:

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

as an expression tree, roughly

(lambda f x0
  (let x1 (eq? x0 0)
    (if x1
        1
        (let x2 (- x0 1)
          (let x3 (f x2)
            (let x4 (* x0 x3)
              x4))))))

— the let-chains inside each if branch being the drained blocks of their reify scopes. Matching is structural, following base.scm, so two separately constructed but identical closures reaching different lift sites also share one residual definition.

Residual variables are positions

Generated variables x0, x1, … are, internally, environment indices like every other variable — the names above are for reading. The fresh counter allocates the next index; scope save/restore keeps indices from leaking between reify scopes. A corollary worth knowing: code values are only meaningful within the staging context that made them, and run closes one off into a self-contained program before executing it.

Cross-Stage Persistence

lift turns a value into syntax. Some values should not become syntax — they are too big to copy, or their identity matters, or they exist only in the running system. Cross-stage persistence is the other way for a value to enter generated code: as a reference to the live value, carried inside the residual program.

lift-ref

(lift-ref name v) produces code that, when run, yields the live value of v itself — not a syntactic reconstruction:

(lift-ref 'p (cons 1 2))
;=> #<code 1 nodes>
(run 0 (lift-ref 'p (cons 1 2)))
;=> (1 . 2)

The name operand doubles as the stage dispatch (code there residualizes the lift-ref itself, one stage up). The difference from lift is identity: the persisted value crosses the stage boundary as itself. A pair containing a cell demonstrates it — lift refuses such a value outright, while lift-ref carries the live cell through, still connected to its store:

(let c (cell-new 5)
  (lift (cons c nil)))
;! staging error: lift Tup: car must be Code, got Cell(0)

(let c (cell-new 5)
  (let p (cons c nil)
    (cell-read (car (run 0 (lift-ref 'p p))))))
;=> 5

Inside the expression tree the persisted value sits in the one node with no surface syntax — the reference’s proc (Part I’s reference chapter). Residual programs are otherwise printable source; a persisted value is the exception, a live object riding in the syntax.

Staged log

log persists rather than lifts for the same reason. When log residualizes — code stage dispatch — its value operand may be any value at all, and demanding code there would make the debugging tool unusable in exactly the stage-oblivious code it exists to observe. So a non-code operand is embedded by reference, and the generated program prints it when it runs:

(run 0 (log (lift 0) (cons 1 2)))
;; prints: [log] (1 . 2)
;=> (1 . 2)

The [log] line is printed by the generated program during the run, not by the generator.

What cannot cross: cells

Cells refuse both crossings, in opposite directions, and both refusals protect the same invariant.

A cell cannot be lifted — Part I stated the rule; the reason is that folding a cell’s identity into generated syntax would freeze a reference whose whole point is to be written later:

(lift (cell-new 0))
;! staging error: cannot lift a cell: cells never fold under staging

Staged cell operations residualize instead, so generated code reads and writes cells when it runs, against whatever the store holds then:

(let f (run 0 (lift (lambda _ c (cell-read c))))
  (let c (cell-new 9)
    (f c)))
;=> 9

The compiled function reads the cell at call time — the 9 was written after the function was generated.

In the other direction, code cannot be written into a cell:

(let c (cell-new 0)
  (cell-set! c (lift 3)))
;! type error in cell-set!: expected non-Code value (cells never contain Code), got (Cell, Code(1 nodes))

This is a scope-extrusion guard. A code value is a fragment of a program under construction, full of residual variables that mean something only inside their reify scope; a cell would let it outlive that scope and surface in a program where those variables bind nothing. Cells hold values, never code — which, with “cells never fold”, gives the two-sided rule the tower of Part IV is built on: mutable state stays live, staging works around it, and a compiled tower still sees every write.

A Metacircular Interpreter

Pink is an interpreter for λ↑↓ written in λ↑↓. On its own that is a standard construction — the metacircular interpreter of every Lisp textbook. What Part III shows is what staging does to the construction: because the interpreter is written in a language with lift, the interpreter can be made to compile the programs it interprets, and then to compile itself. This chapter reads the interpreter; the next two stage it.

The chapters in this part use the Purple session (narju at the shell, the default REPL). The session’s own mechanics — define, load, the tower it runs on — are Part IV’s subject; for now it is just the place where the Pink bindings live.

Programs as data, environments as functions

Pink’s programs are quoted s-expressions and its environments are functions from symbol to value. pink-eval takes both:

((pink-eval '(+ 1 2)) nil-env)
;=> 3
((pink-eval '(let x 5 (+ x 1))) nil-env)
;=> 6
((pink-eval '(cons 1 2)) nil-env)
;=> (1 . 2)
((pink-eval '(quote (a b))) nil-env)
;=> ('a 'b)

nil-env is the session’s name for the empty environment, (lambda _ y 0) — every lookup answers 0. The reference implementation uses the same silent zero, which makes an unbound variable indistinguishable from a bound zero:

((pink-eval 'x) nil-env)
;=> 0

Binding forms extend the environment functionally: eval-let wraps the incoming env in a new function that answers the binder’s name and defers everything else. There is no environment data structure to inspect, only a chain of closures.

The interpreted language is the staged core of λ↑↓ — the forms of Parts I and II except cells, throw/catch, and I/O other than log. Recursion needs no special treatment; a recursive function runs as written —

((pink-eval '((lambda f n (if (eq? n 0) 1 (* n (f (- n 1))))) 5)) nil-env)
;=> 120

The shape of the source

The interpreter is one closed expression in lib/pink-forms.naj: a let-chain of named handlers ending in a small dispatch function. Each handler has the same curried signature — it receives tie and eval (explained below), the stage parameter l (next chapter), the expression, and the environment. A representative pair:

(let eval-plus
  (lambda _ tie (lambda _ eval (lambda _ l (lambda _ exp (lambda _ env
    (+ (((eval l) (cadr exp)) env)
       (((eval l) (caddr exp)) env)))))))

(let eval-if
  (lambda _ tie (lambda _ eval (lambda _ l (lambda _ exp (lambda _ env
    (if (((eval l) (cadr exp)) env)
        (((eval l) (caddr exp)) env)
        (((eval l) (cadddr exp)) env)))))))

Each form of the object language is interpreted by the same form of the meta language: Pink’s + is the floor’s +, Pink’s if is the floor’s if. This is the metacircular bargain — the interpreter is short because it inherits the semantics it implements — and it is also, in Part II’s terms, exactly what makes the interpreter stageable: handlers written against ordinary values work unchanged when the values are code.

base-eval is the dispatch: numbers are constants, symbols are variable lookups, and a pair dispatches on its head through a chain of eq? tests to the matching handler. After the special forms comes application. The final expression of the chain ties the knot:

(lambda tie eval
  (lambda _ l
    (lambda _ exp
      (lambda _ env
        (((((base-eval tie) eval) l) exp) env)))))

The self-name tie is the interpreter’s own recursion — every handler’s eval is this function — and it is also the seam at which the interpreter can be replaced (below).

Booting from data

The session gets pink-eval by reading lib/pink-forms.naj as data and animating it with the floor’s trans/evalms primitives (the floor reference lists both): read-file produces the expression as a list, trans translates it to a code value, evalms evaluates that under an empty environment. The interpreter’s source exists exactly once, in that file; the session also keeps it as plain data:

(car pink-poly-src)
;=> 'let

Programs, interpreters, and the sources of interpreters are all the same kind of value — quoted lists — which is the precondition for everything in the Futamura chapter.

Extending the evaluator

delta-eval is a Pink form that runs a subprogram under a modified interpreter. Its first operand evaluates to an extension: a function that receives tie — the unmodified dispatch — and returns a replacement evaluator, deferring to tie for whatever it does not change. An extension that logs every variable lookup:

((pink-eval '(delta-eval (lambda _ tie (lambda _ eval (lambda ev l (lambda _ exp (lambda _ env (if (symbol? exp) (log 0 (((eval l) exp) env)) ((((tie ev) l) exp) env))))))) (let x 3 (+ x x)))) nil-env)
;=> [log] 3
;=> [log] 3
;=> 6

The two [log] lines are the two lookups of x; the sum still comes out. Nothing about the interpreter was anticipated for this — the extension point is just the tie argument every handler already threads. The matcher chapter’s reference implementation uses the same mechanism to build a tracing matcher.

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.

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.

Case Study: the Matcher

The paper’s §3 develops a small regular-expression matcher and stages it. lib/matcher.naj is the port, close to verbatim. It is the first program in this book written for stage polymorphism: one source that is a matcher when interpreted and a matcher generator when compiled.

The source

A regex here is a list of symbols: literals match themselves, _ matches anything, * (postfix) repeats the preceding element, and done ends both regexes and input strings. The matcher is three functions — star_loop, match_here, match — with a free variable maybe-lift wrapped around every created value, in the same positions the Pink evaluator’s handlers use it. The last of the three:

(let match (lambda match r
  (if (eq? 'done (car r))
      (maybe-lift (lambda _ s (maybe-lift 'yes)))
      (maybe-lift (match_here r))))
match)

maybe-lift is free in the source, so matcher-src is not a closed program. The library closes it by splicing text, not by passing a value — matcher takes the source of a maybe-lift and builds a new program around the matcher source:

(define matcher (lambda _ ml `(let maybe-lift ,ml ,matcher-src)))

Interpreting it

With identity as maybe-lift, the closed program is an ordinary matcher. The stages of use: matcher picks the reading, interpret evaluates the program, the result takes a regex, and that takes a string.

(load lib/matcher.naj)
(define m ((interpret (matcher '(lambda _ e e))) nil-env))
((m '(_ * a _ * done)) '(b a done))
;=> 'yes
((m '(_ * a _ * done)) '(b b done))
;=> 'no

The regex (_ * a _ * done) — anything, then an a, then anything — matches (b a done) and rejects (b b done). One m serves every regex; each call to (m r) walks the regex and the string together, interpreting r as it goes.

Compiling it

With (lambda _ e (lift e)) as maybe-lift, applying the matcher to a regex generates a program: the regex walk happens at generation time, and what residualizes is a matcher specialized to that one regex, with the regex constants folded in and no regex left to consult. Per the last chapter’s discipline, the specialization runs inside the run scope (the boot preamble is the one from the Stage Polymorphism chapter):

(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 msrc (cadr (caddr (car (read-file 'lib/matcher.naj))))
(let prog `(let maybe-lift (lambda _ e (lift e)) ,msrc)
(let nil-env (lambda _ y 0)
  (((pink-eval prog) nil-env) '(_ * a _ * done)))))))))
;=> #<code 101 nodes>

A hundred and one nodes for a six-element regex: the two starred elements each became their own residual loop — star_loop unrolled once per star — and the literal comparisons specialized to their symbols. The compiled matcher accepts and rejects the same strings:

(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 msrc (cadr (caddr (car (read-file 'lib/matcher.naj))))
(let prog `(let maybe-lift (lambda _ e (lift e)) ,msrc)
(let nil-env (lambda _ y 0)
(let cm (run 0 (((pink-eval prog) nil-env) '(_ * a _ * done)))
  (cons (cm '(b a done)) (cm '(b b done)))))))))))
;=> ('yes . 'no)

(The two applications share one floor form because floor forms are closed; the pair packages both answers.)

What the case study shows

The evaluator of the previous chapters needed no changes to compile the matcher, and the matcher needed no compiler — only the maybe-lift calls, placed where values are created. That placement is the entire “staging annotation” burden, and it is inherited unchanged from the paper’s matcher.scm. The reference implementation goes one step further and builds a tracing matcher by running the same source under a delta-eval extension (the mechanism from the metacircular chapter) — instrumentation as an interpreter modification, orthogonal to both the matcher and the staging.

Case Study: µKanren

µKanren (Hemann & Friedman, 2013; the bibliography has the citation) is a relational programming language whose complete kernel fits in under forty lines of Scheme. lib/mk.naj is the port of namin/pink’s mk.scm, and it stresses a different part of Pink than the matcher did: higher-order goals, streams represented partly as closures, and a program built by wrapping.

The kernel

The concepts, compressed: a logic variable is a tagged pair (var . n); a substitution is an association list from variables to terms; a state is a substitution paired with a fresh-variable counter; a goal is a function from a state to a stream of states — each state in the stream a distinct way the goal can succeed. Four combinators build every goal: == (unify two terms), call/fresh (introduce a variable), disj (either goal), conj (both goals).

mk is a program→program wrapper in the same style as matcher: it splices an object program into a let-chain that binds the kernel around it —

(define mk (lambda _ program
  `(let = (lambda _ a (lambda _ b (if (- a b) 0 1)))
   (let assp ...
   ...
   (let empty-state (cons 'nil 0)
   ,program
   )))...))

so (mk prog) is closed Pink source in which prog sees ==, call/fresh, disj, conj, and empty-state. (Two renamings from the reference: $-prefixed stream names became st names, since $ is not a symbol character here, and '() is written 'nil.)

Running goals

A goal runs by applying it to empty-state. The simplest one binds a fresh variable to 5:

(load lib/mk.naj)
((interpret (mk '(let p ((call/fresh (lambda _ q ((== q) 5))) empty-state) (car p)))) nil-env)
;=> (((('var . 0) . 5)) . 1)

The first state in the stream: the substitution binds variable 0 to 5, and the counter says one variable exists. The rest of the stream is empty — unification succeeds exactly one way:

((interpret (mk '(let p ((call/fresh (lambda _ q ((== q) 5))) empty-state) (cdr p)))) nil-env)
;=> nil

Disjunction is where streams earn their keep. The reference test suite’s a-and-b goal constrains a to 7 and b to 5 or 6; the stream has one state per way to satisfy it:

((interpret (mk '(let p (((conj (call/fresh (lambda _ a ((== a) 7)))) (call/fresh (lambda _ b ((disj ((== b) 5)) ((== b) 6))))) empty-state) (car p)))) nil-env)
;=> (((('var . 1) . 5) (('var . 0) . 7)) . 2)
((interpret (mk '(let p (((conj (call/fresh (lambda _ a ((== a) 7)))) (call/fresh (lambda _ b ((disj ((== b) 5)) ((== b) 6))))) empty-state) (car (cdr p))))) nil-env)
;=> (((('var . 1) . 6) (('var . 0) . 7)) . 2)

First state: b is 5. Second: b is 6. Both carry the a-to-7 binding and a counter of two. Streams are not always fully-built lists — mplus and bind suspend work behind zero-argument closures when a stream’s tail is not yet demanded, which is what lets µKanren enumerate answers from infinite relations.

Through the compiler

(mk prog) is a program like any other, so the whole Futamura pipeline of this part applies to it unchanged. Compiling the wrapped goal — kernel and all — produces the same first state as interpreting it:

(compile (mk '(let p ((call/fresh (lambda _ q ((== q) 5))) empty-state) (car p))))
;=> (((('var . 0) . 5)) . 1)

The residual is the program itself in ANF — the collapse property again — and compile’s run 0 executes it, so the printed value is the finished state rather than a function. Compiling a goal into a reusable compiled artifact needs the goal kept behind a function boundary, and choosing where that boundary sits under staging is exactly what clambda is for, in Part IV.

The Purple Session

narju with no flags does not start the floor REPL. It boots the Purple session: an interactive environment that is itself a program — lib/purple.naj, one closed floor expression that constructs everything in Parts I–III at startup and ends in a read-eval-print loop. The purple blocks throughout this book are transcripts of that loop. This chapter is about the session as a user sees it; the next chapter opens the machinery.

Session state

A floor program is one closed expression; there is no floor-level define. The session has one:

(define x 42)
x
;=> 42
(set! x 43)
;=> 'x
x
;=> 43

define binds a name for the rest of the session and prints nothing on success. set! mutates an existing binding and returns the name. Neither is a floor form — the session’s environment is a frame of mutable cells, and define splices a new cell into it. The primitives are bound without cells and cannot be reassigned:

(set! + 9)
;=> ('set-immutable . '+)

Two syntaxes

The session evaluator accepts the floor forms of Part I unchanged — self-named unary lambda, one binder per let:

(let y 5 (+ y 1))
;=> 6
((lambda f n (if (eq? n 0) 1 (* n (f (- n 1))))) 5)
;=> 120

and alongside them the multi-parameter forms of the reference tower (lms-black), plus begin:

((lambda (a b) (+ a b)) 1 2)
;=> 3
(let ((a 1) (b 2)) (+ a b))
;=> 3
(begin (define tries 0) (set! tries (+ tries 1)) tries)
;=> 1

The evaluator tells them apart by shape: a symbol in the parameter or binder position means the floor form, a list means the lms-black form. Both produce the same kind of closure.

Errors

The session’s base environment raises ('unbound . name) where Pink’s nil-env answers a silent 0, so a typo is an error rather than a wrong number. The loop prints each form’s result through catch, so an error is a printed payload and the session continues:

zzz
;=> ('unbound . 'zzz)
(+ 1 2)
;=> 3

The prelude

lib/prelude.naj is loaded at boot: append, map, assoc, length, reverse, all curried in the floor style (the Prelude chapter in Part V has one entry per function):

((append '(1 2)) '(3 4))
;=> (1 2 3 4)
((map (lambda (n) (* n n))) '(1 2 3))
;=> (1 4 9)
(reverse '(1 2 3))
;=> (3 2 1)

load

(load lib/matcher.naj) evaluates a file’s forms into the session. The path is a bare symbol, not quoted — the loop treats load and define as commands, taking their arguments as unevaluated data and printing nothing on success. The matcher and µKanren chapters both start this way.

What boots

lib/purple.naj is a let-chain. In order, it:

1. reads lib/pink-forms.naj as data and animates it with trans/evalms (the boot from the metacircular chapter), producing pink-eval and pink-evalc;
2. runs the second and third Futamura projections — compiler and evalc-compiled are compiled at every boot, which is what the banner’s “running futamura projections” refers to;
3. binds the helpers of Part III: compile, run-compiled, interpret, load-into;
4. reads lib/tower.naj as data and animates it the same way, then builds one meta level and one global environment from it — the session;
5. installs the Pink bindings of steps 1–3 into the session environment as cells (the full list is in Part V’s session-bindings chapter);
6. loads the prelude and enters the loop.

The loop itself sits at the end of the file: read a datum; load and define are handled as above; anything else is evaluated through the tower and printed through catch. Programs, interpreters, compilers, and the session that serves them are all values built by one floor expression — the tower that expression builds is next.

The Tower

The session evaluator of the last chapter lives in lib/tower.naj, narju’s port of the reflective tower in namin/lms-black (eval.scala; the file’s comments carry the correspondence, structure by structure). Like lib/pink-forms.naj it is one closed floor expression, read as data at boot and animated with trans/evalms; it evaluates to a selector function exporting five names, of which the session uses make-level, make-env, env-define, and ev (clambda-code waits for the clambda chapter, and Part V’s tower-API chapter lists everything precisely).

A reflective tower is the answer to a question about interpreters: the session’s programs run under an evaluator — what does that evaluator run under? In the tower, another copy of itself, and so on upward: level 0 is the program at the prompt, level 1 the interpreter evaluating it, level 2 the interpreter evaluating that. The construction is only useful if a program can reach the levels above it — that is EM, next chapter — and only affordable if the infinite regress costs nothing until it is reached for.

Handlers as environment entries

Each level is a pair m = (menv . slot): an environment for the level’s own machinery, and a lazy slot for the level above. The environment’s one frame holds the evaluator itself, split into fifteen named handlers — base-eval, eval-var, eval-lambda, eval-clambda, eval-let, eval-cst, eval-if, eval-begin, eval-set!, eval-define, eval-quote, eval-EM, eval-application, eval-list, base-apply — each boxed in a mutable cell, followed by the eleven primitives (+ through pair?), bound directly without cells.

Evaluating an expression at level 0 means: look up base-eval in level 1’s frame and apply what the cell currently holds. base-eval dispatches on the expression’s shape and looks up the matching handler the same way. The evaluator is therefore not code but environment state — rebinding eval-var in level 1’s frame changes what variable lookup means for every level-0 program evaluated afterward. That is the entire mechanism EM exploits.

Handlers are values, and the session can ask for one:

(EM eval-var)
;=> ('fn . #<closure>)

('fn . …) is the tower’s tag for a native function — a floor closure obeying the handler calling convention. All fifteen boot handlers are natives, which is what stops the regress: dispatching through a native handler is a direct floor call, no level-2 interpretation required. Only when a handler cell is rebound to an interpreted closure does the level above start doing real work — and level 2 is only constructed (the lazy slot filled) the first time something reaches for it.

Values and environments

The tower’s values are the floor’s numbers, symbols, nil, and pairs, plus four tagged shapes: ('clo params body env . m) for interpreted closures — note the closure records the meta level it was made under, which the clambda chapter makes consequential — ('prim . name), ('fn . fc) for natives, and ('cont . k) for continuations. Floor values that are none of these (the Pink evaluators installed at boot, nil-env, the prelude’s closures) pass through untagged and apply natively, one forced argument at a time — which is why Pink currying like ((pink-eval src) env) works unchanged at the prompt.

An environment is a list of frames; a runtime frame is a cell holding an association list, so define can extend it in place. Mutable bindings are themselves cell-boxed, (name . ('cell . c)); the primitives sit in the frame unboxed. The distinction is a staging decision as much as a mutability one: a read through a cell is an effect the compiler must preserve, a read of an unboxed binding is a constant it can fold. Compiled code keeps its dependence on the session’s cells and constant-folds the primitives away.

Evaluation, concretely

The handlers are written in continuation-passing style — every handler receives an expression, an environment, and a continuation, mirroring lms-black. Threaded through all of it is one more parameter: l, a stage dictionary in exactly the sense of Pink’s maybe-lift, grown to a vocabulary of nine operations (lift, force, cell read/write/new, apply, and friends). At the prompt ev passes the concrete dictionary — identity lifts, real cell operations, real application — and the tower is an ordinary, if elaborately indirect, interpreter:

(+ 1 2)
;=> 3
((lambda (a b) (* a b)) 6 7)
;=> 42

Handing the same handlers a staged dictionary instead turns the tower into a compiler, closure by closure. That is clambda, two chapters from here; EM, the reason the handlers sit in cells at all, comes first.

EM

EM — execute at the meta level, the name inherited from Black by way of lms-black — evaluates its argument one level up: in the environment of the interpreter that is running the current level.

(EM 42)
;=> 42
(EM (+ 1 1))
;=> 2

Nothing interesting so far — level 1 has the same primitives. The difference is where names live:

(EM (define counter 0))
;=> 'counter
counter
;=> ('unbound . 'counter)
(EM counter)
;=> 0
(EM (EM counter))
;=> ('unbound . 'counter)

counter exists at level 1 only. Level 0 does not see it, and neither does level 2 — each level’s environment is its own. (EM at the prompt is an ordinary form, so its result prints; define returns the defined name.) The levels continue upward on demand — the first EM is what materializes level 2, per the last chapter’s lazy slot, and a nested EM reaches it:

(EM (EM (define deep 7)))
;=> 'deep
(EM (EM deep))
;=> 7
(EM deep)
;=> ('unbound . 'deep)

The interpreter is in scope

Level 1’s environment is not empty when the session starts: it is the frame the handlers live in. (EM (define counter 0)) put counter in the same association list as eval-var — so at level 1, the running interpreter’s parts are ordinary variables, and set! on them is interpreter surgery. This is the tower’s payoff, and the rest of the chapter is one worked example: counting variable lookups, following the instrumentation examples of the lms-black test suite.

An interpreted handler receives the three arguments the dispatch passes: the expression, the environment, and the continuation. The replacement below counts lookups of the name n and defers everything — including the lookup itself — to the saved original:

(define fib (lambda (n) (if (eq? n 0) 1 (if (eq? n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))))
(fib 5)
;=> 8
(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

Thirteen: (fib 3) calls fib at n = 3, 2, 1, 1, 0, and the body reads n four times per recursive call ((eq? n 0), (eq? n 1), (- n 1), (- n 2)), twice when the second test succeeds, once when the first does — 4+4+2+2+1. fib itself was not touched, or even re-evaluated; the meaning of variable lookup changed under it.

There is a cost, and it is the tower made visible: the replacement handler is an interpreted closure at level 1, so while it is installed, every level-0 variable lookup is interpreted by level 2’s handlers rather than dispatched natively. Restoring the original restores native dispatch:

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

The counter stands still — fib runs under the stock interpreter again. Rebinding a handler affects evaluation while it is bound, and interpreted code always reads the current handler cell. What happens to code that was compiled while the counting handler was installed is a different question, and the next chapter’s central one.

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.

CLI and REPL Commands

Invocation

narju                          boot the Purple session (default)
narju --raw                    floor REPL, no Purple boot
narju file.naj [file2.naj …]   load files into the floor, then floor REPL
narju -e '(+ 1 2)'             evaluate an expression, then floor REPL
narju --run file.naj           run a file, print each form's result, exit
narju --script file.naj        run a file silently, exit
narju --purple FILE            boot an alternate session script
                               (default: lib/purple.naj)
narju --quiet / -q             suppress the banner

-e repeats, and combines with positional files (files load first). --run and --script exclude positional files and each other.

Two path facts worth knowing. read-file — and therefore load, (load …) in the session, and the Purple boot itself — resolves paths against the process’s working directory first, and retries relative paths under $NARJU_LIB when that variable is set. A repository checkout needs no variable: run from the root, where lib/pink-forms.naj, lib/tower.naj, and lib/prelude.naj are reachable directly. The nix package bakes NARJU_LIB into the binary, pointing at its own copies, so an installed narju boots from any directory — while a user’s own relative paths keep taking precedence. And --purple names a floor program, not a configuration file: anything --script could run can be a session.

The floor REPL

--raw, positional files, and bare -e all end in the floor REPL: one λ↑↓ form per evaluation, results printed with their kind, line editing with history (~/.narju_lud_history), filename completion, and history search on Alt-p/Alt-n. A line may contain several forms; each is evaluated and printed in order.

Commands start with a colon:

:help          this list
:q, :quit      exit
:env           all bindings, with kinds and values
:env <name>    one binding
:ctx           staging context: fresh-name counter, block depth
:load <file>   load a file into the current environment
:reset         clear the environment and the staging context

:ctx and :reset concern the staging state of Part II: residual code built at the top level draws fresh variable names from a counter that persists across forms, and :reset is the way to zero it without restarting.

The Purple loop

The session prompt is not the Rust REPL — it is the let-bound loop at the end of lib/purple.naj, reading data through the floor’s read. It has no colon commands; load and define are recognized as data (the session chapter covers both), everything else is evaluated and printed. End of input — Ctrl-D at a terminal — ends the loop, and with it the process.

The Prelude

lib/prelude.naj is loaded into the Purple session at boot. Five list functions, written in pure λ↑↓ — unary lambdas, so multi-argument functions are curried, and the empty list is 'nil. Nothing here is special-cased: each is an ordinary defined binding, visible with the rest of the session state.

((append xs) ys)

The concatenation of two lists:

((append '(1 2)) '(3 4))
;=> (1 2 3 4)
((append 'nil) '(a b))
;=> ('a 'b)

((map f) xs)

The list of (f x) for each element:

((map (lambda (n) (* n n))) '(1 2 3))
;=> (1 4 9)

f may be any applicable value — a session closure as here, a floor closure, a curried prelude function.

((assoc k) alist)

The first pair in alist whose car is k, or nil:

((assoc 'b) '((a 1) (b 2)))
;=> ('b 2)
((assoc 'z) '((a 1) (b 2)))
;=> nil

Note the result is the whole matching pair, not its value, and that the alist here is a list of two-element lists — recall from Part I that dotted pairs cannot be written under a quote.

(length xs)

(length '(a b c))
;=> 3
(length 'nil)
;=> 0

(reverse xs)

(reverse '(1 2 3))
;=> (3 2 1)

Accumulator-based, so linear in the list.

Purple Session Bindings

The boot installs fourteen bindings into the session environment before the prelude loads — the Pink machinery of Part III, made available at the prompt. They fall into four groups.

Sources

Programs as data, exactly as read or spliced at boot:

• pink-poly-src — the contents of lib/pink-forms.naj: the stage-polymorphic evaluator as one expression.
• pink-tie-src — pink-poly-src wrapped with the knot-tying lambda; takes an l pair.
• pink-eval-src — pink-tie-src applied to the identity lift, as source.
• pink-evalc-src — pink-tie-src applied to the real lift, as source.

(car pink-poly-src)
;=> 'let

Evaluators

The same four, animated:

• pink-poly — the evaluator awaiting its own recursion (tie).
• pink-tie — the knot tied; takes an l pair, gives an evaluator.
• pink-eval — ((pink-eval src) env) interprets src.
• pink-evalc — the compiling reading; applications of it must be enclosed by the run that scopes their generated code (the Futamura chapter’s discipline).

((pink-eval '(car '(a b))) nil-env)
;=> 'a

Futamura artifacts

Compiled at every boot:

• compiler — pink-eval compiled by pink-evalc (the second projection): an evaluator with the interpretive overhead removed, used exactly like pink-eval.
• evalc-compiled — pink-evalc compiled by itself (the third projection): the compiler as a compiled artifact.

((compiler '(+ 1 2)) nil-env)
;=> 3

Helpers

• nil-env — the empty Pink environment, (lambda _ y 0): every lookup answers 0.
• ((interpret src) env) — pink-eval, spelled as a verb.
• (compile src) — (run 0 ((evalc-compiled src) nil-env)): compile a closed program and execute the residual, all inside one run scope.
• (run-compiled anf) — (run 0 anf) for code compiled within the same scope; code generated loose at the prompt dangles, per the Futamura chapter.

((interpret '(+ 1 2)) nil-env)
;=> 3
(compile '(* 6 7))
;=> 42

The prelude’s five functions (previous chapter) arrive on top of these, and load/define are loop forms, not bindings. Two more names exist in lib/purple.naj but are boot-internal, not installed: load-into, a Pink-path loader that folds a file’s define forms into an environment-as-function, and tower-load, the loader behind the loop’s load.

The Tower API

lib/tower.naj evaluates to a selector function over five exports. The session uses four of them at boot; all five are available to any floor program that animates the file:

(let tower (evalms nil (trans (car (read-file 'lib/tower.naj)) nil))
(let m ((tower 'make-level) 0)
(let env ((tower 'make-env) 0)
(((((tower 'ev) m) env) '(+ 1 2))))))
;=> 3

Exports

• ((T 'make-level) 0) — construct a meta level: a pair (menv . slot) whose environment holds a fresh set of handlers and whose slot lazily yields the level above.
• ((T 'make-env) 0) — a fresh object-level global environment: one mutable frame holding the primitives.
• (((T 'env-define) env) name) then applied to a value — extend a global environment’s first frame with a cell-backed binding. This is the hook lib/purple.naj uses to install the session bindings.
• ((((T 'ev) m) env) exp) — evaluate exp in env, dispatched through meta level m, at the concrete stage.
• (((T 'clambda-code) m) e) applied to r — the reified residual of a clambda expression e in environment r: code for a stage-polymorphic function, before any run. The clambda handler is this plus run 0; the export exists so the staging of the tower can be inspected without executing it.

Value representations

Floor values outside these shapes (Pink evaluators, nil-env, floor closures generally) apply natively to one forced argument, so curried floor code runs through the tower unchanged. Numbers, symbols, and nil in function position throw ('cannot-apply . v).

Environments

An environment is a list of frames. A runtime frame is a cell over an association list — define extends it in place; a plain list in frame position is a staging-time frame (introduced during clambda compilation, matching lms-black’s inRep environments). Bindings are (name . ('cell . c)) when mutable; the primitives are bound direct, cell-less, so staged reads of them constant-fold.

The meta frame

A level’s environment holds fifteen handlers, each an ('fn . fc) boxed in a cell so EM can set! it:

base-eval          dispatch on expression shape
eval-var           variable lookup
eval-lambda        both lambda shapes (lms-black and floor/pink)
eval-clambda       compile-at-definition (see the clambda chapter)
eval-let           both let shapes
eval-cst           cst: let over direct (cell-less) bindings; staged reads fold
eval-if            three-armed if
eval-begin         sequencing
eval-set!          assignment (throws set-immutable on cell-less bindings)
eval-define        first-frame extension
eval-quote         quotation
eval-EM            evaluate one level up (materializes it if needed)
eval-application   evaluate operator and operands, then base-apply
eval-list          evaluate a list of expressions
base-apply         apply an object value

followed by the eleven primitives, direct: + - * eq? cons car cdr number? symbol? null? pair?.

A handler installed with EM (set! …) receives three arguments — the expression, the environment, and the continuation — and usually ends by deferring to the saved original, as in the EM chapter.

The stage dictionary

Every handler threads l, a selector over nine operations: staged (0 or 1), lift, force, cread/fread (cell read, dread-preserving and forced), cset, cnew, app (dynamic apply), appk (apply a continuation). The concrete dictionary — identity lift and force, real cell operations, real application — makes ev an interpreter. make-staged-dict builds the compiling dictionary used under clambda: pure values lift, cell operations and dynamic applications emit residual code routed through the dictionary the compiled function will receive at run time. Handler dispatch itself is always concrete; only dictionary operations mark where staging residualizes.

The Matcher and µKanren Libraries

Reference entries for the two case-study libraries of Part III. Both load into the session with the loop’s load, and both are ports of examples in namin/pink.

lib/matcher.naj

Two bindings:

• matcher-src — the matcher as open source: three functions (star_loop, match_here, match) with maybe-lift free.
• (matcher ml) — the closed program: maybe-lift bound to the source text ml, wrapped around matcher-src.

The regex language: a list of symbols; a literal matches itself, _ matches any symbol, a postfix * repeats the preceding element, and done terminates both regexes and inputs. Match results are 'yes and 'no.

Interpreting reading — '(lambda _ e e) as the maybe-lift:

(load lib/matcher.naj)
(define m ((interpret (matcher '(lambda _ e e))) nil-env))
((m '(a _ * done)) '(a b c done))
;=> 'yes
((m '(a _ * done)) '(b done))
;=> 'no

Compiling reading — '(lambda _ e (lift e)), with the application to the regex kept inside the run scope; the matcher case study has the full recipe and the residual-size discussion.

lib/mk.naj

One binding:

• (mk program) — program spliced into a let-chain binding the µKanren kernel around it. The result is closed Pink source for interpret or compile.

Names the wrapped program sees: =, assp, var, var?, var=?, walk, ext-s, mzero, unit, unify, ==, call/fresh, mplus, bind, disj, conj, empty-state.

Conventions, all curried:

• a goal applied to a state yields a stream of states: (g empty-state);
• ((== a) b) unifies two terms; (call/fresh (lambda _ q g)) introduces a variable; ((disj g1) g2) and ((conj g1) g2) combine;
• a state is (substitution . counter); a logic variable is ('var . n); a substitution is an association list from variables to terms.

(load lib/mk.naj)
((interpret (mk '(let p ((call/fresh (lambda _ q ((== q) 5))) empty-state) (car p)))) nil-env)
;=> (((('var . 0) . 5)) . 1)

Deviations from the reference mk.scm: $-prefixed stream names became st names ($ is not a symbol character here), and the empty list is written 'nil. Streams may suspend their tails behind zero-argument closures (mplus/bind), so forcing a stream position may require applying it — the case study shows both states of a disjunction being drawn out.

Architecture: the Rust Floor

Everything above the floor is .naj source: Pink is lib/pink-forms.naj, the tower is lib/tower.naj, the session is lib/purple.naj. The floor itself is a Rust crate, and this chapter is a map into its API documentation — build it with cargo doc --no-deps (or nix build .#docs) and start at the crate page, which carries the same three-layer picture this book does.

Modules

• core — the data. Exp is the expression tree over de Bruijn levels; Val is the runtime value: numbers, symbols, pairs, closures, cells, and Code — staged expressions are values like any other, which is half of what Part II rests on.
• parse — reader, surface desugaring (sug, the cadr family), quasiquote expansion for loaded files, and lowering of names to de Bruijn levels, where n-ary applications curry left-to-right. Unbound names fail at lowering, before any evaluation.
• eval — the machine. evalms drives a CK-style interpreter (an explicit continuation stack rather than host recursion), with the staging state — fresh-name counter, residual block accumulation — in EvalCtx. The staging submodule is the reflection surface the upper layers boot through: the trans and evalms primitives that turn read data into running code.
• io — the NarjuIo boundary. Terminal I/O for interactive use; HeadlessIo for embedding, tests, and this book.
• repl — TopLevel, the parse→lower→evaluate driver, and the interactive floor REPL built on it.
• error, colours — error values (Part I’s catchable payloads) and terminal colour constants.

The crate embeds cleanly: construct a TopLevel with TopLevel::with_io(Box::new(HeadlessIo::…)), feed it forms, read the printed output back from the shared sink. The test suite drives whole Purple sessions this way.

How this book’s examples run

The book is built by mdbook with a custom preprocessor, mdbook-narju — a second binary in the same crate, linked against the library. At build time it walks every chapter and executes the fenced code blocks:

• narju blocks are floor forms, evaluated in order against a per-chapter floor session;
• narju,error blocks must fail, and their error text is captured;
• purple blocks are prompt inputs; all the purple blocks of a chapter are fed to one Purple session, booted from lib/purple.naj through a scripted NarjuIo;
• the ;=>, ;; prints:, and ;! lines in the rendered book are the captured outputs, injected into the markdown.

A block that errors (or an error block that succeeds) fails the build. Every output shown in this book was produced, at the moment the book was built, by the same binary the book documents.

Bibliography

• Nada Amin and Tiark Rompf. Collapsing Towers of Interpreters. Proceedings of the ACM on Programming Languages, volume 2, POPL, article 52, 2018. https://doi.org/10.1145/3158140. The paper narju implements: the base language λ↑↓, Pink, and the collapsible reflective tower.
• namin/pink. Reference implementation of the base language and Pink, in Scheme (base.scm, pink.scm) and Scala. narju’s floor semantics and the metacircular evaluator in lib/pink-forms.naj follow it.
• namin/lms-black. Reference implementation of the stage-polymorphic reflective tower, in Scala. narju’s tower (lib/tower.naj) and Purple session follow it.
• Jason Hemann and Daniel P. Friedman. µKanren: A Minimal Functional Core for Relational Programming. Scheme and Functional Programming Workshop, 2013. The source of lib/mk.naj, ported by way of the mk.scm example in namin/pink.
• Yoshihiko Futamura. Partial Evaluation of Computation Process — An Approach to a Compiler-Compiler. Systems, Computers, Controls, 2(5), 1971. The projections carried out in Part III.