EUVIMEDEUVIMED entdecken
Crossref

egg: Fast and Extensible Equality Saturation

Max Willsey, Chandrakana Nandi, Yisu Remy Wang, Oliver Flatt, Zachary Tatlock, Pavel Panchekha

Communications of the ACM · 01.08.2026 · 69 (8) · 105-113

DOI: 10.1145/3815481 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Communications of the ACM, online erschienen am 29.07.2026. Verfasst von Max Willsey und 5 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

E-graphs, originally developed for use in automated theorem provers, are data structures that compactly represent a large number of expressions and the equalities between them. Recently, a technique called equality saturation adapted e-graphs for program optimization. Equality saturation can ameliorate issues with traditional, destructive term rewriting since e-graph rewriting only adds information to the e-graph. After rewriting, the e-graph represents a large space of equivalent terms (including the original term), and a final extraction procedure selects the best term according to a user-provided cost function. The egg library is a fast and flexible open-source implementation of e-graphs and equality saturation. Unlike solvers, egg is a white-box library for programmatic use. Users can easily define their own languages, rewrites, and analyses, and they can inspect and manipulate the e-graph directly. It incorporates novel techniques such as e-class analysis , a mechanism for integrating program analyses modulo equality; and rebuilding , a deferred invariant restoration algorithm. egg has been used in hundreds of academic and industrial projects for program optimization, synthesis, and verification in many domains; some are briefly highlighted in this article.

Zitieren

APA

Willsey, M., Nandi, C., Wang, Y. R., Flatt, O., Tatlock, Z., & Panchekha, P. (2026). egg: Fast and Extensible Equality Saturation. Communications of the ACM, 69(8), 105-113. https://doi.org/10.1145/3815481

Vancouver

Willsey M, Nandi C, Wang YR, Flatt O, Tatlock Z, Panchekha P. egg: Fast and Extensible Equality Saturation. Communications of the ACM. 2026;69(8):105-113. doi:10.1145/3815481

BibTeX
@article{Willsey2026,
  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},
  journal = {Communications of the ACM},
  year = {2026},
  volume = {69},
  number = {8},
  pages = {105--113},
  doi = {10.1145/3815481}
}
Kostenlos starten →