lambda-ref-cat

Lambda calculus with mutable reference cells and a pure-functional mark-sweep garbage collector, built on comp-cat-rs.

This is spike 2 of a comp-cat-rs reformulation of a web engine targeting Tauri integration. Spike 1 (lambda-cat) showed the idioms hold for a pure interpreter. Spike 2 raises the bar: a heap of mutable cells and a tracing collector, expressed without mut, without Rc/Arc, without RefCell/Cell/Mutex, and without unsafe.

Grammar

expr        ::= seq_expr
seq_expr    ::= right_expr (";" right_expr)*
right_expr  ::= lambda | let | fix | assign_expr
lambda      ::= "\" ident "." expr
let         ::= "let" ident "=" expr "in" expr
fix         ::= "fix" ident "." expr
assign_expr ::= app_expr (":=" right_expr)?
app_expr    ::= atom atom*
atom        ::= ident | "(" expr ")" | "ref" atom | "!" atom

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

Precedence (loosest to tightest): ;, :=, application, prefix ref/!, atoms.

ref e allocates a fresh cell holding the value of e, returns the cell's reference.
!r dereferences r, reading the cell's current value.
r := v stores v into the cell r points to, and returns v.
e1 ; e2 evaluates e1 for effect, then evaluates e2 and returns its value.

Usage

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

let source = r"
    let counter = ref (\x. x) in
    counter := (\y. y) ;
    !counter
";
let value = run(source).run()?;
println!("{value}");
# Ok(())
# }

The mark-sweep collector is available via gc::collect. Tests in this crate exercise it directly to confirm that unreachable cells are freed and reachable cells survive, including across reference cycles.

How it stays pure

Heap is BTreeMap<Address, Value> plus a monotonic next-address counter. alloc, store, and retain all return new Heap values; the receiver is never mutated.
Evaluator threads (Value, Heap, Fuel) through every step. Heap changes propagate through the return type, not through interior mutability.
Garbage collector is a pure function from (roots, heap) to a new heap containing only reachable cells. Marking is a fold over reachable addresses; sweeping is a BTreeMap::filter shape implemented via iterator combinators.

Building

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

License