lambda-ref-cat 0.1.0

//! Tree-walking interpreter with heap-threading.
//!
//! Every reduction step takes a [`Heap`] and a [`Fuel`] budget by value and
//! returns a (possibly new) [`Heap`] and [`Fuel`] alongside the resulting
//! [`Value`].  Mutation of a reference cell is expressed by returning a heap
//! that differs from the receiver only at the affected address.  No `mut`,
//! no `Rc`/`Arc`, no `RefCell`/`Cell`/`Mutex`, no `unsafe`.
//!
//! Fixed points are unfolded by substitution, identical to spike 1 except
//! that `subst` now traverses the four new stateful forms (`Ref`, `Deref`,
//! `Assign`, `Seq`).

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

/// A step budget for evaluation.
#[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 heap and step budget.
///
/// Returns the resulting [`Value`], the updated [`Heap`], and the remaining
/// [`Fuel`].  Threading by ownership is intentional: every operation that
/// mutates the heap (`alloc`, `store`) produces a new heap that this
/// function returns to its caller.
///
/// # Errors
///
/// Returns [`Error::UnboundVariable`] on free variables,
/// [`Error::FuelExhausted`] when the budget is exceeded,
/// [`Error::DanglingReference`] on heap accesses to addresses with no live
/// cell, [`Error::NotAReference`] on dereference or assignment of a non-ref
/// value, and [`Error::NotAFunction`] on application of a non-function value.
///
/// # Examples
///
/// ```
/// # fn main() -> Result<(), lambda_ref_cat::error::Error> {
/// use lambda_ref_cat::env::Env;
/// use lambda_ref_cat::eval::{eval, Fuel};
/// use lambda_ref_cat::heap::Heap;
/// use lambda_ref_cat::syntax::Expr;
///
/// let id = Expr::lam("x", Expr::var("x"));
/// let (value, _heap, _fuel) = eval(&id, &Env::empty(), Heap::empty(), Fuel::new(100))?;
/// assert_eq!(format!("{value}"), "\\x. x");
/// # Ok(())
/// # }
/// ```
///
/// [`Error::UnboundVariable`]: crate::error::Error::UnboundVariable
/// [`Error::FuelExhausted`]: crate::error::Error::FuelExhausted
/// [`Error::DanglingReference`]: crate::error::Error::DanglingReference
/// [`Error::NotAReference`]: crate::error::Error::NotAReference
/// [`Error::NotAFunction`]: crate::error::Error::NotAFunction
pub fn eval(expr: &Expr, env: &Env, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
    let fuel = fuel.spend()?;
    step(expr, env, heap, fuel)
}

fn step(expr: &Expr, env: &Env, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
    match expr {
        Expr::Var(name) => eval_var(name, env, heap, fuel),
        Expr::Lam { param, body } => Ok((
            Value::closure(param.clone(), (**body).clone(), env.clone()),
            heap,
            fuel,
        )),
        Expr::App { func, arg } => eval_app(func, arg, env, heap, fuel),
        Expr::Let { name, value, body } => eval_let(name, value, body, env, heap, fuel),
        Expr::Fix { name, body } => eval_fix(expr, name, body, env, heap, fuel),
        Expr::Ref { inner } => eval_ref(inner, env, heap, fuel),
        Expr::Deref { inner } => eval_deref(inner, env, heap, fuel),
        Expr::Assign { target, value } => eval_assign(target, value, env, heap, fuel),
        Expr::Seq { first, second } => eval_seq(first, second, env, heap, fuel),
    }
}

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

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

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

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

fn eval_ref(inner: &Expr, env: &Env, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
    let (inner_v, heap, fuel) = eval(inner, env, heap, fuel)?;
    let (new_heap, addr) = heap.alloc(inner_v);
    Ok((Value::reference(addr), new_heap, fuel))
}

fn eval_deref(
    inner: &Expr,
    env: &Env,
    heap: Heap,
    fuel: Fuel,
) -> Result<(Value, Heap, Fuel), Error> {
    let (ref_v, heap, fuel) = eval(inner, env, heap, fuel)?;
    let addr = expect_ref(&ref_v)?;
    let cell_value = heap
        .load(addr)
        .cloned()
        .ok_or(Error::DanglingReference { address: addr })?;
    Ok((cell_value, heap, fuel))
}

fn eval_assign(
    target: &Expr,
    value: &Expr,
    env: &Env,
    heap: Heap,
    fuel: Fuel,
) -> Result<(Value, Heap, Fuel), Error> {
    let (target_v, heap, fuel) = eval(target, env, heap, fuel)?;
    let addr = expect_ref(&target_v)?;
    let (value_v, heap, fuel) = eval(value, env, heap, fuel)?;
    let new_heap = heap
        .store(addr, value_v.clone())
        .ok_or(Error::DanglingReference { address: addr })?;
    Ok((value_v, new_heap, fuel))
}

fn eval_seq(
    first: &Expr,
    second: &Expr,
    env: &Env,
    heap: Heap,
    fuel: Fuel,
) -> Result<(Value, Heap, Fuel), Error> {
    let (_discarded, heap, fuel) = eval(first, env, heap, fuel)?;
    eval(second, env, heap, fuel)
}

fn apply(func: Value, arg: Value, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
    match func {
        Value::Closure { param, body, env } => {
            let new_env = env.extend(param, arg);
            eval(&body, &new_env, heap, fuel)
        }
        Value::Ref(address) => Err(Error::NotAFunction {
            found: format!("ref({address})"),
        }),
    }
}

fn expect_ref(value: &Value) -> Result<Address, Error> {
    match value {
        Value::Ref(address) => Ok(*address),
        Value::Closure { .. } => Err(Error::NotAReference {
            found: format!("{value}"),
        }),
    }
}

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)),
        },
        Expr::Ref { inner } => Expr::Ref {
            inner: Box::new(subst(inner, target, replacement)),
        },
        Expr::Deref { inner } => Expr::Deref {
            inner: Box::new(subst(inner, target, replacement)),
        },
        Expr::Assign {
            target: t,
            value: v,
        } => Expr::Assign {
            target: Box::new(subst(t, target, replacement)),
            value: Box::new(subst(v, target, replacement)),
        },
        Expr::Seq { first, second } => Expr::Seq {
            first: Box::new(subst(first, target, replacement)),
            second: Box::new(subst(second, 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 {
        Fuel::new(10_000)
    }

    #[test]
    fn identity_is_closure_with_empty_heap() -> Result<(), Error> {
        let id = Expr::lam("x", Expr::var("x"));
        let (value, heap, _fuel) = eval(&id, &Env::empty(), Heap::empty(), empty_fuel())?;
        let shape_ok = matches!(value, Value::Closure { .. });
        let heap_ok = heap.is_empty();
        (shape_ok && heap_ok)
            .then_some(())
            .ok_or(Error::UnboundVariable {
                name: VarName::from("expected closure with empty heap"),
            })
    }

    #[test]
    fn alloc_grows_heap_by_one() -> Result<(), Error> {
        let expr = Expr::alloc(Expr::lam("x", Expr::var("x")));
        let (value, heap, _fuel) = eval(&expr, &Env::empty(), Heap::empty(), empty_fuel())?;
        let is_ref = matches!(value, Value::Ref(_));
        let one_cell = heap.len() == 1;
        (is_ref && one_cell)
            .then_some(())
            .ok_or(Error::UnboundVariable {
                name: VarName::from("expected one heap cell"),
            })
    }
}