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

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.