lambda-cat

Untyped lambda calculus interpreter built on comp-cat-rs.

Lex, parse, and tree-walk evaluation, all expressed as Io<Error, _> effects with static dispatch, hand-rolled Error, exhaustive matches, no panics, no mut, no unsafe, no interior mutability.

What it does

Given a source string in a small lambda calculus dialect, lambda-cat:

1. Lexes the source into tokens via a recursive functional tokenizer.
2. Parses the tokens into an Expr AST.
3. Evaluates the AST against a persistent environment, producing a Value (a closure).
4. Wraps the whole pipeline in Io<Error, Value> so the catamorphism only fires at the boundary.

Grammar

expr ::= var
       | "\" var "." expr           -- lambda abstraction
       | expr expr                  -- application (left-associative)
       | "let" var "=" expr "in" expr
       | "fix" var "." expr         -- fixed point (recursion)
       | "(" expr ")"

var  ::= [a-zA-Z_][a-zA-Z0-9_]*

Application binds tighter than abstraction and let. Whitespace is insignificant.

Usage

# fn main() -> Result<(), lambda_cat::error::Error> {
use lambda_cat::run;

let source = r"(\x. \y. x) a b";
let value = run(source).run()?;
println!("{value}");
# Ok(())
# }

Recursion via fix:

# fn main() -> Result<(), lambda_cat::error::Error> {
use lambda_cat::run;

// Church-encoded fixed-point combinator equivalent.
let source = r"
    let id = \x. x in
    let const = \x. \y. x in
    const id id
";
let _value = run(source).run()?;
# Ok(())
# }

Building

cargo build
cargo test
RUSTFLAGS="-D warnings" cargo clippy --all-targets

Why

This crate is spike 1 of a comp-cat-rs reformulation of a web engine targeting Tauri integration. It exists to falsify the hypothesis that comp-cat-rs idioms can express a stateful tree-walking interpreter cleanly. If the spike fits, spike 2 adds ref cells + a mark-sweep GC; if both fit, the path to a comp-cat-rs JavaScript engine (and beyond, to CSS, layout, DOM, embedder, and Tauri runtime) is open.

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.