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 {
Normal,
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,
}
#[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>;
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
}
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)) }
}
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
}
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());
}
}
}
pub fn normalize(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool) -> Reduction {
run(term, strategy, fuel, resolver, trace, false)
}
pub fn whnf(term: &Term, strategy: Strategy, fuel: u32, resolver: Resolver, trace: bool) -> Reduction {
run(term, strategy, fuel, resolver, trace, true)
}
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))
}
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)
}
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)
}