Thinking Recursively in Prolog

Expressing recursion declaratively…

Most programmers are familiar with recursion, at least at some level. In imperative languages, recursion is generally not needed for straightforward algorithms which can use looping control flow statements defined in the language. In pure functional languages, where looping constructs are not available, recursion is needed to do any sort of looping algorithm. Like a pure functional language, Prolog does not have looping constructs that are available when writing a program, so programming in Prolog requires being comfortable with recursion.

If you already are familiar with recursion as well as simple Prolog programming, you can skip over the “primer” sections and go directly to the “Recursion in Prolog” section.

A primer on recursion

A recursive function consists of one or more base cases and one or more recursive cases. A base case is a situation in which a problem is directly solvable. If no base case applies, then a recursive case creates one or more smaller problems of the same kind as the original problem to solve recursively and then use the recursive solution(s) to formulate the solution to the original problem. It is important to note that the recursive cases need to ensure that the subproblem(s) are closer to a base case situation, otherwise the recursion will not end.

The following pseudocode shows two problems being solved recursively. One of them, summing up the numbers from 0 to n, is perhaps more naturally expressed with a loop in an imperative language. Nevertheless, it can be done recursively in languages without looping constructs.

sum(n)
  if n is less than 0, then return 0
  if n is 0 or 1, then return n
  return n + sum(n-1)

The other, moving a tower of n disks from a source peg to a destination peg using a spare peg, is not as straightforward to express without recursion.

move_tower(n, source, destination, spare)
  if n is less than 1, then output “error”
  if n is 1, output “move top disk on {source} to {destination}”
  else
    move_tower(n-1, source, spare, destination)
    output “move top disk on {source} to {destination}”
    move_toweri(n-1, spare, destination, source)

For those not familiar with the problem, the tower has disks of different sizes, only one disk can be moved at a time, and no disk can ever be put on smaller disk. The recursive solution moves the smaller tower stacked on top of the largest disk to the spare peg, using the destination peg as the spare, then moves the largest disk directly to the destination, and finally moves the smaller tower from the spare peg to destination peg, using the source peg as the spare.

A model set of the Tower of Hanoi (with 8 disks), https://commons.wikimedia.org/wiki/File:Tower_of_Hanoi.jpeg • Attribution-Share Alike 3.0 Unported

A primer on Prolog

Prolog is a declarative language. A Prolog program is represented by query against a database, which consists of statements of fact, which are true all by themselves, and rules which state how to prove that something is true. Rules consist of a predicate name and parameters on the left-hand side and clauses on the right-hand side, usually separated by commas, meaning “and”, or semi-colons, meaning “or”. Capitalized words are variables, which Prolog tries to unify with values which will make the predicate true. If no consistent unification is possible, Prolog backtracks to try a different rule for a predicate or fails if all ways were tried.

As a simple example of programming in Prolog, let’s consider reasoning about animal classification. First, we have facts about particular animals, using descriptive predicate names and symbols to represent individual animals.

bear(b).
elephant(e).
frog(f).
ostrich(o).
salmon(s).

Now we can put together rules for some predicates: warm-blooded, cold-blooded, mammal, bird, fish, and amphibian. Note that this is only a small part of an overall animal classification program.

warm_blooded(A) :- mammal(A) ; bird(A).
cold_blooded(A) :- fish(A) ; amphibian(A).
mammal(A) :- bear(A) ; elephant(A).
bird(A) :- ostrich(A).
fish(A) :- salmon(A).
amphibian(A) :- frog(A).

Given the facts and predicate rules above, we can make queries such as finding all of the warm-blooded animals that are known and finding out whether a predicate is true or false for a particular individual.

?- warm_blooded(A).
A = b ;
A = e ;
A = o ;
false
?- mammal(o).
false
?- cold_blooded(s).
true

Note that in the first query, a variable is used and Prolog gives a successful binding of the variable which makes the query true. Entering a semi-colon forces Prolog to backtrack to try to find another successful binding, which it does. Once all possible bindings are found, it gives back false.

Recursion in Prolog

Thinking recursively in Prolog is no different than in other languages, even though Prolog is an extremely different language than an imperative or even purely functional language. Facts represent base cases. Predicate rules that state a condition for the predicate parameters in order to get a certain solution are also base cases, if they do not recursively call on the predicate.

For the summation problem, the first base case is that the sum from 0 to 1 is 1, represented by the first fact. The other base case, which is used to prevent infinite recursion as well as to indicate that the sum from 0 to 0 is 0, uses a rule with a comparison of the N input variable to 0. The last clause of the rule uses the cut, !, which prevents Prolog from backtracking once the clause before the cut is satisfied and therefore prevents the use of the recursive case when N is less than or equal to 0.

sum(1,1).
sum(N,0) :- N =< 0, !.

Recursive rules are used to state how to use the recursive predicate solution to get the overall solution. In the case of the summation problem, the rule needs to do some arithmetic: first, to set up the M variable to be one less than the input N, and second, to calculate the sum of N and the recursive solution, R, which becomes the overall solution, S. (The cut in the last clause prevents a duplicate solution when Prolog is asked for an alternate solution.)

sum(N,S) :- M is N-1, sum(M,R), S is N+R, !.

Running a query gives an answer for a particular value of N or for whether a particular sum is the correct answer for a particular N:

?- sum(10,Answer).
Answer = 55 ;
false
?- sum(10,56).
false

Note that, because of the arithmetic being done, queries where N is a variable and the sum is a particular value will result in an error, because N-1 cannot be calculated when N is a variable not bound to a concrete value.

The usual first Prolog exercise

Prolog is not typically used for algorithms involving calculating numeric values and outputting to the screen. While those algorithms can be done in Prolog, they feel clunky. Where Prolog excels is in logic-based algorithms where programs are put together using logical statements of “truth,” as shown in the simple animal classification example.

Usually, the first real exercise given to students learning Prolog is to encode a family tree using facts and predicate rules to define relationships between people in the tree.

Universiteitsbibliotheek UGent, CC BY-SA 4.0, via Wikimedia Commons

In the following simple example, there are six known people, represented by the symbols a through f appearing in a person fact. There are also three facts indicating that the parents of c and d are a and b and the parents of f are c and e. Notice that the database does not include information about the parents of a, b, and e.

%% The Facts %%

person(a). 
person(b). 
person(c). 
person(d).
person(e).
person(f).

parents(a,b,c).
parents(a,b,d).
parents(c,e,f).

For convenience, a predicate is defined to answer queries of the form: “is a parent of Child equal to Parent?” or “whom is a parent of Child?” The predicate takes input in the left-most parameter(s) and provides a solution as the right-most parameter, but this is simply a convention. There are two alternative ways to satisfy this predicate: either the parent is listed as the first parent for the child in a parents fact or the parent is listed as the second parent for the child in a parents fact.

%% Convenience Predicate %%

parentOf(Child,Parent) :- parents(Parent,_,Child) ; parents(_,Parent,Child).

The predicate involving recursion is the one for reasoning about a multi-generational link between two people. Following the same convention as mentioned above, this predicate can be read as “is an ancestor of Descendant equal to Ancestor?” or “whom is an ancestor of Descendant?” The first rule for the ancestorOf predicate is the base case, namely when the parentOf predicate is true for Descendant and Ancestor if either or both of the variables have been bound to values. (If neither parameter is bound to a value, Prolog chooses a parents fact from the database and binds the variables in the parentOf predicate, and therefore the ancestorOf predicate, to the appropriate values.)

%% Reasoning about Multi-Generational Relationships %%

ancestorOf(Descendant,Ancestor) :- parentOf(Descendant,Ancestor).

ancestorOf(Descendant,Ancestor) :- parentOf(Descendant,Middle), 
                                   ancestorOf(Middle,Ancestor).

The second rule is the recursive case, which finds a parent, Middle, of the descendant and then sets out to prove ancestorOf recursively to find a person (or confirm) who is an ancestor of that parent. Since the first clause of the rule has gone one generation up in the family tree, the recursion gets closer to the base case of finding a direct parent relationship between two people and thus ending the recursion up the family tree. (Exhausting all of the possible parents facts without success will also end the recursion.)

Since arithmetic is not involved, the ancestorOf predicate can also be used to answer queries of the form “whom is Ancestor an ancestor of?” but those queries would sound more natural as “whom is a descendant of Ancestor?” Another convenience predicate, descendantOf, can be defined which simply reverses the parameters when calling upon the ancestorOf predicate on the right-hand side of the rule.

%% Another Convenience Predicate %%

descendantOf(Ancestor,Descendant) :- ancestorOf(Descendant,Ancestor).

With the small family tree in the database, we can run some queries to explore the relationships between the people a through f.

The small family tree in the Prolog database, where arrows point from child to parent.

?- ancestorOf(f,Ancestor).
Ancestor = c ;
Ancestor = e ;
Ancestor = a ; 
Ancestor = b ;
false

?- ancestorOf(e,Ancestor).
false

The first query is finding all of the ancestors of person f, which include parents c and e and grandparents a and b. The second query demonstrates that no solution is found for an ancestor of e, since there are no parents facts in the database where e is the child.

?- descendantOf(d, Descendant).
false

?- descendantOf(c, Descendant).
Descendant = f ;
false

?- descendantOf(b, Descendant).
Descendant = c ;
Descendant = d ;
Descendant = f ;
false

Likewise, there are no parents facts in the database where d is a parent, so the first query to find a descendant of d cannot succeed. The second query shows that using the ancestorOf predicate with a known ancestor, c in this case, works just fine. Finding all of the descendants of b also works as expected.

For fun, let’s do the tower problem

Even though Prolog is better suited to logic-based programming, recursive programs involving output can still be done. To make the code easier to read, the output code can be put into its own predicate rule and used when a disk is to be moved from the source peg to the destination peg. The base cases include one for enforcing that the number of disks for a tower has to be one or more and one for a tower of one disk, which simply reports the move of that disk from source to destination.

%% Tower Helper and Base Cases %%

report_move(Source, Destination) :- write('move top disk on '), 
                                    write(Source), write(' to '), 
                                    write(Destination), nl.

move_tower(N,_,_,_) :- N < 1, write(‘ERROR’), nl, !.
move_tower(1,S,D,_) :- report_move(S,D).

The recursive case involves two recursive calls for a tower of one less disk, which will output moves for moving the smaller tower, first from source to spare and then from spare to destination. In between those two calls is the move of the largest disk, the bottom of the overall tower, from source to destination.

%% Tower Recursive Case %%

move_tower(N,S,D,X) :- M is N-1,
                       move_tower(M,S,X,D), 
                       report_move(S,D),
                       move_tower(M,X,D,S).

The query for a 3-disk tower outputs the instructions for moving the tower from the starting peg to the ending peg, using the spare peg.

?- move_tower(3, starting, ending, spare).
move top disk on starting to ending
move top disk on starting to spare
move top disk on ending to spare
move top disk on starting to ending
move top disk on spare to starting
move top disk on spare to ending
move top disk on starting to ending

Conclusion

For programmers used to imperative languages and loops, writing recursive declarative code might seem odd at first. The key to programming in Prolog is to learn to formulate base cases and recursive cases for any computation that would otherwise be done with a loop and then express them as facts, non-recursive rules, and recursive rules that are declared for a predicate. Understanding how Prolog answers queries using unification of variables and backtracking search for finding solutions helps de-mystify how the declarative code accomplishes the desired computation.

Next time: Recursion on lists!