CODEWITHSUNDEEP
prologfailure-slice
Gonzalo Solera
Gonzalo Solera

Reputation: 1192

Understanding recursivity in Prolog

I have this example:

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

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

It works great and I understand it. This is a solution of a little exercise. My solution was the same but changing:

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

That is, changing child for descend in the second descend rule.

If I query descend(X, Y). in the first solution, I obtain:

?- descend(X, Y).
X = anne,
Y = bridget ;
X = bridget,
Y = caroline ;
X = caroline,
Y = donna ;
X = anne,
Y = caroline ;
X = anne,
Y = donna ;
X = bridget,
Y = donna ;
false.

Which is correct. But if I query with my solution the same, I get:

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

It doesn't say X = bridget,Y = donna ; and it also overflows. I understand why it overflows. What I don't understand is why it doesn't find this last relationship. Is it because of the overflow? If so, why? (Why is the stack so big with such small knowledge base?).

If I query descend(bridget, donna) it answers yes.

I'm having problems imagining the exploration tree...

Apart from that question, I guess that the original solution is more efficient (ignoring the fact that mine enters in a infinite loop at the end), isn't it?

Thanks!

Upvotes: 3

Views: 169

Answers (1)

false
false

Reputation: 10102

I'm having problems imagining the exploration tree...

Yes, that's quite difficult in Prolog. And it would be worse if you had a bigger database! But most of the time it is not necessary to envision the very precise search tree. Instead, you can use several quite robust notions.

Remember how you formulated your query. You looked at one solution after the other. But what you really were interested in was the question whether or not the query terminates. You can go for it without looking at the solutions by adding false.

?- descend(X, Y), false.
ERROR: Out of local stack

This query can never be true. It can either fail, overflow, or loop, or produce another error. What remains is a very useful notion: Universal termination or as in this case non-termination.

This can be extended to your actual program:

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

If this fragment called a does not terminate, then also your original program does not terminate. Look at this miserable remainder of your program! Not even child/2 is present any longer. And thus we can conclude that child/2 does not influence non-termination! The Y occurs only once. And X will never cause a failure. Thus descend/2 terminates never!

So this conclusion is much more general than just a statement about a specific search tree. It's a statement about all of them.

If you still want to reason about the very precise order of solutions, you will have to go into the very gore of actual execution. But why bother? It's extremely complex, in particular if your child/2 relation contains cycles. Chances are that you will confuse things and build inaccurate theories (at least I did). No need for another cargo cult. I, for one, have given up to "step through" such myriads of detail. And I do not miss it.

Upvotes: 6

Related Questions