awesome-egraphs

Yes, perhaps. This is not written as a general introduction to e-graphs. They are a data structure that compactly holds many equivalent versions of terms / syntax trees. Egraphs are a solution to phase ordering issues for greedy rewrites. They are also just a useful fabric for optimization tasks. They are being used in many compiler projects https://github.com/philzook58/awesome-egraphs . Mostly research compilers, but cranelift and luminal are not for example. Many applications are naturally expressed using bound variables (lambdas, summation expressions, einstein indices, integrals, loops) but the basic e-graph doesn't really support the concept. One can instead model using combinators (SKI combinators, relation algebra, categorical combinators, other) but this tends to be not entirely natural and tends to explodes in the search space

e-graphs have been repeatedly reinvented across decades for many purposes. One of them is superoptimization. https://en.wikipedia.org/wiki/E-graph https://www.cs.cornell.edu/courses/cs6120/2025sp/blog/supero... https://github.com/philzook58/awesome-egraphs

They use triples as triplets can represent any n-tuple facts. E.g., if you have a fact id=(a,b,c,d), you can record triples (id, 1, a), (id, 2, b), (id, 3, c) and (id, 4, d) and reconstruct original fact. Look at it as columnar storage in databases. Then, if your query only needs a third value from a 4-tuple facts, you can get only those, ignoring first, second and fourth values. This is what columnar storage engines do. In fact, I read that one of most efficient datalog engines use relational query execution under the hood. Take a look here: https://github.com/philzook58/awesome-egraphs The paper you'll most probably find interesting is "Better Together: Unifying Datalog and Equality Saturation," but there are many others interesting things there.

Wide context. But to be a bit more specific, I've been involved in the egraphs community https://github.com/philzook58/awesome-egraphs and we don't currently have a shared database of rewrite rules for benchmarking, nor do we collect the rules from different projects. Seeing the actual files is helpful. On a slightly different front, I'm also trying to collect rules or interesting theories up in my python interactive theorem prover Knuckledragger https://github.com/philzook58/knuckledragger . Rewrite rule or equational theory looking things are easier to work with than things with deeply nested notions of quantifiers or tons of typeclass / mathematical abstraction like you find when you try to translate out of Coq, Lean, Isabelle. There are also different approaches to declarative rewrite rules in major compilers. GCC, LLVM, and cranelift