Prolog - recursing down family tree

Question

I am trying to write a Prolog program that will print out the male successors of British Royalty in order. My attempt so far:

son(elizabeth, charles).
son(charles, william).
son(charles, henry).
son(elizabeth, andrew).
son(elizabeth, edward).
son(edward, severn).
successor(X, Y) :- son(X, Y).
successor(X, Y) :- son(X, C), successor(C, Y).

The successor function doesn't quite do what I want: the current output is this:

successor(elizabeth, Y).
Y = charles ;
Y = andrew ;
Y = edward ;
Y = william ;
Y = henry ;
Y = severn ;
false.

The first rule makes all three immediate children print out, then the second rule prints out all the descendants. But the descendants of the first child should come before the second immediate child, like this:

successor(elizabeth, Y).
Y = charles ;
Y = william ; % william and henry should come before andrew
Y = henry ;
Y = andrew ;
Y = edward ;
Y = severn ;
false.

This is my first Prolog program, and I am at a loss for how to express the right relationship. Can anyone give me an idea or pointers to resources that would be helpful to me?

Answer 1

Your rule set looks good to me, it's giving you the right results, it's just printing them as it deduces them, which makes the order seem incorrect. Work through the results on paper and you will likely get a similar result.

Answer 2

You said:

The first rule makes all three immediate children print out, then the second rule prints out all the descendants.

For any given predicate (such as successor/2), PROLOG will generally evaluate all the possible solutions for the 1st clause, then the next, etc. up to the last clause, in that order. Therefore, PROLOG will behave exactly as you've suggested above - solutions to immediate children will be found first, as the first clause of successor/2 does just that, and the second clause finds the descendants. If you were after a different order, try re-ordering the clauses (i.e.);

successor(X, Y) :- son(X, C), successor(C, Y).
successor(X, Y) :- son(X, Y).

This will cause PROLOG to evaluate to:

?- successor(elizabeth, Y).
Y = william ;
Y = henry ;
Y = severn ;
Y = charles ;
Y = andrew ;
Y = edward.

i.e., all descentants before immediate children.

The ordering you've suggested as wanting, however, can't be achieved through a simple reordering of these subgoals. Instead, consider the various tree traversal methods; i.e., in-order, pre-order and post-order. You could write a (simple) program which is capable of walking the tree structure in various different ways, instead of the default evaluation order for PROLOG. For example, consider the following new definition of successor/2:

successor(Parent, [Son|SonDescendents]) :-
    son(Parent, Son),
    successor(Son, SonDescendents).

This clause seeks to depth-first populate a list of children under a son, and will backtrack to find all solutions.

successor(NonParent, []) :-
    \+ son(NonParent, _).

This next clause takes care of the base-case whereby the given individual does not have any sons, therefore no descendants enter the result list (empty).

Evaluating this gives:

?- successor(elizabeth, S).
S = [charles, william] ;
S = [charles, henry] ;
S = [andrew] ;
S = [edward, severn] ;
false.

ps. I highly recommend the following texts for learning PROLOG:

The Art of Prolog, by Leon Sterling and Ehud Shapiro

The Craft of Prolog, by Richard O'Keefe

Programming in Prolog, by Clocksin and Mellish

Answer 3

As rati noted above, Prolog queries are resolved by choosing a rule, recursively evaluating it using depth-first search, then choosing the next rule and repeating the process. However, the particular rules you're starting with actually result in a breadth-first search of the family tree, which, as you noted, does not give output that matches the actual line of succession. Instead, you want to do a depth-first traversal of the royal family tree. This version gives the result you're looking for:

successor(X, Y) :- son(X, Z), (Y = Z; successor(Z, Y)).

Using this rule, Prolog resolves the query successor(X, Y) roughly as follows:

• For each Z who is a son of X:
  • Bind Y to Z, giving Z as a solution.
  • The ; operator functions as a logical OR, so now Y is unbound and successor/2 is called recursively to get the successors who are sons of Z.

And yes, please do try to get a copy of the Art of Prolog. It's not the easiest programming book to read, but I found it extremely helpful in my (ongoing) attempt to understand logic programming. There seem to have been some cheap hardcover copies of the 1994 edition floating around eBay lately.