lambda-ref-cat 0.1.0

Lambda calculus with mutable reference cells and a pure-functional mark-sweep garbage collector, built on comp-cat-rs. Spike 2 of a web-engine reformulation targeting Tauri.
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

# lambda-ref-cat

Lambda calculus with mutable reference cells and a pure-functional mark-sweep garbage collector, built on [comp-cat-rs](https://crates.io/crates/comp-cat-rs).

This is **spike 2** of a comp-cat-rs reformulation of a web engine targeting Tauri integration.  Spike 1 ([lambda-cat](https://crates.io/crates/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

```text
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

```rust
# 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

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

## License

Licensed under either of [Apache License, Version 2.0](LICENSE-APACHE) or [MIT license](LICENSE-MIT) at your option.

[`gc::collect`]: https://docs.rs/lambda-ref-cat/latest/lambda_ref_cat/gc/fn.collect.html