Replacing prolog base case with recursive call

Question

I am new to Prolog, started learning it recently using the awesome book Learn Prolog Now!. There is something I don't fully understand and it's really bugging me. One of the exercises questions is

We have the following knowledge base and predicate:

child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).

descend(X,Y)  :-  child(X,Y).
descend(X,Y)  :-  child(X,Z),
                  descend(Z,Y).

What would happen if we change the predicate to the following:

descend(X,Y)  :-  child(X,Y).
descend(X,Y)  :-  descend(X,Z),
                  descend(Z,Y).

I know that this would cause an infinite recursion on false cases, I can't fully understand why though.

If I understand correctly, in the first case above if a false query is given child(X,Z) would exhaust all its options trying to unify multiple elements to Z then fail, backtrack to the previous X then try option for Z again that would satisfy child(X, Z). (Please correct me if I'm wrong).

I am not sure why the same won't happen though for the second definition of the descend predicate.

Answer 1

Let's take a moment to reduce the snippet you show to a fragment that clearly shows a reason for the nontermination.

The initial fragment is the whole program you posted:

descend(X,Y)  :-  child(X,Y).
descend(X,Y)  :-  descend(X,Z),
                  descend(Z,Y).

Now, we insert false/0 at some places. For example:

descend(X,Y)  :-  false, child(X,Y).
descend(X,Y)  :-  descend(X,Z),
                  false,
                  descend(Z,Y).

I am using strikeout text to indicate parts of the program that have no influence on termination. That is, we actually end up with:

descend(X,Y)  :-  descend(X,Z).

This fragment alone already causes nontermination. No pure clause you add to this, and nothing that follows the single goal can prevent it! Hence, to make this terminating, you must change this fragment.

See failure-slice for more information.

Answer 2

For illustration purposes, let's consider the pair (a,b) since it is not covered by your facts child/2. If you issue the query...

?- descend(a,b).

... Prolog will try the first clause of descend/2, with the substitutions X=a and Y=b:

descend(a,b)  :-  child(a,b).

... and fail, since the goal child(a,b) fails. Then Prolog moves on to the second clause of descend/2:

descend(a,b) :-

... where a new variable Z is introduced and descend/2 is called recursively:

descend(a,b)  :-  descend(a,Z),

Prolog now tries the first clause of descend/2...

descend(a,Z)  :-  child(a,Z).

... and fails, because the goal child(a,Z) fails. So Prolog tries the second clause of descend/2:

descend(a,Z) :-

... where a new variable, let's call it Z2 (depending on the Prolog-system you are using it will be a name like _G3325 (SWI), _A (YAP), ... but for this example let's stick with the more illustrative Z2) is introduced and the recursive goal is called:

descend(a,Z)  :-  child(a,Z2).

Since there's always a new variable that can be introduced, the above definition of descend/2 will loop until you run out of stack. With similar reasoning you can comprehend why the queries...

?- descend(anne,bridget).
true ;
ERROR: Out of local stack

?- descend(X,Y).
X = anne,
Y = bridget ;
X = bridget,
Y = caroline ;
X = caroline,
Y = donna ;
X = donna,
Y = emily ;
X = anne,
Y = caroline ;
X = anne,
Y = donna ;
X = anne,
Y = emily ;
ERROR: Out of local stack

... loop as well after producing answers.

EDIT:

See @mat's excellent answer for a much more elegant way to identify the fragment, that causes non-termination.

Answer 3

The easier way to help you instead of writing a long and detailed explanation here that is just reproducing the run of a trace step by step is to just suggest that you use the graphical trace built into SWI-Prolog and do the stepping yourself.

Before showing you that one change you should make to the code is to rename the predicate for the second example so you have both of them available at the same time.

child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).

descend(X,Y) :-
    child(X,Y).

descend(X,Y) :-
    child(X,Z),
    descend(Z,Y).

descend_2(X,Y) :-
    child(X,Y).

descend_2(X,Y) :-
    descend_2(X,Z),
    descend_2(Z,Y).

Start up SWI-Prolog

Load up your source code. I personally use consult/1 e.g.

consult("C:/Users/Eric/Documents/Projects/Prolog/SO_question_100.pl").

Turn on the graphical tracer with gtrace/0

gtrace.

Enter your query, e.g.

descend_2(anne,bridget).

This will start a second screen with the graphical debugger.

At this point I would have to give a long explanation of how to use the graphical debugger and what all of the different items in the display means but here is one part that is of note. I reached it by just pressing the space a few times to single step. Continue this until you hear a chime. When you hear the chime it means you need to switch to the other screen and give input, in this case just press space bar to accept the answer. Then switch back to the screen with the graphical debugger and continue to press the space bar to single step.

The part of interest is the stack on the right. I put a green box around one of them that shows a Y like icon, which represents a choice point. If you keep doing the space bar you will notice that the stack keeps growing with more choice points.

So what is happening is that you code has a choice but the choice is not getting resolved. Take a look at left recursion and Prolog/Recursive Rules