LobstersHey There Buddo!15 min readadvanced
Lambda MicroEgg
Summary
lambda-microegg is a Rust e‑graph library that adds scoped, alpha‑aware binders and Miller‑style higher‑order patterns to the Egg framework, enabling capture‑avoiding substitution and higher‑order rewriting with modest performance overhead.
- Implements well‑scoped binders directly in the e‑graph, using a byte‑level lifting annotation on node IDs.
- Supports Miller patterns ({?a x y}) for higher‑order matching, enforcing ordered bound‑variable arguments.
- Provides a higher‑order application syntax (`[]`) that curries automatically, contrasting with first‑order `app` encoding.
- Benchmarks show AC saturation on simple arithmetic runs in ~0.6 s (Egg) vs ~0.7 s (lambda‑microegg), with match/apply/rebuild timings reported.
Adding true binder support and Miller patterns to e‑graphs bridges the gap between first‑order term rewriting and higher‑order reasoning, enabling more expressive program‑analysis and synthesis tools without a large performance penalty.
7/10
