lambda_throw_cat/
eval.rs

1//! Tree-walking interpreter with heap-threading, prototype-walking field
2//! access, and `throw`/`try`-`catch` non-local control flow.
3//!
4//! Spike 4 adds two new evaluation cases:
5//!
6//! - [`Expr::Throw`]: evaluate the inner expression, then emit
7//!   [`Error::Thrown`] carrying the resulting value plus the current heap
8//!   and fuel.  Existing `?`-propagation through every other case unwinds
9//!   the stack until either an enclosing [`Expr::TryCatch`] catches the
10//!   signal or it reaches the top boundary as an uncaught exception.
11//! - [`Expr::TryCatch`]: evaluate the body; on [`Error::Thrown`], bind the
12//!   thrown value to the catch parameter and evaluate the handler with the
13//!   heap and fuel that were live at the moment of the throw.  Other
14//!   [`Error`] variants propagate unchanged.
15//!
16//! Substitution traverses the new variants without introducing new binders.
17//!
18//! [`Error::Thrown`]: crate::error::Error::Thrown
19
20use std::collections::BTreeMap;
21
22use crate::env::Env;
23use crate::error::{Error, ThrownPayload};
24use crate::heap::{Address, Heap};
25use crate::syntax::{Expr, VarName};
26use crate::value::Value;
27
28/// A step budget for evaluation.
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub struct Fuel {
31    limit: u64,
32    remaining: u64,
33}
34
35impl Fuel {
36    /// A fresh budget of `limit` steps.
37    #[must_use]
38    pub fn new(limit: u64) -> Self {
39        Self {
40            limit,
41            remaining: limit,
42        }
43    }
44
45    /// The original budget.
46    #[must_use]
47    pub fn limit(&self) -> u64 {
48        self.limit
49    }
50
51    /// Steps still available.
52    #[must_use]
53    pub fn remaining(&self) -> u64 {
54        self.remaining
55    }
56
57    fn spend(self) -> Result<Self, Error> {
58        match self.remaining {
59            0 => Err(Error::FuelExhausted { limit: self.limit }),
60            n => Ok(Self {
61                limit: self.limit,
62                remaining: n - 1,
63            }),
64        }
65    }
66}
67
68/// Evaluate `expr` against `env` with the given heap and step budget.
69///
70/// # Errors
71///
72/// See [`Error`] for the full list of failure modes.
73///
74/// # Examples
75///
76/// ```
77/// # fn main() -> Result<(), lambda_throw_cat::error::Error> {
78/// use lambda_throw_cat::env::Env;
79/// use lambda_throw_cat::eval::{eval, Fuel};
80/// use lambda_throw_cat::heap::Heap;
81/// use lambda_throw_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/// ```
89pub fn eval(expr: &Expr, env: &Env, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
90    let fuel = fuel.spend()?;
91    step(expr, env, heap, fuel)
92}
93
94fn step(expr: &Expr, env: &Env, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
95    match expr {
96        Expr::Var(name) => eval_var(name, env, heap, fuel),
97        Expr::Lam { param, body } => Ok((
98            Value::closure(param.clone(), (**body).clone(), env.clone()),
99            heap,
100            fuel,
101        )),
102        Expr::App { func, arg } => eval_app(func, arg, env, heap, fuel),
103        Expr::Let { name, value, body } => eval_let(name, value, body, env, heap, fuel),
104        Expr::Fix { name, body } => eval_fix(expr, name, body, env, heap, fuel),
105        Expr::Ref { inner } => eval_ref(inner, env, heap, fuel),
106        Expr::Deref { inner } => eval_deref(inner, env, heap, fuel),
107        Expr::Assign { target, value } => eval_assign(target, value, env, heap, fuel),
108        Expr::Seq { first, second } => eval_seq(first, second, env, heap, fuel),
109        Expr::Object { entries, prototype } => {
110            eval_object(entries, prototype.as_deref(), env, heap, fuel)
111        }
112        Expr::Field { object, name } => eval_field(object, name, env, heap, fuel),
113        Expr::Throw { inner } => eval_throw(inner, env, heap, fuel),
114        Expr::TryCatch {
115            body,
116            catch_param,
117            handler,
118        } => eval_try_catch(body, catch_param, handler, env, heap, fuel),
119    }
120}
121
122fn eval_var(
123    name: &VarName,
124    env: &Env,
125    heap: Heap,
126    fuel: Fuel,
127) -> Result<(Value, Heap, Fuel), Error> {
128    env.lookup(name)
129        .cloned()
130        .map(|v| (v, heap, fuel))
131        .ok_or_else(|| Error::UnboundVariable { name: name.clone() })
132}
133
134fn eval_app(
135    func: &Expr,
136    arg: &Expr,
137    env: &Env,
138    heap: Heap,
139    fuel: Fuel,
140) -> Result<(Value, Heap, Fuel), Error> {
141    let (func_v, heap, fuel) = eval(func, env, heap, fuel)?;
142    let (arg_v, heap, fuel) = eval(arg, env, heap, fuel)?;
143    apply(func_v, arg_v, heap, fuel)
144}
145
146fn eval_let(
147    name: &VarName,
148    value: &Expr,
149    body: &Expr,
150    env: &Env,
151    heap: Heap,
152    fuel: Fuel,
153) -> Result<(Value, Heap, Fuel), Error> {
154    let (value_v, heap, fuel) = eval(value, env, heap, fuel)?;
155    let new_env = env.extend(name.clone(), value_v);
156    eval(body, &new_env, heap, fuel)
157}
158
159fn eval_fix(
160    whole: &Expr,
161    name: &VarName,
162    body: &Expr,
163    env: &Env,
164    heap: Heap,
165    fuel: Fuel,
166) -> Result<(Value, Heap, Fuel), Error> {
167    let unfolded = subst(body, name, whole);
168    eval(&unfolded, env, heap, fuel)
169}
170
171fn eval_ref(inner: &Expr, env: &Env, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
172    let (inner_v, heap, fuel) = eval(inner, env, heap, fuel)?;
173    let (new_heap, addr) = heap.alloc(inner_v);
174    Ok((Value::reference(addr), new_heap, fuel))
175}
176
177fn eval_deref(
178    inner: &Expr,
179    env: &Env,
180    heap: Heap,
181    fuel: Fuel,
182) -> Result<(Value, Heap, Fuel), Error> {
183    let (ref_v, heap, fuel) = eval(inner, env, heap, fuel)?;
184    let addr = expect_ref(&ref_v)?;
185    let cell_value = heap
186        .load(addr)
187        .cloned()
188        .ok_or(Error::DanglingReference { address: addr })?;
189    Ok((cell_value, heap, fuel))
190}
191
192fn eval_assign(
193    target: &Expr,
194    value: &Expr,
195    env: &Env,
196    heap: Heap,
197    fuel: Fuel,
198) -> Result<(Value, Heap, Fuel), Error> {
199    match target {
200        Expr::Field { object, name } => eval_field_assign(object, name, value, env, heap, fuel),
201        Expr::Var(_)
202        | Expr::Lam { .. }
203        | Expr::App { .. }
204        | Expr::Let { .. }
205        | Expr::Fix { .. }
206        | Expr::Ref { .. }
207        | Expr::Deref { .. }
208        | Expr::Assign { .. }
209        | Expr::Seq { .. }
210        | Expr::Object { .. }
211        | Expr::Throw { .. }
212        | Expr::TryCatch { .. } => eval_cell_assign(target, value, env, heap, fuel),
213    }
214}
215
216fn eval_cell_assign(
217    target: &Expr,
218    value: &Expr,
219    env: &Env,
220    heap: Heap,
221    fuel: Fuel,
222) -> Result<(Value, Heap, Fuel), Error> {
223    let (target_v, heap, fuel) = eval(target, env, heap, fuel)?;
224    let addr = expect_ref(&target_v)?;
225    let (value_v, heap, fuel) = eval(value, env, heap, fuel)?;
226    let new_heap = heap
227        .store(addr, value_v.clone())
228        .ok_or(Error::DanglingReference { address: addr })?;
229    Ok((value_v, new_heap, fuel))
230}
231
232fn eval_field_assign(
233    object: &Expr,
234    name: &VarName,
235    value: &Expr,
236    env: &Env,
237    heap: Heap,
238    fuel: Fuel,
239) -> Result<(Value, Heap, Fuel), Error> {
240    let (obj_v, heap, fuel) = eval(object, env, heap, fuel)?;
241    let obj_addr = expect_ref(&obj_v)?;
242    let (value_v, heap, fuel) = eval(value, env, heap, fuel)?;
243    let cell = heap
244        .load(obj_addr)
245        .cloned()
246        .ok_or(Error::DanglingReference { address: obj_addr })?;
247    let new_obj = update_object_property(&cell, name, &value_v)?;
248    let new_heap = heap
249        .store(obj_addr, new_obj)
250        .ok_or(Error::DanglingReference { address: obj_addr })?;
251    Ok((value_v, new_heap, fuel))
252}
253
254fn eval_seq(
255    first: &Expr,
256    second: &Expr,
257    env: &Env,
258    heap: Heap,
259    fuel: Fuel,
260) -> Result<(Value, Heap, Fuel), Error> {
261    let (_discarded, heap, fuel) = eval(first, env, heap, fuel)?;
262    eval(second, env, heap, fuel)
263}
264
265fn eval_object(
266    entries: &[(VarName, Expr)],
267    prototype_expr: Option<&Expr>,
268    env: &Env,
269    heap: Heap,
270    fuel: Fuel,
271) -> Result<(Value, Heap, Fuel), Error> {
272    let (prototype, heap, fuel) = eval_prototype(prototype_expr, env, heap, fuel)?;
273    let (properties, heap, fuel) = eval_entries(entries, env, BTreeMap::new(), heap, fuel)?;
274    let object = Value::object(properties, prototype);
275    let (new_heap, addr) = heap.alloc(object);
276    Ok((Value::reference(addr), new_heap, fuel))
277}
278
279fn eval_prototype(
280    prototype_expr: Option<&Expr>,
281    env: &Env,
282    heap: Heap,
283    fuel: Fuel,
284) -> Result<(Option<Address>, Heap, Fuel), Error> {
285    prototype_expr
286        .iter()
287        .copied()
288        .try_fold((None, heap, fuel), |(_, heap, fuel), expr| {
289            let (value, heap, fuel) = eval(expr, env, heap, fuel)?;
290            let addr = extract_object_reference(&value, &heap)?;
291            Ok((Some(addr), heap, fuel))
292        })
293}
294
295fn eval_entries(
296    entries: &[(VarName, Expr)],
297    env: &Env,
298    initial: BTreeMap<VarName, Value>,
299    heap: Heap,
300    fuel: Fuel,
301) -> Result<(BTreeMap<VarName, Value>, Heap, Fuel), Error> {
302    entries.iter().try_fold(
303        (initial, heap, fuel),
304        |(props, heap, fuel), (name, value_expr)| {
305            let (value, heap, fuel) = eval(value_expr, env, heap, fuel)?;
306            let new_props: BTreeMap<VarName, Value> = props
307                .into_iter()
308                .filter(|(k, _)| k != name)
309                .chain(std::iter::once((name.clone(), value)))
310                .collect();
311            Ok((new_props, heap, fuel))
312        },
313    )
314}
315
316fn eval_field(
317    object: &Expr,
318    name: &VarName,
319    env: &Env,
320    heap: Heap,
321    fuel: Fuel,
322) -> Result<(Value, Heap, Fuel), Error> {
323    let (obj_v, heap, fuel) = eval(object, env, heap, fuel)?;
324    let addr = expect_ref(&obj_v)?;
325    let value = lookup_property(addr, name, &heap)?;
326    Ok((value, heap, fuel))
327}
328
329fn eval_throw(
330    inner: &Expr,
331    env: &Env,
332    heap: Heap,
333    fuel: Fuel,
334) -> Result<(Value, Heap, Fuel), Error> {
335    let (value, heap, fuel) = eval(inner, env, heap, fuel)?;
336    Err(Error::Thrown(Box::new(ThrownPayload::new(
337        value, heap, fuel,
338    ))))
339}
340
341fn eval_try_catch(
342    body: &Expr,
343    catch_param: &VarName,
344    handler: &Expr,
345    env: &Env,
346    heap: Heap,
347    fuel: Fuel,
348) -> Result<(Value, Heap, Fuel), Error> {
349    match eval(body, env, heap, fuel) {
350        Ok(triple) => Ok(triple),
351        Err(Error::Thrown(payload)) => {
352            let (value, heap, fuel) = payload.into_parts();
353            let new_env = env.extend(catch_param.clone(), value);
354            eval(handler, &new_env, heap, fuel)
355        }
356        Err(other) => Err(other),
357    }
358}
359
360fn lookup_property(addr: Address, name: &VarName, heap: &Heap) -> Result<Value, Error> {
361    let cell = heap
362        .load(addr)
363        .ok_or(Error::DanglingReference { address: addr })?;
364    let (properties, prototype) = expect_object_fields(cell)?;
365    properties
366        .get(name)
367        .cloned()
368        .map_or_else(|| lookup_in_proto(prototype, name, heap), Ok)
369}
370
371fn lookup_in_proto(
372    prototype: Option<Address>,
373    name: &VarName,
374    heap: &Heap,
375) -> Result<Value, Error> {
376    prototype.map_or_else(
377        || Err(Error::PropertyNotFound { name: name.clone() }),
378        |addr| lookup_property(addr, name, heap),
379    )
380}
381
382fn apply(func: Value, arg: Value, heap: Heap, fuel: Fuel) -> Result<(Value, Heap, Fuel), Error> {
383    match func {
384        Value::Closure { param, body, env } => {
385            let new_env = env.extend(param, arg);
386            eval(&body, &new_env, heap, fuel)
387        }
388        Value::Ref(address) => Err(Error::NotAFunction {
389            found: format!("ref({address})"),
390        }),
391        Value::Object { .. } => Err(Error::NotAFunction {
392            found: format!("{func}"),
393        }),
394    }
395}
396
397fn expect_ref(value: &Value) -> Result<Address, Error> {
398    match value {
399        Value::Ref(address) => Ok(*address),
400        Value::Closure { .. } | Value::Object { .. } => Err(Error::NotAReference {
401            found: format!("{value}"),
402        }),
403    }
404}
405
406fn expect_object_fields(
407    value: &Value,
408) -> Result<(&BTreeMap<VarName, Value>, Option<Address>), Error> {
409    match value {
410        Value::Object {
411            properties,
412            prototype,
413        } => Ok((properties, *prototype)),
414        Value::Closure { .. } | Value::Ref(_) => Err(Error::NotAnObject {
415            found: format!("{value}"),
416        }),
417    }
418}
419
420fn update_object_property(cell: &Value, name: &VarName, value: &Value) -> Result<Value, Error> {
421    match cell {
422        Value::Object {
423            properties,
424            prototype,
425        } => {
426            let new_props: BTreeMap<VarName, Value> = properties
427                .iter()
428                .filter(|(k, _)| *k != name)
429                .map(|(k, v)| (k.clone(), v.clone()))
430                .chain(std::iter::once((name.clone(), value.clone())))
431                .collect();
432            Ok(Value::object(new_props, *prototype))
433        }
434        Value::Closure { .. } | Value::Ref(_) => Err(Error::NotAnObject {
435            found: format!("{cell}"),
436        }),
437    }
438}
439
440fn extract_object_reference(value: &Value, heap: &Heap) -> Result<Address, Error> {
441    let addr = expect_ref(value)?;
442    let cell = heap
443        .load(addr)
444        .ok_or(Error::DanglingReference { address: addr })?;
445    expect_object_fields(cell).map(|_| addr)
446}
447
448fn subst(expr: &Expr, target: &VarName, replacement: &Expr) -> Expr {
449    match expr {
450        Expr::Var(name) => {
451            if name == target {
452                replacement.clone()
453            } else {
454                Expr::Var(name.clone())
455            }
456        }
457        Expr::Lam { param, body } => Expr::Lam {
458            param: param.clone(),
459            body: Box::new(subst_under_binder(body, param, target, replacement)),
460        },
461        Expr::App { func, arg } => Expr::App {
462            func: Box::new(subst(func, target, replacement)),
463            arg: Box::new(subst(arg, target, replacement)),
464        },
465        Expr::Let { name, value, body } => Expr::Let {
466            name: name.clone(),
467            value: Box::new(subst(value, target, replacement)),
468            body: Box::new(subst_under_binder(body, name, target, replacement)),
469        },
470        Expr::Fix { name, body } => Expr::Fix {
471            name: name.clone(),
472            body: Box::new(subst_under_binder(body, name, target, replacement)),
473        },
474        Expr::Ref { inner } => Expr::Ref {
475            inner: Box::new(subst(inner, target, replacement)),
476        },
477        Expr::Deref { inner } => Expr::Deref {
478            inner: Box::new(subst(inner, target, replacement)),
479        },
480        Expr::Assign {
481            target: t,
482            value: v,
483        } => Expr::Assign {
484            target: Box::new(subst(t, target, replacement)),
485            value: Box::new(subst(v, target, replacement)),
486        },
487        Expr::Seq { first, second } => Expr::Seq {
488            first: Box::new(subst(first, target, replacement)),
489            second: Box::new(subst(second, target, replacement)),
490        },
491        Expr::Object { entries, prototype } => Expr::Object {
492            entries: entries
493                .iter()
494                .map(|(k, v)| (k.clone(), subst(v, target, replacement)))
495                .collect(),
496            prototype: prototype
497                .as_ref()
498                .map(|p| Box::new(subst(p, target, replacement))),
499        },
500        Expr::Field { object, name } => Expr::Field {
501            object: Box::new(subst(object, target, replacement)),
502            name: name.clone(),
503        },
504        Expr::Throw { inner } => Expr::Throw {
505            inner: Box::new(subst(inner, target, replacement)),
506        },
507        Expr::TryCatch {
508            body,
509            catch_param,
510            handler,
511        } => Expr::TryCatch {
512            body: Box::new(subst(body, target, replacement)),
513            catch_param: catch_param.clone(),
514            handler: Box::new(subst_under_binder(
515                handler,
516                catch_param,
517                target,
518                replacement,
519            )),
520        },
521    }
522}
523
524fn subst_under_binder(body: &Expr, binder: &VarName, target: &VarName, replacement: &Expr) -> Expr {
525    if binder == target {
526        body.clone()
527    } else {
528        subst(body, target, replacement)
529    }
530}
531
532#[cfg(test)]
533mod tests {
534    use super::*;
535
536    fn empty_fuel() -> Fuel {
537        Fuel::new(10_000)
538    }
539
540    #[test]
541    fn empty_object_allocates_one_cell() -> Result<(), Error> {
542        let e = Expr::object(vec![]);
543        let (value, heap, _fuel) = eval(&e, &Env::empty(), Heap::empty(), empty_fuel())?;
544        let is_ref = matches!(value, Value::Ref(_));
545        let one_cell = heap.len() == 1;
546        (is_ref && one_cell)
547            .then_some(())
548            .ok_or(Error::UnboundVariable {
549                name: VarName::from("expected one cell"),
550            })
551    }
552}
lambda_throw_cat/eval.rs

lambda_throw_cat/
eval.rs
