Skip to main content

clm_rust_core/layer0/term/
mod.rs

1//! The term algebra every interpreter compiles to (INV-626).
2//!
3//! ```text
4//! Term ::= BoundVar(index) | FreeVar(name) | Abs(body, hint) | App(func, arg) | Lit(lit) | Prim(name, args)
5//! ```
6//!
7//! A bound variable is a 0-based de Bruijn index and a free variable keeps its name (locally
8//! nameless), so two terms that differ only in bound-variable names are equal with no renaming pass.
9//! The `Abs` hint is the binder's display name, and equality and hashing ignore it.
10//!
11//! A term is an immutable value: building one, substituting into one, and reducing one allocate new
12//! values and write nothing. `Lit` holds one of seven kinds. Integer and decimal stay distinct, and a
13//! decimal keeps its source text, because the three runtimes do not agree on `1 == 1.0`.
14
15pub mod parse;
16pub mod reduce;
17pub mod render;
18
19use std::collections::BTreeSet;
20use std::hash::{Hash, Hasher};
21
22use crate::layer0::vocabulary::{
23    GUARD_LIT_NULL, JS_TYPE_BOOLEAN, JS_TYPE_STRING, TERM_KIND_COLLECTION, TERM_KIND_DECIMAL,
24    TERM_KIND_INTEGER, TERM_KIND_VERDICT,
25};
26
27pub use parse::{parse, ParseFailure};
28pub use reduce::{
29    check_kinds, eta_expand, eta_reduce, evaluate, no_primitives, normalize, whnf, PrimRule, Reduced,
30    Reduction, Resolver, Strategy, Stuck, StuckReason,
31};
32pub use render::{name_binders, render, render_literal};
33
34/// A binder's display name. Every two hints compare equal and hash alike, so alpha-equal terms are equal.
35#[derive(Clone, Debug, Default)]
36pub struct Hint(pub String);
37
38impl PartialEq for Hint {
39    fn eq(&self, _: &Self) -> bool {
40        true
41    }
42}
43
44impl Eq for Hint {}
45
46impl Hash for Hint {
47    fn hash<H: Hasher>(&self, _: &mut H) {}
48}
49
50#[derive(Clone, Debug, PartialEq, Eq, Hash)]
51pub enum Term {
52    BoundVar(usize),
53    FreeVar(String),
54    Abs(Box<Term>, Hint),
55    App(Box<Term>, Box<Term>),
56    Lit(Lit),
57    Prim(String, Vec<Term>),
58}
59
60#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
61pub enum LitKind {
62    Null,
63    Boolean,
64    Integer,
65    Decimal,
66    String,
67    Collection,
68    Verdict,
69}
70
71impl LitKind {
72    pub fn as_str(self) -> &'static str {
73        match self {
74            LitKind::Null => GUARD_LIT_NULL,
75            LitKind::Boolean => JS_TYPE_BOOLEAN,
76            LitKind::Integer => TERM_KIND_INTEGER,
77            LitKind::Decimal => TERM_KIND_DECIMAL,
78            LitKind::String => JS_TYPE_STRING,
79            LitKind::Collection => TERM_KIND_COLLECTION,
80            LitKind::Verdict => TERM_KIND_VERDICT,
81        }
82    }
83}
84
85#[derive(Clone, Debug, PartialEq, Eq, Hash)]
86pub struct Verdict {
87    pub outcome: String,
88    pub reason: String,
89    pub invariant_code: String,
90}
91
92#[derive(Clone, Debug, PartialEq, Eq, Hash)]
93pub enum Lit {
94    Null,
95    Boolean(bool),
96    Integer(i64),
97    /// The decimal's source text, kept verbatim.
98    Decimal(String),
99    String(String),
100    Collection(Collection),
101    Verdict(Verdict),
102}
103
104/// A list holds literals and a map holds key-sorted pairs. The empty list and the empty map are one value.
105#[derive(Clone, Debug, Eq)]
106pub enum Collection {
107    List(Vec<Lit>),
108    Map(Vec<(String, Lit)>),
109}
110
111impl Collection {
112    pub fn is_empty(&self) -> bool {
113        match self {
114            Collection::List(items) => items.is_empty(),
115            Collection::Map(entries) => entries.is_empty(),
116        }
117    }
118}
119
120impl PartialEq for Collection {
121    fn eq(&self, other: &Self) -> bool {
122        match (self, other) {
123            (Collection::List(left), Collection::List(right)) => left == right,
124            (Collection::Map(left), Collection::Map(right)) => left == right,
125            _ => self.is_empty() && other.is_empty(),
126        }
127    }
128}
129
130/// An empty list and an empty map are equal, and both hash as a zero-length sequence.
131impl Hash for Collection {
132    fn hash<H: Hasher>(&self, state: &mut H) {
133        match self {
134            Collection::List(items) => items.hash(state),
135            Collection::Map(entries) => entries.hash(state),
136        }
137    }
138}
139
140impl Lit {
141    pub fn kind(&self) -> LitKind {
142        match self {
143            Lit::Null => LitKind::Null,
144            Lit::Boolean(_) => LitKind::Boolean,
145            Lit::Integer(_) => LitKind::Integer,
146            Lit::Decimal(_) => LitKind::Decimal,
147            Lit::String(_) => LitKind::String,
148            Lit::Collection(_) => LitKind::Collection,
149            Lit::Verdict(_) => LitKind::Verdict,
150        }
151    }
152
153    pub fn decimal(text: impl Into<String>) -> Lit {
154        Lit::Decimal(text.into())
155    }
156
157    pub fn string(value: impl Into<String>) -> Lit {
158        Lit::String(value.into())
159    }
160
161    pub fn list(items: impl IntoIterator<Item = Lit>) -> Lit {
162        Lit::Collection(Collection::List(items.into_iter().collect()))
163    }
164
165    /// A map literal, as pairs sorted by key with a stable sort.
166    pub fn map(entries: impl IntoIterator<Item = (String, Lit)>) -> Lit {
167        let mut entries: Vec<(String, Lit)> = entries.into_iter().collect();
168        entries.sort_by(|left, right| left.0.cmp(&right.0));
169        Lit::Collection(Collection::Map(entries))
170    }
171
172    pub fn verdict(outcome: impl Into<String>, reason: impl Into<String>, invariant_code: impl Into<String>) -> Lit {
173        Lit::Verdict(Verdict { outcome: outcome.into(), reason: reason.into(), invariant_code: invariant_code.into() })
174    }
175}
176
177impl Term {
178    pub fn free(name: impl Into<String>) -> Term {
179        Term::FreeVar(name.into())
180    }
181
182    pub fn abs(body: Term, hint: impl Into<String>) -> Term {
183        Term::Abs(Box::new(body), Hint(hint.into()))
184    }
185
186    pub fn app(func: Term, arg: Term) -> Term {
187        Term::App(Box::new(func), Box::new(arg))
188    }
189
190    pub fn prim(name: impl Into<String>, args: Vec<Term>) -> Term {
191        Term::Prim(name.into(), args)
192    }
193
194    pub fn children(&self) -> Vec<&Term> {
195        match self {
196            Term::Abs(body, _) => vec![body],
197            Term::App(func, arg) => vec![func, arg],
198            Term::Prim(_, args) => args.iter().collect(),
199            _ => Vec::new(),
200        }
201    }
202
203    /// This term with every child replaced by `f(child)`, in `children` order.
204    pub fn map_children(&self, mut f: impl FnMut(&Term) -> Term) -> Term {
205        match self {
206            Term::Abs(body, hint) => Term::Abs(Box::new(f(body)), hint.clone()),
207            Term::App(func, arg) => Term::app(f(func), f(arg)),
208            Term::Prim(name, args) => Term::Prim(name.clone(), args.iter().map(f).collect()),
209            _ => self.clone(),
210        }
211    }
212
213    /// This term with child `position` replaced by `replacement`.
214    pub fn replace_child(&self, position: usize, replacement: Term) -> Term {
215        let mut replacement = Some(replacement);
216        let mut index = 0;
217        self.map_children(|child| {
218            let next = if index == position { replacement.take() } else { None };
219            index += 1;
220            next.unwrap_or_else(|| child.clone())
221        })
222    }
223
224    fn binders(&self) -> usize {
225        usize::from(matches!(self, Term::Abs(..)))
226    }
227}
228
229/// Add `delta` to every bound index at or above `cutoff`.
230///
231/// Lowering an index below zero is a caller error, as `eta_reduce` shows by checking `occurs` first.
232pub fn shift(term: &Term, delta: isize, cutoff: usize) -> Term {
233    if let Term::BoundVar(index) = term {
234        if *index < cutoff {
235            return term.clone();
236        }
237        let Some(shifted) = index.checked_add_signed(delta) else { unreachable!() };
238        return Term::BoundVar(shifted);
239    }
240    let inner = cutoff + term.binders();
241    term.map_children(|child| shift(child, delta, inner))
242}
243
244/// `term` with bound index `index` replaced by `replacement` and every higher index lowered by one.
245///
246/// Capture cannot happen: `replacement` is shifted by the number of binders it passes under.
247pub fn substitute(term: &Term, index: usize, replacement: &Term) -> Term {
248    if let Term::BoundVar(found) = term {
249        return match (*found).cmp(&index) {
250            std::cmp::Ordering::Equal => shift(replacement, index as isize, 0),
251            std::cmp::Ordering::Greater => Term::BoundVar(found - 1),
252            std::cmp::Ordering::Less => term.clone(),
253        };
254    }
255    let inner = index + term.binders();
256    term.map_children(|child| substitute(child, inner, replacement))
257}
258
259/// The body of an abstraction applied to `argument`: `(λ.body) argument`.
260pub fn instantiate(body: &Term, argument: &Term) -> Term {
261    substitute(body, 0, argument)
262}
263
264/// Whether bound index `index` occurs free in `term`.
265pub fn occurs(term: &Term, index: usize) -> bool {
266    if let Term::BoundVar(found) = term {
267        return *found == index;
268    }
269    let inner = index + term.binders();
270    term.children().into_iter().any(|child| occurs(child, inner))
271}
272
273pub fn free_names(term: &Term) -> BTreeSet<String> {
274    if let Term::FreeVar(name) = term {
275        return BTreeSet::from([name.clone()]);
276    }
277    term.children().into_iter().flat_map(free_names).collect()
278}
279
280pub fn binder_hints(term: &Term) -> BTreeSet<String> {
281    let mut hints: BTreeSet<String> = term.children().into_iter().flat_map(binder_hints).collect();
282    if let Term::Abs(_, hint) = term {
283        hints.insert(hint.0.clone());
284    }
285    hints
286}
287
288/// The height of the term tree, computed without recursion so a deep term cannot exhaust the stack.
289pub fn depth(term: &Term) -> usize {
290    let mut deepest = 0;
291    let mut pending = vec![(term, 1)];
292    while let Some((node, level)) = pending.pop() {
293        deepest = deepest.max(level);
294        pending.extend(node.children().into_iter().map(|child| (child, level + 1)));
295    }
296    deepest
297}