lambda_ref_cat/
eval.rs

1//! Tree-walking interpreter with heap-threading.
2//!
3//! Every reduction step takes a [`Heap`] and a [`Fuel`] budget by value and
4//! returns a (possibly new) [`Heap`] and [`Fuel`] alongside the resulting
5//! [`Value`].  Mutation of a reference cell is expressed by returning a heap
6//! that differs from the receiver only at the affected address.  No `mut`,
7//! no `Rc`/`Arc`, no `RefCell`/`Cell`/`Mutex`, no `unsafe`.
8//!
9//! Fixed points are unfolded by substitution, identical to spike 1 except
10//! that `subst` now traverses the four new stateful forms (`Ref`, `Deref`,
11//! `Assign`, `Seq`).
12
13use crate::env::Env;
14use crate::error::Error;
15use crate::heap::{Address, Heap};
16use crate::syntax::{Expr, VarName};
17use crate::value::Value;
18
19/// A step budget for evaluation.
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub struct Fuel {
22    limit: u64,
23    remaining: u64,
24}
25
26impl Fuel {
27    /// A fresh budget of `limit` steps.
28    #[must_use]
29    pub fn new(limit: u64) -> Self {
30        Self {
31            limit,
32            remaining: limit,
33        }
34    }
35
36    /// The original budget this `Fuel` was created with.
37    #[must_use]
38    pub fn limit(&self) -> u64 {
39        self.limit
40    }
41
42    /// The number of steps still available.
43    #[must_use]
44    pub fn remaining(&self) -> u64 {
45        self.remaining
46    }
47
48    fn spend(self) -> Result<Self, Error> {
49        match self.remaining {
50            0 => Err(Error::FuelExhausted { limit: self.limit }),
51            n => Ok(Self {
52                limit: self.limit,
53                remaining: n - 1,
54            }),
55        }
56    }
57}
58
59/// Evaluate `expr` against `env` with the given heap and step budget.
60///
61/// Returns the resulting [`Value`], the updated [`Heap`], and the remaining
62/// [`Fuel`].  Threading by ownership is intentional: every operation that
63/// mutates the heap (`alloc`, `store`) produces a new heap that this
64/// function returns to its caller.
65///
66/// # Errors
67///
68/// Returns [`Error::UnboundVariable`] on free variables,
69/// [`Error::FuelExhausted`] when the budget is exceeded,
70/// [`Error::DanglingReference`] on heap accesses to addresses with no live
71/// cell, [`Error::NotAReference`] on dereference or assignment of a non-ref
72/// value, and [`Error::NotAFunction`] on application of a non-function value.
73///
74/// # Examples
75///
76/// ```
77/// # fn main() -> Result<(), lambda_ref_cat::error::Error> {
78/// use lambda_ref_cat::env::Env;
79/// use lambda_ref_cat::eval::{eval, Fuel};
80/// use lambda_ref_cat::heap::Heap;
81/// use lambda_ref_cat::syntax::Expr;
82///
83/// let id = Expr::lam("x", Expr::var("x"));
84/// let (value, _heap, _fuel) = eval(&id, &Env::empty(), Heap::empty(), Fuel::new(100))?;
85/// assert_eq!(format!("{value}"), "\\x. x");
86/// # Ok(())
87/// # }
88/// ```
89///
90/// [`Error::UnboundVariable`]: crate::error::Error::UnboundVariable
91/// [`Error::FuelExhausted`]: crate::error::Error::FuelExhausted
92/// [`Error::DanglingReference`]: crate::error::Error::DanglingReference
93/// [`Error::NotAReference`]: crate::error::Error::NotAReference
94/// [`Error::NotAFunction`]: crate::error::Error::NotAFunction
95pub fn eval(expr: &Expr, env: &Env, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
96    let fuel = fuel.spend()?;
97    step(expr, env, heap, fuel)
98}
99
100fn step(expr: &Expr, env: &Env, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
101    match expr {
102        Expr::Var(name) => eval_var(name, env, heap, fuel),
103        Expr::Lam { param, body } => Ok((
104            Value::closure(param.clone(), (**body).clone(), env.clone()),
105            heap,
106            fuel,
107        )),
108        Expr::App { func, arg } => eval_app(func, arg, env, heap, fuel),
109        Expr::Let { name, value, body } => eval_let(name, value, body, env, heap, fuel),
110        Expr::Fix { name, body } => eval_fix(expr, name, body, env, heap, fuel),
111        Expr::Ref { inner } => eval_ref(inner, env, heap, fuel),
112        Expr::Deref { inner } => eval_deref(inner, env, heap, fuel),
113        Expr::Assign { target, value } => eval_assign(target, value, env, heap, fuel),
114        Expr::Seq { first, second } => eval_seq(first, second, env, heap, fuel),
115    }
116}
117
118fn eval_var(
119    name: &VarName,
120    env: &Env,
121    heap: Heap,
122    fuel: Fuel,
123) -> Result<(Value, Heap, Fuel), Error> {
124    env.lookup(name)
125        .cloned()
126        .map(|v| (v, heap, fuel))
127        .ok_or_else(|| Error::UnboundVariable { name: name.clone() })
128}
129
130fn eval_app(
131    func: &Expr,
132    arg: &Expr,
133    env: &Env,
134    heap: Heap,
135    fuel: Fuel,
136) -> Result<(Value, Heap, Fuel), Error> {
137    let (func_v, heap, fuel) = eval(func, env, heap, fuel)?;
138    let (arg_v, heap, fuel) = eval(arg, env, heap, fuel)?;
139    apply(func_v, arg_v, heap, fuel)
140}
141
142fn eval_let(
143    name: &VarName,
144    value: &Expr,
145    body: &Expr,
146    env: &Env,
147    heap: Heap,
148    fuel: Fuel,
149) -> Result<(Value, Heap, Fuel), Error> {
150    let (value_v, heap, fuel) = eval(value, env, heap, fuel)?;
151    let new_env = env.extend(name.clone(), value_v);
152    eval(body, &new_env, heap, fuel)
153}
154
155fn eval_fix(
156    whole: &Expr,
157    name: &VarName,
158    body: &Expr,
159    env: &Env,
160    heap: Heap,
161    fuel: Fuel,
162) -> Result<(Value, Heap, Fuel), Error> {
163    let unfolded = subst(body, name, whole);
164    eval(&unfolded, env, heap, fuel)
165}
166
167fn eval_ref(inner: &Expr, env: &Env, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
168    let (inner_v, heap, fuel) = eval(inner, env, heap, fuel)?;
169    let (new_heap, addr) = heap.alloc(inner_v);
170    Ok((Value::reference(addr), new_heap, fuel))
171}
172
173fn eval_deref(
174    inner: &Expr,
175    env: &Env,
176    heap: Heap,
177    fuel: Fuel,
178) -> Result<(Value, Heap, Fuel), Error> {
179    let (ref_v, heap, fuel) = eval(inner, env, heap, fuel)?;
180    let addr = expect_ref(&ref_v)?;
181    let cell_value = heap
182        .load(addr)
183        .cloned()
184        .ok_or(Error::DanglingReference { address: addr })?;
185    Ok((cell_value, heap, fuel))
186}
187
188fn eval_assign(
189    target: &Expr,
190    value: &Expr,
191    env: &Env,
192    heap: Heap,
193    fuel: Fuel,
194) -> Result<(Value, Heap, Fuel), Error> {
195    let (target_v, heap, fuel) = eval(target, env, heap, fuel)?;
196    let addr = expect_ref(&target_v)?;
197    let (value_v, heap, fuel) = eval(value, env, heap, fuel)?;
198    let new_heap = heap
199        .store(addr, value_v.clone())
200        .ok_or(Error::DanglingReference { address: addr })?;
201    Ok((value_v, new_heap, fuel))
202}
203
204fn eval_seq(
205    first: &Expr,
206    second: &Expr,
207    env: &Env,
208    heap: Heap,
209    fuel: Fuel,
210) -> Result<(Value, Heap, Fuel), Error> {
211    let (_discarded, heap, fuel) = eval(first, env, heap, fuel)?;
212    eval(second, env, heap, fuel)
213}
214
215fn apply(func: Value, arg: Value, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
216    match func {
217        Value::Closure { param, body, env } => {
218            let new_env = env.extend(param, arg);
219            eval(&body, &new_env, heap, fuel)
220        }
221        Value::Ref(address) => Err(Error::NotAFunction {
222            found: format!("ref({address})"),
223        }),
224    }
225}
226
227fn expect_ref(value: &Value) -> Result<Address, Error> {
228    match value {
229        Value::Ref(address) => Ok(*address),
230        Value::Closure { .. } => Err(Error::NotAReference {
231            found: format!("{value}"),
232        }),
233    }
234}
235
236fn subst(expr: &Expr, target: &VarName, replacement: &Expr) -> Expr {
237    match expr {
238        Expr::Var(name) => {
239            if name == target {
240                replacement.clone()
241            } else {
242                Expr::Var(name.clone())
243            }
244        }
245        Expr::Lam { param, body } => Expr::Lam {
246            param: param.clone(),
247            body: Box::new(subst_under_binder(body, param, target, replacement)),
248        },
249        Expr::App { func, arg } => Expr::App {
250            func: Box::new(subst(func, target, replacement)),
251            arg: Box::new(subst(arg, target, replacement)),
252        },
253        Expr::Let { name, value, body } => Expr::Let {
254            name: name.clone(),
255            value: Box::new(subst(value, target, replacement)),
256            body: Box::new(subst_under_binder(body, name, target, replacement)),
257        },
258        Expr::Fix { name, body } => Expr::Fix {
259            name: name.clone(),
260            body: Box::new(subst_under_binder(body, name, target, replacement)),
261        },
262        Expr::Ref { inner } => Expr::Ref {
263            inner: Box::new(subst(inner, target, replacement)),
264        },
265        Expr::Deref { inner } => Expr::Deref {
266            inner: Box::new(subst(inner, target, replacement)),
267        },
268        Expr::Assign {
269            target: t,
270            value: v,
271        } => Expr::Assign {
272            target: Box::new(subst(t, target, replacement)),
273            value: Box::new(subst(v, target, replacement)),
274        },
275        Expr::Seq { first, second } => Expr::Seq {
276            first: Box::new(subst(first, target, replacement)),
277            second: Box::new(subst(second, target, replacement)),
278        },
279    }
280}
281
282fn subst_under_binder(body: &Expr, binder: &VarName, target: &VarName, replacement: &Expr) -> Expr {
283    if binder == target {
284        body.clone()
285    } else {
286        subst(body, target, replacement)
287    }
288}
289
290#[cfg(test)]
291mod tests {
292    use super::*;
293
294    fn empty_fuel() -> Fuel {
295        Fuel::new(10_000)
296    }
297
298    #[test]
299    fn identity_is_closure_with_empty_heap() -> Result<(), Error> {
300        let id = Expr::lam("x", Expr::var("x"));
301        let (value, heap, _fuel) = eval(&id, &Env::empty(), Heap::empty(), empty_fuel())?;
302        let shape_ok = matches!(value, Value::Closure { .. });
303        let heap_ok = heap.is_empty();
304        (shape_ok && heap_ok)
305            .then_some(())
306            .ok_or(Error::UnboundVariable {
307                name: VarName::from("expected closure with empty heap"),
308            })
309    }
310
311    #[test]
312    fn alloc_grows_heap_by_one() -> Result<(), Error> {
313        let expr = Expr::alloc(Expr::lam("x", Expr::var("x")));
314        let (value, heap, _fuel) = eval(&expr, &Env::empty(), Heap::empty(), empty_fuel())?;
315        let is_ref = matches!(value, Value::Ref(_));
316        let one_cell = heap.len() == 1;
317        (is_ref && one_cell)
318            .then_some(())
319            .ok_or(Error::UnboundVariable {
320                name: VarName::from("expected one heap cell"),
321            })
322    }
323}
lambda_ref_cat/eval.rs

lambda_ref_cat/
eval.rs
