Fast and Flexible Program Optimization with E-Graphs -
​​​​​​​Term rewriting is a core technique in many programming language systems, including compilers, synthesizers, and verifiers. In this talk, I will provide an introduction to e-graphs and equality saturation, a technique for non-destructive term rewriting. I will then present our recent work on efficient effect-safe e-graph extraction of imperative programs. When side effects such as memory or I/O operations are present, extraction algorithms must be careful to respect effect ordering constraints. Existing techniques rely on integer linear programming (ILP) solvers to enforce these constraints. I will show that the problem is NP-complete, but can be solved efficiently in practice with our new dynamic programming algorithm, which does not rely on external solvers.

Bio: Anjali is a fourth-year PhD student at the University of Washington, advised by Zachary Tatlock. Her research focuses on programming languages, particularly techniques for building fast, flexible, and correct compilers across a variety of domains. She is passionate about teaching, especially programming languages, systems, and compilers.