| layout |
|---|
default |
{% assign egg = 'egg' %}
The {{egg}} project uses e-graphs to provide a new way to build program optimizers and synthesizers.
The core {{egg}} library provides high-performance, flexible e-graphs implemented in Rust. It is packaged on crates.io and documented on docs.rs, including a tutorial that provides an introduction to e-graphs and their use cases.
The newer egglog system provides an alternative approach to equality saturation based on Datalog. It features a language-based design, incremental execution, and composable analyses. Check out the paper and the web demo.
BibTeX
@article{2021-egg,
author = {Willsey, Max and Nandi, Chandrakana and Wang, Yisu Remy and Flatt, Oliver and Tatlock, Zachary and Panchekha, Pavel},
title = {egg: Fast and Extensible Equality Saturation},
year = {2021},
issue_date = {January 2021},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {POPL},
url = {https://doi.org/10.1145/3434304},
doi = {10.1145/3434304},
abstract = {An e-graph efficiently represents a congruence relation over many expressions. Although they were originally developed in the late 1970s for use in automated theorem provers, a more recent technique known as equality saturation repurposes e-graphs to implement state-of-the-art, rewrite-driven compiler optimizations and program synthesizers. However, e-graphs remain unspecialized for this newer use case. Equality saturation workloads exhibit distinct characteristics and often require ad-hoc e-graph extensions to incorporate transformations beyond purely syntactic rewrites. This work contributes two techniques that make e-graphs fast and extensible, specializing them to equality saturation. A new amortized invariant restoration technique called rebuilding takes advantage of equality saturation's distinct workload, providing asymptotic speedups over current techniques in practice. A general mechanism called e-class analyses integrates domain-specific analyses into the e-graph, reducing the need for ad hoc manipulation. We implemented these techniques in a new open-source library called egg. Our case studies on three previously published applications of equality saturation highlight how egg's performance and flexibility enable state-of-the-art results across diverse domains.},
journal = {Proc. ACM Program. Lang.},
month = jan,
articleno = {23},
numpages = {29},
keywords = {equality saturation, e-graphs}
}
The {{egg}} project is part of the larger EGRAPHS Community, which aims to bring together researchers and practitioners interested in e-graphs and related techniques. Check out the EGRAPHS Community resources, including:
- The annual EGRAPHS Workshop at PLDI,
- The monthly EGRAPHS Seminar,
- The EGRAPHS Zulip for discussion and announcements about egg, egglog, and other projects!
For updates on {{egg}} itself, see the changelog.
- Our work connecting egg to Datalog will appear at PLDI 2023.
- Our paper Small Proofs from Congruence Closure is accepted to FMCAD 2022! See the recorded talk here.
- The inaugural EGRAPHS workshop at PLDI 2022 was a huge success!
- Ruler won a Distinguished Paper Award at OOPSLA 2021! Check out the talk here.
- Our paper on using equality saturation to automatically infer rewrite rules is accepted at OOPSLA 2021!
- Max wrote a post on the SIGPLAN blog about {{egg}}!
- Check out {{egg}}'s POPL 2021 videos on YouTube (5 min and 30 min) or Clowdr.
- The {{egg}} paper won Distinguished Paper at POPL 2021.
- Max gave a 10 minute talk about {{egg}} as part of the UW CSE Colloquium series.
- The {{egg}} paper will appear at POPL 2021! Check out the preprint.
Check out Philip Zucker's page on Awesome E-graphs for a list of {{egg}} and e-graph related projects. PRs are welcome to add your project to the list!
You can also see who's using {{egg}} on GitHub and Google Scholar.
View or edit this site on GitHub.