Prolog: a person is a sibling of himself?

Question

I'm having some trouble understanding why my code in prolog does something based on the order I put my rules in.

Here is my database:

parent(tom, bob).
parent(tom, liz).
parent(mary, bob).
parent(mary, liz).

male(tom).
male(bob).
female(mary).
female(liz).

And here are the rules:

%difference(X, Y) ==> Predicate to check if two people X and Y are not the same person.
difference(X, Y) :- \==(X, Y).
father(X, Y) :- male(X), parent(X, Y), difference(X, Y).
mother(X, Y) :- female(X), parent(X, Y), difference(X, Y).
sibling(X, Y) :-
    difference(X, Y),
    mother(M, X), mother(M, Y),
    father(F, X), father(F, Y).

The problem is that when I do this,

?- sibling(bob, X).

I get

X = bob ;
X = liz ;
false.

But when I change the ordering (I put difference(X, Y) at the last part)

sibling(X, Y) :-
    mother(M, X), mother(M, Y),
    father(F, X), father(F, Y),
    difference(X, Y).

and I call

?- sibling(bob, X).

I get

X = liz;
false.

which is what I want.

So far, I've only seen that the ordering of the rules matter when doing recursion. So I don't understand how bob is still a sibling of himself just because I put the difference check first.

Thanks for any help!

Closestool

Answer 1

This is because of the way unification works. If you put difference first the values of X and Y are not yet unified to any values. Consider the trace:

 goal list: [sibling(bob, Z)]
 goal: sibling(bob, Z).
 X-> bob, Y -> Z
 goal list: [difference(bob, Y), mother(M, bob), mother(M, Y), father(F, bob), father(F, Y).]
 goal: difference(bob, Y) --SUCCESS
 goal list: [mother(M, bob), mother(M, Y), father(F, bob), father(F, Y).]
 goal: mother(M, bob)
 ...

When you put the difference call last, both X and Y have been unified and difference will fail if they are the same value. Then backtracking will occur.

Use the trace feature of your prolog environment to see what happens step by step during the execution.

Phonogram

Answer 2

The actual reason for your problem is (\==)/2 within different/2. It succeeds simply too often. Replace it with dif/2 and you will get the expected behavior. dif/2 is available in many Prolog systems like SICStus, YAP, B, SWI. You can also define a safe approximation in ISO-Prolog like so:

dif_si(X, Y) :-
   X \== Y,
   ( X \= Y -> true
   ; throw(error(instantiation_error,dif_si/2))
   ).

(Also found in library(si) of Scryer.) Now, should the arguments be not sufficiently instantiated, you will get an Instantiation Error. Prolog aborts the computation and says: I have no idea! Which is far better than pretending it does have an idea while it has none.

Using dif_si/2 (previously called iso_dif/2) you will still have to place it at the end of the rule. But this time, Prolog will keep an eye on its correct usage.

?- dif_si(a,b).
   true.
?- dif_si([a,_],[b,_]).
   true.
?- dif_si([a,X],[X,b]).
   true.
?- dif_si([a,X],[a,X]).
   false.
?- dif_si([a,X],[X,X]).
   error(instantiation_error,dif_si/2).

Lyndel

Its not "monotonic" as you call it. For example I have "?- iso_dif(X,4), X=3." gives error. But "?- X=3, iso_dif(X, 4)." succeeds. Example derived from here: https://mcmap.net/q/376250/-undesirable-properties-of-clpb – Kiri

@j4nbur53: Please reread my answer. It covers exactly the case of errors quite clearly. – Lyndel

W.r.t.: "If you place it at the "end of the rule" you most likely end up in "datalog" and can use (\==)/2 anyway directly". That is a misunderstanding: When you use (\==)/2 alone, there is no guarantee that the results will be correct. But with iso_dif/2 they are correct as long as there are no errors. – Lyndel

The predicate ground/1 is probably even faster than the predicate (\=)/2 and it doesn't wake up co-routines. What is the business case exactly? Do you have working examples where iso_dif/2 is better than ground/1 guarded (\==)/2 or dif/2. – Kiri

@j4nbur53: Any comparison for lists! If I want to test for a list being "not empty" and the like – Lyndel

@MostowskiCollapse It might be worth noting though that there are cases where you can't replace dif/2 with iso_dif/2 and get away with mere rearrangement of the terms: e.g. multiple predicates using dif/2. – Idolatry