lambda-cat 0.1.0

Untyped lambda calculus interpreter built on comp-cat-rs. Lex, parse, and tree-walk evaluation expressed as Io effects with static dispatch and no panics.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

//! # lambda-cat
//!
//! Untyped lambda calculus interpreter built on [`comp_cat_rs`].
//!
//! The library is structured around four pure passes (lex, parse, evaluate)
//! over an immutable persistent environment, all wrapped at the boundary in
//! a single [`Io`] effect.  Every value the interpreter produces is itself
//! immutable; recursion is bounded by an explicit [`Fuel`] budget so that
//! diverging programs surface as [`Error::FuelExhausted`] rather than
//! stack overflow.
//!
//! ## Quick start
//!
//! ```
//! # fn main() -> Result<(), lambda_cat::error::Error> {
//! use lambda_cat::run;
//!
//! let value = run(r"(\x. x) (\y. y)").run()?;
//! assert_eq!(format!("{value}"), "\\y. y");
//! # Ok(())
//! # }
//! ```
//!
//! ## Grammar
//!
//! ```text
//! expr     ::= lambda | let | fix | app_expr
//! lambda   ::= "\" ident "." expr
//! let      ::= "let" ident "=" expr "in" expr
//! fix      ::= "fix" ident "." expr
//! app_expr ::= atom atom*
//! atom     ::= ident | "(" expr ")"
//! ```
//!
//! [`Io`]: comp_cat_rs::effect::io::Io
//! [`Fuel`]: crate::eval::Fuel
//! [`Error::FuelExhausted`]: crate::error::Error::FuelExhausted

pub mod env;
pub mod error;
pub mod eval;
pub mod lexer;
pub mod parser;
pub mod syntax;
pub mod value;

use comp_cat_rs::effect::io::Io;

use crate::env::Env;
use crate::error::Error;
use crate::eval::Fuel;
use crate::value::Value;

/// Default step budget used by [`run`].  Large enough for normal expressions,
/// small enough that proptest-generated divergent programs surface promptly.
pub const DEFAULT_FUEL: u64 = 10_000;

/// Lex, parse, and evaluate `source` against the empty environment with the
/// default fuel budget, returning the result wrapped in [`Io`].
///
/// The caller drives the effect by calling `.run()` at the boundary.  Until
/// then the work is suspended.
///
/// # Errors
///
/// Any of the underlying passes can fail; see [`Error`].
///
/// # Examples
///
/// ```
/// # fn main() -> Result<(), lambda_cat::error::Error> {
/// use lambda_cat::run;
///
/// let value = run(r"let id = \x. x in id id").run()?;
/// assert_eq!(format!("{value}"), "\\x. x");
/// # Ok(())
/// # }
/// ```
///
/// [`Io`]: comp_cat_rs::effect::io::Io
#[must_use]
pub fn run(source: &str) -> Io<Error, Value> {
    run_with_fuel(source, Fuel::new(DEFAULT_FUEL))
}

/// Lex, parse, and evaluate `source` against the empty environment with a
/// caller-supplied [`Fuel`] budget.
///
/// # Errors
///
/// Any of the underlying passes can fail; see [`Error`].
///
/// # Examples
///
/// ```
/// # fn main() -> Result<(), lambda_cat::error::Error> {
/// use lambda_cat::eval::Fuel;
/// use lambda_cat::run_with_fuel;
///
/// let value = run_with_fuel(r"(\x. x) (\y. y)", Fuel::new(100)).run()?;
/// assert_eq!(format!("{value}"), "\\y. y");
/// # Ok(())
/// # }
/// ```
#[must_use]
pub fn run_with_fuel(source: &str, fuel: Fuel) -> Io<Error, Value> {
    let owned = source.to_owned();
    Io::suspend(move || {
        let tokens = lexer::lex(&owned)?;
        let expr = parser::parse(&tokens)?;
        let (value, _remaining) = eval::eval(&expr, &Env::empty(), fuel)?;
        Ok(value)
    })
}