Using \==/2 or dif/2

If I want to make sure that two variables do not instantiate to the same term, what is the preferred way to do it?

Let's say I need to find directed edges in a graph, and a node cannot have an edge to itself:

node(a, x, y). node(b, z, x). node(c, y, y).

(the edges here are a -> c, b -> a, but not c -> c)

The following works:

edge(A, B) :- node(A, _, X), node(B, X, _), A \== B.

This works too [swi-prolog]:

edge(A, B) :- dif(A, B), node(A, _, X), node(B, X, _).

This does not work, apparently (because neither A nor B are instantiated yet?):

edge(A, B) :- A \== B, node(A, _, X), node(B, X, _).

I guess my problem with the first solution is that, with a more complex node predicate, a lot of unnecessary unifications might take place before edge fails. The dif on the other hand is in a library, which suggests that it is not meant to be used in such a simple case (although it has the exact function that I seem to be looking for).

Solution 1:

For elegance and didactic reasons alone, dif/2 is clearly preferable here and also in the vast majority of other cases, since as you already note "a lot of unnecessary unifications might take place" otherwise, and also because dif/2 is a pure and nicely declarative predicate that can be used in all directions and at any place in the clause body without changing the meaning of the program, in contrast to (\==)/2. dif/2 is also an autoloaded predicate in SWI-Prolog, meaning that you need not import any library explicitly to use it, and dif/2 is available like any built-in predicate.

If you use dif/2 you can reason much more easily about your code. For example, in your case, you start with:

edge(A, B) :- node(A, _, X), node(B, X, _), dif(A, B).

and then, as you know that dif/2 is a completely pure predicate, you know that you can also write this as:

edge(A, B) :- dif(A, B), node(A, _, X), node(B, X, _).

Further, since you know that dif/2 always terminates, you know that this change can at most improve the termination properties of your program.

Like all constraints, dif/2 is meant to be used. I highly recommend it instead of impure predicates that are not commutative.

In case you are worried about performance, here is a small comparison, just comparing dif/2 against the non-declarative (\==)/2 in a use case where the two predicates can be used interchangeably:

?- N = 1_000_000, time((between(1,N,_),dif(a,b),false)).
% 11,000,005 inferences, 0.352 CPU in 0.353 seconds (100% CPU, 31281029 Lips)

?- N = 1_000_000, time((between(1,N,_),a\==b,false)).
%@ % 3,000,001 inferences, 0.107 CPU in 0.107 seconds (99% CPU, 28167437 Lips)

So, there are sometimes performance benefits when using (\==)/2. However, there are also much more severe drawbacks when using such a low-level predicate: It is harder to understand, more error-prone, and not declarative.

I therefore recommend to simply use dif/2 to express that two terms are different.

Solution 2:

The queries are meta-interpreted and the overhead may outweigh the differences of dif(X,Y) and X\==Y. You should compare these two predicates:

t1:-
    1000=I,
    time(t1(I)).


t1(I):-
    dif(X,Y), 
    between(1,I,X), 
    between(1,I,Y), 
    false.

t2:-
    1000=I,
    time(t2(I)).


t2(I):-
    between(1,I,X), 
    between(1,I,Y), 
    X\==Y,
    false.

On B-Prolog, I got the following results:

| ?- cl(t)
Compiling::t.pl
compiled in 0 milliseconds
loading::t.out

yes
| ?- t1
CPU time 0.14 seconds.
no
| ?- t2
CPU time 0.078 seconds.
no
| ?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false )).
CPU time 0.234 seconds.
no
| ?- 1000=I,time(( between(1,I,X), between(1,I,Y), X \== Y, false )).
CPU time 0.218 seconds.

Solution 3:

First of all, dif/2 and (\==)/2 mean the same when both arguments are ground, that is variable free. So if you can ensure that the arguments will be ground — or rather sufficiently instantiated such that further instantiations will not affect the outcome of (\==)/2 — then it does not make a difference.

In your example, we would need to know for sure that answers for node/3 contain always a ground first argument. In that case, the (\==)/2 program is fine. In rare cases it might be less efficient than the dif/2 version. Think of the goal edge(X, X).

In many situations, the (\==)/2 or even (\=)/2 is significantly more efficient. On the other hand, how important is efficiency when compared to correctness?

Another way of seeing this, is to consider (\==)/2 and (\=)/2 as approximations from two sides: Only if both agree, do we have a safe final outcome.

Historically, dif/2 is one of the oldest built-in predicates. It was present in the very first Prolog system which is sometimes called Prolog 0 to distinguish it from the next version which is often perceived to be the first Prolog — the Marseille Prolog — Prolog 1. Prolog 1 did no longer have dif/2 and it is in this shape that Prolog came to Edinburgh. Also,dif/2 is not part of the ISO standard (currently) since it requires some coroutining-like mechanism. And many (rather older) Prolog systems do not have such a mechanism. However, even in ISO Prolog one could do better:

iso_dif(X, Y) :-
   X == Y,
   !,
   fail.
iso_dif(X, Y) :-
   X \= Y,
   !.
iso_dif(X, Y) :-
   throw(error(instantiation_error,iso_dif/2)).

(Here is another, probably more efficient implementation)

Note how the problematic cases are covered by an error that stops the entire computation.

Current Prolog systems that support dif/2 right out of the box are B, SICStus, SWI, YAP. It is in a library of IF, Ciao, XSB, Scryer.

Using \==/2 or dif/2

Solution 1:

Solution 2:

Solution 3:

Related

Recent Posts