Prolog family tree

2
votes

I'm trying to write a family tree program in Prolog for my homework. This is a part of the code.

/** a sample fact **/
parents(someone, someoneelse, child).

/** are M and F parents of the children in the given list? **/
parents(M,F,[]) :- parents(M,F,_).
parents(M,F,[First|Rest]) :- parents(M,F,First), parents(M,F,Rest).

/** are M and F parents? **/
parents(M,F) :- parents(M,F,_).

When I use a query that matches the fact, above code works.

   [trace] 25 ?- parents(someone,someoneelse).
       Call: (6) parents(someone, someoneelse) ? creep
       Call: (7) parents(someone, someoneelse, _G586) ? creep
       Exit: (7) parents(someone, someoneelse, child) ? creep
       Exit: (6) parents(someone, someoneelse) ? creep
    true 
    .

But when I try this:

[trace] 26 ?- parents(aa, bb).
   Call: (6) parents(aa, bb) ? creep
   Call: (7) parents(aa, bb, _G541) ? creep
   Call: (8) parents(aa, bb, _G541) ? creep
   Call: (9) parents(aa, bb, _G541) ? creep
   Call: (10) parents(aa, bb, _G541) ? 
...

it doesn't work, it enters an infinite loop. What is it that I'm doing wrong here?

Edit: I've changed the code as such:

/** a sample fact **/
parents(someone, someoneelse, child).

/** are M and F parents of the children in the given list? **/
parents(M,F,[]).
parents(M,F,[First|Rest]) :- parents(M,F,First), parents(M,F,Rest).

/** are M and F parents? **/
parents(M,F) :- parents(M,F,A), not(A=[]).

Now what I get is this:

[trace] 3 ?- parents(a,b).
   Call: (6) parents(a, b) ? creep
   Call: (7) parents(a, b, _G514) ? creep
   Exit: (7) parents(a, b, []) ? creep
^  Call: (7) not([]=[]) ? creep
^  Fail: (7) not(user: ([]=[])) ? creep
   Redo: (7) parents(a, b, _G514) ? creep
   Call: (8) parents(a, b, _G508) ? creep
   Exit: (8) parents(a, b, []) ? creep
   Call: (8) parents(a, b, _G509) ? creep
   Exit: (8) parents(a, b, []) ? creep
   Exit: (7) parents(a, b, [[]]) ? creep
^  Call: (7) not([[]]=[]) ? creep
^  Exit: (7) not(user: ([[]]=[])) ? creep
   Exit: (6) parents(a, b) ? creep
true 
.

I don't understand why it goes to redo after fail now. Any ideas?

2
prolog

2 Answers

0
votes

I have a feeling that you are confusing two different predicates into one:

/** a sample fact **/
parents(someone, someoneelse, child).

/** are M and F parents of any child? **/
parents(M,F) :- parents(M,F,_).

/** are M and F parents of the children in the given list? **/
parents_of_all_children(M,F,[]).
parents_of_all_children(M,F,[First|Rest]) :-
    parents(M,F,First), parents_of_all_children(M,F,Rest).

Then, your queries make sense:

?- parents(someone, someoneelse, C).
C = child.
%-- someone & someoneelse have child "child"

?- parents(A, B).
A = someone,
B = someoneelse.
%-- all possible parent pairs out there

?- parents(aa, bb).
false.
%-- do "aa" & "bb" form a parents pair?
0
votes

You have to stop the search. Prolog will go through all the rules and find a match. If it matches, then it will go through the expansion and repeat the process.

The 2nd line is the cause of inf loop, since don't care (from the last rule) is mapped to [].

If you want to find out whether a pair is parent of any child or not, you just remove the 2 middle rules:

parents(M,F,[]) :- parents(M,F,_).
parents(M,F,[First|Rest]) :- parents(M,F,First), parents(M,F,Rest).