Crate narju 

narju — a multi-stage Lisp and collapsible tower of interpreters.

narju implements the language of Amin & Rompf, Collapsing Towers of Interpreters (POPL 2018, https://doi.org/10.1145/3158140), following the reference implementations in namin/pink and namin/lms-black. The system is built in three layers, only the first of which is Rust:

• The floor: λ↑↓. This crate. A CK-machine interpreter for the paper’s base language — a small Lisp with two staging operators, lift (turn a value into code that produces it) and run (evaluate code). 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. lib/pink-forms.naj defines a metacircular evaluator for λ↑↓ in λ↑↓, written stage-polymorphically: the same source 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 tests carry it through the third.
• Purple. lib/purple.naj boots an interactive session on top of a tower of such evaluators (lib/tower.naj), where each level interprets the one above and EM 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.

Module map

• core — the data: expression trees (core::Exp) and runtime values (core::Val).
• parse — reader, surface desugaring, and lowering of names to de Bruijn levels. Unbound names fail here, not at runtime.
• eval — the machine: a CK-style evaluator (eval::evalms / eval::evalmsg) with the staging state in eval::EvalCtx, plus the trans/evalms reflection surface in its staging submodule.
• io — the I/O boundary (io::NarjuIo): terminal or scripted.
• repl — repl::TopLevel, the parse→lower→evaluate driver, and the interactive REPL built on it.
• error — the crate-wide error type (error::NarjuError).
• colours — ANSI colour constants for the REPL surface.

The .naj sources under lib/ are part of the system in the same sense the Rust is: prelude.naj (list utilities), pink-forms.naj (the metacircular evaluator), purple.naj (the session boot), tower.naj (the reflective tower), and matcher.naj / mk.naj (worked examples: a pattern matcher and a µKanren).

Embedding

Drive a session through repl::TopLevel with a scripted I/O implementation. repl::TopLevel::new requires a real terminal and panics without one; everything non-interactive goes through repl::TopLevel::with_io:

use narju::io::headless::HeadlessIo;
use narju::repl::TopLevel;

let mut top = TopLevel::with_io(Box::new(HeadlessIo::empty()));
let results = top.run_str("(+ 1 2) (car '(a b))").unwrap();
assert_eq!(results[0].display(), "3");
assert_eq!(results[1].display(), "'a");

Modules

colours

Terminal colour constants for narju.

core

Core data types: expressions (Exp), values (Val), and environments (Env).

error

The crate-wide error type.

eval

The evaluator: staging state (EvalCtx), the lift operator, and the entry points evalms / evalmsg.

io

The I/O boundary between the evaluator and the outside world.

parse

S-expression reader and name-resolution lowering to Exp.

repl

Top-level runner: parse → lower → evaluate.