Slotted E-Graphs
summary
Implementation builds a new e-graph variant where e-classes are parameterized e-classes that accept slots for bound names, so renaming or removing binders becomes different instantiations instead of graph duplication. Evaluation on the Rise benchmarks compares against named and de Bruijn encodings and shows fusion workloads produce about a 100x smaller e-graph versus de Bruijn in extreme cases. Prototype is generic over languages, supports pattern rewrites, has limited extraction support and is available on GitHub.
AI-written summary · about
chapters (11)
- 0:00Slotted E-graphs intro
- 1:05Name binding problem
- 4:15Slotted E-graphs renaming
- 7:08Slotted E-classes model
- 8:33Binding variables
- 10:24Challenging cases
- 12:50Symmetry in E-classes
- 14:34Evaluation against existing implementations
- 17:43Binder impact
- 18:04Implementation state
- 19:27Q&A
related talks
20mSlotted E-Graphs: First-Class Support for (Bound) Variables in E-Graphs
23mVersioned E-Graphs
25mLifting E-Graphs: A Function Isn’t a Constant
35mOmelets Need Onions: E-graphs Modulo Theories via Bottom Up E-Matching
19mDestructive E-Graph Rewrites
22mFrom Rewriting to Fixpoints: Solving Recursive Equations with E-Graphs
24mIncremental Equality Saturation
20mFast and Optimal Extraction for Sparse Equality Graphs