Skip to main content

clm_rust_core/layer0/term/
reduce.rs

1//! Reduce a term (INV-626).
2//!
3//! Reduction is total. Every reducer returns `Normal`, `OutOfFuel`, or `Stuck` and never panics.
4//! Fuel is a required argument: the shared value is `TERM_REDUCTION_FUEL`, and a caller that wants
5//! another bound passes it. A term deeper than `SPEC_TERM_MAX_DEPTH` is `Stuck`, so a reducer never
6//! exhausts the host stack.
7//!
8//! A primitive is resolved through the `resolver` argument, so this module imports no domain. Its
9//! rule carries a signature over the literal kinds and a pure delta function. `absorbing` lists the
10//! literals that end left-to-right evaluation of the arguments, as `false` does for `and`.
11
12use super::{depth, instantiate, occurs, shift, Lit, LitKind, Term};
13use crate::layer0::limits::SPEC_TERM_MAX_DEPTH;
14use crate::layer0::vocabulary::{
15    TERM_STRATEGY_APPLICATIVE, TERM_STRATEGY_NORMAL, TERM_STUCK_ARITY, TERM_STUCK_DEPTH, TERM_STUCK_KIND,
16    TERM_STUCK_NOT_FIRST_ORDER, TERM_STUCK_NO_RULE, TERM_STUCK_UNKNOWN_PRIMITIVE,
17};
18
19#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
20pub enum Strategy {
21    /// Leftmost outermost.
22    Normal,
23    /// Leftmost innermost.
24    Applicative,
25}
26
27impl Strategy {
28    pub fn as_str(self) -> &'static str {
29        match self {
30            Strategy::Normal => TERM_STRATEGY_NORMAL,
31            Strategy::Applicative => TERM_STRATEGY_APPLICATIVE,
32        }
33    }
34
35    pub fn from_name(name: &str) -> Option<Strategy> {
36        [Strategy::Normal, Strategy::Applicative].into_iter().find(|strategy| strategy.as_str() == name)
37    }
38
39    fn outermost(self) -> bool {
40        self == Strategy::Normal
41    }
42}
43
44#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
45pub enum StuckReason {
46    UnknownPrimitive,
47    Arity,
48    Kind,
49    NoRule,
50    NotFirstOrder,
51    Depth,
52}
53
54impl StuckReason {
55    pub fn as_str(self) -> &'static str {
56        match self {
57            StuckReason::UnknownPrimitive => TERM_STUCK_UNKNOWN_PRIMITIVE,
58            StuckReason::Arity => TERM_STUCK_ARITY,
59            StuckReason::Kind => TERM_STUCK_KIND,
60            StuckReason::NoRule => TERM_STUCK_NO_RULE,
61            StuckReason::NotFirstOrder => TERM_STUCK_NOT_FIRST_ORDER,
62            StuckReason::Depth => TERM_STUCK_DEPTH,
63        }
64    }
65}
66
67#[derive(Clone, Debug, PartialEq, Eq, Hash)]
68pub struct Stuck {
69    pub term: Term,
70    pub reason: StuckReason,
71}
72
73/// A reduct and the steps taken to reach it. `trace` holds the term after every step, starting with
74/// the input, when the caller asked for it, and is empty otherwise.
75#[derive(Clone, Debug, PartialEq, Eq, Hash)]
76pub struct Reduced {
77    pub term: Term,
78    pub steps: u32,
79    pub trace: Vec<Term>,
80}
81
82#[derive(Clone, Debug, PartialEq, Eq, Hash)]
83pub enum Reduction {
84    Normal(Reduced),
85    OutOfFuel(Reduced),
86    Stuck(Stuck),
87}
88
89pub struct PrimRule {
90    pub arg_kinds: Vec<LitKind>,
91    pub result_kind: LitKind,
92    pub delta: Box<dyn Fn(&[Lit]) -> Option<Lit> + Send + Sync>,
93    pub absorbing: Vec<Lit>,
94}
95
96pub type Resolver<'r> = &'r dyn Fn(&str) -> Option<&'r PrimRule>;
97
98/// The resolver that knows no primitive.
99pub fn no_primitives<'r>(_: &str) -> Option<&'r PrimRule> {
100    None
101}
102
103fn stuck(term: Term, reason: StuckReason) -> Stuck {
104    Stuck { term, reason }
105}
106
107fn too_deep(term: &Term) -> bool {
108    depth(term) as i64 > SPEC_TERM_MAX_DEPTH
109}
110
111/// One beta step at the root: `(λ.body) arg` becomes `body` with index 0 replaced by `arg`.
112fn contract(term: &Term) -> Option<Term> {
113    match term {
114        Term::App(func, arg) => match func.as_ref() {
115            Term::Abs(body, _) => Some(instantiate(body, arg)),
116            _ => None,
117        },
118        _ => None,
119    }
120}
121
122fn literal_args(args: &[Term]) -> Option<Vec<Lit>> {
123    args.iter().map(|arg| if let Term::Lit(lit) = arg { Some(lit.clone()) } else { None }).collect()
124}
125
126fn delta(name: &str, args: &[Lit], rule: Option<&PrimRule>) -> Result<Lit, Stuck> {
127    let fail = |reason| stuck(Term::prim(name, args.iter().cloned().map(Term::Lit).collect()), reason);
128    let rule = rule.ok_or_else(|| fail(StuckReason::UnknownPrimitive))?;
129    if args.len() != rule.arg_kinds.len() {
130        return Err(fail(StuckReason::Arity));
131    }
132    if args.iter().zip(&rule.arg_kinds).any(|(arg, kind)| arg.kind() != *kind) {
133        return Err(fail(StuckReason::Kind));
134    }
135    let result = (rule.delta)(args).ok_or_else(|| fail(StuckReason::NoRule))?;
136    if result.kind() == rule.result_kind { Ok(result) } else { Err(fail(StuckReason::Kind)) }
137}
138
139/// The absorbing literal that ends evaluation of a primitive, reading its literal arguments left to right.
140fn absorbed(args: &[Term], rule: Option<&PrimRule>) -> Option<Lit> {
141    for arg in args {
142        let Term::Lit(lit) = arg else { return None };
143        if rule.is_some_and(|rule| rule.absorbing.contains(lit)) {
144            return Some(lit.clone());
145        }
146    }
147    None
148}
149
150/// One reduction step, or `None` when `term` has none. `weak` stops under abstractions and in arguments.
151fn step(term: &Term, strategy: Strategy, resolver: Resolver, weak: bool) -> Result<Option<Term>, Stuck> {
152    if strategy.outermost() {
153        if let Some(reduct) = contract(term) {
154            return Ok(Some(reduct));
155        }
156    }
157    let mut rule = None;
158    match term {
159        Term::Prim(name, args) => {
160            rule = resolver(name);
161            if let Some(lit) = absorbed(args, rule) {
162                return Ok(Some(Term::Lit(lit)));
163            }
164        }
165        Term::App(..) => {}
166        _ if weak => return Ok(None),
167        _ => {}
168    }
169    let parts = term.children();
170    let reachable = if weak && matches!(term, Term::App(..)) { 1 } else { parts.len() };
171    for (position, child) in parts.into_iter().take(reachable).enumerate() {
172        if let Some(stepped) = step(child, strategy, resolver, weak)? {
173            return Ok(Some(term.replace_child(position, stepped)));
174        }
175    }
176    if let Some(reduct) = contract(term) {
177        return Ok(Some(reduct));
178    }
179    if let Term::Prim(name, args) = term {
180        if let Some(values) = literal_args(args) {
181            return delta(name, &values, rule).map(|lit| Some(Term::Lit(lit)));
182        }
183    }
184    Ok(None)
185}
186
187fn run(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool, weak: bool) -> Reduction {
188    let mut term = term.clone();
189    let mut steps = 0;
190    let mut path = if trace { vec![term.clone()] } else { Vec::new() };
191    loop {
192        if too_deep(&term) {
193            return Reduction::Stuck(stuck(term, StuckReason::Depth));
194        }
195        let stepped = match step(&term, strategy, resolver, weak) {
196            Err(stuck) => return Reduction::Stuck(stuck),
197            Ok(None) => return Reduction::Normal(Reduced { term, steps, trace: path }),
198            Ok(Some(_)) if steps >= fuel => return Reduction::OutOfFuel(Reduced { term, steps, trace: path }),
199            Ok(Some(stepped)) => stepped,
200        };
201        term = stepped;
202        steps += 1;
203        if trace {
204            path.push(term.clone());
205        }
206    }
207}
208
209/// Full normal form under `strategy`, in at most `fuel` steps. `trace` records the term after every step.
210pub fn normalize(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool) -> Reduction {
211    run(term, strategy, fuel, resolver, trace, false)
212}
213
214/// Weak head normal form: reduce the head to an abstraction or a literal, and stop there.
215pub fn whnf(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool) -> Reduction {
216    run(term, strategy, fuel, resolver, trace, true)
217}
218
219/// First-order evaluation of a binder-free term in one bottom-up pass. It takes no beta step, so it needs no fuel.
220pub fn evaluate(term: &Term, resolver: Resolver) -> Result<Reduced, Stuck> {
221    if too_deep(term) {
222        return Err(stuck(term.clone(), StuckReason::Depth));
223    }
224    evaluate_within(term, resolver).map(|(lit, steps)| Reduced { term: Term::Lit(lit), steps, trace: Vec::new() })
225}
226
227fn evaluate_within(term: &Term, resolver: Resolver) -> Result<(Lit, u32), Stuck> {
228    let (name, args) = match term {
229        Term::Lit(lit) => return Ok((lit.clone(), 0)),
230        Term::Prim(name, args) => (name, args),
231        _ => return Err(stuck(term.clone(), StuckReason::NotFirstOrder)),
232    };
233    let rule = resolver(name);
234    let mut steps = 1;
235    let mut values = Vec::with_capacity(args.len());
236    for arg in args {
237        let (value, taken) = evaluate_within(arg, resolver)?;
238        steps += taken;
239        if rule.is_some_and(|rule| rule.absorbing.contains(&value)) {
240            return Ok((value, steps));
241        }
242        values.push(value);
243    }
244    delta(name, &values, rule).map(|lit| (lit, steps))
245}
246
247/// The literal kind a binder-free term evaluates to, checked against every primitive's signature without evaluating it.
248pub fn check_kinds(term: &Term, resolver: Resolver) -> Result<LitKind, Stuck> {
249    let (name, args) = match term {
250        Term::Lit(lit) => return Ok(lit.kind()),
251        Term::Prim(name, args) => (name, args),
252        _ => return Err(stuck(term.clone(), StuckReason::NotFirstOrder)),
253    };
254    let rule = resolver(name).ok_or_else(|| stuck(term.clone(), StuckReason::UnknownPrimitive))?;
255    if args.len() != rule.arg_kinds.len() {
256        return Err(stuck(term.clone(), StuckReason::Arity));
257    }
258    for (arg, kind) in args.iter().zip(&rule.arg_kinds) {
259        if check_kinds(arg, resolver)? != *kind {
260            return Err(stuck(term.clone(), StuckReason::Kind));
261        }
262    }
263    Ok(rule.result_kind)
264}
265
266/// Contract every outermost eta redex: `λ.(M 0)` becomes `M` lowered by one when index 0 is not free in `M`.
267pub fn eta_reduce(term: &Term) -> Term {
268    if let Term::Abs(body, _) = term {
269        if let Term::App(func, arg) = body.as_ref() {
270            if **arg == Term::BoundVar(0) && !occurs(func, 0) {
271                return shift(func, -1, 0);
272            }
273        }
274    }
275    term.map_children(eta_reduce)
276}
277
278pub fn eta_expand(term: &Term, hint: &str) -> Term {
279    Term::abs(Term::app(shift(term, 1, 0), Term::BoundVar(0)), hint)
280}