narju/

lib.rs

//! 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](https://github.com/namin/pink) and
//! [namin/lms-black](https://github.com/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`]:
//!
//! ```rust
//! 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");
//! ```

#![deny(missing_docs)]
#![warn(clippy::missing_docs_in_private_items)]

pub mod colours;
pub mod core;
pub mod error;
pub mod eval;
pub mod io;
pub mod parse;
pub mod repl;