Folding an e-graph in pure egglog
This work provides a reusable implementation technique for functional programming with e-graphs, benefiting researchers and practitioners using egglog for program optimization and analysis.
The authors present a method to implement catamorphism (folding) over e-graphs in pure egglog, achieving memoization and reduced computation by operating on e-classes instead of concrete sub-terms. They introduce a staging trick to avoid re-propagation of updated values.
Folding over a recursive data structure (also known as "catamorphism") is an essential operation in functional programming. It allows one to declaratively define a recursive computation by focusing on how solutions of subproblems are combined into the solution of the parent problem. Folding in the context of e-graphs can have several benefits. Not only do we get memoization for free, but also computation is drastically reduced since the subproblems are defined over e-classes as opposed to concrete sub-terms. This short report presents our initial attempt at defining and implementing catamorphism, a general notion of a fold, in pure egglog. We discuss a reusable implementation trick to stage the inference rules so that there is no re-propagation of updated values.