How to prove equations using diagrams, part 1
This article explores the mathematical concept of e-graphs, which are data structures used for equational reasoning in computer science. The author discusses the transition from traditional implementation-focused approaches to a more categorical and diagrammatic understanding of these structures.
Why it matters
E-graphs are increasingly important in compiler optimization and formal verification, making this a significant technical development.
This post is cross-posted at the Topos Institute blog .
An e-graph , short for “equality graph,” is a data structure that maintains a congruence relation on expression trees: an equivalence relation stable under forming new expressions. First devised by Nelson and Oppen in 1980 ( Nelson 1980 ; Nelson and Oppen 1980 ) , e-graphs received a surge of new attention when Willsey et al demonstrated, via their software package egg , that e-graphs combined with equality saturation can be a fast, powerful, and adaptable tool for equational reasoning ( Willsey et al. 2021 ) . In my own work on CatColab , I’ve begun using egg ’s successor, egglog ( Zhang et al. 2023 ) , to reason about finitely presented categories.
Get smarter about the news
Sign up free for a feed built around what you actually care about, Dive Deeper research on any story, and the full text of every article.
Create free accountAlready have an account? Sign in