How to compare/3 without surprises on non-ground terms?

Help!
1

We have ?=/2 , to determine whether 2 terms are certainly different.

However, I’d like to know whether comparing the 2 terms results in <, > or =, i.e. the result of compare/3 , and to be able to use it confidently when the terms might be non-ground - it should fail if uncertain.

I’m probably asking for an imaginary comparable/2, with results such as:

comparable(f(1, 0), f(X, 0)).

… fails - X is not sufficiently instantiated to be comparable to 1.

comparable(f(2, X), f(1, Y)).

… succeeds - 2 is greater than 1, no need to care about X and Y.

Surely there is something better than waiting for both terms to be ground/1?

Google finds sorting - How to define (and name) the corresponding safe term comparison predicates in ISO Prolog? - Stack Overflow , but the answers there are, erm, not obviously sound or verifiable :upside_down_face:

The inspiration for this question comes from posting my comparison code in hubris, and having it collide with false’s scrutiny :grinning:

2

A builtin implementation is, I guess, not too hard. Just do comparison and if the first non-equal is something comparing a variable to something else (including another variable), fail. Is that right? It only starts to make real sense (I think) if when/2 would also support it. B.t.w. could be called ?=@=/2 ?

The main question I have with it is whether it has any practical use. If there is no existing implementation in any of the Prolog systems providing when/2, I start to wonder. I can see some value in a built-in for assertion/1 like checks.

3

I think the main problem is that compare/3 is fundamentally broken:

?- compare(C, f(X), f(1)), X = 2.
C = (<),
X = 2.

… so we have to perform some (independent) checks also, e.g. ground/1, to ensure sanity - but it seems like such a wasted opportunity:

How about adding a built-in compare_si/3 (si as is “sufficiently instantiated”), which is mostly a copy of compare/3 but which fails, rather than producing a possibly-wrong answer, if the comparison is uncertain due to lack of instantiation?

That sounds very convenient, and also sounds like it would be very efficient.

4

I don’t think it’s fundamentally broken, but it’s certainly not “pure”. I also don’t think it’s very hard to implement what you want as a Prolog predicate, so don’t you need a compelling use case case to go further than that?

5

I agree. I have checked that It also breaks transitive law of the total ordering < supposed on the Prolog terms. Thus, compare/3 should be kept in mind as an extra logical predicate like var/1 at least for the non-ground terms.

?- compare(C, X, Y), compare(D, A, B), X = B, Y = A, compare(E, X, Y).
C = D, D = E, E = (<),
X = B,
Y = A.
6

How, then? Give me a clue, and I’ll try to fill in the blanks.

7

My point is that there should be some sensible logic applied, e.g.:

f(2, X) compared to f(1, Y) is blatantly obviously greater, because 2 > 1.

It would be dumb, in a Prolog program, to wait for both to be ground, in order to perform a safe comparison, since a comparison can be safely performed already.

8

dif/2 waits until the two terms are sufficiently ground. I don’t know of a predicate for general comparison that waits until the two terms are sufficiently ground, but if it exists, it would look a lot like dif/2. You could write one in Prolog, by deconstructing the terms using …=/2 or compound_name_arguments/3.

However, if you want to use your improved compare/3 with predsort/3, it won’t work - the improved compare/3 would succeed when the arguments aren’t sufficiently instantiated and if subsequently instantiated and compare/3 fails, predsort/3 wouldn’t backtrack and generate a different result.

1 Like
9

So from your original post, I think you want an equivalent of compare/3 that fails when a comparison with a variable is required, otherwise same semantics as compare (standard term ordering). Perhaps something like:

comparable(Op,X,Y) :- compound(X), compound(Y), !,
	functor(X,_,XA), functor(Y,_,YA),
	( XA = YA
	 -> X =.. Xs, Y =.. Ys,
	    comparableList(Xs,Ys,Op) % Xs and Ys same length
	 ;  compare(Op,XA,YA)
	).
comparable(Op,X,Y) :- nonvar(X), nonvar(Y),
	compare(Op,X,Y).
	
comparableList([],[],=).
comparableList([X|XArgs],[Y|YArgs],Op) :-
	comparable(AOp,X,Y),
	((AOp = =)
	 -> comparableList(XArgs,YArgs,Op)
	 ;  Op = AOp
	).

Examples:

?- comparable(C,f(1, 0), f(X, 0)).
false.

?- comparable(C,f(2, X), f(1, Y)).
C = (>).

Interesting question is what does failure mean? (Not comaparable yet?)

In this case, doesn’t compare/3 work as desired:

?- compare(C,f(2, X), f(1, Y)).
C = (>).
2 Likes
10

It works in this case but will give incorrect results (incorrect according to the spec discussed in this thread), for example for:

?- compare(Order, f(1), f(X)).
Order = (>).

Sorry for the obvious example. I guess the whole idea discussed here is that further instantiation of a term should not change the result of compare/3 (is that right, @brebs?). However (and please correct my misake!) to me it seems that this cannot be used for sorting. It could either “sort” for some set of terms, or fail, which would mean “those terms cannot be sorted”.

11

That’s exactly what I want it (compare_si/3) to do. Failure means a definite comparison cannot be made at this point. Which is correct and appropriate.

It’s not performing sorting, it’s performing a comparison.

Can someone please explain why anyone would find this useful or helpful, or how it got into the language design at all:

?- compare(C, _, _).
C = (<).

:crazy_face:

(Yeah, I know about standard order… but this comparison result is not logical. Surely it’s a design failure.)

12

I don’t have an argument here :slight_smile: I am just stating my opinions as facts in the hope that someone points it out if I am wrong :wink:

13

But you’ll confuse users if you have a compare_si/3 that’s only intended to be used with the first argument instantiated, I think.

Instead of failing when further instantiation could change the result, perhaps it’s better to throw an exception? (I know @ridgeworks would disagree with me on this; but having two meanings for failure (either “this comparison fails” or "this comparison might give a different result if the terms become further instantiated) seems dangerous. If compare(<, T1, T2) fails, that implies compare(>=, T1, T2) would succeed; but it seems that you could have both of them failing, which would probably break a few things (and not just sort/2).

14

It’s “compare if definitely able, else fail”. Throwing an error sounds excessive.

This seems reasonable:

compare_able(Comp, X, Y) :-
    compare_able_([X], [Y], Comp).

compare_able_([], Ys, Comp) :-
    compare_able_empty_(Ys, Comp).
compare_able_([X|Xs], Ys, Comp) :-
    compare_able_ys_(Ys, Xs, X, Comp).
    
compare_able_empty_([], =).
compare_able_empty_([_|_], <).

compare_able_ys_([], _, _, >).
compare_able_ys_([Y|Ys], Xs, X, Comp) :-
    (   X == Y
    ->  compare_able_(Xs, Ys, Comp)
    ;   ground(X),
        ground(Y)
        % Can compare with confidence
    ->  compare(C, X, Y),
        compare_able_map_(C, Xs, Ys, Comp)
    ;   nonvar(X),
        nonvar(Y),
        % Deconstruct
        X =.. Xs0,
        Y =.. Ys0,
        append(Xs0, Xs, Xs1),
        append(Ys0, Ys, Ys1),
        compare_able_(Xs1, Ys1, Comp)
    ).

compare_able_map_(<, _, _, <).
compare_able_map_(>, _, _, >).
compare_able_map_(=, Xs, Ys, Comp) :-
    compare_able_(Xs, Ys, Comp).

Results:

?- compare_able(C, X, X).
C = (=).

?- compare_able(C, a(X), a(Y)).
false.

?- compare_able(C, a(X), b(Y)).
C = (<).

?- compare_able(C, f(X,9,Y), f(Y,3,Y)).
false.

?- compare_able(C, f(X,9,Y), f(X,3,Y)).
C = (>).

?- compare_able(C, [1,2,X], [1,5,X]).
C = (<).
15

The standard compare/3 is surely useful to sort lists with non-ground terms, though this may be poor answer to your question.

?- sort([A,B,A,B,C], X).
X = [A, B, C].

?- flatten([A, B, B, A, C], X), sort(X, Y).
X = [A, B, B, A, C],
Y = [A, B, C].

term_variables/2 seems to use this sort internally.

?- term_variables(f(A, B, A, B, C), Vs).
Vs = [A, B, C].
16

So let me flip the question; why do you want to compare terms (or partially compare) which aren’t ground?

I think the original language designers wanted Prolog terms to be a strictly ordered set, hence the standard order, and variables are terms (at least at that point in the computation). Lots of seemingly arbitrary decisions went into that , e.g.,:

  1. Variables < Numbers < Strings < Atoms < Compound Terms

but it permits the direct comparison of any two terms without failure or ambiguity, hence the sorting of lists of such terms (lists are just compound terms).

As this seems to have been useful for various purposes over the decades, I’m not going to question its purpose. I suspect in most use-cases, it’s used for sorting like-types, e.g., lists of numbers, or at least ground terms, so its “illogical” behaviour has been eliminated and the general purpose sort works just fine.

But if it doesn’t fit your purpose, by all means code up one that does.

P.S. And just for the record, my major beef is with builtin predicates that mandate expensive non-logical error behaviour rather than leaving the decision of what constitutes an error up to the user. They can always wrap the builtin to implement error semantics, whereas it can be expensive in code and/or time to go the other way around (avoid or deal with such errors). And, for the most part, I personally carry this through to library API’s as well.

17

It just seems the next logical step, in e.g. creating a generic predicate to check that a list has increasing elements.

The elements might themselves be e.g. partly-instantiated lists, such as:

[1,2|_] can be compared to [1,3|_], as-is, there is no need to wait for further instantiation. So, I want to make the sensible decision, rather than pointlessly waiting using when/2.

18

Sounds like you don’t want it to fail when variables are encountered. Instead, you want to constrain them and that gets a little trickier.

First, your identity check is a good one to add as the first clause, no use doing a lot of work to compare identical terms.

I think there are two places where you would have to worry about constraints. First, comparing two terms, at least one of which is a variable. So maybe adding a clause at the end of my original example code something like:

comparable(Op,X,Y) :-  % X and/or Y are vars
	when((nonvar(X),nonvar(Y)), comparable(Op,X,Y)).

The second place is when comparing lists; if either of the elements is a variable, you have to defer the rest of the list processing until that comparison is valid, so maybe:

comparableList([X],[Y],Op) :- !,
	comparable(Op,X,Y).
comparableList([X|XArgs],[Y|YArgs],Op) :-
	comparable(AOp,X,Y),
	when(nonvar(AOp),
		((AOp = =)
	 	 -> comparableList(XArgs,YArgs,Op)
	 	 ;  Op = AOp
		)
	).

Now comparable/3 always succeeds but may leave any or all arguments constrained:

?- comparable(Op,f(1,X),f(2,Y)).
Op =  (<).

?- comparable(Op,[Z,2|X],[1,3|Y]).
when(nonvar(Z), comparable(_A, Z, 1)),
when(nonvar(_A),  (_A=(=)->comparableList([[2|X]], [[3|Y]], Op);Op=_A)).

?- comparable(Op,[Z,2|X],[1,2|Y]),Z=1.
Z = 1,
when((nonvar(X), nonvar(Y)), comparable(Op, X, Y)).

?- comparable(Op,[Z,2|X],[1,3|Y]),Z=2.
Op =  (>),
Z = 2.

?- comparable(Op,[Z,2|X],[1,2|Y]),Z=1,X=2,Y=3.
Op =  (<),
Z = 1,
X = 2,
Y = 3.

This the sort of thing you’re looking for?

19

Yeah - I might create a predicate variant, which adds a Boolean variable for whether comparable (instead of deliberately failing), and adds the variables which would need further instantiation in order to retry the comparison.

I’m not currently looking for a comparable which uses when.

20

I think it would be nice to have a sensible and intuitive comparison predicate, so that the weirdness of compare/3 doesn’t come as such a shocking counter-intuitive gotcha to beginners, and instead it can be viewed as a historical relic, designed more for performance than for logic, and considered deprecated.

“Standard order” does not feel like a reasonable excuse for:

?- compare(C, A, B).
C = (<).