Thanks. ?-help(term_variables) says exactly what you told.
Availability: built-in
term_variables(+Term, -List) [ISO]
Unify List with a list of variables, each sharing with a unique variable of
Term. The variables in List are ordered in order of appearance traversing
Term depth-first and left-to-right. See also term_variables/3 and
nonground/2. For example:
?- term_variables(a(X, b(Y, X), Z), L).
L = [X, Y, Z].
Availability: built-in
term_variables(+Term, -List, ?Tail)
Difference list version of term_variables/2. That is, Tail is the tail of
the variable list List.
(END)
Well, compare/3 and a good set of other predicates are defined on standard order of terms. E.g., @>/2, sort/2, etc. That set has proved its value. Seems you also agree we should not change that. You also see people claiming ordered sets, binary trees (library(assoc)) and similar features can only be be used with ground terms. This is clearly not the case as there is both a weaker constraint to make them safe and they are also ok if you can guarantee no values are unified to while relying on their ordering.
If you want sound comparison, I think there are only two ways: throw an instantiation error of the arguments may change order due to instantiation or define an ordering constraint. The first is implementation-wise fairly easy. A constraint is harder and (I think) will quickly result in very poor performance. I doubt it would help much. The ISO predicates are well defined and used everywhere. How is that going to reach students?
P.s. A predicate with reasonable semantics could be cmp(Dif, X, Y, Cond), where Cond expresses the condition under which this holds, so you could ask things as below:
?- cmp(>, f(X, 0), f(1, Y), C),
C = (X>1).
Also not without problems though, especially if Dif is unbound. Giving three conditional solutions seems an overkill.
2 Likes
I’m happy with compare_able.
Could also have:
compare_t(C, X, Y, Comparable) :-
( X == Y
-> C = (=),
Comparable = true
; ground(X),
ground(Y)
-> compare(C, X, Y),
Comparable = true
; Comparable = false
).
Results:
?- compare_t(C, X, X, Bool).
C = (=),
Bool = true.
?- compare_t(C, 5, X, Bool).
Bool = false.
?- compare_t(C, 1, 2, Bool).
C = (<),
Bool = true.
My concern with the legacy compare/3 is that beginners encounter it and become discouraged at, how shall I put it, the “obvious lack of obvious logic” it exhibits. I do feel that Prolog should have a modern built-in replacement that beginners will feel comfortable with.
That then gives them a couple of years to slowly become comfortable with the standard order 
I would argue that an instantiation error is inappropriate, because that’s an expected and acceptable situation - in the same way that memberd_t uses false rather than throwing an error.
Which would also lead to this?
?- is(Sum, 1+X, Bool).
Bool = false.
This sounds weird (to me). Instantiation errors are there to do exactly this: the arguments are insufficiently known at this point in time to give an answer. Adding an extra argument to the computation that represents whether the computation could be completed soundly seems odd. If you want a logical solution, go constraints as that resolves the ordering problem by delaying the comparison.
That would also be compatible with numeric comparison, which comes as >/2, etc. that raise exceptions and e.g. #>/2 that works as a constraint.
As noted elsewhere in this thread though, comparing arbitrary terms typically is not very meaningful at the application level. How different types compare is rather arbitrary. You can sometimes (mis)use that in an application, but that seems beside the point of this discussion.
This doesn’t work for predsort/3 if the comparison predicate delays – the only sensible thing to do if the arguments aren’t sufficiently instantiated is to throw an exception.
However, a total ordering (even with variables) is useful, for example to make a canonical ordering of results. This can also result in some strange results, such as:
?- setof(X, member(X, [1,A,2,B]), Xs).
Xs = [A, B, 1, 2].
?- setof(X, member(X, [1,A,2,B]), Xs), A=B.
A = B,
Xs = [B, B, 1, 2]. % a "set" isn't supposed to have duplicate members
?- A=B, setof(X, member(X, [1,A,2,B]), Xs).
A = B,
Xs = [B, 1, 2]. % This is what the previous query should have returned.
1 Like
That would be an incorrect reuse of Bool. Bool was only applicable to the point that the comparison was made.
The discussion motivated me to go back and look at my simple prototype of a logical compare. I thought it was interesting as an example of how to use constraints (coroutining in this case), to write logically pure predicates, and perhaps even interesting in its own right.
compare/3 is not logically pure because it’s not persistent, i.e., not “once true, always true” (similar issue with var/1). For example:
?- compare(Op,X,Y), X=2, Y=1, compare(Op,X,Y).
false.
The fist call to compare is true but the second identical call fails. But a pure version (comparable/3):
?- comparable(Op,X,Y), X=2, Y=1, comparable(Op,X,Y).
Op = (>),
X = 2,
Y = 1.
?- X=0, comparable(Op,X,Y), Y=1, comparable(Op,X,Y).
X = 0,
Op = (<),
Y = 1.
This is because the initial call to comparable/3 will leave residual goals to be satisfied if the conditions (bindings of necessary variables) are ever satisfied. So
?- compare(Op,X,Y).
Op = (<).
but
?- comparable(Op,X,Y).
when((nonvar(X), nonvar(Y)), comparable(Op, X, Y)).
The “truthful answer” in this case is a residual goal. This isn’t much different than any answer that leaves unbound variables - the program didn’t provide a specific solution for any variables, including the comparison operator.
comparable/3 is fully relational:
?- comparable(<,X,3).
when(nonvar(X), comparable(<, X, 3)).
?- comparable(<,X,3), X=2.
X = 2.
?- comparable(<,X,3), X=4.
false.
?- comparable(Op,X,X).
Op = (=).
Consistent with the OP question, comparable/3 proceeds as far as it can in the comparison until it either succeeds (as in compare/3) or there is insufficient instantiation to proceed:
?- comparable(Op, f(1,X), f(2,Y)).
Op = (<).
?- comparable(=, f(1,X),f(1,Y)).
X = Y.
?- comparable(Op, f(1,X),f(1,Y)).
when((nonvar(X), nonvar(Y)), comparable(Op, X, Y)).
?- comparable(Op, f(1,X),f(1,Y)), X=4, Y=3.
Op = (>),
X = 4,
Y = 3.
?- comparable(<, f(1,X),f(1,Y)), X=4, Y=3.
false.
Does it work with predsort/3 as is?
?- predsort(comparable,[X,Y],L).
L = [X, Y],
when((nonvar(X), nonvar(Y)), comparable(<, X, Y)) ;
L = [X],
when((nonvar(X), nonvar(Y)), comparable(=, X, Y)) ;
L = [Y, X],
when((nonvar(X), nonvar(Y)), comparable(>, X, Y)).
Not quite what I expected, but correct IMO. And L will be a sorted list once X and Y are defined:
?- predsort(comparable,[X,Y],L), X=3, Y=2.
X = 3,
Y = 2,
L = [2, 3].
?- predsort(comparable,[X,Y],L), X=3, Y=4.
X = 3,
Y = 4,
L = [3, 4] ;
false.
?- predsort(comparable,[X,Y],L), X=3, Y=3.
X = Y, Y = 3,
L = [3] ;
false.
predsort/3 just became logical as well.
So I think it’s an intriguing example using coroutining to write logical, well-behaved predicates. It may not perform as well as a C builtin, but it works in situations where the builtin might fail. And as constraint based solution, it may actually prune the search tree (constrain and generate paradigm), improving performance in some applications.
Code if interested:
comparable/3
comparable(Op,X,Y) :- Op == =, !, % Op = =, unify X and Y
X = Y.
comparable(=,X,Y) :- X == Y, !. % X and Y identical, Op = =
comparable(Op,X,Y) :- compound(X), compound(Y), !, % comparing two compound terms
functor(X,_,XA), functor(Y,_,YA),
compare(AOp,XA,YA), % compare arities
( (AOp == =)
-> X =.. FX, Y =.. FY, % arities equal,
comparableList(FX,FY,Op) % compare functors and arguments, lists are same length
; Op = AOp % arities unequal
).
comparable(Op,X,Y) :- nonvar(X), nonvar(Y), !, % comparing two other nonvars
compare(Op,X,Y).
comparable(Op,X,Y) :- % else X and/or Y are vars
when((nonvar(X),nonvar(Y)), comparable(Op,X,Y)).
comparableList([X],[Y],Op) :- !, % compare last items in list
comparable(Op,X,Y).
comparableList([X|XArgs],[Y|YArgs],Op) :-
comparable(COp,X,Y), % compare first items
when(nonvar(COp), % if COp undefined, check will be deferred
((COp = =)
-> comparableList(XArgs,YArgs,Op)
; Op = COp
)
).
Note this version can loop when comparing cyclic terms. So that’s something I want to look at (perhaps using terms:term_factorized).
3 Likes
Really ? The clause in your codes seems block such looping.
Note that the number of pairs of nodes in cyclic terms are finite.
Am I missing ? Could you give an example of such looping cyclic terms if you had ?
It may catch some cases, but not them all:
?- X=f(X,1),Y=f(Y,2),comparable(Op,X,Y).
Action (h for help) ? abort
% Execution Aborted
I see. Thanks.
As the builtin compare takes care of cyclic terms in some way, consuling its source I hope it will be fixed soon.
% ?- X=f(X,A),Y=f(Y, B), compare(C,X,Y).
%@ X = f(X, A),
%@ Y = f(Y, B),
%@ C = (<).
% ?- X=f(X,2),Y=f(Y, 1), compare(C,X,Y).
%@ X = f(X, 2),
%@ Y = f(Y, 1),
%@ C = (>).
Are you claiming the built-in is incorrect? If you refer to @ridgeworks comparable/3, dealing with cyclic terms in Prolog is pretty hard and/or pretty inefficient. At the C level we can temporary “pollute” the term with marks/flags to detect loops at close to zero cost. I think that the basis to all of this should be a compare version that behaves different when it compares a variable to something that is not the same variable. It can than return this pair. comparable/3 could be bootstrapped from that quite easily.
Possibly order(?Diff, ?X, ?Y) would make sense? Note that compare is a verb, hinting at its non-logical behavior while order is a relation.
I meant @ridgwork’s comparable/3 could fix the case of cyclic terms following the way of the builtin compare.
I thought that the builtin compare/2 is efficient enough also for cyclic terms.
Moreover I expected that compare/3 has much hint for the comparable for cyclic terms
However, your comment sounds negative against such expectation.
Hard to say. It could be an issue with the current implementation as well as just that the fundamental problem shows up at a different place. The first is not unlikely though.
The cyclic comparison uses the same trick as for cyclic unification I learned from Bart Demoen and that is described in pl-prims.c in a comment starting at line 71. The idea is that while going through compounds you create a reference link from the compound at one side to the other one. Now, for unification and ==/2 this works fine as the argument order does not matter. For comparison, the argument order does matter.
Now, is there a fundamentally better (not so easy to define what is better) algorithm? Is it possible to improve on the current algorithm, possibly by keeping track of the “side” we are?
Anyone wishing to sort it out, see pl-prims.c, do_compare() 
It surely is an interesting finding. Is there a pointer to the original discussion?
So far I take it obvious that the standard total order on Herbrand universe
has a unique total oder extention on the rational extention of the Herbrand universe. So, IMHO, the example seems to show a bug of compare/3.
This is how I interrpreted it. Unfortunately compare/3 is a C primitive and comparable/3 is a Prolog predicate; not much can be shared. However terms:term_factorized does seem to provide the tools necessary to address the issue. Note that comparable/3 is already largely bootstrapped from compare/3. It just alters the semantics of variables.
I tend to agree (comparison should be transitive); the current work in progress:
?- X=f(X,a(X)), Y=f(Y,b(Y)), Z=f(Y,c(Y)),
comparable(A,X,Y), comparable(B,Y,Z), comparable(C,X,Z).
X = f(X, a(X)),
Y = f(Y, b(Y)),
Z = f(Y, c(Y)),
A = B, B = C, C = (<).
This initially gave me pause:
?- X=f(X), Y=f(Y), comparable(Op,X,Y).
X = Y, Y = f(Y),
Op = (=).
but it seems to be fundamental (X and Y are indistinguisable), at least in SWIP:
?- X=f(X), Y=f(Y), X==Y.
X = Y, Y = f(Y).
There is a remark in the SICtus documentation:
Please note : the standard order is only well-defined for finite (acyclic) terms.
There are infinite (cyclic) terms for which no order relation holds.
https://sicstus.sics.se/sicstus/docs/3.12.11/html/sicstus/Term-Compare.html
But I don’t find the comp.lang.prolog counter example right now.
Google Search is not anymore that good for comp.lang.prolog. Maybe
should search in the usenet groups directly, via Google Groups.
Edit 22.03.2023
Ok, got it, here it is in all its glory:
comparing infinite terms - 16.07.1996
Mats Carlsson
https://groups.google.com/g/comp.lang.prolog/c/Om8bTZ_Mom4/m/uTPb727mMTUJ
3 Likes
Sorry, I totally missed what this was doing.
Ignore most of my post; not quite sure what the right answer is.
Edit:
So comparing X and Z: both terms with the same functor and arity, so it comes down to comparing the arguments in order. First arguments of X and Z are X and Y respectively; X < Y since A = ‘<’, so X < Z and C should also be ‘<’.
Is that right?
Interesting, and from the rest of the thread, it doesn’t look like this ever got officially resolved.
My tentative conclusion is that when comparing two cyclic terms, it is possible to discover when they are equal, but if they’re not equal their order is undecidable in general, so don’t depend on it. Any applications come to mind where this matters?
I think a correct equivalence test is important because that drives the discarding of duplicates, tests for graph isomorphism, etc.
1 Like
I was working on something for comparable/3 along similar lines based on terms:term_factorized when I came across Lee Naish’s idea for an infinte tree syntax in the above 1996 discussion:
There is no reason why a syntax such as f(g(h(@2)) should
not be provided for the term f(g(h(g(h(g(h(… (the “@2” is a shorthand for
the tree two levels up, or speaking in terms of representation, a pointer
to the “g” node).
So the idea is to map the cyclic term to an acyclic term using this “pointer” notation. Rather than use the @ operator which might occasionally be used for other purposes, I substituted the functor '\a' so “@2” becomes “'\a'(2)” instead; a bit unwieldy, but it’s only intended to be used internally.
Now to compare two cyclic terms, translate them to this acyclic format and compare those using existing comparable/3. E.g.,
?- X=f(X,1), acyclic_def(X,XDef).
X = f(X, 1),
XDef = f('\a'(1), 1).
?- X=f(X,a(X)), Y=f(Y,b(Y)), Z=f(Y,c(Y)),
comparable(A,X,Y), comparable(B,Y,Z), comparable(C,X,Z).
X = f(X, a(X)),
Y = f(Y, b(Y)),
Z = f(Y, c(Y)),
A = B, B = C, C = (<).
?- A=s(B,0),B=s(A,1), acyclic_def(A,Adef), acyclic_def(B,Bdef).
A = s(s(A, 1), 0),
B = s(A, 1),
Adef = s(s('\a'(2), 1), 0),
Bdef = s(s('\a'(2), 0), 1).
?- A=s(B,0) ,B=s(A,1), comparable(Op,A,B).
A = s(s(A, 1), 0),
B = s(A, 1),
Op = (>).
(Based on Mats Carlsson’s note, I think either < or > is an acceptable answer for the last query.)