narju/eval/

machine.rs

//! CK machine — explicit-continuation iterative evaluator.
//!
//! ## Overview
//!
//! This is `narju`'s sole evaluator. It walks an `Exp` tree by alternating
//! between two modes:
//!
//!   - `Mode::Eval { env, exp }` — about to evaluate `exp` under `env`.
//!     `step_eval` dispatches on `exp` and either produces a `Val`
//!     immediately (terminals) or pushes a `Cont` onto the kont stack
//!     and switches to a sub-expression.
//!
//!   - `Mode::Apply { val }` — just produced `val`. Pop a `Cont` from
//!     the kont stack; `step_apply` resumes the paused operation,
//!     either producing another val or switching back to `Mode::Eval`.
//!
//! Every operand evaluation, every reify scope, every η-expansion lives
//! on the heap kont rather than the Rust stack. The Rust stack depth is
//! O(1) regardless of program size or staging tower depth. (The name is
//! Felleisen's: C for the control string, K for the continuation stack.
//! Environments ride inside both, so strictly this is a CEK machine
//! with E folded into C and K.)
//!
//! ## Where staging happens
//!
//! The machine does not distinguish "normal" from "staging" evaluation.
//! Staged operations are just the arms of each dispatch that fire when
//! an operand is `Val::Code`: instead of computing, they call
//! `EvalCtx::reflectc`, which appends the operation to the innermost
//! open block in the [`EvalCtx`] and hands back a fresh residual
//! variable. Reify scopes (Class S below) delimit those blocks and fold
//! them into ANF Let-chains. All state involved lives in the `EvalCtx`;
//! `ScopeSnapshot` saves and restores it around each scope — except
//! cells and I/O, which are effects and survive.
//!
//! ## Layout of this file
//!
//! In source order: [`Mode`]; the operator-kind enums ([`BinOpKind`],
//! [`UnOpKind`]); [`Cont`], the continuation alphabet itself; the
//! resume-descriptor enums ([`ForceMode`], [`ForceCodeResume`],
//! [`ReifyResume`]); [`Machine`] and its run loop with
//! `unwind_to_catch`; `step_eval`; `step_apply`; the shared dispatch
//! helpers (`dispatch_unop`, `dispatch_binop`); and [`ScopeSnapshot`]
//! at the end.
//!
//! ## Continuation taxonomy
//!
//!   - **Class T (tail).** `Let` body, `If` chosen-branch (Cst), `App`
//!     closure body. Resumes a `Mode::Eval` directly — no kont frame.
//!
//!   - **Class O (operand).** Binary/unary primitives push a cont
//!     holding the unevaluated sibling (binary) or the op-kind (unary),
//!     then evaluate the first/only operand. Dispatch happens on
//!     resume in `step_apply`.
//!
//!   - **Class S (staged).** Reify scopes (`If`-Code, `LiftRef`-Code,
//!     `Run`-Code, run-now, `Evalms`) push `Cont::ForceCode { resume:
//!     ReifyDrain { saved, then } }` or `Cont::ReifyVExit { saved,
//!     resume }`, save a `ScopeSnapshot`, and evaluate the staged body
//!     under a fresh block. On completion the kont drains `ctx.block`
//!     into a Let-chain and dispatches a `ReifyResume` to describe what
//!     surrounding staged construction is being assembled.
//!
//!     Lift's `Clo` arm η-expansion is implemented as a nested
//!     `ForceCode` → `LiftCloFinish` pair that grows the kont rather
//!     than the Rust stack.
//!
//!   - **Class C (error).** `Catch` pushes `Cont::CatchExit { saved }`
//!     and evaluates the body. The Machine's run loop catches `Err`
//!     results from `step_eval`/`step_apply` and walks the kont via
//!     `unwind_to_catch`, restoring state from each popped cont until
//!     it finds a `CatchExit` (or runs out, in which case the original
//!     error propagates).

use std::rc::Rc;

use crate::core::{Env, Exp, RcExp, Val};

use super::{EvalCtx, FunRegistry};

// ── Mode ──────────────────────────────────────────────────────────────────────

/// The CK machine alternates between two modes:
///
///   - `Eval`: we have an `Exp` to evaluate under `Env`. The dispatcher
///     `step_eval` inspects the `Exp` and either produces a `Val`
///     immediately (literals, vars, lambdas) or pushes a `Cont` and
///     switches to evaluating a sub-expression.
///
///   - `Apply`: we have a finished `Val`. The dispatcher pops the topmost
///     `Cont` from the kont stack and integrates the `Val` into whatever
///     pending operation that continuation represents — possibly producing
///     another `Eval` step (for the next operand), another `Apply` step
///     (the operation produced a final value), or terminating the loop
///     (kont stack empty).
pub enum Mode {
    /// Evaluate `exp` under `env`. The result is fed to whatever
    /// continuation is on top of the stack.
    Eval {
        /// Environment to evaluate under.
        env: Env,
        /// Expression to evaluate.
        exp: RcExp,
    },

    /// Apply the topmost continuation to `val`. If the stack is empty,
    /// `val` is the final result.
    Apply {
        /// The value just produced.
        val: Val,
    },
}

// ── Operator kinds ────────────────────────────────────────────────────────────
//
// Class O dispatch is centralised through these enums so the CK machine's
// `Cont` enum doesn't need a variant per Exp::Plus / Exp::Minus / etc.

/// Binary primitive operators that share the same shape:
///   - eval e1 → v1
///   - eval e2 → v2
///   - dispatch on (v1, v2)
///
/// The dispatch differs per op (arithmetic vs equality vs cons-build),
/// but the operand sequencing is identical.
///
/// **Not in this enum:** `LiftRef`. Although LiftRef takes two Exps,
/// its dispatch on `v1` happens *before* `e2` is evaluated — if `v1` is
/// Code, `e2` must be evaluated inside a reify scope, not normally.
/// LiftRef has its own dedicated continuations (`Cont::LiftRefDispatch`,
/// `Cont::LiftRefForceCode`).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinOpKind {
    /// `+` — Cst+Cst → Cst, Code+Code → reflect Plus, else TypeError
    Plus,
    /// `-` — Cst−Cst → Cst, Code−Code → reflect Minus, else TypeError
    Minus,
    /// `*` — Cst×Cst → Cst, Code×Code → reflect Times, else TypeError
    Times,
    /// `eq?` — any pair → Cst(0|1), Code+Code → reflect Eq
    Eq,
    /// `cell-set!` — Cell×any → write (returns written value),
    /// Code×Code → reflect CellSet, else TypeError
    CellSet,
    /// `cons` — any → Tup, never staged (pairs always run-time data).
    ///
    /// Cons lives in `BinOpKind` to reuse the `BinOpRight`/`BinOpFinish`
    /// operand-sequencing machinery — it's the only variant here that
    /// has no Code-dispatch branch and is not stage-polymorphic at all.
    /// The dispatcher just unconditionally builds a `Val::Tup`; stage
    /// reflection for `cons` happens one level up, when a `Val::Tup` of
    /// two `Val::Code` is fed to `lift` (see `eval/mod.rs::lift`'s Tup
    /// arm). Resist the urge to add a fake Code arm to `dispatch_binop`
    /// for symmetry — the paper's `λ↑↓` does not stage cons directly.
    Cons,
    /// `code?` — Cst(0|1) on second arg's variant; if first is Code,
    /// reflect IsCode (second must then be Code or TypeError)
    IsCode,
    /// `log` — first=Code → stage the log; else IO-print second.
    /// Both operands are evaluated regardless of the dispatch (unlike
    /// LiftRef), so the standard binop sequencing fits.
    Log,
    /// Function application `(f x)` — Clo+_ → tail-jump body; Code+Code →
    /// reflect App; else TypeError. This is the only binop where one
    /// outcome is `Mode::Eval` (tail jump) rather than a pure Val
    /// producer; App is therefore special-cased in `step_apply` and
    /// not dispatched through `dispatch_binop`.
    App,
}

/// Unary primitive operators that share the same shape:
///   - eval e1 → v1
///   - dispatch on v1
///
/// `Run`'s b-operand is also unary in this sense — once b is evaluated,
/// the Run arm decides between staged-run (b is Code) and run-now
/// (b is anything else). The `e` operand is held on the continuation.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum UnOpKind {
    /// `num?` — Cst → 1, Code → reflect IsNum, else 0
    IsNum,
    /// `sym?` — Sym → 1, Code → reflect IsSym, else 0
    IsSym,
    /// `nil?` — Nil → 1, Code → reflect IsNil, else 0
    IsNil,
    /// `pair?` — Tup → 1, Code → reflect IsPair, else 0
    IsPair,
    /// `car` — Tup → first, Code → reflect Car, else TypeError
    Car,
    /// `cdr` — Tup → second, Code → reflect Cdr, else TypeError
    Cdr,
    /// `cell-new` — any non-Code → allocate Cell, Code → reflect CellNew
    CellNew,
    /// `cell-read` — Cell → contents, Code → reflect CellRead, else TypeError
    CellRead,
    /// `lift` — wrap as Code via the `lift` operator (Cst/Sym/Nil are
    /// trivial; Clo triggers η-expansion; Tup recurses on parts;
    /// Code lifts one stage).
    Lift,
    /// `print` — IO side effect, returns Nil
    Print,
}

// ── Continuation stack ────────────────────────────────────────────────────────

/// An entry on the kont stack — represents pending work to resume when the
/// current sub-evaluation produces a `Val`.
///
/// Each variant either:
///   - Holds onto an unevaluated subexpression that becomes the next
///     `Mode::Eval` (operand sequencing), or
///   - Holds enough state to dispatch on the resumed Val and either
///     produce a final Val (Class O), or
///   - Holds a `ScopeSnapshot` for restoring staging state on exit
///     from a reify-like region (Class S).
pub enum Cont {
    // ── Class O — operand sequencing for binary forms ──────────────────────────

    /// We just evaluated the first operand; resumed `Val` becomes `v1`.
    /// We need to evaluate `e2` next, then dispatch via `BinOpKind`.
    /// Pushes `BinOpFinish { op, v1 }` on resume.
    BinOpRight {
        /// Environment for evaluating `e2`.
        env: Env,
        /// Which binary form this is.
        op: BinOpKind,
        /// The unevaluated second operand.
        e2: RcExp,
    },

    /// Both operands have been evaluated. Resumed `Val` is `v2`.
    /// Dispatch on `(v1, v2)` per `BinOpKind` semantics.
    BinOpFinish {
        /// Which binary form this is.
        op: BinOpKind,
        /// The already-evaluated first operand.
        v1: Val,
    },

    // ── Class O — operand sequencing for unary forms ──────────────────────────

    /// We just evaluated the operand. Dispatch on the resumed Val.
    UnOpFinish {
        /// Which unary form this is.
        op: UnOpKind,
    },

    // ── Class O — `If` (three children) ────────────────────────────────────────

    /// We evaluated `c`. If Cst, tail-evaluate the chosen branch.
    /// If Code, push a reify scope to compile both branches and reflect.
    /// Else TypeError.
    IfDispatch {
        /// Environment for evaluating the chosen branch (or both,
        /// staged).
        env: Env,
        /// The unevaluated true branch.
        t: RcExp,
        /// The unevaluated false branch.
        f: RcExp,
    },

    // ── Class O / T — `Let` (two children) ─────────────────────────────────────

    /// We evaluated `e1`; the resumed `Val` becomes the new top of the
    /// environment, and we tail-step into `e2`. This is operand eval on
    /// the kont (Class O) followed by a tail step (Class T) — Let is a
    /// hybrid form whose flow class differs across its two operands.
    LetBody {
        /// Environment the bound value is pushed onto.
        env: Env,
        /// The unevaluated body.
        e2: RcExp,
    },

    // ── Class O — `LiftRef` (two children with v1-dependent e2 evaluation) ─────

    /// We evaluated `e1`. LiftRef's dispatch on `v1` decides *how* to
    /// evaluate `e2` — staged inside a reify scope (if `v1` is Code), or
    /// normally followed by cross-stage persistence (otherwise). This
    /// differs from the standard binop shape (which always evaluates `e2`
    /// normally), so LiftRef has its own dedicated continuation.
    LiftRefDispatch {
        /// Environment for evaluating `e2`.
        env: Env,
        /// The unevaluated second operand.
        e2: RcExp,
    },

    /// LiftRef with non-Code `e1`: `e2` just evaluated. Persist the value
    /// across stages as `(code (proc v))` — base.scm:151's lift-ref is
    /// thunk-based value persistence (`(code (proc ,e1 ,(lambda (ignore)
    /// (e2))))`), never a structural lift. Value identity is preserved:
    /// closures are not η-recompiled, runtime pairs residualize fine.
    LiftRefPersist,

    // ── Class O — `Run` (two children, b first) ────────────────────────────────

    /// We evaluated `b`. If Code, push reify scope to compile e and reflect Run.
    /// Else, enter run-now: snapshot scope, reset, reify-then-reifyv.
    RunDispatch {
        /// Environment for evaluating `e`.
        env: Env,
        /// The unevaluated expression to run.
        e: RcExp,
    },

    // ── Class O — `Trans`/`Evalms` (two children, walk env list afterwards) ────

    /// We evaluated `e_exp`. Now eval `env_exp`, then walk the env list
    /// and call `staging::trans` + `val_cons_to_exp`.
    TransRight {
        /// Environment for evaluating `env_exp`.
        env: Env,
        /// The unevaluated name-environment argument.
        env_exp: RcExp,
    },

    /// Both args evaluated; walk env_val into a NameEnv list and call trans.
    TransFinish {
        /// The already-evaluated expression argument.
        e_val: Val,
    },

    /// We evaluated `env_list_exp`. Now eval `expr_exp`, then walk env list
    /// and recurse into `evalmsg` with explicit env.
    EvalmsRight {
        /// Environment for evaluating `expr_exp`.
        env: Env,
        /// The unevaluated expression argument.
        expr_exp: RcExp,
    },

    /// Both args evaluated; walk env_val into Env, then evalmsg the expr.
    EvalmsFinish {
        /// The already-evaluated environment-list argument.
        env_val: Val,
    },

    // ── Class S — force-code-then-resume ───────────────────────────────────────
    //
    // ForceCode is the iterative form of two *distinct* reference
    // operations, discriminated by `mode` (see `ForceMode`):
    //
    //   - `ForceMode::Strict` — base.scm's `force-code`: Code(e) → e,
    //     anything else errors "expected code". Used everywhere the
    //     reference calls `reifyc` or `force-code` directly.
    //
    //   - `ForceMode::Lift` — base.scm's `lift` coercion:
    //       - Code(e) → produce Exp inline, dispatch resume
    //       - Cst/Sym/Nil/Tup → simple Exp, dispatch resume
    //       - Clo → enter the lift-Clo η-expansion dance via the kont,
    //               eventually producing Code(Var(fun_level)) and
    //               dispatching the same resume.
    //
    // The `resume` describes what surrounding construction is waiting
    // for the Exp.

    /// Force the resumed Val to an Exp per `mode`, then dispatch `resume`.
    ForceCode {
        /// Strict (`force-code`) or lenient (`lift`) coercion.
        mode: ForceMode,
        /// What to assemble from the forced Exp.
        resume: ForceCodeResume,
    },

    // ── Class S — reify-scope exits ────────────────────────────────────────────

    /// Resume from a `reifyv`-style scope: the resumed `Val` is folded
    /// with the accumulated block. If block is empty, return the val
    /// as-is; otherwise wrap the val (force_code'd via the kont) into
    /// a `Val::Code(Let-chain)`. Restore snapshot.
    ReifyVExit {
        /// Staging state to restore on exit.
        saved: ScopeSnapshot,
        /// What surrounding staged Exp the result slots into.
        resume: ReifyResume,
    },

    // ── Class S — the run-now bookkeeping ──────────────────────────────────────

    /// We're inside a `run_now`: the `level` counter has been bumped
    /// and we are about to do the inner reifyc → outer reifyv dance.
    /// `RunNowExit` fires when both phases complete and restores `level`.
    RunNowExit {
        /// The tower level to restore when the run completes.
        saved_level: usize,
    },

    // ── Class S — `lift(Clo)` η-expansion ──────────────────────────────────────

    /// After the body of a lifted Clo finishes evaluation and has been
    /// force_code'd to an Exp inside the inner reify scope, wrap that
    /// Exp in `Lam(...)`, reflect into the surrounding block. The
    /// resulting `Code(Var(fun_level))` is then dispatched per `resume`.
    LiftCloFinish {
        /// The fresh variable the memoised Lam was reflected as.
        fun_level: usize,
        /// What to assemble from the resulting `Code(Var(fun_level))`.
        resume: ForceCodeResume,
    },

    // ── Class C — error-handling boundary ──────────────────────────────────────

    /// `Catch(e)`: marks an error-handling boundary on the kont. Fires
    /// in two modes:
    ///   - Success: `step_apply` runs this arm with the body's val and
    ///     packages it as `(ok val ())`. Saved snapshot is restored,
    ///     discarding any emitted block bindings (consistent with
    ///     `run_scope`'s discard-on-restore semantics for Catch).
    ///   - Error: the machine's unwind walks the kont, restores each
    ///     popped state-carrying cont, stops at `CatchExit`, restores
    ///     its snapshot, and packages the error message as
    ///     `(error msg ())`.
    CatchExit {
        /// Staging state to restore on either success or unwind.
        saved: ScopeSnapshot,
    },

    // ── Class O — finishing forms with no further dispatch ─────────────────────

    /// `Read(prompt_exp)`: after evaluating the prompt arg, format it,
    /// call into IO, and parse the resulting string.
    ReadFinish,

    /// `ReadFile(path_exp)`: after evaluating the path arg (must be a
    /// `Sym`), read the file, parse all forms, sug each, return them as a
    /// list of data.
    ReadFileFinish,

    /// `Throw(payload_exp)`: after evaluating the payload, raise
    /// `NarjuError::Throw(payload)` — the run loop routes it through
    /// `unwind_to_catch`, which delivers the payload structurally to the
    /// nearest `CatchExit`.
    ThrowFinish,
}

/// How `Cont::ForceCode` treats a non-`Code` value.
///
/// The reference (base.scm) has two distinct operations that narju
/// once conflated into a single lenient force-code:
///
///   - `force-code` — strict projection: `(code e) → e`, anything else
///     errors `expected code, not ...`. This is what `reifyc` wraps, so
///     it governs If-Code branches, both Run arms (staged and run-now),
///     the body of a lift-Clo η-expansion, and `code?`'s staged second
///     argument. Verified against base.scm running under Chez: e.g.
///     `(run 0 (lambda (var 1)))`, `(run 0 5)`, `(if (lift 1) 2 3)`,
///     `(code? (lift 1) 2)`, and `(lift (lambda 5))` all error.
///
///   - `lift` — the NBE reify operator: numbers/symbols self-represent,
///     closures η-expand, pairs recurse on force-code'd components.
///     This is the *only* lenient coercion in the reference, and only
///     `lift` itself (plus narju's LiftRef and staged-log paths, whose
///     strictness base.scm never exercises, so they have no oracle to
///     check against) may use it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ForceMode {
    /// `lift` semantics: coerce leniently, η-expand Clo.
    Lift,
    /// `force-code` semantics: Code or error.
    Strict,
}

/// Discriminator for what to do with the Exp produced by a `ForceCode`
/// continuation. Different callers want to assemble different surrounding
/// constructions from the forced Exp.
pub enum ForceCodeResume {
    /// We are completing a `reifyc`-style scope: drain `ctx.block` into
    /// a Let-chain ending in this Exp, restore the snapshot, dispatch
    /// the original `ReifyResume`.
    ReifyDrain {
        /// Staging state to restore after draining the block.
        saved: ScopeSnapshot,
        /// What surrounding staged Exp the Let-chain slots into.
        then: ReifyResume,
    },

    /// Wrap as `Val::Code(exp)` and produce `Mode::Apply`. Used by
    /// LiftRef's non-Code-v1 branch.
    WrapAsCode,

    /// Reflect `Exp::IsCode(s1, exp)` and produce `Mode::Apply`. Used by
    /// `code?`'s Code-first-arg branch — the paper lifts a non-Code v2
    /// via `force-code` before constructing the staged check, so this
    /// resume runs after force-coding v2 (which may have driven a
    /// lift-Clo η-expansion through the kont stack).
    IsCodeStaged {
        /// The first operand's code, already forced.
        s1: Rc<Exp>,
    },
}

/// Discriminator for what shape of staged Exp to assemble when a reify
/// scope completes. Each reify scope in the recursive code corresponds
/// to one of these — the resume action knows what surrounding Exp the
/// reified body slots into.
pub enum ReifyResume {
    /// `Exp::If(c, t, f)` with c=Code: t was being reified; f still
    /// needs reifying. Push a fresh `ReifyCExit { resume: IfFalseDone }`
    /// scope when this fires.
    IfTrueDone {
        /// The condition's code, already forced.
        c: RcExp,
        /// Environment for reifying the false branch.
        env: Env,
        /// The unevaluated false branch.
        f: RcExp,
    },

    /// Both branches reified; reflect the staged If(c, t, f).
    IfFalseDone {
        /// The condition's code, already forced.
        c: RcExp,
        /// The reified true branch.
        t: RcExp,
    },

    /// `Exp::Run(b, e)` with b=Code: reify e, reflect Run(b, e').
    RunStaged {
        /// The first operand's code, already forced.
        b: RcExp,
    },

    /// `Exp::Run(b, e)` run-now path: inner reifyc completed, now do
    /// outer reifyv.
    RunNowInner {
        /// Environment for the outer reifyv evaluation.
        env: Env,
    },

    /// `Exp::LiftRef(e1, e2)` with e1=Code: reify e2, reflect LiftRef.
    LiftRefDone {
        /// The first operand's code, already forced.
        s1: RcExp,
    },

    /// Resume from `evalmsg`-style top-level reifyv. The result is
    /// returned directly (no surrounding staged Exp).
    TopLevel,
}

// ── Machine ───────────────────────────────────────────────────────────────────

/// The CK machine's execution state.
///
/// Owns the `Mode` (current eval/apply step) and the kont stack.
/// `EvalCtx` is passed alongside via reference because it represents
/// long-lived staging context (`fresh`, `block`, `fun`, `level`, `io`)
/// rather than per-evaluation loop state.
///
/// A Machine is constructed at the top of an `evalms` call, run to
/// completion (or error), and then consumed. `Machine::run` drives the
/// loop and returns the final `Val`.
pub struct Machine {
    /// The current step: evaluate an expression or apply a value to the
    /// kont.
    pub mode: Mode,
    /// The continuation stack; empty means the next `Apply` is final.
    pub kont: Vec<Cont>,
}

impl Machine {
    /// Create a fresh machine that will start by evaluating `exp` under
    /// `env`. The kont stack is empty; the loop terminates when an
    /// `Apply` finds the stack empty.
    pub fn new(env: Env, exp: RcExp) -> Self {
        Self {
            mode: Mode::Eval { env, exp },
            kont: Vec::new(),
        }
    }

    /// Drive the machine to completion.
    ///
    /// Every Exp variant is handled natively; there is no recursive
    /// baseline. The loop alternates `Mode::Eval` → `step_eval` and
    /// `Mode::Apply` → pop-cont → `step_apply`, with `unwind_to_catch`
    /// handling `Catch` error boundaries.
    pub fn run(self, ctx: &mut EvalCtx) -> Result<Val, crate::error::NarjuError> {
        // Destructure into locals so the loop can borrow `kont` mutably
        // while moving `mode` out by value on each iteration.
        let Self { mut mode, mut kont } = self;
        loop {
            let step_result = match mode {
                Mode::Eval { env, exp } => step_eval(env, exp, &mut kont, ctx),
                Mode::Apply { val } => match kont.pop() {
                    None => return Ok(val),
                    Some(k) => step_apply(k, val, &mut kont, ctx),
                },
            };
            mode = match step_result {
                Ok(m) => m,
                Err(e) => unwind_to_catch(&mut kont, e, ctx)?,
            };
        }
    }
}

// ── step_eval ────────────────────────────────────────────────────────────────

/// Dispatch on the current `Exp` and produce the next `Mode`.
///
/// Every Exp variant has an explicit arm; the dispatch is exhaustive.
/// Two flavours:
///
///   1. **Class T** — terminals, `Var`, `Lam`, plus the tail-step
///      continuations of `Let`/`If`/`App`. Produces `Mode::Apply`
///      (terminals) or `Mode::Eval` (tail steps).
///
///   2. **Class O / S** — operand-bearing forms push a `Cont` onto the
///      kont and switch to `Mode::Eval` for the first sub-expression.
///      Resumption goes through `step_apply`. This covers all binary
///      and unary forms, as well as the staging forms (`If`-Code,
///      `LiftRef`, `Run`, `Evalms`, lift-`Clo` η-expansion via
///      `Cont::ForceCode`).
fn step_eval(
    env: Env,
    exp: RcExp,
    kont: &mut Vec<Cont>,
    ctx: &mut EvalCtx,
) -> Result<Mode, crate::error::NarjuError> {
    use crate::core::Exp;
    use crate::error::NarjuError;

    match exp.as_ref() {
        // ── Class T: pure terminals ─────────────────────────────────────────
        Exp::Nil => Ok(Mode::Apply { val: Val::Nil }),
        Exp::Lit(n) => Ok(Mode::Apply { val: Val::Cst(*n) }),
        Exp::Sym(s) => Ok(Mode::Apply { val: Val::Sym(s.clone()) }),

        // Cross-stage persisted value: evaluates to the embedded Val,
        // mirroring base.scm's `(((tagged? 'proc) e) ((caddr e) env))`.
        Exp::Proc(v) => Ok(Mode::Apply { val: (**v).clone() }),

        Exp::Var(n) => {
            let val = env.get(*n).cloned().ok_or_else(|| NarjuError::UnboundVar {
                level: *n,
                env_len: env.len(),
            })?;
            Ok(Mode::Apply { val })
        }

        // (lambda e) → (clo env e) — O(1) Rc clones.
        // Closures from the same Lam node share the Rc<Exp> so find_fun
        // can ptr_eq during η-expansion.
        Exp::Lam(body) => Ok(Mode::Apply {
            val: Val::Clo(Rc::clone(&env), Rc::clone(body)),
        }),

        // ── Class O — operand-eval prefixed control flow ────────────────────
        //
        // Let, If, and App all have an operand-evaluation prefix; control
        // flow happens in step_apply when that operand finishes evaluating.

        // (let e1 e2): eval e1 onto the kont; on resume, push v1 to env
        // and tail-step into e2.
        Exp::Let(e1, e2) => {
            kont.push(Cont::LetBody {
                env: Rc::clone(&env),
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }

        // (if c t f): eval c onto the kont, dispatch in step_apply.
        //   - Cst cond → tail-eval chosen branch
        //   - Code cond → reify both branches via the kont, reflect new If
        //   - else → TypeError
        Exp::If(c, t, f) => {
            kont.push(Cont::IfDispatch {
                env: Rc::clone(&env),
                t: t.clone(),
                f: f.clone(),
            });
            Ok(Mode::Eval { env, exp: c.clone() })
        }

        // (e1 e2): eval e1 onto kont, dispatch in step_apply.
        //   - Clo + any → tail-eval body in extended env (Mode::Eval)
        //   - Code + Code → reflect new App (Mode::Apply)
        //   - else → TypeError
        // App's BinOpFinish is special-cased in step_apply because it
        // can produce Mode::Eval (the Clo tail-step), unlike pure-Val
        // binops that always produce Mode::Apply.
        Exp::App(e1, e2) => {
            kont.push(Cont::BinOpRight {
                env: Rc::clone(&env),
                op: BinOpKind::App,
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }

        // ── Class O: binary forms — push BinOpRight, eval e1 ────────────────
        //
        // Each pushes a `BinOpRight { env, op, e2 }` onto the kont and
        // switches to `Mode::Eval` for the first operand. Resumption
        // sequences via step_apply: `BinOpRight` pushes `BinOpFinish`
        // and evaluates e2; `BinOpFinish` dispatches on (v1, v2) per
        // BinOpKind.

        Exp::Plus(e1, e2) => {
            kont.push(Cont::BinOpRight {
                env: Rc::clone(&env),
                op: BinOpKind::Plus,
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::Minus(e1, e2) => {
            kont.push(Cont::BinOpRight {
                env: Rc::clone(&env),
                op: BinOpKind::Minus,
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::Times(e1, e2) => {
            kont.push(Cont::BinOpRight {
                env: Rc::clone(&env),
                op: BinOpKind::Times,
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::Eq(e1, e2) => {
            kont.push(Cont::BinOpRight {
                env: Rc::clone(&env),
                op: BinOpKind::Eq,
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::Cons(e1, e2) => {
            kont.push(Cont::BinOpRight {
                env: Rc::clone(&env),
                op: BinOpKind::Cons,
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::IsCode(e1, e2) => {
            kont.push(Cont::BinOpRight {
                env: Rc::clone(&env),
                op: BinOpKind::IsCode,
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::Log(b_exp, v_exp) => {
            kont.push(Cont::BinOpRight {
                env: Rc::clone(&env),
                op: BinOpKind::Log,
                e2: v_exp.clone(),
            });
            Ok(Mode::Eval { env, exp: b_exp.clone() })
        }

        // ── Class O: LiftRef — custom dispatch shape ────────────────────────
        //
        // LiftRef's `e2` evaluation depends on `v1`: staged via reifyc if
        // v1 is Code, or normal eval+force_code otherwise. So we can't
        // use the standard binop sequencing; instead we push a dedicated
        // `LiftRefDispatch` cont that decides on resume.
        Exp::LiftRef(e1, e2) => {
            kont.push(Cont::LiftRefDispatch {
                env: Rc::clone(&env),
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }

        // ── Class O: unary forms — push UnOpFinish, eval e1 ─────────────────

        Exp::IsNum(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::IsNum });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::IsSym(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::IsSym });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::IsNil(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::IsNil });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::IsPair(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::IsPair });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::CellNew(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::CellNew });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::CellRead(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::CellRead });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::CellSet(e1, e2) => {
            kont.push(Cont::BinOpRight {
                env: Rc::clone(&env),
                op: BinOpKind::CellSet,
                e2: e2.clone(),
            });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::Car(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::Car });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::Cdr(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::Cdr });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::Lift(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::Lift });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }
        Exp::Print(e1) => {
            kont.push(Cont::UnOpFinish { op: UnOpKind::Print });
            Ok(Mode::Eval { env, exp: e1.clone() })
        }

        // ── Class O: I/O and staging meta-primitives (batch 3) ──────────────

        // (read prompt-exp): unary — eval prompt, then format + IO + parse.
        Exp::Read(prompt_exp) => {
            kont.push(Cont::ReadFinish);
            Ok(Mode::Eval { env, exp: prompt_exp.clone() })
        }

        // (read-file path-exp): unary — eval path, then fs + parse + sug.
        Exp::ReadFile(path_exp) => {
            kont.push(Cont::ReadFileFinish);
            Ok(Mode::Eval { env, exp: path_exp.clone() })
        }

        // (trans e env): binary — eval e, eval env, walk env-list, trans.
        // Both branches of the eventual dispatch are pure-Val (no Class S
        // sub-evaluation), so the standard binary sequencing fits.
        Exp::Trans(e_exp, env_exp) => {
            kont.push(Cont::TransRight {
                env: Rc::clone(&env),
                env_exp: env_exp.clone(),
            });
            Ok(Mode::Eval { env, exp: e_exp.clone() })
        }

        // (evalms env-list expr): binary — eval env-list, eval expr, walk
        // env-list into Env, then enter a reifyv scope to evaluate the expr
        // under that explicit env.
        Exp::Evalms(env_list_exp, expr_exp) => {
            kont.push(Cont::EvalmsRight {
                env: Rc::clone(&env),
                expr_exp: expr_exp.clone(),
            });
            Ok(Mode::Eval { env, exp: env_list_exp.clone() })
        }

        // (run b e): unary in b — eval b, dispatch on v1 in step_apply.
        // Code-b → reify e; non-Code-b → run-now (save level, inner reifyc
        // then outer reifyv via the kont).
        Exp::Run(b, e) => {
            kont.push(Cont::RunDispatch {
                env: Rc::clone(&env),
                e: e.clone(),
            });
            Ok(Mode::Eval { env, exp: b.clone() })
        }

        // (catch e): save scope, push CatchExit, eval body. Success
        // produces (ok val ()); error during body is caught by the loop's
        // unwind and produces (error msg ()).
        Exp::Catch(e) => {
            let saved = ScopeSnapshot::save_and_reset_block(ctx);
            kont.push(Cont::CatchExit { saved });
            Ok(Mode::Eval { env, exp: e.clone() })
        }

        // (throw v): unary — eval payload, then raise it via the unwind.
        Exp::Throw(e) => {
            kont.push(Cont::ThrowFinish);
            Ok(Mode::Eval { env, exp: e.clone() })
        }
    }
}

// ── step_apply ───────────────────────────────────────────────────────────────

/// Resume a paused operation by feeding the just-produced `val` to the
/// popped continuation `k`.
///
/// Each Cont variant has an explicit arm. The remaining `_` is for the
/// narrower destructured patterns (`BinOpFinish { op: App, .. }`,
/// `BinOpFinish { op: Log, v1: Code, .. }`, `UnOpFinish { op: Lift }`)
/// where the variant is matched more than once with progressively wider
/// patterns.
fn step_apply(
    k: Cont,
    val: Val,
    kont: &mut Vec<Cont>,
    ctx: &mut EvalCtx,
) -> Result<Mode, crate::error::NarjuError> {
    use crate::core::{code, env_push, env_push_owned, rc_exp, Exp};
    use crate::error::NarjuError;

    match k {
        // Resumed with v1; need to evaluate e2 next.
        // Push BinOpFinish to remember v1 and the op, then switch to Eval.
        Cont::BinOpRight { env, op, e2 } => {
            kont.push(Cont::BinOpFinish { op, v1: val });
            Ok(Mode::Eval { env, exp: e2 })
        }

        // Both operands evaluated. v1 was saved on the cont; v2 is the
        // resumed Val.
        //
        // App is special-cased here because its Clo dispatch produces
        // `Mode::Eval` (a tail jump into the closure body), which
        // doesn't fit the `Result<Val, _>` shape of `dispatch_binop`.
        // Other binops produce a Val and switch to Mode::Apply.
        Cont::BinOpFinish { op: BinOpKind::App, v1 } => {
            let v2 = val;
            match (v1, v2) {
                (Val::Code(s1), Val::Code(s2)) => {
                    let result = ctx.reflectc(Exp::App(s1, s2));
                    Ok(Mode::Apply { val: result })
                }
                (Val::Clo(clo_env, body), v2) => {
                    let self_val = Val::Clo(Rc::clone(&clo_env), Rc::clone(&body));
                    // Inner push: clo_env is shared with the source closure,
                    // so make_mut clones the Vec. Outer push: the inner result
                    // has refcount 1, so env_push_owned mutates it in place.
                    let new_env = env_push_owned(env_push(&clo_env, self_val), v2);
                    Ok(Mode::Eval {
                        env: new_env,
                        exp: Rc::clone(&body),
                    })
                }
                (f, a) => Err(NarjuError::TypeError {
                    op: "app",
                    expected: "Clo or Code",
                    actual: format!("({}, {})", f.short_desc(), a.short_desc()),
                }),
            }
        }

        // Log's staged branch needs to force_code v2, which can drive
        // a lift-Clo η-expansion via the kont. Special-cased here so
        // we can push a ForceCode cont rather than calling force_code
        // inline (which would recurse through Rust on a Clo argument).
        // Staged log (v1 = Code): the reference reflects
        //   (log ,(force-code v1)
        //        ,(force-code (if (code? v2) v2 (lift-ref '_ (lambda () v2)))))
        // — a non-code v2 is *persisted across stages* as a proc exp
        // (`Exp::Proc`), not coerced to syntax. This preserves value
        // identity (closures are not η-recompiled; pairs of run-time
        // values residualize fine). Both cases produce an Exp
        // synchronously, so no ForceCode continuation is needed.
        Cont::BinOpFinish { op: BinOpKind::Log, v1: Val::Code(sb) } => {
            let v2_exp = match val {
                Val::Code(e) => Rc::unwrap_or_clone(e),
                v2 => Exp::Proc(crate::core::rc_val(v2)),
            };
            let result = ctx.reflectc(Exp::Log(sb, rc_exp(v2_exp)));
            Ok(Mode::Apply { val: result })
        }

        // `code?`'s staged branch (v1 = Code): the reference reflects
        // `(code? ,(force-code v1) ,(force-code v2))` — *strict* on v2.
        // A non-Code v2 under a staged first argument is an error, not
        // a lift. (An earlier narju revision lifted v2 here, misreading
        // base.scm's force-code as lenient; it never lifts.)
        Cont::BinOpFinish { op: BinOpKind::IsCode, v1: Val::Code(s1) } => {
            kont.push(Cont::ForceCode {
                mode: ForceMode::Strict,
                resume: ForceCodeResume::IsCodeStaged { s1 },
            });
            Ok(Mode::Apply { val })
        }

        Cont::BinOpFinish { op, v1 } => {
            let result = dispatch_binop(op, v1, val, ctx)?;
            Ok(Mode::Apply { val: result })
        }

        // Lift's Clo case may drive lift-Clo η-expansion via the kont.
        // For all other Val variants the lift is O(1) and goes through
        // dispatch_unop. For Clo, we push ForceCode-with-WrapAsCode and
        // re-dispatch the val; ForceCode handles Clo by entering the
        // lift-Clo dance with the same WrapAsCode resume.
        Cont::UnOpFinish { op: UnOpKind::Lift } => {
            match val {
                Val::Clo(_, _) => {
                    kont.push(Cont::ForceCode {
                        mode: ForceMode::Lift,
                        resume: ForceCodeResume::WrapAsCode,
                    });
                    Ok(Mode::Apply { val })
                }
                _ => {
                    let result = dispatch_unop(UnOpKind::Lift, val, ctx)?;
                    Ok(Mode::Apply { val: result })
                }
            }
        }

        // Single operand evaluated. Dispatch per UnOpKind.
        Cont::UnOpFinish { op } => {
            let result = dispatch_unop(op, val, ctx)?;
            Ok(Mode::Apply { val: result })
        }

        // (let e1 e2) with e1 just evaluated to `val`. Push val to env
        // and tail-step into e2. The `env` here was moved out of the
        // `Cont::LetBody`, so we own it — `env_push_owned` mutates the
        // Vec in place when refcount is 1.
        Cont::LetBody { env, e2 } => {
            let new_env = env_push_owned(env, val);
            Ok(Mode::Eval { env: new_env, exp: e2 })
        }

        // (if c t f) with c just evaluated to `val`.
        //   - Cst(n)  → tail-step into chosen branch (Mode::Eval)
        //   - Code(s) → enter a reify scope for the t-branch, with a
        //               chained resume that does the f-branch next.
        //               After both branches reify, reflect new If.
        //   - else    → TypeError
        Cont::IfDispatch { env, t, f } => {
            match val {
                Val::Cst(n) => {
                    let chosen = if n != 0 { t } else { f };
                    Ok(Mode::Eval { env, exp: chosen })
                }
                Val::Code(vc) => {
                    // Enter the t-branch reify scope. On body completion,
                    // ForceCode forces it to an Exp; ReifyDrain then drains
                    // the block, restores snapshot, and dispatches
                    // IfTrueDone to set up the f-branch reify scope.
                    // Strict: the reference wraps each branch in `reifyc`,
                    // so a branch evaluating to non-Code is an error.
                    let saved = ScopeSnapshot::save_and_reset_block(ctx);
                    kont.push(Cont::ForceCode {
                        mode: ForceMode::Strict,
                        resume: ForceCodeResume::ReifyDrain {
                            saved,
                            then: ReifyResume::IfTrueDone {
                                c: vc,
                                env: Rc::clone(&env),
                                f,
                            },
                        },
                    });
                    Ok(Mode::Eval { env, exp: t })
                }
                other => Err(NarjuError::TypeError {
                    op: "if",
                    expected: "Cst or Code",
                    actual: other.short_desc(),
                }),
            }
        }

        // LiftRef e1 e2 with e1 just evaluated to `val`.
        //   - Code(s1) → enter reify scope for e2; on completion
        //                ForceCode/ReifyDrain dispatches LiftRefDone
        //                which reflects the staged LiftRef.
        //   - else     → eval e2 normally; on completion LiftRefPersist
        //                wraps the value as `(code (proc v))` — base.scm's
        //                lift-ref is thunk-based cross-stage persistence
        //                (never a structural lift), so free closures and
        //                runtime pairs keep their identity. Eager where
        //                the reference thunks, but pink dispatches
        //                lift-ref with both args pre-evaluated
        //                (pink.scm:52), so laziness is unobservable there.
        Cont::LiftRefDispatch { env, e2 } => {
            match val {
                Val::Code(s1) => {
                    let saved = ScopeSnapshot::save_and_reset_block(ctx);
                    kont.push(Cont::ForceCode {
                        mode: ForceMode::Lift,
                        resume: ForceCodeResume::ReifyDrain {
                            saved,
                            then: ReifyResume::LiftRefDone { s1 },
                        },
                    });
                    Ok(Mode::Eval { env, exp: e2 })
                }
                _ => {
                    kont.push(Cont::LiftRefPersist);
                    Ok(Mode::Eval { env, exp: e2 })
                }
            }
        }

        Cont::LiftRefPersist => {
            let result = Val::Code(rc_exp(Exp::Proc(crate::core::rc_val(val))));
            Ok(Mode::Apply { val: result })
        }

        // (read prompt) with prompt evaluated to `val`. Format the prompt
        // string from the Val, call `ctx.io.read_line`, parse the result.
        // Eof / blank line / interrupt → Nil. Parse errors propagate.
        Cont::ReadFinish => {
            use super::val_to_prompt;
            use crate::parse::{parse_one, sexp_to_val};
            let prompt_str = val_to_prompt(&val);
            let result_val = match ctx.io.read_line(&prompt_str)? {
                None => Val::Nil,
                Some(line) => {
                    let line = line.trim().to_string();
                    if line.is_empty() {
                        Val::Nil
                    } else {
                        match parse_one(&line) {
                            Ok(sexp) => sexp_to_val(&sexp),
                            Err(e) => return Err(NarjuError::Parse(format!("read: {e}"))),
                        }
                    }
                }
            };
            Ok(Mode::Apply { val: result_val })
        }

        // (read-file path) with path evaluated to `val`. The path must be a
        // symbol (`.` and `/` are symbol chars). Each parsed form is sugged
        // and qq-expanded — read-file reads *source*, and both are
        // read-time source transforms (pink.scm sugs its quoted source at
        // definition; Scheme gives the reference its quasiquote) — then
        // converted to data. Result: list of forms.
        Cont::ReadFileFinish => {
            use crate::parse::{expand_qq, parse_all, sexp_to_val, sug};
            let path = match &val {
                Val::Sym(s) => s.as_str(),
                other => {
                    return Err(NarjuError::TypeError {
                        op: "read-file",
                        expected: "symbol path",
                        actual: other.short_desc(),
                    })
                }
            };
            let src = crate::io::read_source(path)?;
            let forms = parse_all(&src)
                .map_err(|e| NarjuError::Parse(format!("read-file {path}: {e}")))?;
            let result = forms.iter().rev().try_fold(Val::Nil, |acc, form| {
                let expanded = expand_qq(&sug(form))
                    .map_err(|e| NarjuError::Parse(format!("read-file {path}: {e}")))?;
                Ok::<_, NarjuError>(crate::core::tup(sexp_to_val(&expanded), acc))
            })?;
            Ok(Mode::Apply { val: result })
        }

        // (throw v) with payload evaluated to `val`: raise. The run loop
        // routes the Err through unwind_to_catch, which either delivers
        // the payload to a CatchExit or propagates as "uncaught throw".
        Cont::ThrowFinish => Err(NarjuError::Throw(val)),

        // (trans e env) with e evaluated to `val`. Save it on the cont,
        // switch to evaluate env_exp.
        Cont::TransRight { env, env_exp } => {
            kont.push(Cont::TransFinish { e_val: val });
            Ok(Mode::Eval { env, exp: env_exp })
        }

        // (trans e env) with both args evaluated; `e_val` was saved on the
        // cont; the resumed `val` is env_val. Walk env_val into a NameEnv,
        // then call staging::trans + val_cons_to_exp.
        Cont::TransFinish { e_val } => {
            use super::staging::{trans, val_cons_to_exp, NameEntry};
            let env_val = val;
            let mut name_env: Vec<NameEntry> = Vec::new();
            let mut cur = env_val;
            loop {
                match cur {
                    Val::Nil => break,
                    Val::Tup(h, t) => {
                        let entry = match h.as_ref() {
                            Val::Sym(s) => NameEntry::Name(s.clone()),
                            Val::Tup(name_val, code_val) => {
                                let name = match name_val.as_ref() {
                                    Val::Sym(s) => s.clone(),
                                    other => return Err(NarjuError::Stage(format!(
                                        "trans: splice pair car must be Sym, got {other:?}"
                                    ))),
                                };
                                let exp = match code_val.as_ref() {
                                    Val::Code(e) => (**e).clone(),
                                    other => return Err(NarjuError::Stage(format!(
                                        "trans: splice pair cdr must be Code, got {other:?}"
                                    ))),
                                };
                                NameEntry::Splice { name, exp }
                            }
                            other => return Err(NarjuError::Stage(format!(
                                "trans: env entries must be Sym or (cons name Code), got {other:?}"
                            ))),
                        };
                        name_env.push(entry);
                        cur = Rc::unwrap_or_clone(t);
                    }
                    other => return Err(NarjuError::Stage(format!(
                        "trans: env must be a list, got {other:?}"
                    ))),
                }
            }
            let transd = trans(&e_val, &name_env)?;
            let exp = val_cons_to_exp(&transd)?;
            Ok(Mode::Apply { val: code(exp) })
        }

        // (evalms env-list expr) with env-list evaluated. Save it, eval expr.
        Cont::EvalmsRight { env, expr_exp } => {
            kont.push(Cont::EvalmsFinish { env_val: val });
            Ok(Mode::Eval { env, exp: expr_exp })
        }

        // (evalms env-list expr) with both evaluated. Walk env-list into Env,
        // then enter a reifyv scope to evaluate the expr under that env.
        Cont::EvalmsFinish { env_val } => {
            use crate::core::{env_new, env_push_owned};
            let expr_val = val;
            let mut explicit_env = env_new();
            let mut cur = env_val;
            loop {
                match cur {
                    Val::Nil => break,
                    Val::Tup(h, t) => {
                        // explicit_env is a fresh-built local — refcount 1
                        // through the entire loop, so env_push_owned mutates
                        // the underlying Vec in place each iteration rather
                        // than cloning it.
                        explicit_env = env_push_owned(explicit_env, Rc::unwrap_or_clone(h));
                        cur = Rc::unwrap_or_clone(t);
                    }
                    other => return Err(NarjuError::Stage(format!(
                        "evalms: env must be a list, got {other:?}"
                    ))),
                }
            }
            let exp = match expr_val {
                Val::Code(exp) => exp,
                other => return Err(NarjuError::TypeError {
                    op: "evalms",
                    expected: "Code",
                    actual: other.short_desc(),
                }),
            };
            // evalmsg = reifyv(|ctx| evalms(env, exp, ctx)).
            // Enter the reifyv scope and evaluate exp under explicit_env.
            let saved = ScopeSnapshot::save_and_reset_block(ctx);
            kont.push(Cont::ReifyVExit {
                saved,
                resume: ReifyResume::TopLevel,
            });
            Ok(Mode::Eval { env: explicit_env, exp })
        }

        // (run b e) with b evaluated to `val`.
        //   - Code(b1) → enter reify scope for e; on completion
        //                ForceCode/ReifyDrain dispatches RunStaged
        //                which reflects Run(b, e').
        //   - else     → run-now path: save level, push outer reifyv +
        //                inner reifyc, eval e under reset fresh.
        Cont::RunDispatch { env, e } => {
            match val {
                Val::Code(b1) => {
                    // Strict: reference is `reflectc(run ,b1 ,(reifyc thunk))`.
                    let saved = ScopeSnapshot::save_and_reset_block(ctx);
                    kont.push(Cont::ForceCode {
                        mode: ForceMode::Strict,
                        resume: ForceCodeResume::ReifyDrain {
                            saved,
                            then: ReifyResume::RunStaged { b: b1 },
                        },
                    });
                    Ok(Mode::Eval { env, exp: e })
                }
                _ => {
                    // Run-now: save level, push outer reifyv + inner reifyc,
                    // reset fresh = env_len for the inner scope.
                    let env_len = env.len();

                    // Push level-restore (fires last after both reify scopes).
                    kont.push(Cont::RunNowExit {
                        saved_level: ctx.level,
                    });
                    ctx.level += 1;

                    // Push outer reifyv (fires after inner reifyc completes
                    // and we evaluate the inner-produced let-chain).
                    let saved_outer = ScopeSnapshot::save_and_reset_block(ctx);
                    kont.push(Cont::ReifyVExit {
                        saved: saved_outer,
                        resume: ReifyResume::TopLevel,
                    });

                    // Push inner reifyc (fires first, holding the produced
                    // Exp `inner`; resume RunNowInner switches to evaluating
                    // inner under env, feeding into the outer reifyv).
                    // Strict: `(run 0 <non-code>)` must error "expected
                    // code", not silently η-expand (base.scm errors here).
                    let saved_inner = ScopeSnapshot::save_and_reset_block(ctx);
                    kont.push(Cont::ForceCode {
                        mode: ForceMode::Strict,
                        resume: ForceCodeResume::ReifyDrain {
                            saved: saved_inner,
                            then: ReifyResume::RunNowInner {
                                env: Rc::clone(&env),
                            },
                        },
                    });

                    // Inner reifyc resets fresh per the recursive baseline.
                    ctx.fresh = env_len;

                    Ok(Mode::Eval { env, exp: e })
                }
            }
        }

        // ── Class S — ForceCode and reify-scope exits ──────────────────────
        //
        // ForceCode is the iterative form of `force_code(v)`. It examines
        // the resumed `val`:
        //   - Code/Cst/Sym/Nil/Tup → produce Exp inline, dispatch resume.
        //   - Clo → enter the lift-Clo η-expansion: register the closure,
        //           save a reify scope snapshot, fresh-allocate f/x vars,
        //           push LiftCloFinish + ForceCode-with-ReifyDrain, and
        //           switch into evaluating the closure body. The eventual
        //           Code result flows through LiftCloFinish (which wraps
        //           in Lam, reflects, and re-dispatches the same resume).
        //
        // The `resume` indicates what surrounding construction is waiting
        // for the produced Exp.

        Cont::ForceCode { mode, resume } => {
            // Strict mode is the reference's `force-code`: only Code
            // projects; everything else — including Clo — errors. The
            // η-expansion arms below are `lift`-only territory.
            if let ForceMode::Strict = mode {
                return match val {
                    Val::Code(e) => {
                        force_code_dispatch_resume(resume, (*e).clone(), kont, ctx)
                    }
                    other => Err(NarjuError::Stage(format!(
                        "force-code: expected code, not {}",
                        other.short_desc()
                    ))),
                };
            }
            match val {
                Val::Code(e) => {
                    let exp = (*e).clone();
                    force_code_dispatch_resume(resume, exp, kont, ctx)
                }
                Val::Cst(n) => force_code_dispatch_resume(resume, Exp::Lit(n), kont, ctx),
                Val::Sym(s) => force_code_dispatch_resume(resume, Exp::Sym(s), kont, ctx),
                Val::Nil => force_code_dispatch_resume(resume, Exp::Nil, kont, ctx),
                // Staging rule: cells never fold. Even the lenient
                // lift coercion refuses to freeze a cell into syntax.
                Val::Cell(_) => Err(NarjuError::Stage(
                    "cannot lift a cell: cells never fold under staging".into(),
                )),
                Val::Tup(a, b) => {
                    let ca = match &*a {
                        Val::Code(e) => (**e).clone(),
                        v => return Err(NarjuError::Stage(format!(
                            "lift Tup: car must be Code, got {}",
                            v.short_desc()
                        ))),
                    };
                    let cb = match &*b {
                        Val::Code(e) => (**e).clone(),
                        v => return Err(NarjuError::Stage(format!(
                            "lift Tup: cdr must be Code, got {}",
                            v.short_desc()
                        ))),
                    };
                    let exp = ctx.reflect(Exp::Cons(rc_exp(ca), rc_exp(cb)));
                    force_code_dispatch_resume(resume, exp, kont, ctx)
                }
                Val::Clo(clo_env, body) => {
                    // Fast path: this closure was already η-expanded in
                    // the current scope. Re-use its de Bruijn level.
                    if let Some(n) = ctx.find_fun(&clo_env, &body) {
                        return force_code_dispatch_resume(
                            resume,
                            Exp::Var(n),
                            kont,
                            ctx,
                        );
                    }
                    let fun_level = ctx.fresh;
                    ctx.register_fun(fun_level, &clo_env, &body);

                    // Set up the reify scope for the body. Save snapshot
                    // (mem::take leaves block empty for the new scope).
                    let saved = ScopeSnapshot::save_and_reset_block(ctx);
                    // Allocate f and x vars *inside* the scope, after save.
                    let f_var = Exp::Var(ctx.fresh_var());
                    let x_var = Exp::Var(ctx.fresh_var());
                    // Inner push: clo_env is shared with the source closure,
                    // so make_mut clones the Vec. Outer push consumes the
                    // refcount-1 inner result and mutates it in place.
                    let env2 = env_push_owned(
                        env_push(&clo_env, code(f_var)),
                        code(x_var),
                    );

                    // Push LiftCloFinish (fires after the reify completes;
                    // wraps in Lam, reflects, dispatches resume).
                    kont.push(Cont::LiftCloFinish {
                        fun_level,
                        resume,
                    });
                    // Push the ForceCode that will fire when the body
                    // produces its val; its ReifyDrain resume hands the
                    // resulting Exp back to LiftCloFinish via Code.
                    // Strict: the reference η-expansion is
                    // `(reify (lambda () (force-code (evalms ...))))` —
                    // a lifted closure's body must itself produce code
                    // (`(lift (lambda 5))` errors; lift the 5 explicitly).
                    kont.push(Cont::ForceCode {
                        mode: ForceMode::Strict,
                        resume: ForceCodeResume::ReifyDrain {
                            saved,
                            then: ReifyResume::TopLevel,
                        },
                    });
                    Ok(Mode::Eval {
                        env: env2,
                        exp: Rc::clone(&body),
                    })
                }
            }
        }

        // After the body of a lifted Clo has been reified to a Code val,
        // wrap it in Lam(...) and reflect into the outer block. The
        // resulting Code(Var(fun_level)) is then dispatched per resume.
        Cont::LiftCloFinish { fun_level: _, resume } => {
            let body_exp = match val {
                Val::Code(e) => Rc::unwrap_or_clone(e),
                v => return Err(NarjuError::Stage(format!(
                    "lift Clo: body did not reify to Code, got {}",
                    v.short_desc()
                ))),
            };
            // reflect Lam(body) into the outer block; produces Var(fresh)
            // which equals fun_level by construction (snapshot restored
            // fresh to its pre-scope value, which was fun_level).
            let result_exp = ctx.reflect(Exp::Lam(rc_exp(body_exp)));
            force_code_dispatch_resume(resume, result_exp, kont, ctx)
        }

        // ReifyVExit completes a `reifyv`-style scope: drain ctx.block;
        // if empty, produce `val` as-is; else val must be Code, extract
        // its Exp, wrap in Let-chain, produce Val::Code(let-chain).
        // Then restore snapshot and dispatch on resume.
        Cont::ReifyVExit { saved, resume } => {
            let stmts = std::mem::take(&mut ctx.block);
            let result_val = if stmts.is_empty() {
                val
            } else {
                let last = match val {
                    Val::Code(e) => Rc::unwrap_or_clone(e),
                    v => return Err(NarjuError::Stage(format!(
                        "reifyv: non-empty block but non-Code result: {}",
                        v.short_desc()
                    ))),
                };
                let exp = stmts
                    .into_iter()
                    .rev()
                    .fold(last, |acc, stmt| Exp::Let(rc_exp(stmt), rc_exp(acc)));
                code(exp)
            };
            saved.restore(ctx);
            match resume {
                ReifyResume::TopLevel => {
                    Ok(Mode::Apply { val: result_val })
                }
                // No other reify-resume is currently used with reifyv —
                // all our reifyv sites (Evalms, Run-now-outer) want
                // TopLevel-style "just produce the val."
                _ => unreachable!(
                    "ReifyVExit reached a resume kind only valid for ReifyCExit"
                ),
            }
        }

        // RunNowExit fires after the run-now's outer reifyv completes.
        // Restore the saved level, forward `val` unchanged.
        Cont::RunNowExit { saved_level } => {
            ctx.level = saved_level;
            Ok(Mode::Apply { val })
        }

        // CatchExit success path: body produced `val` without erroring.
        // Restore the saved snapshot (discarding any emitted bindings —
        // Catch is for unstaged user code; staged effects don't leak)
        // and package as `(ok val ())`.
        Cont::CatchExit { saved } => {
            use crate::core::tup;
            saved.restore(ctx);
            let result = tup(
                Val::Sym("ok".into()),
                tup(val, Val::Nil),
            );
            Ok(Mode::Apply { val: result })
        }

    }
}

// ── Class S dispatch helper ──────────────────────────────────────────────────

/// Given an Exp `produced` from a force-code-style operation and a
/// `ForceCodeResume` describing what to do with it, produce the next Mode.
///
/// For `ReifyDrain`: drain `ctx.block` into a Let-chain ending in `produced`,
/// restore the saved snapshot, then dispatch the original `ReifyResume`
/// against the resulting Exp.
///
/// For `WrapAsCode`: wrap as `Val::Code(produced)` and produce `Mode::Apply`.
///
/// For `LogStaged { sb }`: reflect `Exp::Log(sb, produced)` and produce
/// `Mode::Apply { val: code }`.
fn force_code_dispatch_resume(
    resume: ForceCodeResume,
    produced: Exp,
    kont: &mut Vec<Cont>,
    ctx: &mut EvalCtx,
) -> Result<Mode, crate::error::NarjuError> {
    use crate::core::{code, rc_exp};
    match resume {
        ForceCodeResume::WrapAsCode => {
            Ok(Mode::Apply { val: code(produced) })
        }
        ForceCodeResume::IsCodeStaged { s1 } => {
            let val = ctx.reflectc(Exp::IsCode(s1, rc_exp(produced)));
            Ok(Mode::Apply { val })
        }
        ForceCodeResume::ReifyDrain { saved, then } => {
            // Drain block into Let-chain ending in `produced`.
            let stmts = std::mem::take(&mut ctx.block);
            let result_exp = stmts
                .into_iter()
                .rev()
                .fold(produced, |acc, stmt| {
                    Exp::Let(rc_exp(stmt), rc_exp(acc))
                });
            // Restore the reify scope's saved snapshot.
            saved.restore(ctx);
            // Dispatch the original ReifyResume against result_exp.
            reify_dispatch(then, result_exp, kont, ctx)
        }
    }
}

/// Given the staged Exp produced by a reify scope and the `ReifyResume`
/// describing what surrounding construction is being assembled, produce
/// the next Mode.
fn reify_dispatch(
    resume: ReifyResume,
    result_exp: Exp,
    kont: &mut Vec<Cont>,
    ctx: &mut EvalCtx,
) -> Result<Mode, crate::error::NarjuError> {
    use crate::core::{code, rc_exp};
    match resume {
        ReifyResume::IfTrueDone { c, env, f } => {
            // result_exp is the staged t-branch. Set up the f-branch
            // reify scope; on its completion IfFalseDone reflects If.
            // Strict for the same reason as the t-branch: reifyc.
            let saved2 = ScopeSnapshot::save_and_reset_block(ctx);
            kont.push(Cont::ForceCode {
                mode: ForceMode::Strict,
                resume: ForceCodeResume::ReifyDrain {
                    saved: saved2,
                    then: ReifyResume::IfFalseDone {
                        c,
                        t: rc_exp(result_exp),
                    },
                },
            });
            Ok(Mode::Eval { env, exp: f })
        }
        ReifyResume::IfFalseDone { c, t } => {
            let val = ctx.reflectc(Exp::If(c, t, rc_exp(result_exp)));
            Ok(Mode::Apply { val })
        }
        ReifyResume::RunStaged { b } => {
            let val = ctx.reflectc(Exp::Run(b, rc_exp(result_exp)));
            Ok(Mode::Apply { val })
        }
        ReifyResume::LiftRefDone { s1 } => {
            let val = ctx.reflectc(Exp::LiftRef(s1, rc_exp(result_exp)));
            Ok(Mode::Apply { val })
        }
        ReifyResume::RunNowInner { env } => {
            // result_exp is the inner-reifyc-produced Exp. The outer
            // ReifyVExit is on the kont stack; switch to evaluating
            // result_exp under env so its Val flows up to the outer.
            Ok(Mode::Eval { env, exp: rc_exp(result_exp) })
        }
        ReifyResume::TopLevel => {
            // Used by lift-Clo's inner reify (TopLevel hands off the
            // body Exp wrapped as Code to the surrounding LiftCloFinish).
            Ok(Mode::Apply { val: code(result_exp) })
        }
    }
}

// ── Error unwind ─────────────────────────────────────────────────────────────

/// Walk the kont stack on error, restoring state of each popped cont,
/// until we find a `CatchExit`. If found, restore its snapshot, package
/// the error message as `(error msg ())`, and produce `Mode::Apply` for
/// the loop to resume normal execution. If we exhaust the kont without
/// finding a `CatchExit`, propagate the original error.
///
/// This is the only place where error handling crosses the cont boundary;
/// elsewhere `?` is used normally and produces a fresh `Err` value, which
/// the run loop catches and routes here.
fn unwind_to_catch(
    kont: &mut Vec<Cont>,
    err: crate::error::NarjuError,
    ctx: &mut EvalCtx,
) -> Result<Mode, crate::error::NarjuError> {
    use crate::core::tup;
    while let Some(k) = kont.pop() {
        match k {
            Cont::CatchExit { saved } => {
                saved.restore(ctx);
                // A thrown payload arrives structurally; machine errors
                // arrive as a Sym of their message. Both are
                // `(error <payload> ())`, so catch consumers stay uniform.
                let payload = match err {
                    crate::error::NarjuError::Throw(v) => v,
                    other => Val::Sym(other.to_string().into()),
                };
                let val = tup(
                    Val::Sym("error".into()),
                    tup(payload, Val::Nil),
                );
                return Ok(Mode::Apply { val });
            }
            // Conts carrying restorable state: restore before discarding.
            Cont::ForceCode {
                resume: ForceCodeResume::ReifyDrain { saved, .. },
                ..
            }
            | Cont::LiftCloFinish {
                resume: ForceCodeResume::ReifyDrain { saved, .. },
                ..
            }
            | Cont::ReifyVExit { saved, .. } => {
                saved.restore(ctx);
            }
            Cont::RunNowExit { saved_level } => {
                ctx.level = saved_level;
            }
            // All other conts hold no ctx state — just drop.
            _ => {}
        }
    }
    Err(err)
}

// ── Class O dispatch helpers ─────────────────────────────────────────────────
//
// These factor the per-op match out of `step_apply` so the sequencing
// is visually separated from the arithmetic. Each helper takes the
// finished operand value(s) and produces a `Val` (or error), with no
// awareness of the kont stack — pure data-flow.

/// Dispatch a binary operator on its evaluated operands.
fn dispatch_binop(
    op: BinOpKind,
    v1: Val,
    v2: Val,
    ctx: &mut EvalCtx,
) -> Result<Val, crate::error::NarjuError> {
    use crate::core::{rc_exp, tup, Exp};
    use crate::error::NarjuError;
    // lms-black's implicit Convert, in narju terms: for the
    // arithmetic/comparison ops, auto-lift a scalar operand when the
    // other side is Code, so stage-oblivious compiled code reflects
    // instead of erroring. Strictly widening — every case rewritten
    // here was an error before (including eq?'s stage-mismatch arm).
    let scalar_to_exp = |v: &Val| -> Option<Exp> {
        match v {
            Val::Cst(n) => Some(Exp::Lit(*n)),
            Val::Sym(s) => Some(Exp::Sym(s.clone())),
            Val::Nil => Some(Exp::Nil),
            _ => None,
        }
    };
    let (v1, v2) = match op {
        BinOpKind::Plus | BinOpKind::Minus | BinOpKind::Times | BinOpKind::Eq => {
            match (v1, v2) {
                (Val::Code(a), b) if !matches!(b, Val::Code(_)) => {
                    match scalar_to_exp(&b) {
                        Some(e) => (Val::Code(a), Val::Code(rc_exp(e))),
                        None => (Val::Code(a), b),
                    }
                }
                (a, Val::Code(b)) if !matches!(a, Val::Code(_)) => {
                    match scalar_to_exp(&a) {
                        Some(e) => (Val::Code(rc_exp(e)), Val::Code(b)),
                        None => (a, Val::Code(b)),
                    }
                }
                other => other,
            }
        }
        _ => (v1, v2),
    };
    match op {
        BinOpKind::CellSet => match (v1, v2) {
            // Staged: residualize the write (cells never fold).
            (Val::Code(a), Val::Code(b)) => Ok(ctx.reflectc(Exp::CellSet(a, b))),
            // Scope-extrusion guard: a Code value written into a real
            // cell could carry residual Vars out of their reify block.
            // Invariant: cells never contain Code.
            (Val::Cell(_), v2 @ Val::Code(_)) => Err(NarjuError::TypeError {
                op: "cell-set!",
                expected: "non-Code value (cells never contain Code)",
                actual: format!("(Cell, {})", v2.short_desc()),
            }),
            // A cell holds any run-time Val; returns the written value.
            (Val::Cell(i), v2) => {
                ctx.cells[i] = v2.clone();
                Ok(v2)
            }
            (a, b) => Err(NarjuError::TypeError {
                op: "cell-set!",
                expected: "Cell or matching Code",
                actual: format!("({}, {})", a.short_desc(), b.short_desc()),
            }),
        },
        BinOpKind::Plus => match (v1, v2) {
            (Val::Code(a), Val::Code(b)) => Ok(ctx.reflectc(Exp::Plus(
                a,
                b,
            ))),
            (Val::Cst(a), Val::Cst(b)) => Ok(Val::Cst(a + b)),
            (a, b) => Err(NarjuError::TypeError {
                op: "+",
                expected: "matching Cst or Code",
                actual: format!("({}, {})", a.short_desc(), b.short_desc()),
            }),
        },
        BinOpKind::Minus => match (v1, v2) {
            (Val::Code(a), Val::Code(b)) => Ok(ctx.reflectc(Exp::Minus(
                a,
                b,
            ))),
            (Val::Cst(a), Val::Cst(b)) => Ok(Val::Cst(a - b)),
            (a, b) => Err(NarjuError::TypeError {
                op: "-",
                expected: "matching Cst or Code",
                actual: format!("({}, {})", a.short_desc(), b.short_desc()),
            }),
        },
        BinOpKind::Times => match (v1, v2) {
            (Val::Code(a), Val::Code(b)) => Ok(ctx.reflectc(Exp::Times(
                a,
                b,
            ))),
            (Val::Cst(a), Val::Cst(b)) => Ok(Val::Cst(a * b)),
            (a, b) => Err(NarjuError::TypeError {
                op: "*",
                expected: "matching Cst or Code",
                actual: format!("({}, {})", a.short_desc(), b.short_desc()),
            }),
        },
        BinOpKind::Eq => match (v1, v2) {
            (Val::Code(a), Val::Code(b)) => Ok(ctx.reflectc(Exp::Eq(a, b))),
            // The paper's `binary-op` rejects stage mismatch — one
            // operand Code, the other not. Returning 0 instead (which
            // structural Eq on Val would do) hides staging bugs, so the
            // mismatch is an error. Scalar operands were already
            // auto-lifted above (lms-black's implicit Convert), so these
            // arms fire only for non-liftable mixes (closures, cells).
            (Val::Code(_), b) => Err(NarjuError::Stage(format!(
                "eq?: stage mismatch (Code, {})", b.short_desc()
            ))),
            (a, Val::Code(_)) => Err(NarjuError::Stage(format!(
                "eq?: stage mismatch ({}, Code)", a.short_desc()
            ))),
            (a, b) => Ok(Val::Cst(if a == b { 1 } else { 0 })),
        },
        BinOpKind::Cons => Ok(tup(v1, v2)),

        BinOpKind::IsCode => match v1 {
            Val::Code(_) => {
                // Code-first-arg case is special-cased in step_apply
                // (BinOpFinish { op: IsCode, v1: Code }) so we can push
                // a ForceCode cont for v2 — force_code may drive lift-Clo
                // recursion through the kont, including lifting non-Code v2.
                unreachable!(
                    "IsCode with Code v1 must be special-cased in step_apply"
                )
            }
            _ => Ok(Val::Cst(if matches!(v2, Val::Code(_)) { 1 } else { 0 })),
        },

        BinOpKind::Log => match v1 {
            Val::Code(_) => {
                // Code-first-arg case is special-cased in step_apply
                // (BinOpFinish { op: Log, v1: Code }) so we can push a
                // ForceCode cont for v2 — force_code may drive lift-Clo
                // recursion through the kont.
                unreachable!(
                    "Log with Code v1 must be special-cased in step_apply"
                )
            }
            _ => {
                // Unstaged: actually print, return the value unchanged.
                use super::display;
                ctx.io.print(&format!("[log] {}", display(&v2)))?;
                Ok(v2)
            }
        },

        // Apps are special-cased in `step_apply` (they can produce Mode::Eval
        // for the Clo tail-jump branch). Reaching this arm with `App` would
        // mean `step_apply::BinOpFinish` failed to special-case App.
        BinOpKind::App => unreachable!(
            "BinOpKind::App must be special-cased in step_apply::BinOpFinish, \
             not dispatched through dispatch_binop"
        ),
    }
}

/// Dispatch a unary operator on its evaluated operand.
fn dispatch_unop(
    op: UnOpKind,
    v: Val,
    ctx: &mut EvalCtx,
) -> Result<Val, crate::error::NarjuError> {
    use crate::core::{code, Exp};
    use crate::error::NarjuError;
    use super::{display, lift};
    match op {
        UnOpKind::IsNum => match v {
            Val::Code(s) => Ok(ctx.reflectc(Exp::IsNum(s))),
            Val::Cst(_) => Ok(Val::Cst(1)),
            _ => Ok(Val::Cst(0)),
        },
        UnOpKind::IsSym => match v {
            Val::Code(s) => Ok(ctx.reflectc(Exp::IsSym(s))),
            Val::Sym(_) => Ok(Val::Cst(1)),
            _ => Ok(Val::Cst(0)),
        },
        UnOpKind::IsNil => match v {
            Val::Code(s) => Ok(ctx.reflectc(Exp::IsNil(s))),
            Val::Nil => Ok(Val::Cst(1)),
            _ => Ok(Val::Cst(0)),
        },
        UnOpKind::IsPair => match v {
            Val::Code(s) => Ok(ctx.reflectc(Exp::IsPair(s))),
            Val::Tup(_, _) => Ok(Val::Cst(1)),
            _ => Ok(Val::Cst(0)),
        },
        UnOpKind::Car => match v {
            Val::Code(s) => Ok(ctx.reflectc(Exp::Car(s))),
            Val::Tup(a, _) => Ok(Rc::unwrap_or_clone(a)),
            other => Err(NarjuError::TypeError {
                op: "car",
                expected: "Tup",
                actual: other.short_desc(),
            }),
        },
        UnOpKind::Cdr => match v {
            Val::Code(s) => Ok(ctx.reflectc(Exp::Cdr(s))),
            Val::Tup(_, b) => Ok(Rc::unwrap_or_clone(b)),
            other => Err(NarjuError::TypeError {
                op: "cdr",
                expected: "Tup",
                actual: other.short_desc(),
            }),
        },
        UnOpKind::CellNew => match v {
            // Staged: the allocation happens when the residual runs, not
            // at staging time (cells never fold).
            Val::Code(s) => Ok(ctx.reflectc(Exp::CellNew(s))),
            v => Ok(ctx.cell_new(v)),
        },
        UnOpKind::CellRead => match v {
            // Staged: residualize the read — folding would bake the
            // staging-time contents into the residual.
            Val::Code(s) => Ok(ctx.reflectc(Exp::CellRead(s))),
            Val::Cell(i) => Ok(ctx.cells[i].clone()),
            other => Err(NarjuError::TypeError {
                op: "cell-read",
                expected: "Cell",
                actual: other.short_desc(),
            }),
        },
        UnOpKind::Lift => {
            let lifted = lift(v, ctx)?;
            Ok(code(lifted))
        }
        UnOpKind::Print => {
            ctx.io.print(&display(&v))?;
            Ok(Val::Nil)
        }
    }
}

// ── Scope snapshots ───────────────────────────────────────────────────────────

/// A snapshot of the staging-related fields of `EvalCtx`. Used to save
/// and restore the staging context at scope boundaries (reify, reifyc,
/// reifyv, run_now, Catch).
///
/// Replaces the closure-passed `run_scope` pattern of the recursive
/// baseline with a value we can name, hold on a continuation, and
/// inspect in tests. The discipline is identical: every save must be
/// paired with exactly one restore.
///
/// `level` is **not** part of `ScopeSnapshot` because it's saved
/// independently in `RunNowExit` — `level` only changes at run-now
/// boundaries, not at every reify scope.
pub struct ScopeSnapshot {
    /// Saved fresh-variable counter.
    fresh: usize,
    /// Saved pending-ANF block (taken via `mem::take` on save).
    block: Vec<Exp>,
    /// Saved closure memo table.
    fun: FunRegistry,
}

impl ScopeSnapshot {
    /// Save the current staging state. The saved `block` is taken via
    /// `mem::take` — callers who want to start fresh in the new scope
    /// will set `ctx.block = Vec::new()` afterwards (typically via
    /// `save_and_reset_block` for ergonomics).
    ///
    /// `fun` is `Rc::clone`d (O(1) refcount bump, not a structural copy).
    pub fn save(ctx: &mut EvalCtx) -> Self {
        Self {
            fresh: ctx.fresh,
            block: std::mem::take(&mut ctx.block),
            fun: Rc::clone(&ctx.fun),
        }
    }

    /// Save and reset block to empty. Equivalent to:
    ///
    /// ```ignore
    /// let snap = ScopeSnapshot::save(ctx);
    /// // ctx.block is already Vec::new() because mem::take left it empty.
    /// ```
    ///
    /// Provided for symmetry with `save` — most reify-style scopes want
    /// the block reset, so this is the common path. Functionally
    /// equivalent to plain `save` but more explicit at the call site.
    pub fn save_and_reset_block(ctx: &mut EvalCtx) -> Self {
        // mem::take leaves ctx.block as Vec::new() already.
        Self::save(ctx)
    }

    /// Restore the saved state into `ctx`. Consumes the snapshot — each
    /// snapshot may be restored at most once.
    pub fn restore(self, ctx: &mut EvalCtx) {
        ctx.fresh = self.fresh;
        ctx.block = self.block;
        ctx.fun = self.fun;
    }
}

// ── Tests ─────────────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;
    use crate::io::headless::HeadlessIo;

    #[test]
    fn snapshot_round_trip_restores_fresh_and_block() {
        let mut ctx = EvalCtx::new(Box::new(HeadlessIo::empty()));
        ctx.fresh = 7;
        ctx.block.push(Exp::Lit(1));
        ctx.block.push(Exp::Lit(2));

        let snap = ScopeSnapshot::save(&mut ctx);

        // After save, block was taken — should be empty in ctx.
        assert_eq!(ctx.block.len(), 0);
        // fresh stays as it was (snapshot is a copy).
        assert_eq!(ctx.fresh, 7);

        // Mutate ctx in the "scope".
        ctx.fresh = 42;
        ctx.block.push(Exp::Lit(99));

        // Restore.
        snap.restore(&mut ctx);

        assert_eq!(ctx.fresh, 7);
        assert_eq!(ctx.block.len(), 2);
        assert!(matches!(ctx.block[0], Exp::Lit(1)));
        assert!(matches!(ctx.block[1], Exp::Lit(2)));
    }

    #[test]
    fn machine_new_starts_in_eval_mode_with_empty_kont() {
        let env: Env = Rc::new(Vec::new());
        let exp: RcExp = Rc::new(Exp::Lit(7));
        let m = Machine::new(env, exp);
        assert!(matches!(m.mode, Mode::Eval { .. }));
        assert_eq!(m.kont.len(), 0);
    }
}