Infinite recursion in SWI-Prolog

Question

I am trying to define a family tree and the relationships between its nodes basing their definitions on three predicates: male/1, female/1 and parent_of/2.

I have defined the notions of ascendant, descendant, father, mother, son, daughter, grandfather, grandmother, aunt, uncle and cousin. Any new definition can't be based on the notion of "brother/sister of", but only on the previous ones.

This is the code:

male(daniel).
male(miguelangel).
male(mario).
male(mahmoud).
male(esteban).
male(enrique).
male(javier).
male(miguelin).

female(diana).
female(hengameh).
female(vicenta).
female(mahvash).
female(angeles).
female(mexicana).
female(eloina).
female(esmeralda).
female(cristina).
female(otilia).

parent_of(miguelangel, daniel).
parent_of(miguelangel, diana).
parent_of(hengameh, daniel).
parent_of(hengameh, diana).
parent_of(mario, miguelangel).
parent_of(mario, esteban).
parent_of(mario, eloina).
parent_of(mario, angeles).
parent_of(mario, otilia).
parent_of(vicenta, miguel).
parent_of(vicenta, esteban).
parent_of(vicenta, eloina).
parent_of(vicenta, angeles).
parent_of(vicenta, otilia).
parent_of(mahmoud, hengameh).
parent_of(mahvash, hengameh).
parent_of(enrique, javier).
parent_of(angeles, javier).
parent_of(cristina, miguelin).
parent_of(otilia, cristina).
parent_of(eloina, esmeralda).

% Rules

ancestor(X, Y) :-
    parent_of(X, Y);
    parent_of(X, Z),
    ancestor(Z, Y).

descendant(X, Y) :-
    ancestor(Y, X).

father(X, Y) :- 
    parent_of(X, Y),
    male(X).

mother(X, Y) :-
    parent_of(X, Y),
    female(X).

son(X, Y) :-
    parent_of(Y, X),
    male(X).

daughter(X, Y) :-
    parent_of(Y, X),
    female(X).

grandfather(X, Y) :-
    parent_of(X, Z),
    parent_of(Z, Y),
    male(X).

grandmother(X, Y) :-
    parent_of(X, Z),
    parent_of(Z, Y),
    female(X).

aunt(X, Y) :-
    (grandfather(Z, Y) ; grandmother(Z, Y)),
    (father(Z, X) ; mother(Z, X)),
    not(parent_of(X, Y)),
    female(X).

uncle(X, Y) :-
    (grandfather(Z, Y) ; grandmother(Z, Y)),
    (father(Z, X) ; mother(Z, X)),
    not(parent_of(X, Y)),
    male(X).

cousin(X, Y) :-
    ((uncle(Z, Y), parent_of(Z, X)) ; (cousin(P, Y), descendant(X, P)));    
    ((aunt(Z, Y), parent_of(Z, X)) ; (cousin(P, Y), descendant(X, P))).

For the sake of clarity I have represented through an image the part of the tree where I'm having issues:

enter image description here

When I write

cousin(X, Y) :-
    ((uncle(Z, Y), parent_of(Z, X)));   
    ((aunt(Z, Y), parent_of(Z, X))).

instead of

cousin(X, Y) :-
    ((uncle(Z, Y), parent_of(Z, X)) ; (cousin(P, Y), descendant(X, P)));    
    ((aunt(Z, Y), parent_of(Z, X)) ; (cousin(P, Y), descendant(X, P))).

I get

?- cousin(miguelin, daniel).
false.

?- cousin(cristina, daniel).
true .

which are valid results. But when I introduce the recursive definitions on the right, as stated on the first (big) code, for saying that the descendants of the cousins of Y are also the cousins of Y, the program crashes:

?- cousin(miguelin, daniel).
ERROR: Out of local stack

I don't understand why. If I look at the image, it makes sense (at least to me) that recursive definition, and miguelin should be now the cousin of daniel (since he is a descendant of another cousin of daniel, which is cristina). I also tested it "manually" and I got the right result:

?- cousin(cristina, daniel), descendant(X, cristina).
X = miguelin ;

What's wrong with the definition?

lurker lurker · Accepted Answer · 2014-03-29T23:38:43

One problem with the cousin/2 predicate is that the recursion is occurring before you resolve the descendant/2, and cousin/2 is having an infinite recursion issue in this context. As a simple way to fix that, you can swap them around. Also, you have one redundant recursive subclause. So the modified cousin/2 predicate would be:

cousin(X, Y) :-
    (uncle(Z,Y), parent_of(Z,X)) ;
    (aunt(W,Y), parent_of(W,X)) ;
    (descendant(X,P), cousin(P,Y)).

And then you get:

?- cousin(miguelin, daniel).
true ;
false.

?- cousin(cristina, daniel).
true ;
false.

?-

Infinite recursion in SWI-Prolog

1 Answers