clm-kernel 0.0.24

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! The term algebra every interpreter compiles to (INV-626).
//!
//! ```text
//! Term ::= BoundVar(index) | FreeVar(name) | Abs(body, hint) | App(func, arg) | Lit(lit) | Prim(name, args)
//! ```
//!
//! A bound variable is a 0-based de Bruijn index and a free variable keeps its name (locally
//! nameless), so two terms that differ only in bound-variable names are equal with no renaming pass.
//! The `Abs` hint is the binder's display name, and equality and hashing ignore it.
//!
//! A term is an immutable value: building one, substituting into one, and reducing one allocate new
//! values and write nothing. `Lit` holds one of seven kinds. Integer and decimal stay distinct, and a
//! decimal keeps its source text, because the three runtimes do not agree on `1 == 1.0`.

pub mod parse;
pub mod reduce;
pub mod render;

use std::collections::BTreeSet;
use std::hash::{Hash, Hasher};

use crate::layer0::vocabulary::{
    GUARD_LIT_NULL, JS_TYPE_BOOLEAN, JS_TYPE_STRING, TERM_KIND_COLLECTION, TERM_KIND_DECIMAL,
    TERM_KIND_INTEGER, TERM_KIND_VERDICT,
};

pub use parse::{parse, ParseFailure};
pub use reduce::{
    check_kinds, eta_expand, eta_reduce, evaluate, no_primitives, normalize, whnf, PrimRule, Reduced,
    Reduction, Resolver, Strategy, Stuck, StuckReason,
};
pub use render::{name_binders, render, render_literal};

/// A binder's display name. Every two hints compare equal and hash alike, so alpha-equal terms are equal.
#[derive(Clone, Debug, Default)]
pub struct Hint(pub String);

impl PartialEq for Hint {
    fn eq(&self, _: &Self) -> bool {
        true
    }
}

impl Eq for Hint {}

impl Hash for Hint {
    fn hash<H: Hasher>(&self, _: &mut H) {}
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum Term {
    BoundVar(usize),
    FreeVar(String),
    Abs(Box<Term>, Hint),
    App(Box<Term>, Box<Term>),
    Lit(Lit),
    Prim(String, Vec<Term>),
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum LitKind {
    Null,
    Boolean,
    Integer,
    Decimal,
    String,
    Collection,
    Verdict,
}

impl LitKind {
    pub fn as_str(self) -> &'static str {
        match self {
            LitKind::Null => GUARD_LIT_NULL,
            LitKind::Boolean => JS_TYPE_BOOLEAN,
            LitKind::Integer => TERM_KIND_INTEGER,
            LitKind::Decimal => TERM_KIND_DECIMAL,
            LitKind::String => JS_TYPE_STRING,
            LitKind::Collection => TERM_KIND_COLLECTION,
            LitKind::Verdict => TERM_KIND_VERDICT,
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Verdict {
    pub outcome: String,
    pub reason: String,
    pub invariant_code: String,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum Lit {
    Null,
    Boolean(bool),
    Integer(i64),
    /// The decimal's source text, kept verbatim.
    Decimal(String),
    String(String),
    Collection(Collection),
    Verdict(Verdict),
}

/// A list holds literals and a map holds key-sorted pairs. The empty list and the empty map are one value.
#[derive(Clone, Debug, Eq)]
pub enum Collection {
    List(Vec<Lit>),
    Map(Vec<(String, Lit)>),
}

impl Collection {
    pub fn is_empty(&self) -> bool {
        match self {
            Collection::List(items) => items.is_empty(),
            Collection::Map(entries) => entries.is_empty(),
        }
    }
}

impl PartialEq for Collection {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Collection::List(left), Collection::List(right)) => left == right,
            (Collection::Map(left), Collection::Map(right)) => left == right,
            _ => self.is_empty() && other.is_empty(),
        }
    }
}

/// An empty list and an empty map are equal, and both hash as a zero-length sequence.
impl Hash for Collection {
    fn hash<H: Hasher>(&self, state: &mut H) {
        match self {
            Collection::List(items) => items.hash(state),
            Collection::Map(entries) => entries.hash(state),
        }
    }
}

impl Lit {
    pub fn kind(&self) -> LitKind {
        match self {
            Lit::Null => LitKind::Null,
            Lit::Boolean(_) => LitKind::Boolean,
            Lit::Integer(_) => LitKind::Integer,
            Lit::Decimal(_) => LitKind::Decimal,
            Lit::String(_) => LitKind::String,
            Lit::Collection(_) => LitKind::Collection,
            Lit::Verdict(_) => LitKind::Verdict,
        }
    }

    pub fn decimal(text: impl Into<String>) -> Lit {
        Lit::Decimal(text.into())
    }

    pub fn string(value: impl Into<String>) -> Lit {
        Lit::String(value.into())
    }

    pub fn list(items: impl IntoIterator<Item = Lit>) -> Lit {
        Lit::Collection(Collection::List(items.into_iter().collect()))
    }

    /// A map literal, as pairs sorted by key with a stable sort.
    pub fn map(entries: impl IntoIterator<Item = (String, Lit)>) -> Lit {
        let mut entries: Vec<(String, Lit)> = entries.into_iter().collect();
        entries.sort_by(|left, right| left.0.cmp(&right.0));
        Lit::Collection(Collection::Map(entries))
    }

    pub fn verdict(outcome: impl Into<String>, reason: impl Into<String>, invariant_code: impl Into<String>) -> Lit {
        Lit::Verdict(Verdict { outcome: outcome.into(), reason: reason.into(), invariant_code: invariant_code.into() })
    }
}

impl Term {
    pub fn free(name: impl Into<String>) -> Term {
        Term::FreeVar(name.into())
    }

    pub fn abs(body: Term, hint: impl Into<String>) -> Term {
        Term::Abs(Box::new(body), Hint(hint.into()))
    }

    pub fn app(func: Term, arg: Term) -> Term {
        Term::App(Box::new(func), Box::new(arg))
    }

    pub fn prim(name: impl Into<String>, args: Vec<Term>) -> Term {
        Term::Prim(name.into(), args)
    }

    pub fn children(&self) -> Vec<&Term> {
        match self {
            Term::Abs(body, _) => vec![body],
            Term::App(func, arg) => vec![func, arg],
            Term::Prim(_, args) => args.iter().collect(),
            _ => Vec::new(),
        }
    }

    /// This term with every child replaced by `f(child)`, in `children` order.
    pub fn map_children(&self, mut f: impl FnMut(&Term) -> Term) -> Term {
        match self {
            Term::Abs(body, hint) => Term::Abs(Box::new(f(body)), hint.clone()),
            Term::App(func, arg) => Term::app(f(func), f(arg)),
            Term::Prim(name, args) => Term::Prim(name.clone(), args.iter().map(f).collect()),
            _ => self.clone(),
        }
    }

    /// This term with child `position` replaced by `replacement`.
    pub fn replace_child(&self, position: usize, replacement: Term) -> Term {
        let mut replacement = Some(replacement);
        let mut index = 0;
        self.map_children(|child| {
            let next = if index == position { replacement.take() } else { None };
            index += 1;
            next.unwrap_or_else(|| child.clone())
        })
    }

    fn binders(&self) -> usize {
        usize::from(matches!(self, Term::Abs(..)))
    }
}

/// Add `delta` to every bound index at or above `cutoff`.
///
/// Lowering an index below zero is a caller error, as `eta_reduce` shows by checking `occurs` first.
pub fn shift(term: &Term, delta: isize, cutoff: usize) -> Term {
    if let Term::BoundVar(index) = term {
        if *index < cutoff {
            return term.clone();
        }
        let Some(shifted) = index.checked_add_signed(delta) else { unreachable!() };
        return Term::BoundVar(shifted);
    }
    let inner = cutoff + term.binders();
    term.map_children(|child| shift(child, delta, inner))
}

/// `term` with bound index `index` replaced by `replacement` and every higher index lowered by one.
///
/// Capture cannot happen: `replacement` is shifted by the number of binders it passes under.
pub fn substitute(term: &Term, index: usize, replacement: &Term) -> Term {
    if let Term::BoundVar(found) = term {
        return match (*found).cmp(&index) {
            std::cmp::Ordering::Equal => shift(replacement, index as isize, 0),
            std::cmp::Ordering::Greater => Term::BoundVar(found - 1),
            std::cmp::Ordering::Less => term.clone(),
        };
    }
    let inner = index + term.binders();
    term.map_children(|child| substitute(child, inner, replacement))
}

/// The body of an abstraction applied to `argument`: `(λ.body) argument`.
pub fn instantiate(body: &Term, argument: &Term) -> Term {
    substitute(body, 0, argument)
}

/// Whether bound index `index` occurs free in `term`.
pub fn occurs(term: &Term, index: usize) -> bool {
    if let Term::BoundVar(found) = term {
        return *found == index;
    }
    let inner = index + term.binders();
    term.children().into_iter().any(|child| occurs(child, inner))
}

pub fn free_names(term: &Term) -> BTreeSet<String> {
    if let Term::FreeVar(name) = term {
        return BTreeSet::from([name.clone()]);
    }
    term.children().into_iter().flat_map(free_names).collect()
}

pub fn binder_hints(term: &Term) -> BTreeSet<String> {
    let mut hints: BTreeSet<String> = term.children().into_iter().flat_map(binder_hints).collect();
    if let Term::Abs(_, hint) = term {
        hints.insert(hint.0.clone());
    }
    hints
}

/// The height of the term tree, computed without recursion so a deep term cannot exhaust the stack.
pub fn depth(term: &Term) -> usize {
    let mut deepest = 0;
    let mut pending = vec![(term, 1)];
    while let Some((node, level)) = pending.pop() {
        deepest = deepest.max(level);
        pending.extend(node.children().into_iter().map(|child| (child, level + 1)));
    }
    deepest
}