CODEWITHSUNDEEP
recursionprologgenealogy
small502
small502

Reputation: 43

Prolog "Not Enough Stack" Error

I'm writing a genealogy program in Prolog. Here are my rules:

father(X,Y):-male(X),parent(X,Y).
mother(X,Y):-female(X),parent(X,Y).
parent(X, Y) :- father(X, Y).
parent(X, Y) :- mother(X, Y).
ancestor(X,Y):-parent(X,Y).
ancestor(X,Y):-parent(X,Z),ancestor(Z,Y).
grandfather(X,Y):-male(X),parent(X,Z),parent(Z,Y).
grandMother(X,Y):-female(X),parent(X,Z),parent(Z,Y).
sibling(X,Y):-parent(Z,X),parent(Z,Y),X \= Y.
cousin(X,Y) :-ancestor(Z,X),ancestor(Z,Y),not(parent(Z,X)),not(parent(Z,X)),not(ancestor(X,Y)),not(ancestor(Y,X)).

However, whenever I query "ancestor" I get the error:

1815KB of Code Space (025D0000--02795D90)
  Current hole: 4FE40000--80040000
%
% PC: user:parent/2 at clause 1
%   Continuation: prolog:$do_yes_no/2 at clause 2
%    512KB of Global Stack (029C2000--02A4207C)
%    1265384KB of Local Stack (02A55E4C--4FE10000)
%    0KB of Trail (4FE10004--4FE10044)
%    Performed 1 garbage collections
% All Active Calls and
%         Goals With Alternatives Open  (Global In Use--Local In Use)
%
%         user:parent/2 (512KB--1265384KB)
%         user:parent/2 (512KB--1265384KB)...
%      ...user:parent/2 (512KB--1265377KB)
%  .....
     ERROR!!
     RESOURCE ERROR- not enough stack

This also causes problems for the "cousin" rule, which gives

%
%
% YAP OOOPS: likely bug in YAP, segmentation violation.
%
%

What could I have done wrong with my "ancestor" rule?

Upvotes: 1

Views: 216

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

Say that there is a fact:

male(adam).

If one now queries for:

parent(adam,cain).

Then it will evaluate:

parent(adam,cain) :-
    father(adam,cain).

Now father/2 will evaluate further to:

parent(adam,cain) :-
    father(adam,cain) :-
        male(adam),
        parent(adam,cain).

So we see it is stuck in an infinite loop: in order to validate/ground parent/2, it is defined in terms of parent/2, but there is no progression: we call it with exactly the same arguments.

So Prolog will get stuck in this infinite loop. Since ancestor/2 depends on parent/2, it suffers from the same symptoms as parent/2.

Try to remove the cyclic dependency.

Upvotes: 1

Related Questions