lambda_cat/

eval.rs

//! Tree-walking interpreter for the lambda calculus.
//!
//! Evaluation is purely functional: every reduction step is a non-mutating
//! transformation of an immutable environment.  Recursion is bounded by a
//! [`Fuel`] budget so that proptest-generated inputs cannot stall the test
//! suite.  Fixed points are unfolded by substitution; the captured
//! environment carries no self-reference, which keeps every value
//! representable without `Rc`, `Arc`, or interior mutability.

use crate::env::Env;
use crate::error::Error;
use crate::syntax::{Expr, VarName};
use crate::value::Value;

/// A step budget for evaluation.
///
/// Spend one unit at every reduction step so that diverging programs
/// surface as [`Error::FuelExhausted`] rather than stack overflow or
/// non-termination.
///
/// [`Error::FuelExhausted`]: crate::error::Error::FuelExhausted
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Fuel {
    limit: u64,
    remaining: u64,
}

impl Fuel {
    /// A fresh budget of `limit` steps.
    #[must_use]
    pub fn new(limit: u64) -> Self {
        Self {
            limit,
            remaining: limit,
        }
    }

    /// The original budget this `Fuel` was created with.
    #[must_use]
    pub fn limit(&self) -> u64 {
        self.limit
    }

    /// The number of steps still available.
    #[must_use]
    pub fn remaining(&self) -> u64 {
        self.remaining
    }

    fn spend(self) -> Result<Self, Error> {
        match self.remaining {
            0 => Err(Error::FuelExhausted { limit: self.limit }),
            n => Ok(Self {
                limit: self.limit,
                remaining: n - 1,
            }),
        }
    }
}

/// Evaluate `expr` against `env` with the given step budget.
///
/// Returns the resulting [`Value`] paired with the remaining fuel.  The
/// returned fuel can be threaded into further evaluations.
///
/// # Errors
///
/// Returns [`Error::UnboundVariable`] if evaluation references a free
/// variable not bound in `env`, or [`Error::FuelExhausted`] if reduction
/// exceeds the budget.
///
/// [`Error::UnboundVariable`]: crate::error::Error::UnboundVariable
/// [`Error::FuelExhausted`]: crate::error::Error::FuelExhausted
///
/// # Examples
///
/// ```
/// # fn main() -> Result<(), lambda_cat::error::Error> {
/// use lambda_cat::env::Env;
/// use lambda_cat::eval::{eval, Fuel};
/// use lambda_cat::syntax::Expr;
///
/// let id = Expr::lam("x", Expr::var("x"));
/// let (value, _fuel) = eval(&id, &Env::empty(), Fuel::new(100))?;
/// assert_eq!(format!("{value}"), "\\x. x");
/// # Ok(())
/// # }
/// ```
pub fn eval(expr: &Expr, env: &Env, fuel: Fuel) -> Result<(Value, Fuel), Error> {
    let fuel = fuel.spend()?;
    step(expr, env, fuel)
}

fn step(expr: &Expr, env: &Env, fuel: Fuel) -> Result<(Value, Fuel), Error> {
    match expr {
        Expr::Var(name) => eval_var(name, env, fuel),
        Expr::Lam { param, body } => Ok((
            Value::closure(param.clone(), (**body).clone(), env.clone()),
            fuel,
        )),
        Expr::App { func, arg } => eval_app(func, arg, env, fuel),
        Expr::Let { name, value, body } => eval_let(name, value, body, env, fuel),
        Expr::Fix { name, body } => eval_fix(expr, name, body, env, fuel),
    }
}

fn eval_var(name: &VarName, env: &Env, fuel: Fuel) -> Result<(Value, Fuel), Error> {
    env.lookup(name)
        .cloned()
        .map(|v| (v, fuel))
        .ok_or_else(|| Error::UnboundVariable { name: name.clone() })
}

fn eval_app(func: &Expr, arg: &Expr, env: &Env, fuel: Fuel) -> Result<(Value, Fuel), Error> {
    let (func_v, fuel) = eval(func, env, fuel)?;
    let (arg_v, fuel) = eval(arg, env, fuel)?;
    apply(func_v, arg_v, fuel)
}

fn eval_let(
    name: &VarName,
    value: &Expr,
    body: &Expr,
    env: &Env,
    fuel: Fuel,
) -> Result<(Value, Fuel), Error> {
    let (value_v, fuel) = eval(value, env, fuel)?;
    let new_env = env.extend(name.clone(), value_v);
    eval(body, &new_env, fuel)
}

fn eval_fix(
    whole: &Expr,
    name: &VarName,
    body: &Expr,
    env: &Env,
    fuel: Fuel,
) -> Result<(Value, Fuel), Error> {
    let unfolded = subst(body, name, whole);
    eval(&unfolded, env, fuel)
}

fn apply(func: Value, arg: Value, fuel: Fuel) -> Result<(Value, Fuel), Error> {
    match func {
        Value::Closure { param, body, env } => {
            let new_env = env.extend(param, arg);
            eval(&body, &new_env, fuel)
        }
    }
}

fn subst(expr: &Expr, target: &VarName, replacement: &Expr) -> Expr {
    match expr {
        Expr::Var(name) => {
            if name == target {
                replacement.clone()
            } else {
                Expr::Var(name.clone())
            }
        }
        Expr::Lam { param, body } => Expr::Lam {
            param: param.clone(),
            body: Box::new(subst_under_binder(body, param, target, replacement)),
        },
        Expr::App { func, arg } => Expr::App {
            func: Box::new(subst(func, target, replacement)),
            arg: Box::new(subst(arg, target, replacement)),
        },
        Expr::Let { name, value, body } => Expr::Let {
            name: name.clone(),
            value: Box::new(subst(value, target, replacement)),
            body: Box::new(subst_under_binder(body, name, target, replacement)),
        },
        Expr::Fix { name, body } => Expr::Fix {
            name: name.clone(),
            body: Box::new(subst_under_binder(body, name, target, replacement)),
        },
    }
}

fn subst_under_binder(body: &Expr, binder: &VarName, target: &VarName, replacement: &Expr) -> Expr {
    if binder == target {
        body.clone()
    } else {
        subst(body, target, replacement)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn empty() -> Fuel {
        Fuel::new(10_000)
    }

    #[test]
    fn identity_is_closure() -> Result<(), Error> {
        let id = Expr::lam("x", Expr::var("x"));
        let (value, _fuel) = eval(&id, &Env::empty(), empty())?;
        matches!(value, Value::Closure { .. })
            .then_some(())
            .ok_or(Error::UnboundVariable {
                name: VarName::from("not a closure"),
            })
    }

    #[test]
    fn unbound_variable_errors() -> Result<(), Error> {
        let expr = Expr::var("missing");
        let result = eval(&expr, &Env::empty(), empty());
        match result {
            Err(Error::UnboundVariable { .. }) => Ok(()),
            Err(other) => Err(other),
            Ok(_) => Err(Error::UnboundVariable {
                name: VarName::from("expected unbound error"),
            }),
        }
    }
}