1use 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 Normal,
23 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#[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
98pub 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
111fn 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
139fn 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
150fn 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
209pub fn normalize(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool) -> Reduction {
211 run(term, strategy, fuel, resolver, trace, false)
212}
213
214pub fn whnf(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool) -> Reduction {
216 run(term, strategy, fuel, resolver, trace, true)
217}
218
219pub 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
247pub 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
266pub 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}