Lambda MicroEgg extends e-graphs with binders and Miller patterns

A developer has released Lambda MicroEgg, an e-graph based rewriting tool with an s-expression frontend, built heavily on top of an existing tool called microegg by a developer named Max. The new tool adds three things microegg lacked: built-in binders that are well-scoped and alpha aware, higher-order Miller pattern matching, and capture-avoiding substitution inside rewrite right-hand sides. E-graphs are a data structure used to represent many equivalent versions of a program or expression at once, and are commonly used for equality saturation in compilers and theorem provers; historically they have struggled to handle binders (like lambda abstraction or summation) cleanly, which is what this project targets.

The author demonstrates the tool on several examples, including rewriting sum expressions with a binder notation (using @sum) and Miller pattern notation ({?a x}), and modeling beta substitution over a lambda term where {?body x} matches a body that may reference the bound variable x, substituting the applied value with capture avoidance. Alpha-equivalent terms (terms that differ only in variable naming) are shown to hash cons to the same internal representation, and the demo shows memory can even be shared between structurally similar but non-alpha-equivalent terms that differ only in unused bound variables.

On performance, the author ran a standard AC-10 associativity/commutativity saturation benchmark two ways. With the original first-order, parenthesis-based application, running 100 saturation rounds produced an e-graph of 1023 classes and 57012 e-nodes, with the apply phase taking about 999.98 milliseconds; the author notes that the comparison e-graph library 'egg' takes about 0.6 seconds for a similar example on the same machine, so Lambda MicroEgg is somewhat slower but not drastically. Switching to the higher-order, bracket-based application syntax (HOApp) on the same benchmark grew the e-graph to 2046 classes and 58035 e-nodes, with the apply phase taking about 1.29 seconds, showing the higher-order encoding carries a real performance cost, which the author suggests could potentially be reduced with optimizations like precomputing ground IDs in patterns.

A key limitation the author calls out is that the tool currently supports only 'ordered Miller patterns': when a nonlinear metavariable (one used more than once in a pattern) has its bound-variable arguments out of order, the tool raises an error rather than matching, and instructs the user to write the pattern in order on the match left-hand side and permute the arguments on the rewrite right-hand side instead. The author also notes being surprised that a map/comp fusion rewrite example could cause the e-graph to explode in size, and expresses a wish to eventually support more than seven pattern variables without much overhead when they are unused. The post ends with a list of further ideas the author is considering, including proof logging, injecting algebraic completion procedures (Buchberger's algorithm, multiset and semiring completion), and using the approach for relational calculus, type checkers, and program interpreters.

Key facts

Lambda MicroEgg is a new e-graph tool with an s-expression frontend, built on top of Max's microegg, adding built-in well-scoped alpha-aware binders, higher-order Miller pattern matching, and capture-avoiding substitution in rewrite right-hand sides.
On a first-order AC-10 saturation benchmark run for 100 rounds, the tool produced an e-graph of 1023 classes and 57012 e-nodes with an apply-phase time of about 999.98ms, versus roughly 0.6s for the comparison library 'egg' on a similar example on the author's machine.
The same AC-10 benchmark using higher-order, bracket-based application (HOApp) grew to 2046 classes and 58035 e-nodes with an apply-phase time of about 1.29 seconds, showing a real cost for the higher-order encoding.
The tool only supports 'ordered Miller patterns': nonlinear metavariables with out-of-order bound-variable arguments trigger an error instructing the user to reorder the pattern and permute arguments on the rewrite right-hand side instead.
The author was surprised that a map/comp fusion rewrite example could cause the e-graph to explode, and wants to eventually support more than seven pattern variables without much overhead when unused.

Why it matters

E-graphs power equality saturation techniques used in compilers, theorem provers and program optimization, but handling variable binding (lambda abstraction, summation, and similar scoped constructs) inside an e-graph cleanly has been a persistent difficulty. Lambda MicroEgg adds built-in alpha-aware binders and higher-order Miller pattern matching on top of an existing tool, microegg, which is a concrete step toward e-graphs that can natively reason about programs with binders rather than needing awkward encodings around them.

Who it affects

This is aimed at researchers and developers working on e-graph based equality saturation, term rewriting systems, compiler optimization passes, and automated theorem proving, particularly anyone who needs to rewrite expressions containing bound variables (like lambda terms or summations) rather than only first-order ground terms.

How to use it

Lambda MicroEgg is published as an open-source repository (philzook58/lambda-microegg on GitHub), and a WebAssembly demo is hosted on the author's site. It is driven by small s-expression script files run through a command-line interface, using commands like insert, rewrite, run, match, extract, guard and print-egraph, with binder notation such as @sum and @lam and Miller pattern notation like {?a x} for matching under binders.

How solid is it

The account comes from the tool's own author, working from the same codebase and running the benchmarks and demo transcripts shown in the post on their own machine; the numbers (e-graph sizes, timing figures) are reproduced directly from those runs rather than being third-party claims. It is an informal, blog-style technical writeup rather than a peer-reviewed paper, and no publication date is given in the visible text.

Risks and caveats

The tool runs measurably slower than the comparison library 'egg' on the first-order AC-10 benchmark, and switching to the higher-order application encoding adds further overhead on the same benchmark. Nonlinear Miller pattern support is currently restricted to 'ordered' patterns only, forcing manual workarounds when variable order doesn't match, and the author flags that certain rewrite examples (like map/comp fusion) can cause the e-graph to explode in size, along with an unresolved limit on efficiently supporting more than seven pattern variables.

“I was a bit surprised that the map comp fusion example can explode.”

— the author, in the Lambda MicroEgg post