# E-Graph implementation using prolog variables

**URL:** <https://swi-prolog.discourse.group/t/e-graph-implementation-using-prolog-variables/9264>\
**Category:** General\
**Created:** [September 9, 2025, 8:06pm UTC](https://swi-prolog.discourse.group/t/e-graph-implementation-using-prolog-variables/9264 "2025-09-09T20:06:19Z")\
**Posts on this page:** 1\
**Showing post:** 4

<div class="post-metadata">

**Author:** ![kwon-young](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/kwon-young/32/4841_2.png) [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)\
**Post date:** [September 14, 2025, 12:05pm UTC](https://swi-prolog.discourse.group/t/e-graph-implementation-using-prolog-variables/9264/4 "2025-09-14T12:05:29Z")

</div>

> [@philzook58](#):
>
> Have you seen this one? [Unification Modulo E-Graphs | Hey There Buddo!](https://www.philipzucker.com/unify_mod_egraphs/)

No, I haven’t read that blog post and the idea is amazing (although I haven’t took the time to read the python code much).  
In a [previous post of mine](https://swi-prolog.discourse.group/t/extending-unification-2/8930), I thought about extending syntactical unification, but nobody brought egraph to the discussion.

So currently, the implementation treats variables like any other term.  
But one could first saturate the egraph of a term, extract and check for syntactical unification:

```prolog
?- phrase((
     add_term(X+a, Xa),
     add_term(a+b, AB),
     saturate([comm]),
     extract), [], G),
   unifiable(Xa, AB, Unifs).
Xa = X+a,
AB = b+a,
G = [X-node(X, 1), a-node(a, 1), b-node(b, 1), ...],
Unifs = [X=b] ;
Xa = a+X,
AB = a+b,
G = [X-node(X, 1), a-node(a, 1), b-node(b, 1), ...],
Unifs = [X=b] ;
false.

```

But I suppose this is very, very inefficient.  
I would guess a more efficient unification strategy would be to traverse the egraph classes directly without doing any extraction ?

I also don’t really understand where would constraints came into play here ?  
Could you help me understand with a simple example ?

---

_[View the full topic](https://swi-prolog.discourse.group/t/e-graph-implementation-using-prolog-variables/9264)._