4. Recursion and Structures

Recursion

If we want to find all the descendants of a particular person, we could first find all the immediate descendants using the parent relation. We could then repeatedly find all the descendants of the descendants and so on. In Prolog this is done using recursion .

We will now add a recursive definition for the rule descendant(Person, Descendant) which succeeds when Descendant is a direct or indirect descendant of Person. First the base case:

descendant(Person, Descendant) :-
    parent(Person, Descendant).

How would you phrase this rule in English?

Here is the recursive case:

descendant(Person, Descendant) :-
    parent(Person, Child),
    descendant(Child, Descendant).

Add the descendant predicate (both the base case and the recursive case) to the family.pl program and re-consult.

Find all the descendants of Irene using the new predicate.

To find the ancestors of Kyle you could use:

 ?- descendant(Ancestor, kyle).

However, as an exercise, write a predicate, ancestor(Person, Ancestor), to do the same thing without using descendant. The predicate ancestor should use only the parent predicate and recursion.

Confirm that ancestor(Person, Ancestor) gives the same results as descendant(Ancestor, Person).

Structures and Pattern Matching

So far we have only seen terms which are atoms . A term can also be a structure .

Structures in Prolog are objects that have several components, but are treated as a single object. To combine the components into a single structure, we choose a functor and use it to group the components together. (See also Bratko, section 2.1.3. and section 2.2)

The following rule, test, takes two arguments. The first is a stucture with three components using functor, f. The rule succeeds if (1) the first and second component of the structure are the same, and (2) the last component of the structure is the same as the last argument.

test(f(A, A, B), B).

Enter the rule into a file called, say, test.pl, start up Prolog with prolog -s test.pl and try the following queries. Before each query write down what you expect the resultss to be, then try it. If your expectations fail, you should try to understand what is happening. (See also Bratko, section 2.2)

 ?- test(f(1, 1, 2), 2).
 ?- test(f(1, 2, 3), 3).
 ?- test(f(1, 1, 2), 3).
 ?- test(f(1, X, 2), 2).
 ?- test(f(1, _, _), 2).
 ?- test(f(1, X, 2), Y).
 ?- test(g(1, X, 2), Y).
 ?- test(f(X, 1, Y, 1), 1).
 ?- test(f(X, 1, Y, 1)).
 ?- test(f(X, Y, Z), A).
 ?- test(f(X, Y), A).
 ?- test(X, a).

The Climbing Database

In the next exercise you will create a new Prolog program from scratch and experiment with structures and pattern matching.

We will create a program to store predicates for a rock climbing database. In this database there are particular climbs which have a name and a grade. We also want to track who first ascended the climb and the date they did it.

Use your text editor to create a new file, climbing.pl, and add the following facts to the file.

 % male(Person)
 % female(Person)
 %
 % The argument term for these predicates is a structure
 % representing a person. It is in the form:
 % person(FirstName, LastName)
 %
 male(person('Will', 'Bilson')).
 male(person('Jim', 'Fried')).
 male(person('Barry', 'Drake')).
 female(person('Dot', 'Kanga')).
 % climb(Name, Grade, FirstAscentPerson, FirstAscentDate).
 %
 % This predicate records the climb details.
 %
 climb('Happy Go Lucky', 15, person('Barry', 'Drake'), date(11, 9,1996)).
 climb('High n Dry', 16, person('Jim', 'Fried'), date(1, 4,2001)).
 climb('Roller', 21, person('Will', 'Bilson'), date(15, 9,2005)).
 climb('Naturally', 14, person('Barry', 'Drake'), date(11,10,1997)).
 climb('The Picnic', 10, person('Dot', 'Kanga'), date(14, 2,1953)).

You should also add some comments at the start of your program describing its purpose, author and date. Comments start with the percent sign (%) and continue to the end of the line.

Single quotes ' are used here to construct atoms; in SWI Prolog double quotes " are used to build strings. You can read about the differences in the manual .

We will start with two simple queries which show the males and females in the database:

% swipl -s climbing.pl

 ?- female(Person).
 ?- male(Person).

Note that the Person variable gets bound to a structure .

We can access the individual components of a structure by using Prolog's pattern matching ability. The following queries the last names of all the males:

 ?- male(person(_, LastName)).

Recall that the underscore (_) is a special variable where the results are not printed and different instances are not required to match.

We can use this technique to ask who did the first ascent of "Roller":

 ?- climb('Roller', _, person(FirstName, LastName), _).

Notice that in order to find a fact in the database which would answer the question, Prolog performed a quite complex matching operation between the structures in the query and those in the head of the clause .

Write and execute a query to find the climbs first climbed by Barry Drake.

Write and execute a query to find the climbs first climbed by a female. (It is okay if your query returns other information besides the climb name.)

Next we would like to know which climbs were first climbed before "High n Dry". To do this we need to work out how to compare dates. The following predicate tells us when the first date comes after the second.

later(date(Day1, Month, Year), date(Day2, Month, Year)) :-
    Day1 > Day2.
later(date(_, Month1, Year), date(_, Month2, Year)) :-
    Month1 > Month2.
later(date(_, _, Year1), date(_, _, Year2)) :-
    Year1 > Year2.

Add this new predicate to climbing.pl and re-consult.

Test the new predicate by finding those climbs which were first climbed before "High n Dry". (It is okay if your query returns other information besides the climb name.)