# Instability of standard order

**URL:** <https://swi-prolog.discourse.group/t/instability-of-standard-order/9830>\
**Category:** Request For Comments\
**Created:** [September 21, 2026, 2:31pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830 "2026-09-21T14:31:09Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [September 21, 2026, 2:31pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/1 "2026-09-21T14:31:09Z")

</div>

The discussion has been here before: standard order of terms is complete (except cyclic terms ☹ ), but unstable, i.e.,

```
X @< a, X = b

```

succeeds, but `a @< b` rather than `a @> b`. I wonder whether we should have a variant of compare/3 that fixes this. I see two sensible behaviours: a compare/3 variant that raises an instantiation exception and one that tells us which comparison decides. The implementation of compare/3 at some point stumbles on a variable. That means we cannot decide (unless the other side is the same variable, e.g., X==X). We can return a pair indicating the undecidable comparison, so we get

```
?- compare_ex(Diff, f(a), f(X)).
Diff = compare(a, X)

```

The sad thing is that `instantiation_error` has no culprit. Else, we could also consider

```
?- catch(compare_ex(Diff, f(a), f(X)), E, true).
E = error(instantiation_error(compare(a,X), _).

```

I know we can use the second argument. That is nice for a message, but not for something you want to act upon. Of course, the disadvantage is that normal computation may need to use catch/3, something I’ve never liked.

Opinions? Existing practice?

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [September 21, 2026, 4:00pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/2 "2026-09-21T16:00:03Z")

</div>

I found compare/3 to be [disappointingly illogical](https://swi-prolog.discourse.group/t/how-to-compare-3-without-surprises-on-non-ground-terms/6386) as a learner 😀

Exceptions are a last resort, for when there are no other reasonable actions… how about, for a point-in-time comparison:

```prolog
compare_sound(C, X, Y) :-
    ( X \= Y
    -> compare(S, X, Y),
        % Will be < or > sign
        C = comp(S)
    ; X == Y
    -> C = comp(=)
        % Insufficiently instantiated for sound comparison
    ; C = insuf
    ).

```

Results:

```prolog
?- compare_sound(C, A, A).
C = comp(=).

?- compare_sound(C, b(_), a(_)).
C = comp(>).

?- compare_sound(C, A, B).
C = insuf.

```

I think these results would be the [least surprising](https://principles-wiki.net/principles:principle_of_least_surprise) for a learner.

---

<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 21, 2026, 6:38pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/3 "2026-09-21T18:38:59Z")

</div>

hm, I heavily rely on being able to compare 2 variables and ground terms with variables in my egraph implementations.  
In my case, the current status quo is okay I found…

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [September 21, 2026, 6:39pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/4 "2026-09-21T18:39:10Z")

</div>

> [@brebs](#):
>
> ```prolog
> compare_sound(C, X, Y) :-
> ( X \= Y
> -> compare(S, X, Y),
> 
> ```

I thought about this as well. It is not correct. consider `compare(D, f(X, a), f(x, b))`. These do not unify, but their comparison is unstable. The current working hypothesis is to introduce

```
 partial_compare(?Dif, @T1, @T2)

```

Which will unify Dif with one of \>, =. \< or `undefined(X,Y)`, which expresses that we can not decide, but Dif is the same as compare(X,Y) _when_ we can compare. Related, there is a proposal for

```
must_compare(Dif, T1, T2)

```

which raises an instantiation\_error if the above returns undefined(_,_). Finally,

```
compare_when(Dif, T1, T2)

```

Which could act as a constraint, i.e., delays if we cannot decide now.

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [September 22, 2026, 7:13am UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/5 "2026-09-22T07:13:44Z")

</div>

> [@jan](#):
>
> their comparison is unstable

How about this idea - work in progress:

```prolog
compare_sound(C, X, Y) :-
	compare(Comp, X, Y),
	(	Comp == (=)
        % Trustworthy equality
	->	C = Comp
	;	ground(X),
		ground(Y)
        % Trustworthy comparison
	->	C = Comp
	;	X \= Y,
		% Prevent attributed variables from interfering with later comparison
		copy_term(X, XC, _),
		copy_term(Y, YC, _),
		var_to_simple_list(XC, XL),
		var_to_simple_list(YC, YL),
		walk_vars_to_first_term_variable(XL, YL, FTV),
		(	first_term_variable_does_not_change_comparison(Comp, XC, YC, FTV)
		->	C = Comp
		;	C = insuf
		)
	;	C = insuf
    ).

walk_vars_to_first_term_variable(XL, YL, FTV) :-
	(	var(XL)
	->	FTV = XL
	;	var(YL)
	->	FTV = YL
	;	XL = [H|_],
		var(H)
	->	FTV = H
	;	YL = [H|_],
		var(H)
	-> FTV = H
	;	XL = [XH|_],
		YL = [YH|_],
		var_to_simple_list(XH, XSL),
		var_to_simple_list(YH, YSL),
		walk_vars_to_first_term_variable(XSL, YSL, FTVW)
	->	FTV = FTVW
	;	XL = [_|XT],
		YL = [_|YT],
		walk_vars_to_first_term_variable(XT, YT, FTV)
	).

var_to_simple_list(V, L) :-
    % To be able to walk through the variable's components
	(	atomic(V)
	->	L = V
	;	V =.. L
	).

first_term_variable_does_not_change_comparison(Comp, XC, YC, FTV) :-
    % TODO: Compare with instantiated extremities, to test that comparison result does not change

```

The method is basically:

- if compare/3 gives `=`, or both variables are ground, then the result is trustworthy
- Otherwise “walk” through both variables together until the first var
- Run compare/3 with var temporarily instatiated to a lower then higher extremity, to check that the compare/3 result does not change - if it does not change, it is trustworthy

This should be easier than reimplementing the [standard order](https://www.swi-prolog.org/pldoc/man?section=standardorder)’s subtleties. Hopefully 😀

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [September 22, 2026, 7:28am UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/6 "2026-09-22T07:28:51Z")

</div>

> [@brebs](#):
>
> How about this idea - work in progress:

It is lacking some high level description … The idea behind partial\_compare/3 is that it is a good and fast to implement primitive that allows building higher level primitives. It simply does the normal compare/3, but when it encounters a comparison between a variable and anything but the same variable, it “returns” `undecided(Var,Other)`. Now, this not always the end of the story. We could have

?- A in 1..6, partial\_compare(D, A, a).

That results in undecided(A, a) and the constraint reasoner can decide this means `<`, as all integers are `'@<'/2` to all atoms. In some cases a constraint reasoner could decide the undecided is always `=`. In that case the values are equal, so we can unify them and try again.

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [September 22, 2026, 7:52am UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/7 "2026-09-22T07:52:39Z")

</div>

Is there a _lowest_ (and _highest_) possible ground value, to use in compare/3, that works when compared to any datatype?

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [September 22, 2026, 8:44am UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/8 "2026-09-22T08:44:25Z")

</div>

`partial_compare/3` is now in the git (can change if someone comes up with something better). Not really clear what should be provided on top, as this is mostly a _building block_, similarly like unifiable/3. Some candidates:

- must\_compare(?Diff, @Term1, @Term2)   
As compare/3, but throws instantiation\_error in case the comparison is unstable.
- compare\_when(?Diff, @Term1, @Term2)   
As compare/3, but delays (is a constraint).
- ord\_stable(@List)  
 true if `List` is a stable ordered set.
- stable\_assoc(@Assoc)
- rb\_stable(@RbTree)
- …

Or just leave it to the imagination of the users …

---

<div class="post-metadata">

**Author:** ![abaljeu](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/abaljeu/32/136_2.png) [@abaljeu](https://swi-prolog.discourse.group/u/abaljeu)\
**Post date:** [October 2, 2026, 5:18pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/9 "2026-10-02T17:18:08Z")

</div>

Who depends on stable order with unbound variables that may become bound? I might to a (when(ground(X), X @\< a → ; ), but if I’m doing X @\< A and X is not ground it’s because I am committed to never grounding X, or I know the variable is not the key in differentiating order.

---

<div class="post-metadata">

**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\
**Post date:** [October 3, 2026, 5:13am UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/10 "2026-10-03T05:13:35Z")

</div>

**Subject (or Reply):** Observation: Non-transitivity in cyclic term sorting vs. robustness of DFA minimization

Hi all,

While I haven’t been able to follow every detail of this extensive thread, I ran into an interesting empirical finding while testing Jan’s `term_automaton/2` and `automaton_minimal/3` that might be of interest to the discussion.

When sorting random ground cyclic terms (N=1000), I noticed occasional discrepancies between the built-in `sort/2`and a sort based on minimal automata (`rt_sort`):

Prolog

```prolog
?- rt_sort(GroundNs, S1), sort(GroundNs, S2), S1 \== S2.

```

Investigating the difference revealed that this is not caused by deduplication differences, but by a violation of transitivity in the built-in standard order comparison for cyclic terms. Specifically, we can isolate concrete pairs where:

1. Direct comparison yields A\<B in both `compare/3` and `rt_compare/3`:

2. Yet in `sort/2` (`S2`), B is placed _before_ A:

Because cyclic term comparison via cycle-detection traversal can depend on traversal paths and pointer identities, transitivity (X\<Y∧Y\<Z⟹X\<Z) occasionally breaks down during sorting, causing sorting anomalies depending on which pairs the sort algorithm compares first.

By contrast, normalizing the terms upfront via Paige-Tarjan minimization (`automaton_minimal/3`) establishes a canonical, path-independent state representation. Although it is computationally a more round-about route, it strictly preserves a mathematically sound total order and avoids these ordering paradoxes altogether.

Just sharing this observation in case it provides useful context for the ongoing discussion on rational term comparison semantics and robustness.

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [October 3, 2026, 7:49am UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/11 "2026-10-03T07:49:16Z")

</div>

> [@kuniaki.mukai](#):
>
> By contrast, normalizing the terms upfront via Paige-Tarjan minimization ([`automaton_minimal/3`](https://www.swi-prolog.org/pldoc/doc_for?object=automaton_minimal/3 "As automaton\_minimal/2, where Map says what became of each state.")) establishes a canonical, path-independent state representation. Although it is computationally a more round-about route, it strictly preserves a mathematically sound total order and avoids these ordering paradoxes altogether.

I think that is true. It is just too costly as a default compare/3 implementation ☹ I was hoping that we can use this only for the complicated cases, which we already identify. Unfortunately that does not seem to work. I should still look at the proof (a counter example found by Claude).

---

<div class="post-metadata">

**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\
**Post date:** [October 3, 2026, 12:23pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/12 "2026-10-03T12:23:17Z")

</div>

I agree with the current approach.

BTW. Comparing rational trees directly using the output of `term_automaton`without minimization should work correctly.

Also I have an idea to detect cycles directly in O(1) without scanning the stack, so I will test this in C as a small hobby project. I will let you know if I obtain any noteworthy benchmark results.

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [October 3, 2026, 12:28pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/13 "2026-10-03T12:28:43Z")

</div>

> [@kuniaki.mukai](#):
>
> BTW. Comparing rational trees directly using the output of `term_automaton`without minimization should work correctly.

You have to minimize the automaton, no? Than you should indeed get a total ordering, but again different from ISO compare/3 ☹ The problem is that we need a total ordering that is depth-first-left-right as that is what a lot of existing code expects.

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [October 3, 2026, 12:50pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/14 "2026-10-03T12:50:03Z")

</div>

> [@abaljeu](#):
>
> Who depends on stable order with unbound variables that may become bound?

The issue got concrete when faced with the requirement to define `(@<)/2`, etc. as a constraint. If the order is already stable, you are fine. Else you want to find the variable that is first compared to something and delay on that. `when(ground(...)` is too strong.

Then, there have been various suggestions that e.g., library(assoc) should require its key to be ground. That is too tight. They just need a stable order or, indeed, the user must be aware that the order may change. The new `incomparable` flag allows you to spot possible bugs caused by violating these assumptions. Few applications will want this flag, but it can be a good safely net and debugging tool.

---

<div class="post-metadata">

**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\
**Post date:** [October 3, 2026, 2:22pm UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/15 "2026-10-03T14:22:20Z")

</div>

Jan,

I see your point about the compatibility expectations for the standard order.

My primary goal right now is simply to investigate the total ordering mathematically and explore the cycle-detection performance in C without getting stuck in specification details.

I will experiment on my side first. Thanks for the clarification!

---

<div class="post-metadata">

**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\
**Post date:** [October 5, 2026, 2:36am UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/16 "2026-10-05T02:36:44Z")

</div>

**Subject:** Experimental result on rational tree comparison / Request regarding term\_automaton

I would like to share a brief experimental result regarding the comparison of rational trees, without getting into deep theoretical discussions.

Using a fast C-based state-pair stack traversal (`fast_rt_compare`), I tested whether the comparison order on raw automata directly generated from terms matches the order obtained after Paige-Tarjan minimization (`fast_rt_min_compare`).

In an experiment comparing 1,000,000 randomly generated cyclic term pairs:

- All 1,000,000 pairs yielded completely identical comparison results (`<`, `=`, `>`).

- The order on raw automata appears to be consistent with the minimized canonical order in practice.

Also, for our experiments, having built-in support for `term_automaton/2` (or `automaton/3`) in SWI-Prolog would be very helpful.

---

<div class="post-metadata">

**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\
**Post date:** [October 5, 2026, 3:49am UTC](https://swi-prolog.discourse.group/t/instability-of-standard-order/9830/17 "2026-10-05T03:49:33Z")

</div>

**Title:** Benchmark: C-based pair-stack vs. Automaton-based comparison for rational trees

Hi all,

I would like to share a brief benchmark comparison between different rational tree comparison implementations on SWI-Prolog.

### Benchmark Setup

- Repeated 1,000,000 iterations for a fixed pair of random cyclic terms (X,Y).

- Comparison targets:

````prolog
% ===================================================================
% Benchmark: fast_rt_compare vs fast_rt_min_compare vs rt_compare
% ===================================================================

% ?- benchmark_compare(1000000).
%@ Generating test terms...
%@ @(S_1,[S_1=h(h(h(h(S_1,S_1,S_1),h(S_1,S_1,S_1),g(S_1,S_1,S_1),h(S_1,S_1,S_1,S_1))),h(h(f(S_1,S_1,S_1),h(S_1)),f(g(S_1,S_1,S_1,S_1,S_1)),h(g(S_1,S_1),g(S_1,S_1,S_1,S_1,S_1))),h(h(h(S_1),h(S_1,S_1,S_1),f(S_1,S_1,S_1),h(S_1,S_1,S_1,S_1,S_1),h(S_1,S_1,S_1,S_1)),f(h(S_1,S_1),g(S_1),h(S_1,S_1,S_1))),h(h(g(S_1,S_1,S_1),g(S_1,S_1,S_1,S_1,S_1)),f(f(S_1,S_1,S_1),h(S_1),h(S_1,S_1,S_1,S_1,S_1)),h(f(S_1,S_1,S_1))),g(g(h(S_1,S_1,S_1,S_1,S_1),h(S_1,S_1,S_1,S_1,S_1),g(S_1,S_1,S_1,S_1),f(S_1),f(S_1,S_1)),h(f(S_1),h(S_1,S_1,S_1,S_1,S_1),f(S_1,S_1,S_1),f(S_1,S_1)),h(h(S_1,S_1,S_1,S_1,S_1),h(S_1,S_1,S_1,S_1,S_1),g(S_1,S_1),h(S_1,S_1,S_1),f(S_1)),h(f(S_1,S_1),f(S_1),g(S_1,S_1,S_1),g(S_1,S_1,S_1)),h(g(S_1),h(S_1,S_1,S_1,S_1),f(S_1,S_1))))])
%@ @(S_1,[S_1=f(h(f(g(S_1,S_1,S_1)),h(g(S_1,S_1,S_1),f(S_1,S_1))),f(f(f(S_1,S_1,S_1),g(S_1,S_1,S_1)),g(f(S_1,S_1,S_1,S_1)),h(h(S_1,S_1,S_1),g(S_1,S_1,S_1,S_1),f(S_1,S_1,S_1),f(S_1)),h(g(S_1,S_1),f(S_1,S_1),f(S_1,S_1,S_1,S_1),f(S_1,S_1)),f(g(S_1,S_1,S_1),f(S_1,S_1,S_1,S_1))),f(f(g(S_1,S_1,S_1,S_1)),f(h(S_1),g(S_1,S_1),f(S_1,S_1,S_1),g(S_1,S_1,S_1,S_1)),h(g(S_1,S_1,S_1,S_1,S_1),f(S_1,S_1),g(S_1,S_1)),g(f(S_1,S_1,S_1),f(S_1,S_1),h(S_1,S_1,S_1,S_1),f(S_1,S_1,S_1))),h(h(h(S_1,S_1),g(S_1,S_1)),f(g(S_1,S_1,S_1,S_1,S_1),h(S_1),f(S_1,S_1)),g(h(S_1,S_1),h(S_1,S_1,S_1,S_1),f(S_1,S_1),h(S_1,S_1),h(S_1)),f(g(S_1,S_1,S_1,S_1,S_1))))])
%@ 
%@ --- 1. fast_rt_compare (C stack, raw terms) [1000000 iterations] ---
%@ % 11,999,999 inferences, 5.831 CPU in 5.853 seconds (100% CPU, 2057990 Lips)
%@ 
%@ --- 2. fast_rt_min_compare (C stack, with minimization) [1000000 iterations] ---
%@ % 17,999,999 inferences, 16.863 CPU in 16.918 seconds (100% CPU, 1067431 Lips)
%@ 
%@ --- 3. rt_compare (raw automaton) [1000000 iterations] ---
%@ % 2,999,999 inferences, 0.296 CPU in 0.297 seconds (99% CPU, 10142019 Lips)
%@ 
%@ --- 4. rt_compare (minimized automaton) [1000000 iterations] ---
%@ % 2,999,999 inferences, 0.294 CPU in 0.296 seconds (100% CPU, 10189349 Lips)
%@ true.
```

### Notes

* Once converted into automaton tables outside the loop, `rt_compare/5` runs very fast (\~0.34s / 1M calls), with essentially no speed difference between raw and minimized tables.

* For direct term comparison, `fast_rt_compare/3` (without prior minimization) runs about 2x faster than `fast_rt_min_compare/3`.

* In a separate consistency test over 1,000,000 random cyclic term pairs, `fast_rt_compare/3` and `fast_rt_min_compare/3` produced identical ordering results in all cases.

Just sharing the benchmark data for reference.

Best regards,

Kuniaki Mukai

EDIT 2026/10

I would like to report the results of this experiment on the rational tree ordering:
Minimization via Jan's automaton_minimal/3 turned out to be strictly essential.
I have not yet analyzed why term_automaton/2 alone unexpectedly fails transitivity.
This update is a C implementation of my earlier Prolog prototypes that satisfied transitivity.
The algorithm uses cycle length information, though it remains unclear to me why incorporating cycle length is so effective.
````