An Introduction to E-Graphs with Rebecca Swords

E-graphs are a data structure that efficiently stores equivalence relations over language terms, well-suited to a broad spectrum of term-rewriting applications. Rather than applying rewrites destructively as many compilers do, e-graphs track equivalent terms, using a technique called equality saturation to efficiently apply large sets of rewriting rules, and then use a cost model to extract an optimized term.

In this talk, I will present an overview of e-graphs, sketching core operations including equality saturation; describing e-class analyses; and explaining the e-graph approach to optimized term extraction. This work is based on Quiche, which is my project implementing e-graphs in Python with specialized support for Python AST rewriting.

About Rebecca:
Rebecca Swords received her M.S. in Computer Science from Indiana University, Bloomington in 2011, and has since worked in both full stack application development and in industry research in program synthesis. Her most recent work is on Quiche, a Python implementation of e-graphs. She is currently a stay-at-home mom, engaging with research in her spare moments.