🔢 mathematics

Categorical E-Graphs for Lambda Calculi

Dit artikel breidt het categorische raamwerk van e-grafen uit naar gesloten symmetrische monoidale categorieën om variabele binding in de $\lambda$ -calculus natief te ondersteunen, waarbij een hiërarchische hypergraafrepresentatie wordt geïntroduceerd met een double-pushout herschrijvingsmechanisme dat bewezen equivalent is aan standaard termherschrijving.

Oorspronkelijke auteurs: Aleksei Tiurin, Dan R. Ghica, Nick Hu

Gepubliceerd 2026-06-26

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Aleksei Tiurin, Dan R. Ghica, Nick Hu

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme puzzel probeert op te lossen, maar elke keer als je een stukje verplaatst, vernietig je per ongeluk de stukjes die je al hebt geplaatst. Dit is het probleem waar informaticus tegen aan lopen bij het proberen te optimaliseren van complexe computerprogramma's. Ze gebruiken een hulpmiddel genaamd een e-graph (equality graph), wat een soort superefficiënte archiefkast is. In plaats van oude versies van een programma weg te gooien wanneer ze een betere versie vinden, bewaart de e-graph alle versies in dezelfde kast, waarbij ze stukjes groeperen die hetzelfde betekenen. Dit stelt de computer in staat om miljoenen mogelijkheden tegelijkertijd te verkennen zonder de weg kwijt te raken.

Er is echter een addertje onder het gras: e-graphs hadden historisch gezien moeite met variabelen (zoals de "x" in wiskundige vergelijkingen). In een programma is een variabele als een naamkaartje dat rondverplaatst kan worden. Als je het naamkaartje verplaatst, kan de betekenis van het programma veranderen, of kunnen twee identieke programma's er verschillend uitzien, simpelweg omdat de naamkaartjes op andere plekken staan. Dit maakt het erg moeilijk voor de e-graph om te beseffen dat ze eigenlijk hetzelfde zijn.

Het Grote Idee: Van Tekst naar Afbeeldingen

De auteurs van dit artikel stellen een nieuwe manier voor om deze variabele naamkaartjes te behandelen. In plaats van programma's als tekst te behandelen (zoals een zin die je leest), behandelen ze ze als string diagrammen (zoals een kaart of een flowchart).

De Oude Manier (Tekst): Stel je voor dat je een recept opschrijft. Als je in stap 1 schrijft "Voeg zout toe" en in stap 5 ook "Voeg zout toe", ziet een computer twee aparte zinnen. Zelfs als ze hetzelfde betekenen, moet de computer extra werk verrichten om te beseffen dat ze identiek zijn.
De Nieuwe Manier (String Diagrammen): Stel je het recept voor als een fysieke flowchart waarbij draden ingrediënten verbinden met acties. Als je twee "Voeg zout toe"-stappen hebt, zijn het letterlijk dezelfde fysieke draad die verbonden is met twee verschillende punten. Je hoeft de tekst niet te vergelijken; de afbeelding laat zien dat ze hetzelfde zijn.

De "Magische Doos" Oplossing

Om dit werkend te krijgen voor variabelen (die "gebonden" kunnen zijn of vastgelijnd binnen een specifief deel van het programma, zoals een lokale variabele in een functie), gebruiken de auteurs een concept uit de geavanceerde wiskunde genaamd Categorietheorie.

Beschouw een programma als een machine met inputs en outputs.

De Doos: Ze representeren een functie (zoals een lambda-abstractie, λx) als een afgeronde doos. De variabele x is een draad die de doos in gaat.
Het Delen: Ze gebruiken gestippelde dozen om groepen dingen te representeren die equivalent zijn. Als twee delen van het programma wiskundig gelijk zijn, zitten ze in dezelfde gestippelde doos.
Het Resultaat: Door deze dozen te combineren, creëren ze een structuur genaamd een Closed E-Hypergraph. Dit is een chique naam voor een "puzzelkaart" die automatisch weet wanneer twee stukjes hetzelfde zijn, zelfs als ze in verschillende dozen zijn verpakt of verschillende variabelen hebben.

Hoe het werkt: De "Rewiring" Truc

In traditionele e-graphs, om een programma te veranderen, moet je een oud stukje verwijderen en een nieuw stukje plakken. Dit is riskant en traag.

In dit nieuwe systeem is het veranderen van het programma als het herbedraden van een printplaat.

Stel je een "Beta-reductie" voor (een fundamentele regel in programmeren waarbij je een waarde in een functie plaatst) niet als het verwijderen van tekst, maar als simpelweg een draad uit een stopcontact trekken en in een ander stopcontact steken.
Omdat de structuur gebouwd is op deze diagrammen, hoeft de computer zich geen zorgen te maken over het hernoemen van variabelen of het controleren of ze "gecaptureerd" zijn (gestolen door de verkeerde scope). De draden stromen er natuurlijk doorheen.

Waarom dit ertoe doet (volgens het artikel)

De auteurs testten dit idee met een specifiek type programmeerlogica genaamd de lineaire substitutie calculus (een manier om "let"-statements en sharing in code af te handelen).

Het Probleem met de Oude Manier: Om "let"-statements (zoals let x = 1 in...) af te handelen, moesten oude e-graphs speciale "bureaucratische" nodes en regels toevoegen om namen te beheren. Dit vervuilde het systeem en vertraagde het.
De Nieuwe Manier: In hun diagramsysteem zijn "let"-statements gewoon natuurlijke verbindingen. Het systeem begrijpt automatisch dat let x = 1 in (x + x) hetzelfde is als let y = 1 in (y + y) zonder dat er extra regels nodig zijn. De "sharing" zit ingebakken in de geometrie van het diagram.

De Kern van het Verhaal

Het artikel beweert een nieuwe wiskundige basis te hebben gebouwd voor e-graphs die programma's behandelt als topologische kaarten in plaats van tekst. Door "dozen" te gebruiken om variabelen te verbergen en "draden" om ze te verbinden, hebben ze een systeem gecreëerd waar:

Equivalentie is automatisch: Als twee diagrammen topologisch hetzelfde zijn, zijn ze hetzelfde programma.
Herschrijven is veilig: Je kunt delen van het programma veranderen zonder de rest te vernietigen.
Variabelen worden natuurlijk afgehandeld: Geen meer rommelig hernoemen of speciale "bureaucratische" nodes.

De auteurs stellen dat deze benadering bijzonder krachtig is voor functionele programmeertalen (zoals die gebaseerd op de Lambda Calculus), omdat het een schonere, efficiëntere manier biedt om code te optimaliseren vergeleken met eerdere methoden die vertrouwden op "slotted" e-graphs (die variabelen behandelen als expliciete datastandaarden). Ze leveren het wiskundige bewijs dat hun diagram-gebaseerde herschrijven net zo correct is als traditioneel tekst-gebaseerd herschrijven, maar dan met het voordeel dat de "vorm" van het programma direct wordt afgehandeld.

Technische Samenvatting: Categorische E-Grafen voor Lambda-calculi

Probleemstelling

Equality saturation is een krachtige techniek voor programmaoptimalisatie en redeneren, waarbij gebruik wordt gemaakt van equivalentieklassen van termen (e-grafen) om een ruimte van herschrijfregels niet-destructief te verkennen. Traditionele e-grafen missen echter natuurlijke ondersteuning voor variabele binding, een fundamenteel kenmerk van functionele programmeertalen gebaseerd op de $\lambda$ -calculus.

Bestaande benaderingen voor het integreren van binding kampen met aanzienlijke uitdagingen:

Textuele Representaties: In standaard tekstuele syntaxis zijn $\alpha$ -equivalente termen verschillend en kunnen ze niet worden gedeeld. Hoewel De Bruijn-indices $\alpha$ -equivalentie syntactisch identificeren, zijn de indices afhankelijk van de variabele scope, wat het delen van termen verhindert die alleen verschillen in de toewijzing van indices (bijv. $\lambda f. f((\lambda x. fx)2)$ ).
Expliciete Substitutie: Het toevoegen van expliciete substitutie-nodes (bijv. $t[x/u]$ ) om binding te behandelen, introduceert "bureaucratie". Dit vereist extra nodes en herschrijfregels om permutaties van niet-interagerende substituties (grafische equivalentie) te beheren, wat de toestandsruimte vervuilt met administratieve overhead in plaats van domeinspecifieke herschrijving.
Slotted E-Grafen: Recent werk (Schneider et al.) introduceert "slotted e-grafen" waarbij variabelen als first-class data worden behandeld. Hoewel effectief, vertrouwt deze aanpak op nominale technieken die toepasbaar zijn op willekeurige talen (zoals de $\pi$ -calculus), maar maakt het mogelijk om de specifieke structurele eigenschappen van de $\lambda$ -calculus niet zo efficiënt te benutten als een toegewijd semantisch model.

Het kernprobleem is het gebrek aan een natuurlijke, categorische datastructuur voor e-grafen die binding ondersteunt, waardoor efficiënte equality saturation in $\lambda$ -calculi mogelijk is zonder de overhead van expliciete substitutie-nodes of complexe herbeneningsregels.

Methodologie

De auteurs stellen een oplossing voor die geworteld is in categorische semantiek, waarbij de interpretatie van e-grafen als stringdiagrammen wordt uitgebreid.

1. Categorisch Kader

Het artikel bouwt voort op het werk van Tiurin et al., die e-grafen (zonder binding) modelleerden als morfismen in symmetrische monoidale semilattice-verrijkte categorieën (SLat-categorieën).

SLat-Verrijking: De Hom-sets zijn semilattices, waarbij de join-operatie ( $+$ ) de equivalentie van subtermen (e-graaf klassen) vertegenwoordigt.
Monoidale Gesloten Structuur: Om variabele binding te behandelen, breiden de auteurs de categorie uit naar een monoidale gesloten structuur. Dit introduceert het interne hom-object ( $A \multimap B$ ) en de conjunctie $- \otimes B \dashv B \multimap -$ .
String Diagrammen: Termen worden gerepresenteerd als string diagrammen. Binding wordt gemodelleerd via "afgeronde boxen" (die $\lambda$ -abstractie representeren) en equivalentieklassen worden gemodelleerd via "gestreepte boxen" (die de semilattice join representeren).

2. Combinatorische Representatie: Closed E-Hypergraphs

Om een concrete datastructuur te bieden, definiëren de auteurs closed e-hypergraphs. Dit zijn hiërarchische hypergrafen die coderen:

Hyperedges: Representeren operaties (generatoren).
Hiërarchische Edges: Twee soorten geneste structuren:
- E-classes (Gestreepte boxen): Representeren equivalentieklassen van subtermen.
- Abstraction Boxes (Afgeronde boxen): Representeren $\lambda$ -abstracties.
Interfaces: De structuur gebruikt extended cospans om inputs en outputs te beheren, waarbij onderscheid wordt gemaakt tussen externe interfaces (top-level) en strikt interne interfaces (genest binnen boxen).

3. Herschrijfsysteem

De auteurs definiëren een Double-Pushout with Interfaces (DPOI) herschrijfsysteem voor closed e-hypergraphs.

Herschrijfregels: Gedefinieerd als spans van extended cospans.
Boundary Complements: Een gespecialiseerde definitie van de "gat" (hole) die achterblijft na het verwijderen van een match wordt geïntroduceerd om de hiërarchische aard van de grafen te behandelen. Dit zorgt ervoor dat wanneer een subgraaf wordt verwijderd, de interne interfaces correct worden aangepast (bijv. het verwijderen van een geneste term werkt de strikt interne interface van de ouder bij).
Correctheid en Volledigheid: Het artikel stelt vast dat DPO-herschrijven op deze closed e-hypergraphs correct en volledig is ten opzichte van het herschrijven van closed $\Sigma^+$ -termen modulo de vergelijkingen van symmetrische monoidale SLat-categorieën en de distributiewet van de gesloten structuur.

Belangrijkste Bijdragen

Categorische Uitbreiding: De constructie van een vorm van e-grafen die binding ondersteunt door de categorische domein uit te breiden van vrije symmetrische monoidale SLat-categorieën naar vrije gesloten symmetrische monoidale SLat-categorieën.
Closed E-Hypergraphs: De definitie van een concrete combinatorische representatie (closed e-hypergraphs) die de vergelijkingen van de symmetrische monoidale structuur en de gesloten structuur (binding) op natuurlijke wijze absorbeert.
DPOI Herschrijven voor Binding: De formulering van een DPOI herswijfsysteem voor deze structuren, waarbij de correctheid en volledigheid worden bewezen ten opzichte van term-herschrijven in de corresponderende categorische theorie.
Vergelijking met Slotted E-Grafen: Een theoretische vergelijking die aantoont dat hoewel slotted e-grafen generieke binding bieden via nominale technieken, de categorische aanpak binding embedt in de interne taal van het model, wat potentieel voordelen biedt voor $\lambda$ -calculus specifieke optimalisaties.

Resultaten

Equivalentie van Herschrijven: Het artikel bewijst dat term-herschrijven van closed $\Sigma^+$ -termen equivalent is aan DPO-herschrijven van closed e-hypergraphs.
Afhandeling van Grafische Equivalentie: De aanpak handelt "grafische equivalentie" (permutaties van niet-interagerende substituties) op natuurlijke wijze af zonder dat er expliciete substitutie-nodes nodig zijn. In het categorische model wordt expliciete substitutie gemodelleerd als compositie, waarbij de structurele wetten van de categorie de noodzakelijke equivalenties absorberen.
Casestudy ( $\lambda_{lsub}$ ): De auteurs passen de theorie toe op de lineaire substitutie calculus ( $\lambda_{lsub}$ ). Ze demonstreren dat termen met expliciete substituties (bijv. let-bindings) direct als string diagrammen kunnen worden gerepresenteerd.
- In tegenstelling tot conventionele e-grafen, die expliciete nodes voor substitutie en herschrijfregels vereisen om hun permutatie te beheren, behandelt het categorische model deze als structurele eigenschappen van het diagram.
- Het artikel laat zien dat semantisch equivalente programma's (bijv. het herordenen van let-bindings) naar hetzelfde string diagram mappen, waardoor equality saturation op een genormaliseerde representatie kan opereren.

Betekenis en Claims

Het artikel claimt een fundamentele categorische semantiek te bieden voor e-grafen met binding, een gebied dat voorheen onderontwikkeld was.

Theoretische Rechtvaardiging: Het biedt een rigoureuze rechtvaardiging voor de congruenties die worden onderhouden door e-grafen met binding, door ze te funderen in de eigenschappen van closed symmetric monoidal SLat-categorieën.
Efficiëntiepotentieel: Door structurele vergelijkingen (zoals associativiteit, commutativiteit en permutaties van substituties) te absorberen in de grafische syntaxis en de onderliggende categorie, beoogt de aanpak de "bureaucratie" in de equality saturation toestandsruimte te verminderen. Dit staat in contrast met benaderingen die deze als expliciete herschrijfregels behandelen.
Scope: De auteurs geven expliciet aan dat hun aanpak gespecialiseerd is voor de $\lambda$ -calculus en varianten daarvan, waarbij gebruik wordt gemaakt van de metathetische interne taal van het categorische model. Ze erkennen dat slotted e-grafen flexibeler kunnen zijn voor willekeurige talen met binders (zoals de $\pi$ -calculus), maar beargumenteren dat hun methode superieur is voor $\lambda$ -calculus specifieke optimalisaties.

Het werk presenteert geen volledige software-implementatie of empirische benchmarks in dit artikel, maar positioneert de closed e-hypergraph representatie als een levensvatbaar fundament voor het bouwen van "e-grafen voor string diagram herschrijven" in toekomstig werk.