TBD: Slotted E-Graphs
2025-03-20
Rudi and Michel will present their most recent work on slotted e-graphs, which was first seen at EGRAPHS 2024.
Abstract
E-graphs are bad at efficiently representing (bound) variables! However we represent variables in e-graph (as names or using de Bruijn indices), sub-terms that differ only in the names of their variables are represented separately and not shared. For many practical applications this results in aggressive e-graph growth, huge memory consumption and bad performance.
In this talk, I will present slotted e-graphs, which makes (bound) variables a first-class feature built into the data structure. Terms that differ only by (bound or free) variable names are represented uniquely and therefore efficiently shared. E-classes are parameterized by slots, abstracting over the free variables of the terms represented by their e-nodes. Referring to an e-class from an e-node now requires relating the variables from its context to the slots of the e-class.
In the talk, I will demonstrate with the help of two case studies that slotted e-graphs greatly simplify equality saturation for languages with variables and that memory efficiency is greatly improved allowing slotted e-graphs to solve practical problems that cannot be solved with traditional e-graphs using either names or using de Bruijn indices for variables.
Bio
Rudi Schneider and Michel Steuwer.