Efficient Extraction for Effectful E-graphs

# Efficient Extraction for Effectful E-graphs Source: [https://ztatlock.net/pubs/2026-oopsla-eggcc/](https://ztatlock.net/pubs/2026-oopsla-eggcc/) [Oliver Flatt](https://www.oflatt.com/),[Anjali Pal](https://ajpal.github.io/),[Yihong Zhang](https://effect.systems/),[Ryan Tjoa](https://rtjoa.com/),[Kirsten Graham](https://kirstenmg.github.io/),[Alex Fischman](https://www.linkedin.com/in/alex-fischman-775259265/),[Chandrakana Nandi](https://cnandi.com/),[Eli Rosenthal](https://www.linkedin.com/in/eli-rosenthal-79230264/),[Zachary Tatlock](https://ztatlock.net/),[Haobin Ni](https://haobin.cx/) Object\-Oriented Programming, Systems, Languages & Applications 2026 [](https://ztatlock.net/pubs/2026-oopsla-eggcc/2026-oopsla-eggcc.pdf) - [paper](https://ztatlock.net/pubs/2026-oopsla-eggcc/2026-oopsla-eggcc.pdf) - [code](https://github.com/egraphs-good/eggcc) - [bib](https://ztatlock.net/pubs/2026-oopsla-eggcc/2026-oopsla-eggcc.bib) ## Abstract E\-graphs have enabled recent advances in program optimization, synthesis, and verification, yet remain difficult to apply to effectful programs whose memory and I/O operations must respect execution order\. Existing effect\-aware extraction algorithms rely on integer linear programming \(ILP\) and dominate total runtime\. We introduce statewalk DP, a new extraction algorithm that enforces effect ordering efficiently without external solvers\. We prove that finding any effect\-safe extraction is NP\-complete, but show that statewalk DP is tractable in statewalk width, a parameter that measures the complexity of dataflow interactions among effects\. In practice, statewalk width generally remains small, enabling statewalk DP to achieve order\-of\-magnitude speedups over ILP extraction while producing programs comparable to LLVM across our benchmarks\. We implement the algorithm in eggcc, a prototype e\-graph\-based compiler for imperative Bril programs, and demonstrate that effect\-aware extraction is no longer a bottleneck\. ## BibTeX ``` @article{2026-oopsla-eggcc, author = {Flatt, Oliver and Pal, Anjali and Zhang, Yihong and Tjoa, Ryan and Graham, Kirsten and Fischman, Alex and Nandi, Chandrakana and Rosenthal, Eli and Tatlock, Zachary and Ni, Haobin}, title = {Efficient Extraction for Effectful E-graphs}, year = {2026}, month = oct, journal = {Proceedings of the ACM on Programming Languages}, volume = {10}, number = {OOPSLA2}, articleno = {398}, numpages = {28}, publisher = {Association for Computing Machinery}, url = {https://doi.org/10.1145/3839530}, doi = {10.1145/3839530} } ``` [📝 publications index](https://ztatlock.net/pubs/)