Crate lambda_cat 

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

use lambda_cat::run;

let value = run(r"(\x. x) (\y. y)").run()?;
assert_eq!(format!("{value}"), "\\y. y");

Grammar

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 ")"

Modules

env

Persistent lexical environments.

error

Project-wide error type.

eval

Tree-walking interpreter for the lambda calculus.

lexer

Tokenizer for the lambda calculus surface syntax.

parser

Recursive-descent parser for the lambda calculus surface syntax.

syntax

Abstract syntax and source-position newtypes.

value

Runtime values produced by evaluation.

Constants

DEFAULT_FUEL

Default step budget used by run. Large enough for normal expressions, small enough that proptest-generated divergent programs surface promptly.

Functions

run

Lex, parse, and evaluate source against the empty environment with the default fuel budget, returning the result wrapped in Io.

run_with_fuel

Lex, parse, and evaluate source against the empty environment with a caller-supplied Fuel budget.