How can I implement, "I am my own Grandpa", in Prolog?

Question

The following story is from N. Wirth's (1976) Algorithms + Datastructures = Programs.

I married a widow (let's call her W) who had a grown-up daughter (call her D). My father (F), who visited us quite often, fell in love with my step-daughter and married her. Hence, my father became my son-in-law and my step-daughter became my mother. Some months later, my wife gave birth to a son (S1), who become the brother-in-law of my father, as well as my uncle. This wife of my father, that is, my step-daughter, also had a son (S2).

I'm attempting to model these relations in prolog so eventually I'll be able to type:

| ?- grandfather(i,i).

And I'll be given a "Yes", or a "No" on whether or not I'm my own grandpa.

Here is the code I have written so far (grandpa.pl):

aunt(X,Y):-
    sibling(X,Z),
    parent(Z,Y),
    female(X).

brother(X,Y):-
    sibling(X,Y),
    male(X).

brother_in_law(X,Y):-
    child(X,Z),
    married(Z,W),
    parent(W,Y),
    not(sibling(X,Y)),
    male(X).

brother_in_law(s1,f).

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

daughter(X,Y):-
    parent(Y,X),
    child(X,Y),
    female(X).

daughter(d,w).

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

father(f,i).

father_in_law(X,Y):-
    child(X,Z),
    married(Y,Z),
    not(child(X,Y)),
    male(X).

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

grandmother(X,Y):-
    grandparent(X,Y),
    female(X).

grandfather(X,Y):-
    grandparent(X,Y),
    male(X).

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

married(X,Y):-
    wife(X,Y),
    female(X).

married(X,Y):-
    husband(X,Y),
    male(X).

married(i,w).
married(f,d).

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

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

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

sister(X,Y):-
    sibling(X,Y),
    female(X).

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

son(s1,w).
son(s2,d).

son_in_law(X,Y):-
    child(X,Z),
    not(child(X,Y)),
    married(Z,Y),
    male(X).

son_in_law(f,i).

step_daughter(X,Y):-
    child(X,Z),
    married(Z,Y),
    not(child(X,Y)),
    female(X).

step_daughter(d,i).

step_parent(X,Y):-
    married(X,Z),
    parent(Z,Y),
    not(parent(X,Y)).

step_father(X,Y):-
    step_parent(X,Y),
    male(X).

step_mother(X,Y):-
    step_parent(X,Y),
    female(X).

step_mother(d,i).

uncle(X,Y):-
    sibling(X,Z),
    parent(Z,Y),
    male(X).

uncle(s1,i).

Right now I'm having a lot of trouble with circular definitions so that I get into infinite loops when running the query: grandfather(i,i).

For example, I have:

(1 ms) yes {trace} | ?- grandfather(i,i). 1 1 Call: grandfather(i,i) ?
2 2 Call: grandparent(i,i) ?
3 3 Call: parent(i,_103) ?
4 4 Call: child(_127,i) ?
5 5 Call: parent(i,_151) ?
6 6 Call: child(_175,i) ?
7 7 Call: parent(i,_199) ?
8 8 Call: child(_223,i) ?
9 9 Call: parent(i,_247) ?
10 10 Call: child(_271,i) ?
11 11 Call: parent(i,_295) ?
12 12 Call: child(_319,i) ?
13 13 Call: parent(i,_343) ?
14 14 Call: child(_367,i) ?
15 15 Call: parent(i,_391) ?
...

This is because child defines itself as has having a parent, and parent defines itself has having a child (as you'll see in the above predicates I posted).

Can anyone help me re-define my predicates for these relationships so that I can determine if I'm my own grandpa?

Answer 1

I removed everything that was unnecessary in your code and changed a few things and this is what I ended up with:

% married(Husband, Wife)
married(i,w).
married(f,d).

One would suppose that married(X,Y) :- married(Y,X), but it leads to nasty circular proofs, so we will just put the husband first by convention.

About parenthood, similar problem arises. We need to consider step parents as real parents, because the riddle depends on it. We know you can never be your own biological ancestor!

However, parent(X,Y) :- parent(Z,Y), married(X,Z) runs into the same problems, so I just made bio_parent denote biological parenthood.

bio_parent(f,i).
bio_parent(w,d).
bio_parent(w,s1).
bio_parent(i,s1).
bio_parent(d,s2).
bio_parent(f,s2).

Note that we have to be explicit about both parents, as there is no way to conclude biological parenthood from marriage! Also, your way of specification was problematic. You had something like:

son(X,Y) :- child(X,Y), male(X).
son(a,b).

However, from these rules Prolog could not infer child(a,b), so you ended up whith sons who were not children! This occured a few times in your code. If you derive b from a, always state a as the fact! At first glance, this might seem like a shortcoming of Prolog's, but it isn't. Remember that every clause is just one way of proving a certain predicate. In the example above, you stated that every male child is a son, and also a just so happens to be a son of b. Nowhere it is said that being a male child is the only way that someone could be a son though, a might just be the exception.

The next one is a bit wordy as our definition of married forces us to treat step fathers separately from step mothers. We unify them to step parents immediately though.

step_father(X,Y) :- married(X,Z),bio_parent(Z,Y),\+bio_parent(X,Y).
step_mother(X,Y) :- married(Z,X),bio_parent(Z,Y),\+bio_parent(X,Y).
step_parent(X,Y) :- step_father(X,Y).
step_parent(X,Y) :- step_mother(X,Y).

As I said above, we need to consider step-parents as parents!

parent(X,Y) :- step_parent(X,Y).
parent(X,Y) :- bio_parent(X,Y).

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

There were also some other mistakes in your code which I took out, I just show you some examples so you can learn from it.

First, here you say that female wives are married, and male husbands are married. So, male wives would be unmarried. Should be the other way round though, female married people are called wives!

% wrong:
%
% married(X,Y):-
%    wife(X,Y),
%    female(X).
%
% married(X,Y):-
%    husband(X,Y),
%    male(X).
% 
% right:
% wife(X,Y) :- married(Y,X). % according to our new definition of 'married'
% husband(X,Y) :- married(X,Y).

Here I added the last line, as you don't usually consider yourself your own sibling:

% sibling(X,Y):-
%    parent(Z,X),
%    parent(Z,Y),
%    X \= Y. % added this

Those last two are facts on the wrong predicate again. You basically override Prolog's deduction with them. They should be deducted, not stated as facts!

% son_in_law(f,i).
% step_mother(d,i).

Now, try the program like this. And don't be surprised: You will not be the only one to be their own grandparent! ;-)

Answer 2

My prolog course has been a long long time ago but what about removing

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

and just replacing any usage of parent(A,B) with child(B,A)? You can still add facts about parents because the inverse rule is still available - you could also remove that one but in that case you cannot use any facts about parents anymore and you'll have to write all your facts as child(a,b) as well.

It's the same isn't it?

Answer 3

Note that my knowledge of Prolog is old (and never that deep)...

I think you need to make parent (or child) primary (not dependent on other relationships).

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

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

is what is probably causing the loops.

Answer 4

Here are the facts and rules

couples(i,w).
mother_of(w,d).
father_of(f,i).
couples(f,d).
son_in_law(f,i).
mother_of(d,i).
mother_of(w,s1).
mother_of(d,s2).
grand(F,C):- son_in_law(F,C),couples(H,D),mother_of(D,C).
grand(F,C):- father_of(F,D),father_of(D,C).

query

?-grand(i,i).