Anatomy of a Lisp
A zero-dependency Lisp interpreter in Rust — one homoiconic value, one iterative core, three execution engines. Here is how the pieces fit.
the core idea
One Value enum is both the parsed AST and the runtime value. Four consequences follow — each its own idea.
The parsed syntax tree and the runtime value are the same enum. No node type sits between source and execution.
pub enum Value {
Nil,
Bool(bool),
Int(i64),
Sym(Rc<str>),
Pair(Rc<Cons>),
Closure(Rc<Closure>),
Builtin(BuiltinFn),
}A list is just nested pairs. cons builds one; car and cdr take it apart. Program structure and data structure are the same structure.
;; a list is just nested pairs
(cons 1 (cons 2 (cons 3 '()))) ;; => (1 2 3)
// …and a Pair is two slots:
struct Pair { car: Value, cdr: Value }Because code is data, a macro is just a function from forms to forms. Quasiquote builds the new form and the evaluator runs it.
;; a macro maps forms to forms
(defmacro unless (c body)
`(if ,c nil ,body))
;; (unless done (step))
;; => (if done nil (step))Every heap payload sits behind an Rc, so passing a Value clones a pointer, not a tree.
Pair(Rc<Cons>) // payload behind an Rc
let b = a.clone(); // O(1): refcount++,
// shares the same conshow it fits together
Follow the wires. Source becomes one homoiconic value, and that Value hub is what everything else reads from. Hover any node to light up its internals.
Text → tokens → one Value tree, on an explicit stack that never overflows.
The Value hub feeds the macro expander, the environment, and the evaluator.
The evaluator hands each form to a tree-walker, a bytecode VM, or a JIT.
All three see the same errors, the same builtins, the same prelude.
inside the core
Three components do the real work between source and result. Each runs on an explicit stack, so user-controlled depth never reaches the host call stack.
Text becomes tokens, then one explicit-stack loop folds them into a Value tree. A million-deep nest parses without recursive descent.
struct Frame {
items: Vec<Value>, // gathered so far
wrappers: Vec<Rc<str>>, // pending 'quote
tail: Option<Value>, // after a dot
}
// one loop — never recursive descentScopes are a chain of Rc<RefCell> frames. Lookup walks parents in a loop; a closure captures its defining frame — lexical, not dynamic.
type Env = Rc<RefCell<Environment>>;
fn lookup(env: &Env, name: &str) -> Option<Value> {
let mut cur = env.clone();
loop { // walk parents
if let Some(v) = cur.borrow().vars.get(name)
{ return Some(v.clone()); }
cur = cur.borrow().parent.clone()?;
}
}An explicit-stack CEK machine. The Rust call stack stays three frames deep; nesting lives on a heap Vec<Frame>, so tail calls loop in constant space.
enum St { Eval(Value, Env), Ret(Value) }
fn run_loop(mut st: St, mut stack: Vec<Frame>) {
loop {
st = match st {
St::Eval(e, env) => step_eval(e, env, stack)?,
St::Ret(v) => match stack.pop() {
None => return Ok(v),
Some(f) => step_return(f, v, stack)?,
},
};
}
}three ways to run
The tree-walker, the bytecode VM, and the JIT are interchangeable front-ends over a single evaluator, a single environment model, and a single standard library. Swap the engine; the language does not change.
The reference interpreter and the oracle for differential testing — every other engine is checked byte-for-byte against it.
Compiles to a compact instruction set and runs a tight dispatch loop. Beats CPython 3.14 on loops and arithmetic.
Optional, behind a feature flag. Emits native code through Cranelift and runs 10–23× faster than CPython.
measured
Every program runs on all three engines, and the results must match the tree-walker byte for byte. Speed never costs correctness.
never crashes
User input controls recursion depth, so every part of the core runs on an explicit heap stack instead of the host call stack.
Evaluator, parser, printer, and Drop all run on explicit stacks. A million-deep nest returns an answer where CPython raises RecursionError.
Scopes are Rc<RefCell<Environment>> frames with closure capture, torn down iteratively so deep chains never blow the host stack.
agree() reruns every test on the VM and the JIT and asserts byte-identical output against the tree-walker.
the standard library
A flat native table covers the primitives — checked arithmetic, cons / car / cdr, equality, predicates. Everything else is Lisp, embedded at compile time: fold is tail-recursive, and map and filter are defined in terms of fold, so their recursion lives on the evaluator's heap stack, never the host C stack.
(def fold
(lambda (f acc xs)
(if (null? xs) acc
(fold f (f acc (car xs)) (cdr xs)))))
(def map
(lambda (f xs)
(reverse (fold (lambda (a x) (cons (f x) a)) '() xs))))