clm-kernel 0.0.24

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Reduce a term (INV-626).
//!
//! Reduction is total. Every reducer returns `Normal`, `OutOfFuel`, or `Stuck` and never panics.
//! Fuel is a required argument: the shared value is `TERM_REDUCTION_FUEL`, and a caller that wants
//! another bound passes it. A term deeper than `SPEC_TERM_MAX_DEPTH` is `Stuck`, so a reducer never
//! exhausts the host stack.
//!
//! A primitive is resolved through the `resolver` argument, so this module imports no domain. Its
//! rule carries a signature over the literal kinds and a pure delta function. `absorbing` lists the
//! literals that end left-to-right evaluation of the arguments, as `false` does for `and`.

use super::{depth, instantiate, occurs, shift, Lit, LitKind, Term};
use crate::layer0::limits::SPEC_TERM_MAX_DEPTH;
use crate::layer0::vocabulary::{
    TERM_STRATEGY_APPLICATIVE, TERM_STRATEGY_NORMAL, TERM_STUCK_ARITY, TERM_STUCK_DEPTH, TERM_STUCK_KIND,
    TERM_STUCK_NOT_FIRST_ORDER, TERM_STUCK_NO_RULE, TERM_STUCK_UNKNOWN_PRIMITIVE,
};

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Strategy {
    /// Leftmost outermost.
    Normal,
    /// Leftmost innermost.
    Applicative,
}

impl Strategy {
    pub fn as_str(self) -> &'static str {
        match self {
            Strategy::Normal => TERM_STRATEGY_NORMAL,
            Strategy::Applicative => TERM_STRATEGY_APPLICATIVE,
        }
    }

    pub fn from_name(name: &str) -> Option<Strategy> {
        [Strategy::Normal, Strategy::Applicative].into_iter().find(|strategy| strategy.as_str() == name)
    }

    fn outermost(self) -> bool {
        self == Strategy::Normal
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum StuckReason {
    UnknownPrimitive,
    Arity,
    Kind,
    NoRule,
    NotFirstOrder,
    Depth,
}

impl StuckReason {
    pub fn as_str(self) -> &'static str {
        match self {
            StuckReason::UnknownPrimitive => TERM_STUCK_UNKNOWN_PRIMITIVE,
            StuckReason::Arity => TERM_STUCK_ARITY,
            StuckReason::Kind => TERM_STUCK_KIND,
            StuckReason::NoRule => TERM_STUCK_NO_RULE,
            StuckReason::NotFirstOrder => TERM_STUCK_NOT_FIRST_ORDER,
            StuckReason::Depth => TERM_STUCK_DEPTH,
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Stuck {
    pub term: Term,
    pub reason: StuckReason,
}

/// A reduct and the steps taken to reach it. `trace` holds the term after every step, starting with
/// the input, when the caller asked for it, and is empty otherwise.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Reduced {
    pub term: Term,
    pub steps: u32,
    pub trace: Vec<Term>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum Reduction {
    Normal(Reduced),
    OutOfFuel(Reduced),
    Stuck(Stuck),
}

pub struct PrimRule {
    pub arg_kinds: Vec<LitKind>,
    pub result_kind: LitKind,
    pub delta: Box<dyn Fn(&[Lit]) -> Option<Lit> + Send + Sync>,
    pub absorbing: Vec<Lit>,
}

pub type Resolver<'r> = &'r dyn Fn(&str) -> Option<&'r PrimRule>;

/// The resolver that knows no primitive.
pub fn no_primitives<'r>(_: &str) -> Option<&'r PrimRule> {
    None
}

fn stuck(term: Term, reason: StuckReason) -> Stuck {
    Stuck { term, reason }
}

fn too_deep(term: &Term) -> bool {
    depth(term) as i64 > SPEC_TERM_MAX_DEPTH
}

/// One beta step at the root: `(λ.body) arg` becomes `body` with index 0 replaced by `arg`.
fn contract(term: &Term) -> Option<Term> {
    match term {
        Term::App(func, arg) => match func.as_ref() {
            Term::Abs(body, _) => Some(instantiate(body, arg)),
            _ => None,
        },
        _ => None,
    }
}

fn literal_args(args: &[Term]) -> Option<Vec<Lit>> {
    args.iter().map(|arg| if let Term::Lit(lit) = arg { Some(lit.clone()) } else { None }).collect()
}

fn delta(name: &str, args: &[Lit], rule: Option<&PrimRule>) -> Result<Lit, Stuck> {
    let fail = |reason| stuck(Term::prim(name, args.iter().cloned().map(Term::Lit).collect()), reason);
    let rule = rule.ok_or_else(|| fail(StuckReason::UnknownPrimitive))?;
    if args.len() != rule.arg_kinds.len() {
        return Err(fail(StuckReason::Arity));
    }
    if args.iter().zip(&rule.arg_kinds).any(|(arg, kind)| arg.kind() != *kind) {
        return Err(fail(StuckReason::Kind));
    }
    let result = (rule.delta)(args).ok_or_else(|| fail(StuckReason::NoRule))?;
    if result.kind() == rule.result_kind { Ok(result) } else { Err(fail(StuckReason::Kind)) }
}

/// The absorbing literal that ends evaluation of a primitive, reading its literal arguments left to right.
fn absorbed(args: &[Term], rule: Option<&PrimRule>) -> Option<Lit> {
    for arg in args {
        let Term::Lit(lit) = arg else { return None };
        if rule.is_some_and(|rule| rule.absorbing.contains(lit)) {
            return Some(lit.clone());
        }
    }
    None
}

/// One reduction step, or `None` when `term` has none. `weak` stops under abstractions and in arguments.
fn step(term: &Term, strategy: Strategy, resolver: Resolver, weak: bool) -> Result<Option<Term>, Stuck> {
    if strategy.outermost() {
        if let Some(reduct) = contract(term) {
            return Ok(Some(reduct));
        }
    }
    let mut rule = None;
    match term {
        Term::Prim(name, args) => {
            rule = resolver(name);
            if let Some(lit) = absorbed(args, rule) {
                return Ok(Some(Term::Lit(lit)));
            }
        }
        Term::App(..) => {}
        _ if weak => return Ok(None),
        _ => {}
    }
    let parts = term.children();
    let reachable = if weak && matches!(term, Term::App(..)) { 1 } else { parts.len() };
    for (position, child) in parts.into_iter().take(reachable).enumerate() {
        if let Some(stepped) = step(child, strategy, resolver, weak)? {
            return Ok(Some(term.replace_child(position, stepped)));
        }
    }
    if let Some(reduct) = contract(term) {
        return Ok(Some(reduct));
    }
    if let Term::Prim(name, args) = term {
        if let Some(values) = literal_args(args) {
            return delta(name, &values, rule).map(|lit| Some(Term::Lit(lit)));
        }
    }
    Ok(None)
}

fn run(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool, weak: bool) -> Reduction {
    let mut term = term.clone();
    let mut steps = 0;
    let mut path = if trace { vec![term.clone()] } else { Vec::new() };
    loop {
        if too_deep(&term) {
            return Reduction::Stuck(stuck(term, StuckReason::Depth));
        }
        let stepped = match step(&term, strategy, resolver, weak) {
            Err(stuck) => return Reduction::Stuck(stuck),
            Ok(None) => return Reduction::Normal(Reduced { term, steps, trace: path }),
            Ok(Some(_)) if steps >= fuel => return Reduction::OutOfFuel(Reduced { term, steps, trace: path }),
            Ok(Some(stepped)) => stepped,
        };
        term = stepped;
        steps += 1;
        if trace {
            path.push(term.clone());
        }
    }
}

/// Full normal form under `strategy`, in at most `fuel` steps. `trace` records the term after every step.
pub fn normalize(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool) -> Reduction {
    run(term, strategy, fuel, resolver, trace, false)
}

/// Weak head normal form: reduce the head to an abstraction or a literal, and stop there.
pub fn whnf(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool) -> Reduction {
    run(term, strategy, fuel, resolver, trace, true)
}

/// First-order evaluation of a binder-free term in one bottom-up pass. It takes no beta step, so it needs no fuel.
pub fn evaluate(term: &Term, resolver: Resolver) -> Result<Reduced, Stuck> {
    if too_deep(term) {
        return Err(stuck(term.clone(), StuckReason::Depth));
    }
    evaluate_within(term, resolver).map(|(lit, steps)| Reduced { term: Term::Lit(lit), steps, trace: Vec::new() })
}

fn evaluate_within(term: &Term, resolver: Resolver) -> Result<(Lit, u32), Stuck> {
    let (name, args) = match term {
        Term::Lit(lit) => return Ok((lit.clone(), 0)),
        Term::Prim(name, args) => (name, args),
        _ => return Err(stuck(term.clone(), StuckReason::NotFirstOrder)),
    };
    let rule = resolver(name);
    let mut steps = 1;
    let mut values = Vec::with_capacity(args.len());
    for arg in args {
        let (value, taken) = evaluate_within(arg, resolver)?;
        steps += taken;
        if rule.is_some_and(|rule| rule.absorbing.contains(&value)) {
            return Ok((value, steps));
        }
        values.push(value);
    }
    delta(name, &values, rule).map(|lit| (lit, steps))
}

/// The literal kind a binder-free term evaluates to, checked against every primitive's signature without evaluating it.
pub fn check_kinds(term: &Term, resolver: Resolver) -> Result<LitKind, Stuck> {
    let (name, args) = match term {
        Term::Lit(lit) => return Ok(lit.kind()),
        Term::Prim(name, args) => (name, args),
        _ => return Err(stuck(term.clone(), StuckReason::NotFirstOrder)),
    };
    let rule = resolver(name).ok_or_else(|| stuck(term.clone(), StuckReason::UnknownPrimitive))?;
    if args.len() != rule.arg_kinds.len() {
        return Err(stuck(term.clone(), StuckReason::Arity));
    }
    for (arg, kind) in args.iter().zip(&rule.arg_kinds) {
        if check_kinds(arg, resolver)? != *kind {
            return Err(stuck(term.clone(), StuckReason::Kind));
        }
    }
    Ok(rule.result_kind)
}

/// Contract every outermost eta redex: `λ.(M 0)` becomes `M` lowered by one when index 0 is not free in `M`.
pub fn eta_reduce(term: &Term) -> Term {
    if let Term::Abs(body, _) = term {
        if let Term::App(func, arg) = body.as_ref() {
            if **arg == Term::BoundVar(0) && !occurs(func, 0) {
                return shift(func, -1, 0);
            }
        }
    }
    term.map_children(eta_reduce)
}

pub fn eta_expand(term: &Term, hint: &str) -> Term {
    Term::abs(Term::app(shift(term, 1, 0), Term::BoundVar(0)), hint)
}