Search code examples
prologtransitive-closurefailure-slice

Understanding prolog better

I'm trying to understand Prolog and how the resolution algorithm it uses. I have this example that I found:

hates(1, 2).
hates(2, 3).
hates(3, 4).
jealous(A, B) :- jealous(A, C), jealous(C,B).
jealous(A,B) :- hates(A,B).

But when I try to say that jealous(1,4) then it keeps overflowing and never yields true, which is weird as if 1 hates 2 and 2 hates 3 and 3 hates 4, then 1 should also hate 4.

But but I tried change it so it was like this:

hates(1, 2).
hates(2, 3).
hates(3, 4).
jealous(A,B) :- hates(A,B).
jealous(A, B) :- jealous(A, C), jealous(C,B).

And then it works when I say jealous(1,4).

Solution

  • And then it works when I say jealous(1,4)

    No, it did not. Or, well, kind of. Just type SPACE to see that it loops again. And what about jealous(4,1) which loops immediately?

    To understand this, it suffices to look at a very tiny part of your program, namely this one:

    jealous(A,B) :- false, hates(A,B).
jealous(A, B) :- jealous(A, C), false, jealous(C,B).

    Note the variable B which is never used in the visible part. So it cannot have any influence on termination. And note A which is just handed to the first goal. So both arguments have no influence in this program. Thus this program terminates never. It might find a solution here and there, but it will never terminate when asked to find all of them.

    This tiny fragment is called a and if it does not terminate so does your entire program! That is, there is no need to read your definition of hates/2 at all1.

    If you want to master Prolog's execution, you need to master that notion of a failure slice. For, experienced programmers do this more or less by intuition. Thus, they do not read the entire program, they just scan for relevant parts. The nice thing here in Prolog being that there is a truly causal relationship between such a slice and the entire program.

    To solve this problem, you need to change something in the part that has been highlighted by the failure slice. Here is one such possible change:

    jealous(A,B) :- hates(A,B).
jealous(A, B) :- hates(A, C), jealous(C,B).

    But once you have cycles in hates/2, this no longer works. Then, consider closure/3:

    jealous(A, B) :-
   closure(hates, A, B).

    Another way is to use tabling. But be warned, tabling solves this one problem but will no longer work in the context of constraints (which sooner or later you will encounter).

    1) provided you have a pure monotonic program as you do.