elly_core/

builtins.rs

//! Native builtins of the reserved `__` namespace: the [`Builtin`] enum,
//! the [`MODULES`] table grouping them into modules, and [`invoke`], which runs a
//! fully-applied builtin. Split from `eval.rs`; the evaluator drives these via
//! `apply1`/`apply_n`.

use alloc::borrow::Cow;
use alloc::rc::Rc;
use alloc::string::{String, ToString};
use core::cmp::Ordering;

use num_bigint::{BigInt, Sign};
use rpds::{HashTrieMap, Vector};

use crate::ast::{Text, TyKind};
use crate::eval::{self, proto_of, Ctx, EnvNode, EnvRef, Raised};
use crate::value::{ObjectData, Value};

/// A native builtin operation in the reserved `__` namespace. All are curried.
#[allow(clippy::enum_variant_names)]
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Builtin {
    IntAdd,
    IntSub,
    IntMul,
    IntPow,
    IntDivrem,
    IntFor,
    /// Relational tests on two integers, each returning a [`Bool`](Builtin::Bool)
    /// iota. These feed `if` through receiver dispatch (`n.lt 60`).
    IntEq,
    IntLt,
    IntLe,
    IntGt,
    IntGe,
    ErrRaise,
    ErrCatch,
    Match,
    ListSize,
    ListGet,
    ListAppend,
    ListWith,
    ListSplit,
    Eq,
    MapNil,
    MapWith,
    MapGet,
    MapGets,
    MapFor,
    MapMerge,
    MapCat,
    MapWithout,
    MapSize,
    IntStr,
    IntParse,
    StrPack,
    StrUnpack,
    SymFrom,
    SymStr,
    ModName,
    /// `__Mod.exports <Mod>`: returns the module's exported item names as a
    /// sorted list of symbols. A local, private iota, or non-re-exported import
    /// is not an export. Reads the frozen table without evaluating item bodies.
    /// Non-modules raise `.not_a_module`.
    ModExports,
    /// `__proto v`: the prototype of any value: an object's own, or the
    /// builtin module for other kinds. A bare builtin that cuts across kinds.
    /// Total, it serves as the classifier `as <Proto>` and the basis for
    /// object design. It grants no authority to construct or unwrap.
    Proto,
    /// `__repr v`: the display string of any value, matching
    /// [`to_display`](Value::to_display). A bare builtin that cuts across kinds.
    Repr,
    /// Object constructor `(prototype, payload)`. Not reachable by name;
    /// only accessible via the [`__new`](crate::HomeLeaf::New) leaf, which
    /// supplies the prototype from the current module.
    ObjNew,
    /// Object payload reader `(prototype, object)`. Accessible only via the
    /// [`__value`](crate::HomeLeaf::Value) leaf. Refuses objects whose prototype
    /// does not match the supplied one (`.foreign_object`), preventing methods
    /// from unwrapping foreign objects.
    ObjValue,
    // The **builtin modules** — a 0-arity builtin each, naming the module that
    // gathers the operations above as its items (see [`MODULES`]).
    Int,
    Str,
    Sym,
    List,
    Map,
    Err,
    Mod,
    /// `__Bool`, the two-iota boolean module. Its `const` declarations are
    /// [`true`](Builtin::BoolTrue) and [`false`](Builtin::BoolFalse), name-sorted
    /// so `false` is iota index 0 and `true` is index 1 (see `bool_value`); it
    /// re-exports each as an item forwarding to it — so `Bool.true` resolves like a
    /// user module's re-exported iota, while `__true` / `__false` name them
    /// directly (see [`from_name`](Builtin::from_name)). Its logic operations
    /// [`and`](Builtin::BoolAnd) / [`or`](Builtin::BoolOr) / [`not`](Builtin::BoolNot)
    /// compose them; the relational `__Int.*` tests produce them.
    Bool,
    /// `__Bool.true` / `__true`: the true iota, an arity-0 value builtin that fires
    /// on reference to `bool_value(ctx, true)`. Both spellings fold to this one op,
    /// so they are the *same* iota of the same cached `__Bool` instance.
    BoolTrue,
    /// `__Bool.false` / `__false`: the false iota — [`BoolTrue`](Builtin::BoolTrue)'s
    /// counterpart.
    BoolFalse,
    /// `__Bool.and` / `or` / `not` — strict logic over two [`Bool`](Builtin::Bool)
    /// iotas (one, for `not`); a non-`Bool` argument raises `.not_a_bool`.
    BoolAnd,
    BoolOr,
    BoolNot,
    /// `__Fun`, the prototype of every callable kind — a closure, a builtin, and
    /// a host function. It has no items yet: `docs/todo/elly-function-arity.md`
    /// is what gives it `nargs` / `nfree` / `nrets`. It exists for the totality of
    /// [`Proto`](Builtin::Proto), which is enough on its own to make it a module.
    Fun,
    /// `__Unit`, the prototype of the [unit](Value::Unit) value `()`. It has no
    /// items — a nominal type only, exactly like [`Fun`](Builtin::Fun) — and
    /// exists so every value, unit included, answers [`Proto`](Builtin::Proto).
    Unit,
}

/// A builtin module's item table: `(item name, the builtin it names)`, **sorted
/// by name** — the order a [`ModuleData`] wants, and what
/// [`member`](Builtin::member) binary-searches.
pub(crate) type Members = &'static [(&'static str, Builtin)];

/// A builtin module's `const` declarations — its **iotas** — as name-sorted static
/// strings. Only [`__Bool`](Builtin::Bool) has any today; every other module's is
/// empty. The names populate [`ModuleData::iotas`], which is what an iota's
/// `<const .name>` rendering reads (see [`Value::write_display`]).
pub(crate) type Iotas = &'static [&'static str];

/// The **builtin modules**, in cache-slot order (see [`Ctx::builtin_module`]):
/// the 0-arity builtin naming each module, its shadowable bare alias, and its
/// items. The `__<Ns>_<op>` naming convention the flat builtins used to spell out
/// lives here instead — `__Int.add` is the module `__Int`'s item `add` — so this
/// table is the whole of the `__` namespace's structure.
///
/// `__match`, `__eq` and `__proto` are not in it: they cut across kinds and
/// belong to no module.
const MODULES: &[(Builtin, &str, Members, Iotas)] = &[
    (
        Builtin::Int,
        "Int",
        &[
            ("add", Builtin::IntAdd),
            ("divrem", Builtin::IntDivrem),
            ("eq", Builtin::IntEq),
            ("for", Builtin::IntFor),
            ("ge", Builtin::IntGe),
            ("gt", Builtin::IntGt),
            ("le", Builtin::IntLe),
            ("lt", Builtin::IntLt),
            ("mul", Builtin::IntMul),
            ("parse", Builtin::IntParse),
            ("pow", Builtin::IntPow),
            ("str", Builtin::IntStr),
            ("sub", Builtin::IntSub),
        ],
        &[],
    ),
    (
        Builtin::Str,
        "Str",
        &[("pack", Builtin::StrPack), ("unpack", Builtin::StrUnpack)],
        &[],
    ),
    (
        Builtin::Sym,
        "Sym",
        &[("from", Builtin::SymFrom), ("str", Builtin::SymStr)],
        &[],
    ),
    (
        Builtin::List,
        "List",
        &[
            ("append", Builtin::ListAppend),
            ("get", Builtin::ListGet),
            ("size", Builtin::ListSize),
            ("split", Builtin::ListSplit),
            ("with", Builtin::ListWith),
        ],
        &[],
    ),
    (
        Builtin::Map,
        "Map",
        &[
            ("cat", Builtin::MapCat),
            ("for", Builtin::MapFor),
            ("get", Builtin::MapGet),
            ("gets", Builtin::MapGets),
            ("merge", Builtin::MapMerge),
            ("nil", Builtin::MapNil),
            ("size", Builtin::MapSize),
            ("with", Builtin::MapWith),
            ("without", Builtin::MapWithout),
        ],
        &[],
    ),
    (
        Builtin::Err,
        "Err",
        &[("catch", Builtin::ErrCatch), ("raise", Builtin::ErrRaise)],
        &[],
    ),
    (
        Builtin::Mod,
        "Mod",
        &[("exports", Builtin::ModExports), ("name", Builtin::ModName)],
        &[],
    ),
    // The two-iota boolean module. `true` / `false` are both iotas (`const`
    // declarations, populating the iota table for rendering) and items that
    // re-export them — the same double declaration a user's `false = const` makes
    // — so `Bool.true` resolves through the ordinary member path while `__true`
    // names the iota directly. The iotas are name-sorted: `false` is index 0,
    // `true` index 1 (see [`bool_value`]).
    (
        Builtin::Bool,
        "Bool",
        &[
            ("and", Builtin::BoolAnd),
            ("false", Builtin::BoolFalse),
            ("not", Builtin::BoolNot),
            ("or", Builtin::BoolOr),
            ("true", Builtin::BoolTrue),
        ],
        &["false", "true"],
    ),
    // No items yet, and a module all the same: it is the prototype the three
    // callable kinds answer `__proto` with (see [`Builtin::Fun`]).
    (Builtin::Fun, "Fun", &[], &[]),
    // Likewise item-less: the nominal type of the unit value `()`.
    (Builtin::Unit, "Unit", &[], &[]),
];

/// How many builtin modules there are — the width of the [`Ctx`] cache.
pub(crate) const NMODULES: usize = MODULES.len();

impl Builtin {
    /// Every nameable builtin in declaration order; the source of truth for
    /// tooling enumerating the `__` namespace. Keep in sync with the enum.
    ///
    /// [`ObjNew`](Builtin::ObjNew) and [`ObjValue`](Builtin::ObjValue) are
    /// omitted as no name resolves to them; they only render via [`name`](Builtin::name).
    pub const ALL: &'static [Builtin] = &[
        Builtin::IntAdd,
        Builtin::IntSub,
        Builtin::IntMul,
        Builtin::IntPow,
        Builtin::IntDivrem,
        Builtin::IntFor,
        Builtin::IntEq,
        Builtin::IntLt,
        Builtin::IntLe,
        Builtin::IntGt,
        Builtin::IntGe,
        Builtin::ErrRaise,
        Builtin::ErrCatch,
        Builtin::Match,
        Builtin::ListSize,
        Builtin::ListGet,
        Builtin::ListAppend,
        Builtin::ListWith,
        Builtin::ListSplit,
        Builtin::Eq,
        Builtin::MapNil,
        Builtin::MapWith,
        Builtin::MapGet,
        Builtin::MapGets,
        Builtin::MapFor,
        Builtin::MapMerge,
        Builtin::MapCat,
        Builtin::MapWithout,
        Builtin::MapSize,
        Builtin::IntStr,
        Builtin::IntParse,
        Builtin::StrPack,
        Builtin::StrUnpack,
        Builtin::SymFrom,
        Builtin::SymStr,
        Builtin::ModName,
        Builtin::ModExports,
        Builtin::Proto,
        Builtin::Repr,
        Builtin::Int,
        Builtin::Str,
        Builtin::Sym,
        Builtin::List,
        Builtin::Map,
        Builtin::Err,
        Builtin::Mod,
        Builtin::Bool,
        Builtin::BoolTrue,
        Builtin::BoolFalse,
        Builtin::BoolAnd,
        Builtin::BoolOr,
        Builtin::BoolNot,
        Builtin::Fun,
        Builtin::Unit,
    ];

    /// Resolves a `__`-name to its builtin: a bare name (`__eq`), a builtin
    /// module (`__Int`), or a module member in dotted form (`__Int.add`).
    ///
    /// Since Muon symbols cannot contain dots, the parser reaches members via
    /// [`member`](Self::member) after folding. This method is used by tooling and
    /// the `Builtin::ALL` round-trip.
    pub fn from_name(name: &str) -> Option<Builtin> {
        if let Some((ns, item)) = name.split_once('.') {
            return Builtin::from_name(ns)?.member(item);
        }
        Some(match name {
            "__match" => Builtin::Match,
            "__eq" => Builtin::Eq,
            "__proto" => Builtin::Proto,
            "__repr" => Builtin::Repr,
            // The two boolean iotas name themselves in the closed `__` namespace,
            // beside `Bool.true` / `Bool.false`: one Muon `<sym>` each, so a
            // comparand (`&(= __true)`) can name one where the dotted member is
            // two items. Both spellings fold to the same op, hence the same iota.
            "__true" => Builtin::BoolTrue,
            "__false" => Builtin::BoolFalse,
            "__Int" => Builtin::Int,
            "__Str" => Builtin::Str,
            "__Sym" => Builtin::Sym,
            "__List" => Builtin::List,
            "__Map" => Builtin::Map,
            "__Err" => Builtin::Err,
            "__Mod" => Builtin::Mod,
            "__Bool" => Builtin::Bool,
            "__Fun" => Builtin::Fun,
            "__Unit" => Builtin::Unit,
            _ => return None,
        })
    }

    /// The builtin module this bare alias names (e.g. `Int` → `__Int`).
    /// Aliases are the resolver's bottom tier (the prelude), consulted last to
    /// ensure they are shadowed by lexical bindings.
    pub fn from_alias(name: &str) -> Option<Builtin> {
        MODULES
            .iter()
            .find(|(_, alias, _, _)| *alias == name)
            .map(|(op, _, _, _)| *op)
    }

    /// The items of this builtin module, or `None` if not a module.
    pub(crate) fn items(self) -> Option<Members> {
        MODULES
            .iter()
            .find(|(op, _, _, _)| *op == self)
            .map(|(_, _, items, _)| *items)
    }

    /// The iota names of this builtin module, or `None` if not a module.
    /// Empty for all but [`__Bool`](Builtin::Bool).
    pub(crate) fn iotas(self) -> Option<Iotas> {
        MODULES
            .iter()
            .find(|(op, _, _, _)| *op == self)
            .map(|(_, _, _, iotas)| *iotas)
    }

    /// The cache slot for this builtin module in a [`Ctx`], or `None`.
    /// Positional and stable for the life of the process.
    pub(crate) fn module_slot(self) -> Option<usize> {
        MODULES.iter().position(|(op, _, _, _)| *op == self)
    }

    /// The item of this builtin module matching `name`, if any. Returns `None`
    /// if the name is not held or the builtin is not a module. Safe to call on
    /// any callee of a call spine.
    pub fn member(self, name: &str) -> Option<Builtin> {
        let items = self.items()?;
        items
            .binary_search_by(|(item, _)| (*item).cmp(name))
            .ok()
            .map(|i| items[i].1)
    }

    /// The value kind this builtin module is the prototype of, enabling `as <Proto>`
    /// patterns to compile to discriminant tests. Returns `None` if not a module
    /// or for `__Err` (no value has `__Err` as its prototype).
    pub fn proto_kind(self) -> Option<TyKind> {
        Some(match self {
            Builtin::Int => TyKind::Int,
            Builtin::Str => TyKind::Str,
            Builtin::Sym => TyKind::Sym,
            Builtin::List => TyKind::List,
            Builtin::Map => TyKind::Map,
            Builtin::Mod => TyKind::Mod,
            Builtin::Fun => TyKind::Fun,
            Builtin::Unit => TyKind::Unit,
            Builtin::Bool => TyKind::Bool,
            _ => return None,
        })
    }

    /// Number of arguments the op consumes before firing. Arity 0 ops are bare
    /// values that fire on reference (e.g. `__Map.nil` or builtin modules).
    pub(crate) fn arity(self) -> usize {
        match self {
            Builtin::MapNil
            | Builtin::Int
            | Builtin::Str
            | Builtin::Sym
            | Builtin::List
            | Builtin::Map
            | Builtin::Err
            | Builtin::Mod
            | Builtin::Bool
            // The two boolean iotas are values: they fire on reference.
            | Builtin::BoolTrue
            | Builtin::BoolFalse
            | Builtin::Fun
            | Builtin::Unit => 0,
            Builtin::Proto
            | Builtin::Repr
            | Builtin::ErrRaise
            | Builtin::ListSize
            | Builtin::MapSize
            | Builtin::IntStr
            | Builtin::IntParse
            | Builtin::StrPack
            | Builtin::StrUnpack
            | Builtin::SymFrom
            | Builtin::SymStr
            | Builtin::BoolNot
            | Builtin::ModName
            | Builtin::ModExports => 1,
            Builtin::IntAdd
            | Builtin::IntSub
            | Builtin::IntMul
            | Builtin::IntPow
            | Builtin::IntDivrem
            | Builtin::IntEq
            | Builtin::IntLt
            | Builtin::IntLe
            | Builtin::IntGt
            | Builtin::IntGe
            | Builtin::BoolAnd
            | Builtin::BoolOr => 2,
            // `__match clauses val`: strict in the clause list and the subject.
            // `__new proto data` / `__value proto obj` — the prototype is the
            // first argument, and the home-module leaf has already supplied it.
            Builtin::ObjNew
            | Builtin::ObjValue
            | Builtin::Match
            | Builtin::ErrCatch
            | Builtin::ListGet
            | Builtin::ListAppend
            | Builtin::ListSplit
            | Builtin::MapGet
            | Builtin::MapGets
            | Builtin::MapCat
            | Builtin::MapWithout => 2,
            Builtin::ListWith | Builtin::MapWith | Builtin::MapFor | Builtin::MapMerge => 3,
            Builtin::IntFor | Builtin::Eq => 4,
        }
    }

    /// Whether argument `i` is a callback that is only ever applied, never stored.
    /// Literals in such positions use [`Captures::Chain`] to share the defining
    /// environment instead of copying a frame.
    ///
    /// Must stay in sync with [`invoke`]: arguments listed here must only be
    /// reached via `apply1`/`apply_n`.
    pub(crate) fn applies_arg(self, i: usize) -> bool {
        match self {
            // `__Err.catch handler thunk` — both are run by the catch.
            Builtin::ErrCatch => i == 0 || i == 1,
            // `__eq a b then else` — one of the two branches is forced.
            Builtin::Eq => i == 2 || i == 3,
            // `__Int.for from to init f` — the fold callback.
            Builtin::IntFor => i == 3,
            // `__Map.for m init f` / `__Map.merge m1 m2 f` — the fold callbacks.
            Builtin::MapFor | Builtin::MapMerge => i == 2,
            _ => false,
        }
    }

    /// Whether argument `i` is a list of callbacks applied in order (e.g.
    /// `__match` clauses). Literal abstractions in such lists use [`Captures::Chain`].
    pub(crate) fn applies_elements_of(self, i: usize) -> bool {
        matches!(self, Builtin::Match) && i == 0
    }

    /// The reserved `__`-name for this builtin. Module members are dotted
    /// (e.g. `__Int.add`).
    pub fn name(self) -> &'static str {
        match self {
            Builtin::IntAdd => "__Int.add",
            Builtin::IntSub => "__Int.sub",
            Builtin::IntMul => "__Int.mul",
            Builtin::IntPow => "__Int.pow",
            Builtin::IntDivrem => "__Int.divrem",
            Builtin::IntFor => "__Int.for",
            Builtin::IntEq => "__Int.eq",
            Builtin::IntLt => "__Int.lt",
            Builtin::IntLe => "__Int.le",
            Builtin::IntGt => "__Int.gt",
            Builtin::IntGe => "__Int.ge",
            Builtin::ErrRaise => "__Err.raise",
            Builtin::ErrCatch => "__Err.catch",
            Builtin::Match => "__match",
            Builtin::ListSize => "__List.size",
            Builtin::ListGet => "__List.get",
            Builtin::ListAppend => "__List.append",
            Builtin::ListWith => "__List.with",
            Builtin::ListSplit => "__List.split",
            Builtin::Eq => "__eq",
            Builtin::MapNil => "__Map.nil",
            Builtin::MapWith => "__Map.with",
            Builtin::MapGet => "__Map.get",
            Builtin::MapGets => "__Map.gets",
            Builtin::MapFor => "__Map.for",
            Builtin::MapMerge => "__Map.merge",
            Builtin::MapCat => "__Map.cat",
            Builtin::MapWithout => "__Map.without",
            Builtin::MapSize => "__Map.size",
            Builtin::IntStr => "__Int.str",
            Builtin::IntParse => "__Int.parse",
            Builtin::StrPack => "__Str.pack",
            Builtin::StrUnpack => "__Str.unpack",
            Builtin::SymFrom => "__Sym.from",
            Builtin::SymStr => "__Sym.str",
            Builtin::ModName => "__Mod.name",
            Builtin::ModExports => "__Mod.exports",
            Builtin::Proto => "__proto",
            Builtin::Repr => "__repr",
            // The two capabilities render under the leaf that produced them —
            // there is no other way to hold one, so this is the name a reader
            // wrote (see [`ALL`](Builtin::ALL) for why they are not in it).
            Builtin::ObjNew => "__new",
            Builtin::ObjValue => "__value",
            Builtin::Int => "__Int",
            Builtin::Str => "__Str",
            Builtin::Sym => "__Sym",
            Builtin::List => "__List",
            Builtin::Map => "__Map",
            Builtin::Err => "__Err",
            Builtin::Mod => "__Mod",
            Builtin::Bool => "__Bool",
            // The members render dotted, as every module member does; `__true` /
            // `__false` are the extra bare spellings [`from_name`](Self::from_name)
            // also accepts, the way `Int` aliases `__Int`.
            Builtin::BoolTrue => "__Bool.true",
            Builtin::BoolFalse => "__Bool.false",
            Builtin::BoolAnd => "__Bool.and",
            Builtin::BoolOr => "__Bool.or",
            Builtin::BoolNot => "__Bool.not",
            Builtin::Fun => "__Fun",
            Builtin::Unit => "__Unit",
        }
    }
}

/// Runs a fully-applied builtin. Borrows arguments to avoid `Value::Builtin`
/// allocation when a call spine saturates a builtin exactly.
pub(crate) fn invoke(op: Builtin, args: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
    match op {
        Builtin::IntAdd => int_arith(&args[0], &args[1], i64::checked_add, |a, b| a + b),
        Builtin::IntSub => int_arith(&args[0], &args[1], i64::checked_sub, |a, b| a - b),
        Builtin::IntMul => int_arith(&args[0], &args[1], i64::checked_mul, |a, b| a * b),
        // `x ^ y`, `y >= 0`. A negative exponent has no integer value.
        Builtin::IntPow => {
            let e = u32::try_from(&*as_big(&args[1])?)
                .map_err(|_| Raised::symbol("negative_exponent"))?;
            // Small-base fast path: `i64::checked_pow`, promoting on overflow.
            if let Value::I64(x) = &args[0] {
                if let Some(z) = x.checked_pow(e) {
                    return Ok(Value::I64(z));
                }
            }
            Ok(Value::from_bigint(as_big(&args[0])?.pow(e)))
        }
        Builtin::IntDivrem => {
            // Fast path: both operands fit `i64`. `i64::MIN / -1` overflows, so on a
            // `None` from either `checked_*` we fall through to the `BigInt` path.
            if let (Value::I64(x), Value::I64(y)) = (&args[0], &args[1]) {
                if *y == 0 {
                    return Err(Raised::symbol("div_by_zero"));
                }
                if let (Some(q), Some(r)) = (x.checked_div_euclid(*y), x.checked_rem_euclid(*y)) {
                    let mut t = Vector::new();
                    t.push_back_mut(Value::I64(q));
                    t.push_back_mut(Value::I64(r));
                    return Ok(Value::List(t));
                }
            }
            let (q, r) = div_rem_euclid(&*as_big(&args[0])?, &*as_big(&args[1])?)?;
            let mut t = Vector::new();
            t.push_back_mut(Value::from_bigint(q));
            t.push_back_mut(Value::from_bigint(r));
            Ok(Value::List(t))
        }
        // The relational tests: strict in two integers, each yielding a `Bool`
        // iota. An `i64` fast path (a native compare) falls through to `BigInt`
        // only for a wide operand, and a non-integer raises `.not_an_int` through
        // `as_big` — the same strictness the arithmetic ops have.
        Builtin::IntEq => int_cmp(&args[0], &args[1], ctx, |o| o == Ordering::Equal),
        Builtin::IntLt => int_cmp(&args[0], &args[1], ctx, |o| o == Ordering::Less),
        Builtin::IntLe => int_cmp(&args[0], &args[1], ctx, |o| o != Ordering::Greater),
        Builtin::IntGt => int_cmp(&args[0], &args[1], ctx, |o| o == Ordering::Greater),
        Builtin::IntGe => int_cmp(&args[0], &args[1], ctx, |o| o != Ordering::Less),
        // The boolean iotas fire on reference, deriving from the cached `__Bool`.
        Builtin::BoolTrue => Ok(bool_value(ctx, true)),
        Builtin::BoolFalse => Ok(bool_value(ctx, false)),
        // Strict logic: both operands are forced (they arrive already evaluated),
        // so there is no short-circuit — nor a need for one, the operands being
        // values. A non-`Bool` raises `.not_a_bool`.
        Builtin::BoolAnd => Ok(bool_value(
            ctx,
            as_bool(&args[0], ctx)? && as_bool(&args[1], ctx)?,
        )),
        Builtin::BoolOr => Ok(bool_value(
            ctx,
            as_bool(&args[0], ctx)? || as_bool(&args[1], ctx)?,
        )),
        Builtin::BoolNot => Ok(bool_value(ctx, !as_bool(&args[0], ctx)?)),
        // ascending fold over `[from, to)`, index first: `onEach i acc`.
        // `from >= to` runs zero iterations and returns the initial state.
        Builtin::IntFor => {
            let f = &args[3];
            let mut acc = args[2].clone();
            // Fast path: both bounds fit `i64` — an inline counter, no per-iteration
            // `BigInt` allocation. (`i` only ever reaches `to <= i64::MAX`, so the
            // `i += 1` after the last iteration cannot overflow.)
            if let (Value::I64(from), Value::I64(to)) = (&args[0], &args[1]) {
                let (from, to) = (*from, *to);
                let mut i = from;
                while i < to {
                    let with_i = eval::apply1(f.clone(), Value::I64(i), ctx)?;
                    acc = eval::apply1(with_i, acc, ctx)?;
                    i += 1;
                }
                return Ok(acc);
            }
            // General path: a bound is a wide `BigInt` (an astronomically long loop).
            let to = as_big(&args[1])?.into_owned();
            let mut i = as_big(&args[0])?.into_owned();
            while i < to {
                let with_i = eval::apply1(f.clone(), Value::from_bigint(i.clone()), ctx)?;
                acc = eval::apply1(with_i, acc, ctx)?;
                i += 1;
            }
            Ok(acc)
        }
        // `onEqual () if a == b else onDiff ()` — structural for data, by identity
        // for callables (see `impl PartialEq for Value`). Nullary-thunk branches, so only
        // the taken side runs; the operands may be any values and never raise.
        Builtin::Eq => {
            let taken = if args[0] == args[1] {
                &args[2]
            } else {
                &args[3]
            };
            eval::apply1(taken.clone(), args[0].clone(), ctx)
        }
        // Raise the (already-evaluated) argument as a genuine error, unwinding to
        // the nearest catch.
        Builtin::ErrRaise => Err(Raised::Error(args[0].clone())),
        // Force the wrapped thunk; on *any* raise, hand the payload to the handler
        // — `__Err.catch` is the universal boundary, so it catches a refutation
        // too, delivering the original error it decayed to. A raise from the
        // handler itself propagates (not re-caught here).
        Builtin::ErrCatch => match eval::apply1(args[1].clone(), unit(), ctx) {
            Ok(v) => Ok(v),
            Err(r) => eval::apply1(args[0].clone(), r.into_value(), ctx),
        },
        // The refutable form: `__match clauses val`. Try each clause (a matcher,
        // typically `&(<pat>) <body>`) against `val` in order; the first whose
        // pattern *matches* returns its body's value, and no later clause runs. A
        // clause that *refutes* (a `NoMatch`) is skipped and the next is tried;
        // every other raise — a real `Error` from the body or a `= <expr>`
        // sub-expression — propagates. Falling off the end (an empty list, or all
        // clauses refuting) itself refutes `.no_match`, so an uncaught `__match`
        // surfaces `.no_match` while a nested one can still be caught by an outer
        // matcher. `__match` is the *only* boundary
        // that singles out `NoMatch` (which user code cannot forge), making "only
        // pattern mismatches fall through" exact. See `docs/elly-spec.md` § patterns.
        Builtin::Match => {
            for clause in list(&args[0])?.iter() {
                match eval::apply1(clause.clone(), args[1].clone(), ctx) {
                    Ok(v) => return Ok(v),
                    Err(Raised::NoMatch(_)) => continue,
                    Err(e) => return Err(e),
                }
            }
            Err(Raised::NoMatch(Value::Symbol(Text::from_static(
                "no_match",
            ))))
        }
        // Element count of a list.
        Builtin::ListSize => Ok(Value::I64(list(&args[0])?.len() as i64)),
        // Element at a 0-based integer index; out of range (or negative) raises
        // `.projection_out_of_range`, generalizing `.N` projection to a computed
        // index.
        Builtin::ListGet => {
            let t = list(&args[0])?;
            index_of(&args[1])?
                .and_then(|idx| t.get(idx))
                .cloned()
                .ok_or_else(|| Raised::symbol("projection_out_of_range"))
        }
        // Concatenate two lists: `[a…] ++ [b…]`.
        Builtin::ListAppend => {
            let mut r = list(&args[0])?.clone();
            for e in list(&args[1])?.iter() {
                r.push_back_mut(e.clone());
            }
            Ok(Value::List(r))
        }
        // Replace the element at index `i` with `v`, returning a new list;
        // out of range (or a negative index) raises `.projection_out_of_range`.
        Builtin::ListWith => {
            let t = list(&args[0])?;
            let v = args[2].clone();
            index_of(&args[1])?
                .and_then(|idx| t.set(idx, v))
                .map(Value::List)
                .ok_or_else(|| Raised::symbol("projection_out_of_range"))
        }
        // Split a list at position `n` into `[left, right]` (left holds the
        // first `n` elements). `n` must be in `[0, size]`, else
        // `.projection_out_of_range`.
        Builtin::ListSplit => {
            let t = list(&args[1])?;
            let n = index_of(&args[0])?
                .filter(|&n| n <= t.len())
                .ok_or_else(|| Raised::symbol("projection_out_of_range"))?;
            let mut left = Vector::new();
            let mut right = Vector::new();
            for (idx, e) in t.iter().enumerate() {
                if idx < n {
                    left.push_back_mut(e.clone());
                } else {
                    right.push_back_mut(e.clone());
                }
            }
            let mut pair = Vector::new();
            pair.push_back_mut(Value::List(left));
            pair.push_back_mut(Value::List(right));
            Ok(Value::List(pair))
        }
        // The empty map (a 0-arity value; `args` is empty).
        Builtin::MapNil => Ok(Value::Map(HashTrieMap::new())),
        // `m` with `k` bound to `v` (overwriting any prior binding). Any value is
        // a key — no key restriction, no bad-key error.
        Builtin::MapWith => {
            let m = map(&args[0])?;
            Ok(Value::Map(m.insert(args[1].clone(), args[2].clone())))
        }
        // Value at `k`; a missing key raises `.missing_key` (a catchable tag).
        Builtin::MapGet => {
            let m = map(&args[0])?;
            m.get(&args[1])
                .cloned()
                .ok_or_else(|| Raised::symbol("missing_key"))
        }
        // Parallel projection: a list of the values for a list of keys; any
        // missing key raises `.missing_key`.
        Builtin::MapGets => {
            let m = map(&args[0])?;
            let mut out = Vector::new();
            for k in list(&args[1])?.iter() {
                let v = m
                    .get(k)
                    .cloned()
                    .ok_or_else(|| Raised::symbol("missing_key"))?;
                out.push_back_mut(v);
            }
            Ok(Value::List(out))
        }
        // Fold over the map (unspecified order): `onEach key value state -> state`.
        Builtin::MapFor => {
            let m = map(&args[0])?;
            let f = &args[2];
            let mut acc = args[1].clone();
            for (k, v) in m.iter() {
                let with_k = eval::apply1(f.clone(), k.clone(), ctx)?;
                let with_v = eval::apply1(with_k, v.clone(), ctx)?;
                acc = eval::apply1(with_v, acc, ctx)?;
            }
            Ok(acc)
        }
        // Generic merge over the union of keys. For each key the callback gets the
        // key and each side's value as an option (`[]` none / `[v]` some) and
        // returns an option — `[]` drops the key, `[v]` sets it.
        Builtin::MapMerge => {
            let m1 = map(&args[0])?;
            let m2 = map(&args[1])?;
            let f = &args[2];
            let mut result = HashTrieMap::new();
            // Every key in the union, visited once (order unspecified): all of
            // `m1`'s keys, then `m2`'s keys that `m1` lacks.
            let union = m1.keys().chain(m2.keys().filter(|k| !m1.contains_key(*k)));
            for k in union {
                let k = k.clone();
                let with_k = eval::apply1(f.clone(), k.clone(), ctx)?;
                let with_l = eval::apply1(with_k, option(m1.get(&k)), ctx)?;
                let out = eval::apply1(with_l, option(m2.get(&k)), ctx)?;
                if let Some(v) = un_option(&out)? {
                    result.insert_mut(k, v);
                }
            }
            Ok(Value::Map(result))
        }
        // Union with `b` winning on a key conflict (a `__Map.merge` special case).
        Builtin::MapCat => {
            let mut r = map(&args[0])?.clone();
            for (k, v) in map(&args[1])?.iter() {
                r.insert_mut(k.clone(), v.clone());
            }
            Ok(Value::Map(r))
        }
        // `m` with `k` removed (a no-op if absent); the persistent-update
        // counterpart of `__Map.with`.
        Builtin::MapWithout => {
            let m = map(&args[0])?;
            Ok(Value::Map(m.remove(&args[1])))
        }
        // Element count of a map, symmetric with `__List.size`.
        Builtin::MapSize => Ok(Value::I64(map(&args[0])?.size() as i64)),
        // Canonical signed decimal of an integer (`15` → `"15"`); the Int half of
        // the scalar→text bridge. A non-int raises `.not_an_int`.
        Builtin::IntStr => {
            let s = match &args[0] {
                Value::I64(x) => x.to_string(),
                Value::BigInt(n) => n.to_string(),
                _ => return Err(Raised::symbol("not_an_int")),
            };
            Ok(Value::Str(Text::from(s.as_str())))
        }
        // Inverse of `Int.str`: parse an integer literal (decimal / `0x`
        // hex / `0b` binary, with optional `_` separators and leading sign)
        // from a string. A non-string raises `.not_a_str`; a string that is
        // not a valid literal or has trailing content raises `.cannot_parse_int`.
        Builtin::IntParse => {
            let s = str_ref(&args[0])?;
            let n = crate::parse::parse_int(s).ok_or_else(|| Raised::symbol("cannot_parse_int"))?;
            Ok(Value::from_bigint(n))
        }
        // Build a string from a list of **codepoints** (Unicode scalar values). A
        // non-int element raises `.not_an_int`; a value outside `0..=0x10FFFF` or in
        // the surrogate range raises `.bad_codepoint`.
        Builtin::StrPack => {
            let t = list(&args[0])?;
            let mut s = String::new();
            for elem in t.iter() {
                let code = match elem {
                    Value::I64(x) => u32::try_from(*x).ok(),
                    Value::BigInt(n) => u32::try_from(&**n).ok(),
                    _ => return Err(Raised::symbol("not_an_int")),
                };
                let cp = code
                    .and_then(char::from_u32)
                    .ok_or_else(|| Raised::symbol("bad_codepoint"))?;
                s.push(cp);
            }
            Ok(Value::Str(Text::from(s.as_str())))
        }
        // Explode a string into a list of its codepoints — the inverse of
        // `__Str.pack`. A non-string raises `.not_a_str`.
        Builtin::StrUnpack => {
            let mut t = Vector::new();
            for ch in str_ref(&args[0])?.chars() {
                t.push_back_mut(Value::I64(ch as i64));
            }
            Ok(Value::List(t))
        }
        // Intern a string as a symbol (`"foo"` → `.foo`); the string→symbol half of
        // the text bridge. The text must be a single Muon `<sym>` segment — the
        // only form that re-parses from `.<text>` — else `.bad_symbol`. A
        // non-string raises `.not_a_str`.
        Builtin::SymFrom => {
            let s = str_ref(&args[0])?;
            if is_sym_segment(s) {
                Ok(Value::Symbol(s.clone()))
            } else {
                Err(Raised::symbol("bad_symbol"))
            }
        }
        // A symbol's text without the dot (`.foo` → `"foo"`); the Sym half of the
        // scalar→text bridge and the inverse of `__Sym.from`. A non-symbol raises
        // `.not_a_sym`.
        Builtin::SymStr => match &args[0] {
            Value::Symbol(s) => Ok(Value::Str(s.clone())),
            _ => Err(Raised::symbol("not_a_sym")),
        },
        // The canonical name a module's code came from (see [`ModuleData::name`]).
        Builtin::ModName => match &args[0] {
            Value::Module(node) => match &**node {
                EnvNode::Module { data, .. } => Ok(match data.name() {
                    Some(name) => Value::Str(name.clone()),
                    // The host never named this code, so there is no name to
                    // report and the unit says so.
                    None => unit(),
                }),
                _ => Err(Raised::symbol("not_a_module")),
            },
            _ => Err(Raised::symbol("not_a_module")),
        },
        // The exported item names as a sorted list of symbols (see
        // [`Builtin::ModExports`]). The table is name-sorted already, so the
        // listing is a straight read — no sort, and no body evaluated.
        Builtin::ModExports => match &args[0] {
            Value::Module(node) => match &**node {
                EnvNode::Module { data, .. } => {
                    let mut out = Vector::new();
                    for (name, _) in data.items() {
                        out.push_back_mut(Value::Symbol(name.clone()));
                    }
                    Ok(Value::List(out))
                }
                _ => Err(Raised::symbol("not_a_module")),
            },
            _ => Err(Raised::symbol("not_a_module")),
        },
        // The prototype of any value at all (see [`proto_of`]).
        Builtin::Proto => Ok(proto_of(&args[0], ctx)),
        Builtin::Repr => {
            let s = args[0].to_display();
            Ok(Value::Str(Text::from(s.as_str())))
        }
        // `__new proto data` — an object of the prototype the leaf supplied. The
        // prototype slot takes a module and nothing else, which is what keeps a
        // prototype a const-time entity with a known item table.
        Builtin::ObjNew => {
            let Value::Module(proto) = &args[0] else {
                return Err(Raised::symbol("not_a_module"));
            };
            Ok(Value::Object(Rc::new(ObjectData {
                proto: proto.clone(),
                data: args[1].clone(),
            })))
        }
        // `__value proto obj` — the payload, provided the object is of that
        // prototype. A non-object is `.not_an_object`; an object of another
        // prototype is `.foreign_object`, so a method cannot unwrap a value that
        // merely passed through it.
        Builtin::ObjValue => {
            let Value::Module(proto) = &args[0] else {
                return Err(Raised::symbol("not_a_module"));
            };
            let Value::Object(obj) = &args[1] else {
                return Err(Raised::symbol("not_an_object"));
            };
            if !EnvRef::ptr_eq(&obj.proto, proto) {
                return Err(Raised::symbol("foreign_object"));
            }
            Ok(obj.data.clone())
        }
        // A builtin module names itself: 0-arity, so a reference *is* the module
        // value (see [`Ctx::builtin_module`]).
        Builtin::Int
        | Builtin::Str
        | Builtin::Sym
        | Builtin::List
        | Builtin::Map
        | Builtin::Err
        | Builtin::Mod
        | Builtin::Bool
        | Builtin::Fun
        | Builtin::Unit => Ok(ctx.builtin_module(op)),
    }
}

/// Borrows an integer as a `BigInt`, or raises `.not_an_int`. `BigInt` is
/// borrowed; `I64` materializes a small allocation. Fast paths in `invoke` avoid this.
fn as_big(v: &Value) -> Result<Cow<'_, BigInt>, Raised> {
    match v {
        Value::I64(x) => Ok(Cow::Owned(BigInt::from(*x))),
        Value::BigInt(n) => Ok(Cow::Borrowed(n)),
        _ => Err(Raised::symbol("not_an_int")),
    }
}

/// Binary `+ - *` logic: `i64` fast path with `BigInt` fallback. The fallback
/// borrows operands to minimize allocations, normalizing the result via
/// [`Value::from_bigint`] to maintain the `I64`-if-it-fits invariant.
fn int_arith(
    a: &Value,
    b: &Value,
    small: impl Fn(i64, i64) -> Option<i64>,
    big: impl Fn(&BigInt, &BigInt) -> BigInt,
) -> Result<Value, Raised> {
    if let (Value::I64(x), Value::I64(y)) = (a, b) {
        if let Some(z) = small(*x, *y) {
            return Ok(Value::I64(z));
        }
    }
    Ok(Value::from_bigint(big(&*as_big(a)?, &*as_big(b)?)))
}

/// Relational `__Int.*` logic: compares two integers and maps [`Ordering`] to a
/// [`Bool`](Builtin::Bool) iota. Uses `i64` fast path and `BigInt` fallback.
fn int_cmp(
    a: &Value,
    b: &Value,
    ctx: &Ctx,
    hold: impl Fn(Ordering) -> bool,
) -> Result<Value, Raised> {
    let ord = if let (Value::I64(x), Value::I64(y)) = (a, b) {
        x.cmp(y)
    } else {
        as_big(a)?.cmp(&as_big(b)?)
    };
    Ok(bool_value(ctx, hold(ord)))
}

/// Borrows a value as a list, or raises `.not_a_list`. Used by `__List.*` builtins.
fn list(v: &Value) -> Result<&Vector<Value>, Raised> {
    match v {
        Value::List(t) => Ok(t),
        _ => Err(Raised::symbol("not_a_list")),
    }
}

/// Borrows a value as a string, or raises `.not_a_str`. Used by `__Str.*` / `__Sym.*` builtins.
fn str_ref(v: &Value) -> Result<&Text, Raised> {
    match v {
        Value::Str(s) => Ok(s),
        _ => Err(Raised::symbol("not_a_str")),
    }
}

/// Checks if `s` is a single Muon `<sym>` (non-empty run of `[0-9A-Za-z_+-]`).
/// This is the admissible domain of `__Sym.from`.
fn is_sym_segment(s: &str) -> bool {
    !s.is_empty()
        && s.bytes()
            .all(|c| c.is_ascii_alphanumeric() || matches!(c, b'_' | b'-' | b'+'))
}

/// Borrows a value as a map, or raises `.not_a_map`. Used by `__Map.*` builtins.
fn map(v: &Value) -> Result<&HashTrieMap<Value, Value>, Raised> {
    match v {
        Value::Map(m) => Ok(m),
        _ => Err(Raised::symbol("not_a_map")),
    }
}

/// Encodes an optional map value as `__Map.merge`'s option: `[]` (none) or `[v]`
/// (some) for the merge callback.
fn option(v: Option<&Value>) -> Value {
    match v {
        None => Value::List(Vector::new()),
        Some(v) => {
            let mut t = Vector::new();
            t.push_back_mut(v.clone());
            Value::List(t)
        }
    }
}

/// Decodes a `__Map.merge` callback result as an option: `[]` (drop key) or `[v]`
/// (set key). Raises `.not_a_list` or `.list_size_mismatch`.
fn un_option(v: &Value) -> Result<Option<Value>, Raised> {
    let t = list(v)?;
    match t.len() {
        0 => Ok(None),
        1 => Ok(Some(t.get(0).unwrap().clone())),
        _ => Err(Raised::symbol("list_size_mismatch")),
    }
}

/// Reads an integer as a 0-based index. Non-integers raise `.not_an_int`;
/// negative or out-of-`usize` values yield `None`. Shared by `__List.get`/`with`/`split`.
fn index_of(v: &Value) -> Result<Option<usize>, Raised> {
    match v {
        // A negative `i64` fails `usize::try_from` → `None` (out of range).
        Value::I64(x) => Ok(usize::try_from(*x).ok()),
        Value::BigInt(n) => Ok(u64::try_from(&**n)
            .ok()
            .and_then(|u| usize::try_from(u).ok())),
        _ => Err(Raised::symbol("not_an_int")),
    }
}

/// Euclidean quotient/remainder: `a = b*q + r` with `0 <= r < |b|`.
/// Raises `.div_by_zero` if `b == 0`.
fn div_rem_euclid(a: &BigInt, b: &BigInt) -> Result<(BigInt, BigInt), Raised> {
    if b.sign() == Sign::NoSign {
        return Err(Raised::symbol("div_by_zero"));
    }
    let q = a / b; // truncated toward zero
    let r = a - &q * b;
    // Truncated `r` carries the sign of `a`; nudge it into `[0, |b|)`.
    Ok(if r.sign() == Sign::Minus {
        if b.sign() == Sign::Plus {
            (q - 1, r + b)
        } else {
            (q + 1, r - b)
        }
    } else {
        (q, r)
    })
}

/// The unit value `()`. Fed by the nullary marker `()` and used to force the
/// `__Int.*` / `__Err.catch` branch thunks.
fn unit() -> Value {
    Value::Unit
}

/// The `false` / `true` iota positions in [`__Bool`](Builtin::Bool)'s name-sorted
/// iota table — `false` before `true`. [`bool_value`] and [`as_bool`] both read
/// the table through these, so a change to the table's order is a change here.
const BOOL_FALSE_IDX: u32 = 0;
const BOOL_TRUE_IDX: u32 = 1;

/// A [`Bool`](Builtin::Bool) iota for a Rust `bool`, derived from the context's
/// cached `__Bool` instance — no minting, exactly as a member access on the module
/// would produce (see the *iotas* section of
/// `docs/done/2026-08-13_elly-modules-iotas.md`). Both `__true` and `Bool.true`
/// funnel here, so they are the same iota of the same instance and compare equal.
fn bool_value(ctx: &Ctx, b: bool) -> Value {
    let Value::Module(home) = ctx.builtin_module(Builtin::Bool) else {
        unreachable!("a builtin module is a module value")
    };
    let index = if b { BOOL_TRUE_IDX } else { BOOL_FALSE_IDX };
    Value::Iota { home, index }
}

/// Read a value as a Rust `bool`, or raise `.not_a_bool` — the strict-argument
/// check the `__Bool.*` logic shares, mirroring [`as_big`] / [`list`]. A value is
/// a boolean only if it is an iota of *this* context's `__Bool` instance, told by
/// pointer identity against the cached module; the index then names which.
pub(crate) fn as_bool(v: &Value, ctx: &Ctx) -> Result<bool, Raised> {
    let Value::Module(home) = ctx.builtin_module(Builtin::Bool) else {
        unreachable!("a builtin module is a module value")
    };
    if let Value::Iota { home: h, index } = v {
        if EnvRef::ptr_eq(h, &home) {
            return Ok(*index == BOOL_TRUE_IDX);
        }
    }
    Err(Raised::symbol("not_a_bool"))
}