narju/core/

mod.rs

//! Core data types: expressions ([`Exp`]), values ([`Val`]), and
//! environments ([`Env`]).
//!
//! The floor language is λ↑↓ as defined by base.scm in namin/pink
//! (Amin & Rompf, *Collapsing Towers of Interpreters*, POPL 2018): a
//! unary lambda calculus with pairs, staging operators, and a small set
//! of effects. The representation is nameless — the parser resolves
//! every identifier to an environment slot, so variables are
//! [`Exp::Var`] indices and binders carry no names. This module holds
//! only the data: the CK machine that evaluates it lives in
//! [`crate::eval`], the reader in [`crate::parse`].

use std::fmt;
use std::rc::Rc;

use smol_str::SmolStr;

// ── Shared reference types ────────────────────────────────────────────────────
//
// All `Exp` operator children are `RcExp = Rc<Exp>` rather than `Box<Exp>`
// so that cloning is O(1) (a ref-count bump) rather than a deep tree copy.
//
// This matters because the CK machine threads sub-expressions through
// `Cont` variants (e.g. `BinOpRight { e2: RcExp }`) and `Mode::Eval`,
// each of which needs to take an owned `Exp` out of a `&Exp` match.
// With `Box`, that meant `*e.clone()` — a full subtree clone per
// dispatch. With `Rc`, it's `Rc::clone(e)` — pointer-bump per dispatch.
//
// `Lam` body: shared across all closures created from the same `Lam` node,
//             enabling O(1) pointer-equality in `find_fun` during staging.
// `Code` body: shared as staged code values are threaded through staging.
// `Tup` arms: Pink source lists (pink-eval-src etc.) are traversed many
//             times; sharing makes car/cdr O(1) rather than deep-cloning.

/// Shared expression node. See the note above on why `Rc` and not `Box`.
pub type RcExp = Rc<Exp>;
/// Shared value node.
pub type RcVal = Rc<Val>;

// ── Constructor helpers ───────────────────────────────────────────────────────

/// Wrap an expression as a shared child node.
#[inline] pub fn rc_exp(e: Exp) -> RcExp { Rc::new(e) }
/// Wrap a value as a shared child node.
#[inline] pub fn rc_val(v: Val) -> RcVal { Rc::new(v) }

/// Cons two values into a [`Val::Tup`] pair.
#[inline] pub fn tup(a: Val, b: Val) -> Val {
    Val::Tup(rc_val(a), rc_val(b))
}
/// Wrap an expression tree as a [`Val::Code`] staged-code value.
#[inline] pub fn code(e: Exp) -> Val {
    Val::Code(rc_exp(e))
}

// ── Expression type ───────────────────────────────────────────────────────────

/// A floor expression, after parsing and sugar expansion.
///
/// Each variant's doc gives the surface syntax it corresponds to;
/// variants with no surface syntax ([`Exp::Proc`], [`Exp::Catch`]) say
/// so. A common pattern throughout: primitives dispatch on whether
/// their operands are plain values or staged [`Val::Code`] — the value
/// case computes now, the code case emits a copy of the operation into
/// the residual program being built (see [`crate::eval::machine`]).
#[derive(Debug, Clone, PartialEq)]
pub enum Exp {
    /// Integer literal. Booleans share this encoding: the reader takes
    /// `#t` to `Lit(1)` and `#f` to `Lit(0)`, and predicates answer 1 or 0.
    Lit(i64),
    /// Nil literal — the empty list / false sentinel.
    Nil,
    /// Symbol literal. `SmolStr` stores strings ≤22 bytes inline (no heap).
    Sym(SmolStr),
    /// Variable — an index into the environment, counted from its base
    /// (a de Bruijn level, matching list position in base.scm's `env`).
    /// The parser resolves surface names to these indices.
    Var(usize),

    /// `(lambda f x body)`: unary, self-naming lambda. Application
    /// extends the closure's environment with the closure itself and
    /// then the argument, so `body` reaches `f` at the first new slot
    /// (recursion without a fixpoint combinator) and `x` at the second.
    ///
    /// Body as `Rc<Exp>`: all closures from the same `Lam` site share
    /// one allocation, making `find_fun`'s ptr_eq fast path fire reliably.
    Lam(RcExp),

    /// `(f a)`: unary application. A code operand pair residualizes an
    /// application instead of β-reducing.
    App(RcExp, RcExp),
    /// `(cons a b)`: pair construction.
    Cons(RcExp, RcExp),
    /// `(let x e body)`: evaluate `e`, bind it as the next environment
    /// slot, evaluate `body`. The name is resolved away by the parser.
    Let(RcExp, RcExp),
    /// `(if c t f)`: the condition must produce a number — 0 is false,
    /// anything else true — or code, in which case both branches are
    /// reified and the `if` residualizes.
    If(RcExp, RcExp, RcExp),

    /// `(number? e)`: 1 if the value is a number, else 0.
    IsNum(RcExp),
    /// `(symbol? e)`: 1 if the value is a symbol, else 0.
    IsSym(RcExp),
    /// `(null? e)`: 1 if the value is nil, else 0.
    IsNil(RcExp),
    /// `(pair? e)`: 1 if the value is a pair, else 0.
    IsPair(RcExp),
    /// `(code? d e)`: 1 if `e`'s value is staged code, else 0. The
    /// first operand is a stage dispatch: when it evaluates to code,
    /// the test itself residualizes (strict — a non-code `e` under a
    /// staged dispatch is an error, never an implicit lift).
    IsCode(RcExp, RcExp),
    /// `(car p)`: first component of a pair.
    Car(RcExp),
    /// `(cdr p)`: second component of a pair.
    Cdr(RcExp),

    /// `(+ a b)`: integer addition.
    Plus(RcExp, RcExp),
    /// `(- a b)`: integer subtraction.
    Minus(RcExp, RcExp),
    /// `(* a b)`: integer multiplication.
    Times(RcExp, RcExp),
    /// `(eq? a b)`: structural equality, answering 1 or 0. Closures and
    /// code compare by pointer first, then structurally; cells compare
    /// by identity.
    Eq(RcExp, RcExp),

    /// `(lift e)`: reify a value into next-stage code — numbers and
    /// symbols become literals, pairs of code become `cons` nodes,
    /// closures are η-expanded into staged lambdas (memoized per
    /// closure, so recursive functions lift to a single residual
    /// definition).
    Lift(RcExp),
    /// `(run b e)`: stage dispatch on `b`. Non-code `b` compiles `e`
    /// (evaluates it in a fresh reify scope, expecting code) and
    /// immediately executes the result; code `b` reifies `e` and
    /// residualizes the `run` itself.
    Run(RcExp, RcExp),
    /// `(lift-ref name v)`: cross-stage persistence. With a non-code
    /// first operand, `v` is evaluated and embedded in code as
    /// [`Exp::Proc`] — the residual program references the live value
    /// rather than a syntactic copy. With a code first operand, the
    /// `lift-ref` residualizes.
    LiftRef(RcExp, RcExp),
    /// `(log b v)`: stage-aware debug print. Non-code `b`: print `v`
    /// (as `[log] …`) and return it. Code `b`: residualize the `log`,
    /// persisting a non-code `v` via [`Exp::Proc`].
    Log(RcExp, RcExp),

    /// Cross-stage persisted value — the reference's `(proc _ <thunk>)`
    /// (see base.scm's `lift-ref` wrapper). Evaluates to the embedded
    /// `Val`. Not reachable from the parser; only constructed by staged
    /// `log`, which persists a non-code logged value into residual code
    /// rather than coercing it to syntax.
    Proc(RcVal),

    /// `(read prompt)`: print the prompt, read one line from the
    /// evaluator's [`NarjuIo`](crate::io::NarjuIo), parse it as a datum.
    /// End-of-input and blank lines read as nil. Like `read-file`, this
    /// has no Pink-source representation, so `trans` never emits it.
    Read(RcExp),
    /// `(read-file 'path)`: parse a source file into a list of forms-as-data
    /// (each pre-sugged — read-file reads *source*, and `sug` is a read-time
    /// source transform). Floor primitive for Pink-level `load`; like `Read`,
    /// it has no Pink-source representation, so `trans` never emits it.
    ReadFile(RcExp),
    /// `(print e)`: write the value to the evaluator's
    /// [`NarjuIo`](crate::io::NarjuIo); returns nil (`log` is the
    /// variant that returns its value).
    Print(RcExp),

    /// Single restricted floor primitive for error handling in the Purple
    /// REPL loop — not reachable from the user-facing parser.
    Catch(RcExp),

    /// `(throw v)`: evaluate `v`, then raise it as a first-class error
    /// payload. Unwinds to the nearest `Catch`, arriving as
    /// `(error <payload> ())`; uncaught, it propagates as a top-level
    /// error. This is how a base env reports unbound variables loudly
    /// instead of returning a silent zero.
    Throw(RcExp),

    /// `(evalms env-list expr)`: evaluate a code value under an
    /// explicit environment given as a list of values. base.scm's
    /// `evalms` exposed as a primitive — the back half of the
    /// `trans` + `evalms` pipeline that lets floor programs animate
    /// source-as-data (this is how lib/purple.naj boots Pink).
    Evalms(RcExp, RcExp),
    /// `(trans e env)`: translate an s-expression value into a code
    /// value, resolving names positionally against `env` — a list
    /// whose entries are symbols (plain names) or `(name . code)`
    /// pairs (splices: the name resolves to the given code rather
    /// than a variable). base.scm's `trans` as a primitive.
    Trans(RcExp, RcExp),

    /// `(cell-new v)`: allocate a fresh mutable cell holding v.
    CellNew(RcExp),
    /// `(cell-read c)`: current contents of a cell.
    CellRead(RcExp),
    /// `(cell-set! c v)`: write v into the cell; returns v.
    CellSet(RcExp, RcExp),
}

/// Constructor helpers that hide `Box::new` and `rc_exp` at call sites.
///
/// Using these everywhere means changing an `Exp` variant's storage type
/// (e.g. `Box` → `Rc`) only requires updating the constructor, not every
/// call site in tests and the evaluator.
impl Exp {
    /// Construct [`Exp::Lam`].
    pub fn lam(body: Exp) -> Self                      { Exp::Lam(rc_exp(body)) }
    /// Construct [`Exp::App`].
    pub fn app(f: Exp, a: Exp) -> Self                 { Exp::App(rc_exp(f), rc_exp(a)) }
    /// Construct [`Exp::Let`].
    pub fn let_(init: Exp, body: Exp) -> Self           { Exp::Let(rc_exp(init), rc_exp(body)) }
    /// Construct [`Exp::If`].
    pub fn if_(c: Exp, t: Exp, f: Exp) -> Self         { Exp::If(rc_exp(c), rc_exp(t), rc_exp(f)) }
    /// Construct [`Exp::Cons`].
    pub fn cons(a: Exp, b: Exp) -> Self                { Exp::Cons(rc_exp(a), rc_exp(b)) }
    /// Construct [`Exp::Car`].
    pub fn car(e: Exp) -> Self                         { Exp::Car(rc_exp(e)) }
    /// Construct [`Exp::Cdr`].
    pub fn cdr(e: Exp) -> Self                         { Exp::Cdr(rc_exp(e)) }
    /// Construct [`Exp::Plus`].
    pub fn plus(a: Exp, b: Exp) -> Self                { Exp::Plus(rc_exp(a), rc_exp(b)) }
    /// Construct [`Exp::Minus`].
    pub fn minus(a: Exp, b: Exp) -> Self               { Exp::Minus(rc_exp(a), rc_exp(b)) }
    /// Construct [`Exp::Times`].
    pub fn times(a: Exp, b: Exp) -> Self               { Exp::Times(rc_exp(a), rc_exp(b)) }
    /// Construct [`Exp::Eq`].
    pub fn eq(a: Exp, b: Exp) -> Self                  { Exp::Eq(rc_exp(a), rc_exp(b)) }
    /// Construct [`Exp::IsNum`].
    pub fn is_num(e: Exp) -> Self                      { Exp::IsNum(rc_exp(e)) }
    /// Construct [`Exp::IsSym`].
    pub fn is_sym(e: Exp) -> Self                      { Exp::IsSym(rc_exp(e)) }
    /// Construct [`Exp::IsNil`].
    pub fn is_nil(e: Exp) -> Self                      { Exp::IsNil(rc_exp(e)) }
    /// Construct [`Exp::IsPair`].
    pub fn is_pair(e: Exp) -> Self                     { Exp::IsPair(rc_exp(e)) }
    /// Construct [`Exp::IsCode`].
    pub fn is_code(dispatch: Exp, tested: Exp) -> Self { Exp::IsCode(rc_exp(dispatch), rc_exp(tested)) }
    /// Construct [`Exp::Lift`].
    pub fn lift(e: Exp) -> Self                        { Exp::Lift(rc_exp(e)) }
    /// Construct [`Exp::Run`].
    pub fn run(b: Exp, e: Exp) -> Self                 { Exp::Run(rc_exp(b), rc_exp(e)) }
    /// Construct [`Exp::LiftRef`].
    pub fn lift_ref(a: Exp, b: Exp) -> Self            { Exp::LiftRef(rc_exp(a), rc_exp(b)) }
    /// Construct [`Exp::Log`].
    pub fn log(b: Exp, v: Exp) -> Self                 { Exp::Log(rc_exp(b), rc_exp(v)) }
    /// Construct [`Exp::Read`].
    pub fn read(prompt: Exp) -> Self                   { Exp::Read(rc_exp(prompt)) }
    /// Construct [`Exp::ReadFile`].
    pub fn read_file(path: Exp) -> Self                { Exp::ReadFile(rc_exp(path)) }
    /// Construct [`Exp::Print`].
    pub fn print(e: Exp) -> Self                       { Exp::Print(rc_exp(e)) }
    /// Construct [`Exp::Catch`].
    pub fn catch(e: Exp) -> Self                       { Exp::Catch(rc_exp(e)) }
    /// Construct [`Exp::Throw`].
    pub fn throw(e: Exp) -> Self                       { Exp::Throw(rc_exp(e)) }
    /// Construct [`Exp::Evalms`].
    pub fn evalms(env_list: Exp, expr: Exp) -> Self    { Exp::Evalms(rc_exp(env_list), rc_exp(expr)) }
    /// Construct [`Exp::Trans`].
    pub fn trans(e: Exp, env: Exp) -> Self             { Exp::Trans(rc_exp(e), rc_exp(env)) }
    /// Construct [`Exp::CellNew`].
    pub fn cell_new(v: Exp) -> Self                    { Exp::CellNew(rc_exp(v)) }
    /// Construct [`Exp::CellRead`].
    pub fn cell_read(c: Exp) -> Self                   { Exp::CellRead(rc_exp(c)) }
    /// Construct [`Exp::CellSet`].
    pub fn cell_set(c: Exp, v: Exp) -> Self            { Exp::CellSet(rc_exp(c), rc_exp(v)) }
}

// ── Iterative Drop for Exp ────────────────────────────────────────────────────
//
// The Futamura projections produce residual programs shaped as Let-chains
// nested thousands deep (one Let per reflected statement — see
// EvalCtx::reifyv). A derived Drop deconstructs such a chain recursively,
// one native stack frame per nesting level, and overflows small thread
// stacks in debug builds (test threads default to 2 MiB). count_nodes was
// made iterative for the same reason; Drop gets the same treatment with an
// explicit worklist.
//
// Mechanism: `take_children` detaches every non-leaf RcExp child by
// swapping in a fresh `Exp::Nil` tombstone, pushing the detached Rc onto
// the worklist. `Rc::try_unwrap` succeeds only for uniquely-owned nodes —
// shared nodes just get their refcount decremented, exactly as derived
// Drop would. An unwrapped node has its own children detached before it
// falls out of scope, so its nested Drop call sees only leaf tombstones
// and returns without pushing — nesting depth stays constant.
//
// Val keeps its derived Drop: Val-linked depth (Tup list length, Clo env
// chains) is bounded by data shape, not residual size, and any Exp tree
// reached *through* a Val (Code, Clo body, Proc) still lands in this
// impl when its Rc uniquely drops.

impl Exp {
    /// Detach non-leaf `RcExp` children onto `out`, leaving `Exp::Nil`
    /// tombstones. Leaf children are left in place — their derived drop
    /// is shallow, and skipping them keeps tombstones from re-entering
    /// the worklist.
    fn take_children(&mut self, out: &mut Vec<RcExp>) {
        fn grab(slot: &mut RcExp, out: &mut Vec<RcExp>) {
            if matches!(
                **slot,
                Exp::Lit(_) | Exp::Nil | Exp::Sym(_) | Exp::Var(_) | Exp::Proc(_)
            ) {
                return;
            }
            out.push(std::mem::replace(slot, rc_exp(Exp::Nil)));
        }
        match self {
            Exp::Lit(_) | Exp::Sym(_) | Exp::Var(_) | Exp::Nil | Exp::Proc(_) => {}
            Exp::Lam(b)
            | Exp::Lift(b)
            | Exp::Car(b)
            | Exp::Cdr(b)
            | Exp::IsNum(b)
            | Exp::IsSym(b)
            | Exp::IsNil(b)
            | Exp::IsPair(b)
            | Exp::Read(b)
            | Exp::ReadFile(b)
            | Exp::Print(b)
            | Exp::Catch(b)
            | Exp::Throw(b)
            | Exp::CellNew(b)
            | Exp::CellRead(b) => grab(b, out),
            Exp::App(a, b)
            | Exp::Let(a, b)
            | Exp::Cons(a, b)
            | Exp::Plus(a, b)
            | Exp::Minus(a, b)
            | Exp::Times(a, b)
            | Exp::Eq(a, b)
            | Exp::Run(a, b)
            | Exp::IsCode(a, b)
            | Exp::LiftRef(a, b)
            | Exp::Log(a, b)
            | Exp::Evalms(a, b)
            | Exp::Trans(a, b)
            | Exp::CellSet(a, b) => {
                grab(a, out);
                grab(b, out);
            }
            Exp::If(c, t, e) => {
                grab(c, out);
                grab(t, out);
                grab(e, out);
            }
        }
    }
}

impl Drop for Exp {
    fn drop(&mut self) {
        let mut stack: Vec<RcExp> = Vec::new();
        self.take_children(&mut stack);
        while let Some(rc) = stack.pop() {
            if let Ok(mut e) = Rc::try_unwrap(rc) {
                e.take_children(&mut stack);
            }
        }
    }
}

// ── Value type ────────────────────────────────────────────────────────────────

/// A runtime value.
///
/// Values and expressions are distinct types, unlike base.scm where
/// both are s-expressions. Staged code crosses the divide as
/// [`Val::Code`] — an expression tree held as a value — and
/// [`Exp::Proc`] carries a value back into an expression.
#[derive(Debug, Clone)]
pub enum Val {
    /// Integer constant (also the boolean encoding: 0 false, 1 true).
    Cst(i64),
    /// Symbol. `SmolStr` is O(1) clone for strings ≤22 bytes.
    Sym(SmolStr),

    /// Cons cell. `Rc<Val>` makes car/cdr O(1) — Pink source lists are
    /// traversed many times during staging.
    Tup(RcVal, RcVal),

    /// Closure: environment + body.
    /// Both are `Rc` for O(1) clone and ptr_eq in find_fun.
    Clo(Env, RcExp),

    /// The empty list, terminating every [`Val::Tup`] chain. Note that
    /// `if` does not accept it as a condition — conditions are numbers
    /// (or code); test for nil with `null?`.
    Nil,

    /// Staged code value. `Rc<Exp>` — shared through the staging machinery.
    Code(RcExp),

    /// First-class mutable cell — an index into `EvalCtx.cells` (the
    /// per-instance, in-process store: each evaluator owns its own
    /// heap, so instances snapshot and compose freely). Identity
    /// is the index: `eq?` compares indices, `cell-set!` through one alias
    /// is visible through all. Cells **never fold under staging**: `lift`
    /// of a Cell errors, and staged cell ops residualize as operations.
    Cell(usize),
}

impl PartialEq for Val {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Val::Cst(a),      Val::Cst(b))      => a == b,
            (Val::Sym(a),      Val::Sym(b))       => a == b,
            (Val::Tup(a1, a2), Val::Tup(b1, b2)) => a1 == b1 && a2 == b2,
            (Val::Nil,         Val::Nil)           => true,
            (Val::Code(a),     Val::Code(b))      => Rc::ptr_eq(a, b) || a == b,
            (Val::Clo(_, a),   Val::Clo(_, b))    => Rc::ptr_eq(a, b) || a == b,
            (Val::Cell(a),     Val::Cell(b))      => a == b,
            _ => false,
        }
    }
}

impl Val {
    /// Compact description suitable for error messages. Avoids dumping
    /// large `Val::Code` trees — instead reports node count.
    ///
    /// This is the form to use in `NarjuError::TypeError.actual` and
    /// similar diagnostic strings. Use `display(v)` (in `eval/mod.rs`)
    /// or `format!("{v}")` (via `fmt::Display`) for user-facing output
    /// where the full structure matters.
    pub fn short_desc(&self) -> String {
        match self {
            Val::Cst(n)    => format!("Cst({n})"),
            Val::Sym(s)    => format!("Sym({s:?})"),
            Val::Nil       => "Nil".to_string(),
            Val::Clo(_, _) => "Clo(_, _)".to_string(),
            Val::Code(e)   => format!("Code({} nodes)", count_nodes(e)),
            Val::Tup(_, _) => "Tup(_, _)".to_string(),
            Val::Cell(i)   => format!("Cell({i})"),
        }
    }
}

// ── Environment type ──────────────────────────────────────────────────────────

/// A persistent, copy-on-write environment: `Rc<Vec<Val>>`.
pub type Env = Rc<Vec<Val>>;

/// Push a value onto a borrowed environment, returning a new `Env`.
///
/// The input `env` is borrowed, so we always need at least one `Rc::clone`
/// to obtain an owning handle. If anyone else holds a reference to the
/// underlying `Vec<Val>` (refcount > 1 after the clone), `Rc::make_mut`
/// will clone the vector for copy-on-write semantics — this is the common
/// case where a parent closure or a sibling kont frame is also looking at
/// the same env.
///
/// Prefer `env_push_owned` when the caller has unique ownership of the
/// `Env` and is about to discard it (e.g. inside `Cont::LetBody` after
/// the cont has been popped) — that path avoids the redundant `Rc::clone`
/// and, when refcount is 1, mutates the vector in place.
pub fn env_push(env: &Env, val: Val) -> Env {
    let mut new_env = Rc::clone(env);
    Rc::make_mut(&mut new_env).push(val);
    new_env
}

/// Push a value onto an owned environment, returning a new `Env`.
///
/// Consumes `env` directly, so `Rc::make_mut` sees the caller's refcount
/// unchanged. When the caller is the sole owner (refcount == 1), this
/// mutates the underlying `Vec<Val>` in place — no clone of the vector,
/// no clone of the `Rc`. When other handles exist (e.g. a captured
/// closure environment also references this `Env`), the standard
/// copy-on-write clone still happens.
///
/// Used in the CK machine wherever a `Cont` arm has just taken ownership
/// of its `env` field and is about to install a new `env` into a child
/// `Mode::Eval` — see the `LetBody`, `EvalmsFinish`, and `BinOpFinish`
/// `App` paths in `eval/machine.rs`.
pub fn env_push_owned(mut env: Env, val: Val) -> Env {
    Rc::make_mut(&mut env).push(val);
    env
}

/// An empty environment.
pub fn env_new() -> Env {
    Rc::new(Vec::new())
}

// ── Display for Val ───────────────────────────────────────────────────────────
//
// Placed in core/ rather than eval/ so any crate layer can format a Val
// without pulling in the evaluator. count_nodes is the only dependency on
// Exp structure; it lives here for the same reason.

/// Count Exp tree nodes — used by Val::Display for `#<code N nodes>`,
/// and by tests that need to bound compiled-ANF size.
///
/// Iterative (Vec-worklist) rather than recursive, so it can handle the
/// deeply-nested Exp trees produced by Futamura-3 self-compilation
/// without overflowing the native stack. Each pop adds one to the count
/// and pushes the node's children for later visitation; the final count
/// is the total number of pops.
pub fn count_nodes(e: &Exp) -> usize {
    let mut count: usize = 0;
    let mut stack: Vec<&Exp> = vec![e];
    while let Some(node) = stack.pop() {
        count += 1;
        match node {
            // Proc counts as one node: the persisted Val is a value,
            // not syntax, so its structure doesn't contribute.
            Exp::Lit(_) | Exp::Sym(_) | Exp::Var(_) | Exp::Nil | Exp::Proc(_) => {}
            Exp::Lam(b)
            | Exp::Lift(b)
            | Exp::Car(b)
            | Exp::Cdr(b)
            | Exp::IsNum(b)
            | Exp::IsSym(b)
            | Exp::IsNil(b)
            | Exp::IsPair(b)
            | Exp::Read(b)
            | Exp::ReadFile(b)
            | Exp::Print(b)
            | Exp::Catch(b)
            | Exp::Throw(b)
            | Exp::CellNew(b)
            | Exp::CellRead(b) => stack.push(b.as_ref()),
            Exp::App(a, b)
            | Exp::Let(a, b)
            | Exp::Cons(a, b)
            | Exp::Plus(a, b)
            | Exp::Minus(a, b)
            | Exp::Times(a, b)
            | Exp::Eq(a, b)
            | Exp::Run(a, b)
            | Exp::IsCode(a, b)
            | Exp::LiftRef(a, b)
            | Exp::Log(a, b)
            | Exp::Evalms(a, b)
            | Exp::Trans(a, b)
            | Exp::CellSet(a, b) => {
                stack.push(a.as_ref());
                stack.push(b.as_ref());
            }
            Exp::If(c, t, e) => {
                stack.push(c.as_ref());
                stack.push(t.as_ref());
                stack.push(e.as_ref());
            }
        }
    }
    count
}

impl fmt::Display for Val {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Val::Cst(n)    => write!(f, "{n}"),
            Val::Nil       => write!(f, "nil"),
            Val::Sym(s)    => write!(f, "'{s}"),
            Val::Clo(_, _) => write!(f, "#<closure>"),
            Val::Code(e)   => write!(f, "#<code {} nodes>", count_nodes(e)),
            Val::Tup(h, t) => fmt_list(f, h, t),
            Val::Cell(i)   => write!(f, "#<cell {i}>"),
        }
    }
}

/// Print a `Tup` chain in list notation, falling back to dotted-pair
/// notation for an improper tail.
fn fmt_list(f: &mut fmt::Formatter<'_>, head: &RcVal, tail: &RcVal) -> fmt::Result {
    write!(f, "(")?;
    write!(f, "{head}")?;
    let mut cur = tail.as_ref();
    loop {
        match cur {
            Val::Tup(h, t) => {
                write!(f, " {h}")?;
                cur = t.as_ref();
            }
            Val::Nil => break,
            v => { write!(f, " . {v}")?; break; }
        }
    }
    write!(f, ")")
}