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.