Search code examples
prologfailure-slice

Prolog: Out of local stack error

Consider the following code (taken from Introduction to Prolog by RP Suri):

/* A set of father-child pairs declared */
father("Motilal", "Jawaharlal").
father("Motilal", "Vijayalakshmi").
father("Motilal", "Krishna").
father("Jawaharlal", "Indira").
father("Ranjit", "Tara").
father("Ranjit", "Lekha").
father("Ranjit", "Rita").
father("Feroz", "Sanjay").
father("Feroz", "Rajiv").
father("Sanjay", "Varun").
father("Rajiv", "Rahul").
father("Rajiv", "Priyanka").

/* Mothers declared */
wife_of("Swaruprani", "Motilal").
wife_of("Kamla", "Jawaharlal").
wife_of("Vijayalakshmi", "Ranjit").
wife_of("Indira", "Feroz").
wife_of("Maneka", "Sanjay").
wife_of("Sonia", "Rajiv").
wife_of("Priyanka", "Robert").

/* Predicates declared */
mother(M, C) :- wife_of(M, Hus) , father(Hus, C).

parent(P, C) :- mother(P, C) ; father(P, C).

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- ancestor(X, Z) , parent(Z, Y).

Now if I query

ancestor("Motilal", X)

I get output as:

?- ancestor("Motilal", X).
X = "Jawaharlal" ;
X = "Vijayalakshmi" ;
.
.
.
X = "Priyanka" ;

(which is the correct output), after which the program stops and a few seconds later I get the message:

ERROR: Out of local stack

A similar thing happens when I query

ancestor(X, "Motilal").

This should return nothing, but the prompt again disappears for a few seconds followed by the same error message. What is the problem in the code?

Solution

  • To understand the problem in your code there is no need to look at your entire program. Instead it suffices to look at a tiny fraction that is responsible for non-termination:

    ?- ancestor(X, 'Motilal'), false.

ancestor(X, Y) :- false, parent(X, Y).
ancestor(X, Y) :- ancestor(X, Z) , false, parent(Z, Y).

    This fragment already does not terminate, and thus the entire program does not terminate. No matter what you wrote in the other parts! So you need to change something in the remaining part. Otherwise, the error will persist.

    For more see .

    Do you see what you need to change?

    Put the goal parent(Z, Y) in front!

    BTW, it is common in Prolog to use single-quoted atoms in such a situation, since this is much more efficient!