lambda_cat/
lib.rs

1//! # lambda-cat
2//!
3//! Untyped lambda calculus interpreter built on [`comp_cat_rs`].
4//!
5//! The library is structured around four pure passes (lex, parse, evaluate)
6//! over an immutable persistent environment, all wrapped at the boundary in
7//! a single [`Io`] effect.  Every value the interpreter produces is itself
8//! immutable; recursion is bounded by an explicit [`Fuel`] budget so that
9//! diverging programs surface as [`Error::FuelExhausted`] rather than
10//! stack overflow.
11//!
12//! ## Quick start
13//!
14//! ```
15//! # fn main() -> Result<(), lambda_cat::error::Error> {
16//! use lambda_cat::run;
17//!
18//! let value = run(r"(\x. x) (\y. y)").run()?;
19//! assert_eq!(format!("{value}"), "\\y. y");
20//! # Ok(())
21//! # }
22//! ```
23//!
24//! ## Grammar
25//!
26//! ```text
27//! expr     ::= lambda | let | fix | app_expr
28//! lambda   ::= "\" ident "." expr
29//! let      ::= "let" ident "=" expr "in" expr
30//! fix      ::= "fix" ident "." expr
31//! app_expr ::= atom atom*
32//! atom     ::= ident | "(" expr ")"
33//! ```
34//!
35//! [`Io`]: comp_cat_rs::effect::io::Io
36//! [`Fuel`]: crate::eval::Fuel
37//! [`Error::FuelExhausted`]: crate::error::Error::FuelExhausted
38
39pub mod env;
40pub mod error;
41pub mod eval;
42pub mod lexer;
43pub mod parser;
44pub mod syntax;
45pub mod value;
46
47use comp_cat_rs::effect::io::Io;
48
49use crate::env::Env;
50use crate::error::Error;
51use crate::eval::Fuel;
52use crate::value::Value;
53
54/// Default step budget used by [`run`].  Large enough for normal expressions,
55/// small enough that proptest-generated divergent programs surface promptly.
56pub const DEFAULT_FUEL: u64 = 10_000;
57
58/// Lex, parse, and evaluate `source` against the empty environment with the
59/// default fuel budget, returning the result wrapped in [`Io`].
60///
61/// The caller drives the effect by calling `.run()` at the boundary.  Until
62/// then the work is suspended.
63///
64/// # Errors
65///
66/// Any of the underlying passes can fail; see [`Error`].
67///
68/// # Examples
69///
70/// ```
71/// # fn main() -> Result<(), lambda_cat::error::Error> {
72/// use lambda_cat::run;
73///
74/// let value = run(r"let id = \x. x in id id").run()?;
75/// assert_eq!(format!("{value}"), "\\x. x");
76/// # Ok(())
77/// # }
78/// ```
79///
80/// [`Io`]: comp_cat_rs::effect::io::Io
81#[must_use]
82pub fn run(source: &str) -> Io<Error, Value> {
83    run_with_fuel(source, Fuel::new(DEFAULT_FUEL))
84}
85
86/// Lex, parse, and evaluate `source` against the empty environment with a
87/// caller-supplied [`Fuel`] budget.
88///
89/// # Errors
90///
91/// Any of the underlying passes can fail; see [`Error`].
92///
93/// # Examples
94///
95/// ```
96/// # fn main() -> Result<(), lambda_cat::error::Error> {
97/// use lambda_cat::eval::Fuel;
98/// use lambda_cat::run_with_fuel;
99///
100/// let value = run_with_fuel(r"(\x. x) (\y. y)", Fuel::new(100)).run()?;
101/// assert_eq!(format!("{value}"), "\\y. y");
102/// # Ok(())
103/// # }
104/// ```
105#[must_use]
106pub fn run_with_fuel(source: &str, fuel: Fuel) -> Io<Error, Value> {
107    let owned = source.to_owned();
108    Io::suspend(move || {
109        let tokens = lexer::lex(&owned)?;
110        let expr = parser::parse(&tokens)?;
111        let (value, _remaining) = eval::eval(&expr, &Env::empty(), fuel)?;
112        Ok(value)
113    })
114}
lambda_cat/lib.rs

lambda_cat/
lib.rs
