🔢 mathematics

Categorical E-Graphs for Lambda Calculi

This paper extends the categorical framework of e-graphs to closed symmetric monoidal categories to natively support variable binding in $\lambda$ -calculus, introducing a hierarchical hypergraph representation with a double-pushout rewriting mechanism that is proven equivalent to standard term rewriting.

Original authors: Aleksei Tiurin, Dan R. Ghica, Nick Hu

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Aleksei Tiurin, Dan R. Ghica, Nick Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive puzzle, but every time you move a piece, you accidentally destroy the pieces you've already placed. This is the problem computer scientists face when trying to optimize complex computer programs. They use a tool called an e-graph (equality graph), which is like a super-efficient filing cabinet. Instead of throwing away old versions of a program when they find a better one, the e-graph keeps all the versions in the same cabinet, grouping together pieces that mean the same thing. This allows the computer to explore millions of possibilities at once without getting lost.

However, there's a catch: e-graphs have historically struggled with variables (like the "x" in math equations). In a program, a variable is like a name tag that can be moved around. If you move the name tag, the meaning of the program might change, or two identical programs might look different just because the name tags are in different spots. This makes it very hard for the e-graph to realize they are actually the same.

The Big Idea: From Text to Pictures

The authors of this paper propose a new way to handle these variable name tags. Instead of treating programs as text (like a sentence you read), they treat them as string diagrams (like a map or a flowchart).

The Old Way (Text): Imagine writing a recipe. If you write "Add salt" in step 1 and "Add salt" in step 5, a computer sees two separate sentences. Even if they mean the same thing, the computer has to do extra work to realize they are identical.
The New Way (String Diagrams): Imagine the recipe as a physical flowchart where wires connect ingredients to actions. If you have two "Add salt" steps, they are literally the same physical wire connected to two different spots. You don't need to compare text; the picture shows they are the same.

The "Magic Box" Solution

To make this work for variables (which can be "bound" or locked inside a specific part of the program, like a local variable in a function), the authors use a concept from advanced math called Category Theory.

Think of a program as a machine with inputs and outputs.

The Box: They represent a function (like a lambda abstraction, λx) as a rounded box. The variable x is a wire that goes into the box.
The Sharing: They use dashed boxes to represent groups of things that are equivalent. If two parts of the program are mathematically equal, they sit inside the same dashed box.
The Result: By combining these boxes, they create a structure called a Closed E-Hypergraph. This is a fancy name for a "puzzle map" that automatically knows when two pieces are the same, even if they are wrapped inside different boxes or have different variable names.

How It Works: The "Rewiring" Trick

In traditional e-graphs, to change a program, you have to delete an old piece and paste a new one. This is risky and slow.

In this new system, changing the program is like rewiring a circuit board.

Imagine a "Beta-reduction" (a fundamental rule in programming where you plug a value into a function) not as deleting text, but as simply unplugging a wire from one socket and plugging it into another.
Because the structure is built on these diagrams, the computer doesn't need to worry about renaming variables or checking if they are "captured" (stolen by the wrong scope). The wires just flow naturally.

Why This Matters (According to the Paper)

The authors tested this idea using a specific type of programming logic called the linear substitution calculus (a way of handling "let" statements and sharing in code).

The Problem with the Old Way: To handle "let" statements (like let x = 1 in...), old e-graphs had to add special "bureaucratic" nodes and rules just to manage the names. This cluttered the system and slowed it down.
The New Way: In their diagram system, "let" statements are just natural connections. The system automatically understands that let x = 1 in (x + x) is the same as let y = 1 in (y + y) without needing extra rules. The "sharing" is built into the geometry of the diagram.

The Bottom Line

The paper claims to have built a new mathematical foundation for e-graphs that treats programs as topological maps rather than text. By using "boxes" to hide variables and "wires" to connect them, they created a system where:

Equivalence is automatic: If two diagrams look the same topologically, they are the same program.
Rewriting is safe: You can change parts of the program without destroying the rest.
Variables are handled naturally: No more messy renaming or special "bureaucratic" nodes.

The authors argue that this approach is particularly powerful for functional programming languages (like those based on the Lambda Calculus), offering a cleaner, more efficient way to optimize code compared to previous methods that relied on "slotted" e-graphs (which treat variables as explicit data slots). They provide the mathematical proof that their diagram-based rewriting is just as correct as traditional text-based rewriting, but with the added benefit of handling the "shape" of the program directly.

Technical Summary: Categorical E-Graphs for Lambda Calculi

Problem Statement

Equality saturation is a powerful technique for program optimization and reasoning, utilizing equivalence classes of terms (e-graphs) to explore a space of rewrite rules non-destructively. However, traditional e-graphs lack native support for variable binding, a fundamental feature of functional programming languages based on the $\lambda$ -calculus.

Existing approaches to incorporating binding face significant challenges:

Textual Representations: In standard textual syntax, $\alpha$ -equivalent terms are distinct and cannot be shared. While De Bruijn indices identify $\alpha$ -equivalence syntactically, the indices depend on variable scope, preventing sharing of terms that differ only in index assignment (e.g., $\lambda f. f((\lambda x. fx)2)$ ).
Explicit Substitution: Adding explicit substitution nodes (e.g., $t[x/u]$ ) to handle binding introduces "bureaucracy." It requires additional nodes and rewrite rules to manage permutations of non-interacting substitutions (graphical equivalence), cluttering the state space with administrative overhead rather than domain-specific rewriting.
Slotted E-Graphs: Recent work (Schneider et al.) introduces "slotted e-graphs" where variables are first-class data. While effective, this approach relies on nominal techniques applicable to arbitrary languages (like the $\pi$ -calculus) but may not leverage the specific structural properties of $\lambda$ -calculus as efficiently as a dedicated semantic model.

The core problem is the lack of a native, categorical data structure for e-graphs that supports variable binding, allowing for efficient equality saturation in $\lambda$ -calculi without the overhead of explicit substitution nodes or complex renaming rules.

Methodology

The authors propose a solution grounded in categorical semantics, extending the interpretation of e-graphs as string diagrams.

1. Categorical Framework

The paper builds upon the work of Tiurin et al., who modeled e-graphs (without binding) as morphisms in symmetric monoidal semilattice-enriched categories (SLat-categories).

SLat-Enrichment: The Hom-sets are semilattices, where the join operation ( $+$ ) represents the equivalence of subterms (e-graph classes).
Monoidal Closed Structure: To handle variable binding, the authors extend the category to be monoidal closed. This introduces the internal hom object ( $A \multimap B$ ) and the adjunction $- \otimes B \dashv B \multimap -$ .
String Diagrams: Terms are represented as string diagrams. Binding is modeled via "rounded boxes" (representing $\lambda$ -abstraction), and equivalence classes are modeled via "dashed boxes" (representing the semilattice join).

2. Combinatorial Representation: Closed E-Hypergraphs

To provide a concrete data structure, the authors define closed e-hypergraphs. These are hierarchical hypergraphs that encode:

Hyperedges: Representing operations (generators).
Hierarchical Edges: Two types of nested structures:
- E-classes (Dashed boxes): Representing equivalence classes of subterms.
- Abstraction Boxes (Rounded boxes): Representing $\lambda$ -abstractions.
Interfaces: The structure uses extended cospans to manage inputs and outputs, distinguishing between external interfaces (top-level) and strictly internal interfaces (nested within boxes).

3. Rewriting System

The authors define a Double-Pushout with Interfaces (DPOI) rewriting system for closed e-hypergraphs.

Rewrite Rules: Defined as spans of extended cospans.
Boundary Complements: A specialized definition of the "hole" left after removing a match is introduced to handle the hierarchical nature of the graphs. This ensures that when a subgraph is removed, the internal interfaces are correctly adjusted (e.g., removing a nested term updates the strictly internal interface of the parent).
Soundness and Completeness: The paper establishes that DPO rewriting on these closed e-hypergraphs is sound and complete with respect to rewriting of closed $\Sigma^+$ -terms modulo the equations of symmetric monoidal SLat-categories and the distributivity law of the closed structure.

Key Contributions

Categorical Extension: The construction of a form of e-graphs supporting binding by extending the categorical domain from free symmetric monoidal SLat-categories to free closed symmetric monoidal SLat-categories.
Closed E-Hypergraphs: The definition of a concrete combinatorial representation (closed e-hypergraphs) that naturally absorbs the equations of the symmetric monoidal structure and the closed structure (binding).
DPOI Rewriting for Binding: The formulation of a DPOI rewriting system for these structures, proving its soundness and completeness relative to term rewriting in the corresponding categorical theory.
Comparison with Slotted E-Graphs: A theoretical comparison demonstrating that while slotted e-graphs offer generic binding via nominal techniques, the categorical approach embeds binding into the internal language of the model, potentially offering advantages for $\lambda$ -calculus specific optimizations.

Results

Equivalence of Rewriting: The paper proves that term rewriting of closed $\Sigma^+$ -terms is equivalent to DPO rewriting of closed e-hypergraphs.
Handling Graphical Equivalence: The approach naturally handles "graphical equivalence" (permutations of non-interacting substitutions) without requiring explicit substitution nodes. In the categorical model, explicit substitution is modeled as composition, and the structural laws of the category absorb the necessary equivalences.
Case Study ( $\lambda_{lsub}$ ): The authors apply the theory to the linear substitution calculus ( $\lambda_{lsub}$ ). They demonstrate that terms with explicit substitutions (e.g., let-bindings) can be represented directly as string diagrams.
- Unlike conventional e-graphs which require explicit nodes for substitution and rewrite rules to handle their permutation, the categorical model treats these as structural properties of the diagram.
- The paper shows that semantically equivalent programs (e.g., reordering let-bindings) map to the same string diagram, allowing equality saturation to operate on a normalized representation.

Significance and Claims

The paper claims to provide a foundational categorical semantics for e-graphs with binding, an area previously underdeveloped.

Theoretical Justification: It offers a rigorous justification for the congruences maintained by e-graphs with binding, grounding them in the properties of closed symmetric monoidal SLat-categories.
Efficiency Potential: By absorbing structural equations (like associativity, commutativity, and substitution permutations) into the graphical syntax and the underlying category, the approach aims to reduce the "bureaucracy" in the equality saturation state space. This contrasts with approaches that treat these as explicit rewrite rules.
Scope: The authors explicitly state that their approach is specialized for $\lambda$ -calculus and variations thereof, leveraging the metatheoretic internal language of the categorical model. They acknowledge that slotted e-graphs may be more flexible for arbitrary formal languages with binders (like the $\pi$ -calculus), but argue their method is superior for $\lambda$ -calculus specific optimizations.

The work does not present a full software implementation or empirical benchmarks in this paper but positions the closed e-hypergraph representation as a viable foundation for building "e-graphs for string diagram rewriting" in future work.