ERROR: [14] call_dcg(esimplify:(...,...),[],_1070) at /Applications/SWI-Prolog10.1.3.app/Contents/Resources/swipl/boot/dcg.pl:368
ERROR: [13] phrase(esimplify:(...,...),[],_1110) at /Applications/SWI-Prolog10.1.3.app/Contents/Resources/swipl/boot/dcg.pl:360
ERROR: [12] esimplify:esimplify(_1158+0,_1154) at /Users/rickworkman/Documents/Prolog/egraph_tst/esimplify.pl:6
ERROR: [11] toplevel_call(user:user: ...) at /Applications/SWI-Prolog10.1.3.app/Contents/Resources/swipl/boot/toplevel.pl:1520
```
Did I miss something for this use case?
---
### Author:  [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)
#### Post date: [April 16, 2026, 4:15pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/4 "2026-04-16T16:15:40Z")
Ah, the rules are expanded in the module they are defined, in your case `esimplify`.
I can now see how this could be counterintuitive with the `egraph` module qualification of rewrite…
This was done to restrict where rewrite term would be expanded.
So the quick fix is to module qualify the rules in saturate.
Does anyone know of a better solution ?
---
### Author:  [@ridgeworks](https://swi-prolog.discourse.group/u/ridgeworks)
#### Post date: [April 16, 2026, 5:10pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/5 "2026-04-16T17:10:31Z")
Yes, that fixed the exception. Now:
```prolog
147 ?- esimplify(A+0,S).
S = _S1, % where
_S1 = _S1+_S2,
_S2 = 2*_S2 ;
S = _S1, % where
_S1 = _S1+_S2,
_S2 = _S2+_S2 ;
S = S+0 ;
S = _S2, % where
_S1 = 2*_S1,
_S2 = _S1+_S2 ;
S = _S2, % where
_S1 = _S1+_S1,
_S2 = _S1+_S2 ;
S = 0+S ;
A = S ;
A = S ;
A = S ;
false.
```
Is this the expected result? The desired answer (`A = S`) is there but why all the others? Should I expect this to be deterministic with “best” answer, or is some additional filtering required?
---
### Author:  [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)
#### Post date: [April 16, 2026, 6:51pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/6 "2026-04-16T18:51:12Z")
> [@ridgeworks](#):
>
> Is this the expected result? The desired answer (`A = S`) is there but why all the others?
Yes, unfortunately…
e-graph can produce highly cyclical terms.
Given that the extract is driven by a structural cost, the extraction code have a hard time prioritizing non cyclical term vs cyclical term.
edit: after thinking more about this, the pb is that I extract structural cost through clpr and cyclical term produces cyclical cost, which are never resolved.
Then, when sorting by cost, variables are actually sorted before numbers, so extract will produce all cyclical terms first !
Definitely not what I wanted, I’ll try to fix it quickly.
> [@ridgeworks](#):
>
> Should I expect this to be deterministic with “best” answer, or is some additional filtering required?
No, `extract` is fully non-deterministic and will produce all possible variation of a term given the rewrite rules.
Fortunately, we can easily filter solutions in prolog, so something like this:
```prolog
% if you want the first non-cyclical solution
?- once((esimplify(a+0, S), \+ cyclic_term(S))).
S = a.
% if you want to explore the set of non-cyclical solution
?- distinct((esimplify(a+0, S), \+ cyclic_term(S))).
S = a ;
false.
```
---
### Author:  [@ridgeworks](https://swi-prolog.discourse.group/u/ridgeworks)
#### Post date: [April 16, 2026, 8:33pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/7 "2026-04-16T20:33:35Z")
In the context of term rewriting, is it ever desirable to produce cyclic terms? (Or are they just an artifact of the implementation?) If yes, is the answer the same if the input term is not cyclic?
For my use case, I’m pretty sure cyclic solutions can be eliminated so I’ll build that into `esimplify/2`. That leaves me with non-determinism. As per your suggestion, for now I’ll use `library(solution_sequences):distinct`, also built-in to `esimplify`. Now:
```prolog
?- esimplify(A+0,S).
A = S ;
false.
?- esimplify(0+A,S).
A = S ;
false.
```
OK, but:
```prolog
?- esimplify(A+B,S).
S = A+B ;
S = B+A ;
false.
?- esimplify(A+0+A,S).
S = 2*A ;
S = A+A ;
false.
?- esimplify(A+B+A,S).
S = B+2*A ;
S = B+(A+A) ;
S = 2*A+B ;
S = A+A+B ;
S = A+B+A ;
S = B+A+A ;
S = A+(A+B) ;
S = A+(B+A) ;
false.
```
So this still leaves the additional job of selecting one from the several distinct solutions, and some are definitely better than others for my particular application. Perhaps the situation can be improved with a more selective set of rules, or perhaps by exploring the `cost` option.
I also did a simple performance measurement to compare this with my current, rather simple minded, expression simplification library:
```prolog
% fail to generate all solutions for picking the best
?- time((esimplify(A+0+A,S),fail)).
% 6,805 inferences, 0.002 CPU in 0.003 seconds (54% CPU, 4200617 Lips)
false.
?- time((esimplify(A+B+A,S),fail)).
% 8,564 inferences, 0.003 CPU in 0.003 seconds (88% CPU, 2793216 Lips)
false.
% using library in pack clpBNR
?- time(simplify_constraint:simplify(A+0+A,S)).
% 157 inferences, 0.000 CPU in 0.000 seconds (27% CPU, 1427273 Lips)
S = 2*A.
?- time(simplify_constraint:simplify(A+B+A,S)).
% 249 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 3557143 Lips)
S = 2*A+B.
```
I admit this is comparing apples to oranges, but it illustrates the performance gap to overcome in replacing the current, customized expression rewriting system in `clpBNR`.
---
### Author:  [@jan](https://swi-prolog.discourse.group/u/jan)
#### Post date: [April 17, 2026, 7:25am UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/8 "2026-04-17T07:25:51Z")
> [@kwon-young](#):
>
> @jan I can’t see my egraph package anymore on [SWI-Prolog packages](https://www.swi-prolog.org/pack/list) ?
Somehow the US mirror did not sync and thus the visibility depends on the backend chosen by the CDN. Synced the mirror by hand, but I think something is wrong there ☹
---
### Author:  [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)
#### Post date: [April 17, 2026, 3:48pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/10 "2026-04-17T15:48:55Z")
> [@ridgeworks](#):
>
> In the context of term rewriting, is it ever desirable to produce cyclic terms?
It seems not.
I didn’t put enough effort on the extraction part of the library.
Writing the rule compiler seemed already like such a feat that I wanted to share it with others.
Given your feedback, improving extraction is going to be my next focus for improving this library.
> [@ridgeworks](#):
>
> So this still leaves the additional job of selecting one from the several distinct solutions, and some are definitely better than others for my particular application.
The whole point of tracking the cost per node is to prioritize which will be the first extracted term (which is currently kind of bugged because of cyclical term).
If the first solution is correct for your need, you would just need to extract the first solution with `once/1`.
I don’t really have a reason for `extract` to be non-deterministic. Moreover, it seems like other egraph libraries have dedicated min cost extraction primitives.
> [@ridgeworks](#):
>
> I admit this is comparing apples to oranges,
Even if we compare only extracting the first solution for egraph, egraph is still like 10x to 100x slower than your `simplify` solution in clpBNR.
I think I can still optimize extraction a lot, which should reduce the overhead of using egraph a lot.
On the other hand, egraph can do things that your `simplify` implementation cannot (I think ?):
```prolog
% adding these rules
egraph:rewrite(factorize_aba, A+B*A, A*(B+1), [cost(9r10)]).
egraph:rewrite(distribute, A*(B+C), A*B+A*C).
egraph:rewrite(cancel_add_sub, A+B-A, B).
```
```prolog
?- time(once(esimplify(A+B*A,S))).
% 9,097 inferences, 0.003 CPU in 0.003 seconds (99% CPU, 3173606 Lips)
S = A*(B+1).
?- time(clpBNR:simplify(A+B*A,S)).
% 81 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 1249730 Lips)
S = B*A+A.
?- time(clpBNR:simplify(A*(X+Y) - A*X,S)).
% 201 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 1733177 Lips)
S = A*(Y+X)-X*A.
?- time(esimplify(A*(X+Y) - A*X,S)).
% 7,329 inferences, 0.002 CPU in 0.003 seconds (94% CPU, 2948093 Lips)
S = A*(X+Y)-A*X ;
% 37 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 980210 Lips)
S = A*(Y+X)-A*X ;
% 65 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 1797020 Lips)
S = A*Y ; % extraction is bugged in this case, should be first
```
---
### Author:  [@ridgeworks](https://swi-prolog.discourse.group/u/ridgeworks)
#### Post date: [April 17, 2026, 6:09pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/11 "2026-04-17T18:09:54Z")
> [@kwon-young](#):
>
> If the first solution is correct for your need, you would just need to extract the first solution with `once/1`.
> I don’t really have a reason for `extract` to be non-deterministic. Moreover, it seems like other egraph libraries have dedicated min cost extraction primitives.
I suspect there is a case to be made for the cost function to be user definable. For my purposes I defined the cost of an expression to be the sum of the number of operators and variable occurrences in the expression, but that probably doesn’t fit all use cases.
I then collect all the solutions (using `bagof`), and then select the one in the list with the lowest cost:
```prolog
esimplify(Exp,SExp) :-
bagof(S,esimplify_(Exp,S),Ss), % collect all solutions
ecost(Exp,Cin), % cost of input expression
mincost(Ss,Cin,Exp,SExp). % select lowest cost alternative
esimplify_(Exp,SExp) :-
phrase((
add_term(Exp, SExp),
saturate([
esimplify:comm_add,
esimplify:assoc_add,
esimplify:factorize_aa,
esimplify:reduce_add0,
esimplify:constant_folding
]),
extract
), [], _Graph),
acyclic_term(SExp).
```
Seems to do what I want for these simple tests:
```prolog
?- esimplify(A+0+A,S).
S = 2*A.
?- esimplify(B+0+A,S).
S = B+A.
```
So the fact that `extract` is nondeterministic works in my favour for this use case. But it comes at the expense of generating all solutions then testing them. But maybe there’s something useful in this prototype that can be pushed back into egraph to improve overall performance or usability.
> [@kwon-young](#):
>
> I think I can still optimize extraction a lot, which should reduce the overhead of using egraph a lot.
>
> On the other hand, egraph can do things that your `simplify` implementation cannot (I think ?):
Almost certainly. the `clpBNR simplify` is really only looking at the low-hanging fruit to generate a hopefully simpler expression with the proviso that it has to be quick since pretty much every added constraint is simplified. It’s primarily useful for machine generated code, e.g., the result of a symbolic partial differentiation. I would think that `egraph` could be used to find an optimal equivalent of any expression, however optimal is defined. (The clpBNR version also has some special requirements, e.g., no floating point arithmetic, and `0*X` can’t be reduced in cases where the domain of `X` can include infinity.)
Now that I have the basics running it would be interesting to expand my set of egraph rules to cover what the `clpBNR` simplify does to better understand the gap between it and “optimal” (as defined by the egraph version).
---
### Author:  [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)
#### Post date: [April 18, 2026, 7:46pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/12 "2026-04-18T19:46:14Z")
I have published a new version of this pack (v0.3.0) with the following fixes:
- compile the list of rules given to `saturate` on-the-fly to avoid meta `call` and recursion during matching. I can see performance improvement when doing small term saturation over and over again with a lot of rules. This also fixes the need to module qualify rules.
- complete rewrite of `extract` based on dijkstra min-cost computation. `extract` is now deterministic and always extract the minimal cost representation of a rewritten term.
- it also avoids naturally any cyclic terms
- WARNING: the interfaced `extract` has changed
here is the new way of using extract:
```prolog
?- use_module(library(egraph)).
true.
?- phrase((
add_term(a+0, Id),
saturate([reduce_add0]),
extract(Id, Optimized)
), [], _Graph).
Optimized = a,
```
Unfortunately, the use of dijkstra didn’t improve the overhead of using egraph, but at least `extract` is not correct.
it is still much much slower than `clpBNR:simplify` for example.
> [@ridgeworks](#):
>
> I suspect there is a case to be made for the cost function to be user definable. For my purposes I defined the cost of an expression to be the sum of the number of operators and variable occurrences in the expression, but that probably doesn’t fit all use cases.
Yes, for sure.
I think that your use-case could be cleanly integrated into the current cost mechanism in egraph.
I think you would only need to override the cost for constants to be 0.
Maybe I could add a user definable hook in add\_term to override the default cost assignement ?
or you could do a fake `rewrite(A, [const(A, Const)], A, [cost(0)]).` but that would be a very bad performance wise ?
> [@ridgeworks](#):
>
> I would think that `egraph` could be used to find an optimal equivalent of any expression, however optimal is defined.
Yes, maybe there could be some instances where you don’t need to be quick but would prefer more optimized expressions ?
For example, when calling a labelling predicate like `global_minimum` or `enumerate`, you could optimize once before doing the actual labelling ?
or maybe provide an `optimize_constraints` predicate that the user could manually call, that will reevaluate all the constraints after an egraph optimization ?
> [@ridgeworks](#):
>
> (The clpBNR version also has some special requirements, e.g., no floating point arithmetic, and `0*X` can’t be reduced in cases where the domain of `X` can include infinity.)
so, currently, the left hand side options in the rewrite rules only includes `const(A, B)` terms.
However, I could let the user put any kind of guard code in there.
Meaning you could do a `[const(A, B), \+ float(B)]` to avoid matching any floats.
Or `[domain(X, real(Min, Max)), Min =\= -inf, Max =\= inf]`.
But that would mean trusting the user with providing correct guards for SSU rules.
I would be very interested to implement any features that would allow you to express cleanly any requirements for clpBNR.
Please list them and I will try to implement each of them.
---
### Author:  [@ridgeworks](https://swi-prolog.discourse.group/u/ridgeworks)
#### Post date: [April 19, 2026, 2:51pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/14 "2026-04-19T14:51:10Z")
> [@kwon-young](#):
>
> I have published a new version of this pack (v0.3.0) with the following fixes:
That seems to address the major reasons for writing additional user code to filter the results of the previous non-deterministic version. But I don’t really understand the operational semantics of the various forms of rewrite rules. As a simple example I tried to write a set pf rules to simplify expressions using only the add operation, e.g.,
```prolog
A ==> A
A = 0 ==> A
A + A ==> 2*A
A + A + A ==> 3*A
A + A + A + A ==> 4*A
A + 0 + A ==> 2*A
A + B + A ==> 2*A+B
A + B + A + B ==> 2*(A+B)
...
```
My attempt at a set of rules for this:
```prolog
egraph:rewrite(comm_add, A+B, B+A).
egraph:rewrite(assoc_add, A+(B+C), (A+B)+C).
egraph:rewrite(factorize_add, A+A, 2*A).
egraph:rewrite(reduce_add0, A+B, [const(B, 0)], A, []).
egraph:rewrite(factor_add1, N*A+A, (N+1)*A).
egraph:rewrite(factor_add, N1*A+N2*A, (N1+N2)*A).
egraph:rewrite(constant_folding_add, A+B, [const(A, VA), const(B, VB)], VC, [const(VC)]) :-
VC is VA + VB.
```
but I couldn’t get anything useful. The two typical results were no simplification or stack limit exceeded (1.0 GB) so I’m clearly not understanding something.
> [@kwon-young](#):
>
> Yes, maybe there could be some instances where you don’t need to be quick but would prefer more optimized expressions ?
> For example, when calling a labelling predicate like `global_minimum` or `enumerate`, you could optimize once before doing the actual labelling ?
> or maybe provide an `optimize_constraints` predicate that the user could manually call, that will reevaluate all the constraints after an egraph optimization ?
I would leave this decision up to the user, i.e., pre-optimize any expressions before adding a constraint via `{..}` if that’s useful for the problem at hand. I don’t see any merit in trying to optimize anything after the constraints have been defined.
> [@kwon-young](#):
>
> But that would mean trusting the user with providing correct guards for SSU rules.
Don’t follow but then, as I said, I don’t really understand the operational semantics of this pack’s rewrite rules. At least one form of the rewrite rule has a body; why not put this code there? How does SSU impact how the user writes these rules? Shouldn’t they be largely declarative?
```prolog
rewrite(RuleName,From,To,Cost) :- Body. % rewrite From to To with cost Cost
```
---
### Author:  [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)
#### Post date: [April 20, 2026, 8:23am UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/16 "2026-04-20T08:23:34Z")
> [@ridgeworks](#):
>
> but I couldn’t get anything useful. The two typical results were no simplification or stack limit exceeded (1.0 GB) so I’m clearly not understanding something.
So, I have worked on your examples here: [egraph/examples/test\_clpBNR.pl at d99b1a2db171588530c4262752e2e1c416979d60 · kwon-young/egraph · GitHub](https://github.com/kwon-young/egraph/blob/d99b1a2db171588530c4262752e2e1c416979d60/examples/test_clpBNR.pl)
There was 2 bugs in the rule compiler that I have now fixed. Thank you !
I have published a v0.4.0 that fixes this.
The reason that some rewrites are not terminating is not a bug but the fact that combining reduction rules with commutativty/associativity/factorize rewrite rules produces an exploding system of rules that generates new eclasses infinitely.
The basic solution is to stratify the saturation by first doing comm/assoc/factorize and then do the reduction after as is done here: [egraph/examples/test\_clpBNR.pl at d99b1a2db171588530c4262752e2e1c416979d60 · kwon-young/egraph · GitHub](https://github.com/kwon-young/egraph/blob/d99b1a2db171588530c4262752e2e1c416979d60/examples/test_clpBNR.pl#L49-L50)
what @anon37422618 has written is relevant in the sense that if you are very careful with how you specify your rewrite rules, you can actually prove termination through the Knuth Bendix algorithm.
This puts a lot of restriction on the rewrite rules one can specify (for example, associativity A+B =\> B+A is not allowed), so much so that I have always found Knuth Bendix to be kind of useless.
> [@ridgeworks](#):
>
> Don’t follow but then, as I said, I don’t really understand the operational semantics of this pack’s rewrite rules. At least one form of the rewrite rule has a body; why not put this code there? How does SSU impact how the user writes these rules? Shouldn’t they be largely declarative?
So, the separation of the guard code and body code is largely to ease the compilation of the rules.
In theory, I could put the whole Body inside the guard of the compiled SSU predicate, but that is hard for practical “reasons”.
Basically, rewrite rules are compiled into a nested calls of SSU predicates, where each nested call checks a single node in the left hand side pattern.
Now that I have the addition tests working, would you mind listing other type of rewrite rules needed for clpBNR ?
---
### Author:  [@ridgeworks](https://swi-prolog.discourse.group/u/ridgeworks)
#### Post date: [April 20, 2026, 7:33pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/18 "2026-04-20T19:33:25Z")
> [@kwon-young](#):
>
> So, I have worked on your examples here: [egraph/examples/test\_clpBNR.pl at d99b1a2db171588530c4262752e2e1c416979d60 · kwon-young/egraph · GitHub](https://github.com/kwon-young/egraph/blob/d99b1a2db171588530c4262752e2e1c416979d60/examples/test_clpBNR.pl)
But you found a need to modify my rule set, so some questions:
```prolog
% Factoring terms with constant multipliers
egraph:rewrite(factorize_naa, N*A+A, [const(N, VN)], M*A, [const(M)]) :-
M is VN + 1.
egraph:rewrite(factorize_ana, A+N*A, [const(N, VN)], M*A, [const(M)]) :-
M is VN + 1.
```
This is an example of what I mean about my lack of understanding of the operational semantics. Why do I need two rules? Isn’t the second achieved by applying the `comm_add`? I.e., `A+N*A` is equivalent to `N*A+A` by `comm_add` which is then reduced to `M*A` via `factorize_naa`.
Also note that my intent was to handle any `N` in the rule, i.e., the rewrite result is `(N+1)*A` (`N` needn’t be a constant). Now if `N` was a constant, `N+1` would be reduced to a single constant using the constant folding rule (`constant_folding_add` in my rule set).
> [@kwon-young](#):
>
> The reason that some rewrites are not terminating is not a bug but the fact that combining reduction rules with commutativty/associativity/factorize rewrite rules produces an exploding system of rules that generates new eclasses infinitely.
Well, that’s a problem!
> [@kwon-young](#):
>
> The basic solution is to stratify the saturation by first doing comm/assoc/factorize and then do the reduction after as is done here:
That doesn’t seem very satisfactory. How would you describe the properties of the rules such that you can divide them into the two required sets? Could this be done inside `egraph`?
> [@kwon-young](#):
>
> So, the separation of the guard code and body code is largely to ease the compilation of the rules.
> In theory, I could put the whole Body inside the guard of the compiled SSU predicate, but that is hard for practical “reasons”.
> Basically, rewrite rules are compiled into a nested calls of SSU predicates, where each nested call checks a single node in the left hand side pattern.
I’m wondering why this should be of concern to a user. Can’t this level of detail be abstracted away?
> [@kwon-young](#):
>
> Now that I have the addition tests working, would you mind listing other type of rewrite rules needed for clpBNR ?
clpBNR doesn’t “need” any rewrite rules. It has a builtin quick (and dirty) constraint simplification function which could be implemented with a general purpose rewriting system given adequate performance. While I’m not currently contemplating this, the requirements for such a system have largely been discussed:
- arbitrary code in the body a) to filter the input expression (type checks or things that can’t be done with only using unification) , and b) to call helper predicates provided by the system (e.g., `is`) or user.
- the ability to customize the selection of the result through the `cost` option or some other mechanism. (I’m not sure what the current default criteria is or how the `cost` option can be used to modify its behaviour.)
But also, and more importantly for the general user, a rewriting system that’s understandable and easy to use.
In addition, I think there’s a need to provide some tools or guidance as to how to “debug” the rewrite rules. The rules themselves seem to transformed in the compilation process, so it’s difficult to discern root causes when an unexpected result is produced.
---
### Author:  [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)
#### Post date: [April 21, 2026, 6:40am UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/19 "2026-04-21T06:40:41Z")
> [@ridgeworks](#):
>
> This is an example of what I mean about my lack of understanding of the operational semantics. Why do I need two rules? Isn’t the second achieved by applying the `comm_add`? I.e., `A+N*A` is equivalent to `N*A+A` by `comm_add` which is then reduced to `M*A` via `factorize_naa`.
>
> Also note that my intent was to handle any `N` in the rule, i.e., the rewrite result is `(N+1)*A` (`N` needn’t be a constant). Now if `N` was a constant, `N+1` would be reduced to a single constant using the constant folding rule (`constant_folding_add` in my rule set).
Sorry, you are right about all this.
I have corrected the rules exactly as you provided them: [egraph/examples/test\_clpBNR.pl at f362c3b883386cb2e7f5a1b7a10844bfb2f26971 · kwon-young/egraph · GitHub](https://github.com/kwon-young/egraph/blob/f362c3b883386cb2e7f5a1b7a10844bfb2f26971/examples/test_clpBNR.pl#L6-L23)
The only modification I did was to add a custom cost to the `factor_add1` rule:
```prolog
egraph:rewrite(factor_add1, N*A+A, (N+1)*A, [cost(9r10)]).
```
Because `N*A+A` has the same structural cost as `(N+1)*A`, we lower the cost of the node `(N+1)*A` to prioritize it during extraction.
> [@ridgeworks](#):
>
> That doesn’t seem very satisfactory. How would you describe the properties of the rules such that you can divide them into the two required sets? Could this be done inside `egraph`?
Well, as said before, one could try to use knuth bendix algorithm to prove that a set of rewrite rules terminates, but that puts so much constraints on which rules you can write, I find it quite useless.
Egraphs (in general) are better than naive term rewriting system because they can natively represent cycles, so rules like commutativity doesn’t lead to non-terminating saturation.
But it is still possible (and very easy) to write a set of rewrite rules that doesn’t terminate, as we have seen here.
And it is kind of impossible to automatically prove non-termination (this is like the halting pb).
Note that `saturate` has a 2 arguments version where you can specify a maximum number of iterations. this will bound your saturation budget and stop eventually even if the rule set is non-terminating.
> [@ridgeworks](#):
>
> I’m wondering why this should be of concern to a user. Can’t this level of detail be abstracted away?
Yes of course, I’m just saying that writing the rule compiler pushed my brain to my limits…
I’ll try but can’t promise anything.
> [@ridgeworks](#):
>
> clpBNR doesn’t “need” any rewrite rules. It has a builtin quick (and dirty) constraint simplification function which could be implemented with a general purpose rewriting system given adequate performance.
Just to be clear, I don’t want clpBNR to integrate egraph or anything.
I am just asking for potential use-case for my egraph library that I can try.
As seen above, this leads to bugfixes and actual improvement of the library.
I am really thankful for you to take the time and try my libraries idea ^^
> [@ridgeworks](#):
>
> arbitrary code in the body a) to filter the input expression (type checks or things that can’t be done with only using unification)
I agree, I’ll see what I can do.
> [@ridgeworks](#):
>
> b) to call helper predicates provided by the system (e.g., `is`) or user.
Note that you can already do this in the body of the rule, like what is used in the constant\_folding rewrite rule.
But the body of a rule currently need to be deterministic.
> [@ridgeworks](#):
>
> the ability to customize the selection of the result through the `cost` option or some other mechanism. (I’m not sure what the current default criteria is or how the `cost` option can be used to modify its behaviour.)
You can already do that.
Each node in the egraph has a default cost of 1.
when computing the total cost of a compound node for extraction, I sum the cost of each arg + the cost of the compound node.
so, by altering the cost of a rewritten term, you can influence its priority for extraction like what is done in the factorize rules.
> [@ridgeworks](#):
>
> In addition, I think there’s a need to provide some tools or guidance as to how to “debug” the rewrite rules. The rules themselves seem to transformed in the compilation process, so it’s difficult to discern root causes when an unexpected result is produced.
Yes, I do feel that need too.
I have tried adding [a debug topic](https://github.com/kwon-young/egraph/blob/f362c3b883386cb2e7f5a1b7a10844bfb2f26971/examples/test_clpBNR.pl#L4C1-L4C26) which you can use as a directive, which will print the results of expanding rewrite rules.
The problem is that if you don’t know how rewrite rules works under the hood, you won’t understand a thing.
But I have had some success in feeding the whole debug output to LLM and it can manage to pinpoint bugs very accurately.
I’ll try to add a section in the README about this.
> [@ridgeworks](#):
>
> But also, and more importantly for the general user, a rewriting system that’s understandable and easy to use.
Yes, of course. Because I spent so much time with the implementation, I don’t really know what will trip up new user when trying the library for the first time.
That’s why I am asking for feedback on this forum 🙂
---
### Author:  [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)
#### Post date: [April 21, 2026, 11:21am UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/20 "2026-04-21T11:21:24Z")
> [@ridgeworks](#):
>
> Don’t follow but then, as I said, I don’t really understand the operational semantics of this pack’s rewrite rules. At least one form of the rewrite rule has a body; why not put this code there? How does SSU impact how the user writes these rules? Shouldn’t they be largely declarative?
>
> ```prolog
> rewrite(RuleName,From,To,Cost) :- Body. % rewrite From to To with cost Cost
>
> ```
I would also like to take some time to explain why egraph rewrite rules can’t be express exactly like this.
For example, with egraphs, you can’t do something like:
```prolog
rewrite(constant_folding, A+B, C, 1) :-
number(A), number(B),
C is A+B.
```
The reason for this is because egraph represent a term by flattening it into a list of nodes.
For example, `0+1` is flattened into a list of nodes: `[(A+B)-AB, A-0, B-1]`.
Similarly, when compiling a rewrite rule, the left hand side pattern is flattened into a list of nodes that needs to be found in the egraph:
For example, `0+D` is flattened into `[(C+D)-CD, C-0]` and then each pair is checked for membership in the list of nodes:
- `(C+D)-CD` matches `(A+B)-AB`
- `C-0` matches `A-0`
Note that C is never actually unified with 0 here, but that we checked that a node inside a eclass C has the literal 0.
The implication is that when doing:
```prolog
rewrite(constant_folding, A+B, C, 1) :-
number(A), number(B), % this won't work as A and B are eclass id variables
C is A+B.
```
A and B are not numbers but eclass id variables.
The workaround that egraph libraries provides is to attach custom properties to eclass ids.
In our case, since eclass ids are variables, I use attributed variables to store properties like `put_attr(A, const, 0)` when parsing the term in `add_term` and then when using `const(A, VA)` in rewrite rules, it is translated as `get_attr(A, const, VA)`.
In the end, I would like to make the library modular so that users can define any custom properties on eclass ids.
@ridgeworks Does this help you understand better the operational semantic of an egraph rewrite rules ? Or in other words, why I need to separate guard code operating on eclass ids and the body of the rule ?
---
### Author:  [@ridgeworks](https://swi-prolog.discourse.group/u/ridgeworks)
#### Post date: [April 21, 2026, 4:21pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/21 "2026-04-21T16:21:08Z")
> [@kwon-young](#):
>
> The only modification I did was to add a custom cost to the `factor_add1` rule:
With this modification, all the simple test cases listed work as advertised.
But I’m not sure why you thought it was necessary to add the cost option. It doesn’t seem to make any difference for these tests anyway. As a test, I removed all the "costs"s and it doesn’t seem to make any difference for this small use case. So is this just an optimization mechanism/strategy?
However, by separating out the `reduce-add0`, the following now seems to overflow the stack:
```prolog
?- esimplify(A+0+1,S).
ERROR: Stack limit (1.0Gb) exceeded
ERROR: Stack sizes: local: 3Kb, global: 0.9Gb, trail: 22.9Mb
ERROR: Stack depth: 5,705, last-call: 100%, Choice points: 4
ERROR: In:
ERROR: [5,705] esimplify:factor_add ____ (, _230034490, , , , [length:1|_230034534], _230034500, [length:1|_230034540], _230034504)
ERROR: [5,704] esimplify:factor_add___([length:1,363], _230034560, , , ,
```
but this works:
```prolog
?- esimplify(A+1+1,S).
S = A+2.
?- esimplify(A+1+1+A,S).
S = 2*(A+1).
?- esimplify(A+1+2+A,S).
S = 2*A+3.
```
> [@kwon-young](#):
>
> You can already do that.
> Each node in the egraph has a default cost of 1.
So “node” and “egraph” are still little understood concepts to me so I’ll have to spend some time with your subsequent post to see if something clicks. Again, do costs matter from a semantic perspective or are they just a priority mechanism for optimization?
From the user perspective, things that are variables on input and are output as variables (after `extract`?) aren’t just variables as seen from the rewrite rule bodies executed during the rewrite process (`saturate`?).
---
### Author:  [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)
#### Post date: [April 21, 2026, 8:21pm UTC](https://swi-prolog.discourse.group/t/new-egraph-pack-v0-1-0-annoucement-for-term-rewriting/9572/22 "2026-04-21T20:21:38Z")
> [@ridgeworks](#):
>
> But I’m not sure why you thought it was necessary to add the cost option. It doesn’t seem to make any difference for these tests anyway. As a test, I removed all the "costs"s and it doesn’t seem to make any difference for this small use case. So is this just an optimization mechanism/strategy?
Yes, in this case, it doesn’t really impact your examples since the custom costs are applied to intermediate nodes that are further simplified.
For example, `(2+1)*A` would extract first compared to `2*A+A` but we then apply constant folding `3*A` which is smaller than both anyway.
For `A+A => 2*A`, it is rather a coincidence that `2*A` extracts before `A+A` without a custom cost.
> [@ridgeworks](#):
>
> However, by separating out the `reduce-add0`, the following now seems to overflow the stack:
>
> `?- esimplify(A+0+1,S).`
So, in this case, constant folding acts in the same way as reduce\_add0: `0+1 => 1` which creates a cycle and explodes the saturation.
The solution is the same as for before, separate factorization from constant folding and do it in a second step together with reduce\_add0.
> [@ridgeworks](#):
>
> Again, do costs matter from a semantic perspective or are they just a priority mechanism for optimization?
Costs are used to prioritize which nodes will extract first.
It is not a performance optimization mechanism.
> [@ridgeworks](#):
>
> From the user perspective, things that are variables on input and are output as variables (after `extract`?) aren’t just variables as seen from the rewrite rule bodies executed during the rewrite process (`saturate`?).
Exactly. Variables in rewrite patterns are eclass ids.
If you want to match literal prolog variables (as given in an input term), you have to use the special quoting `'$VAR'(Var)` as shown in this rewrite rule example: [egraph/examples/compiled\_rules.pl at f362c3b883386cb2e7f5a1b7a10844bfb2f26971 · kwon-young/egraph · GitHub](https://github.com/kwon-young/egraph/blob/f362c3b883386cb2e7f5a1b7a10844bfb2f26971/examples/compiled_rules.pl#L22)