When writing a recursive procedure in Prolog, there will always be
at least two rules to code: at least one rule for the *base case*,
or non-recursive case, and at least one rule for the *recursive case*.

Typically the base-case rule(s) will deal with the smallest possible
example(s) of the problem that you are trying to solve - a list with
no members, or just one member, for example. If you are working with
a tree structure, the base case might deal with an `empty`

tree, or a tree with just one node in it (like
`tree(empty, a, empty)`

).

To write the recursive case rule(s), you need to think of how
the current case of the problem could be solved assuming you had already
solved it for all smaller cases. For example, if you were adding a list
of 10 numbers, and you had a way of summing the last 9 numbers in the
list, then you would do so, then add on the first number on the list.
(It might seem more natural to add up the *first* 9 numbers and then
add the last number to the subtotal, but in Prolog it is easy to access
the first item in the list, but not the last.)

Here's an example of how to apply this to adding up a list of numbers. The comments beginning %% would not normally appear - they are there this time to help you match the scheme described in the previous paragraphs to the code.

% addup(List, Sum) % Binds Sum to the sum of the numbers in the list. % Assumes that each member of the list really is a number. % The List must be instantiated at the time addup is called. % Example of use: % addup([1,2,3,4], X)? % X = 10 %% base case addup([], 0). % sum of the empty list of numbers is zero %% recursive case: if the base-case rule does not match, this one must: addup([FirstNumber | RestOfList], Total) :- addup(RestOfList, TotalOfRest), % add up the numbers in RestOfList Total is FirstNumber + TotalOfRest.

This example shows how to find the last item in a list:

% lastitem(List, Last) % Binds Last to the item at the end of List. % List must be instantiated at the time of call, and must not be empty. % Example of use: % lastitem([a,b,c,d], X)? % X = d %% base case: list with just one item. lastitem([OnlyOne], OnlyOne). %% recursive case: ignore first item, seek last item of rest of list lastitem([First | Rest], Last) :- lastitem(Rest, Last).

This example shows how to build a result that is a list, i.e. we are transforming a list to produce a new list.

This time we'll start with a version with bugs (= errors) in it and also a stylistic error, and then we'll correct the errors. With each version of the code, you should look carefully at it before reading on, and try to spot the bug (or stylistic error). Spotting the bugs and stylistic errors is something you will have to do for yourself when you write your own programs, so start on it now!

NB:
`square_1`

,
`square_2`

,
`square_3`

, and
`square_4`

**are all wrong**. Only
`square_5`

is correct.

For the sake of brevity in this exposition, I've left out the comments in all but the final version. In practice you would develop the comments as you wrote the code. However, remember that just because you say something is true about the code, in your comments, doesn't mean it is. And don't forget to review and if necessary correct your comments when you find and fix a bug.

square_1([First | Rest], [First * First | SquareRest]) :- square_1(Rest, SquareRest).Try it out:

:square_1([1, 3, 5], Squares)?** no

Oops - we left out the base case. If you turn on tracing before you execute the query above, you will be able to see 1 * 1, 3 * 3, and 5 * 5 being produced, but because there is no base case, Prolog cannot complete the query.

square_2([], []). square_2([First | Rest], [First * First | SquareRest]) :- square_2(Rest, SquareRest).Try it out again:

:square_2([1, 3, 5], Squares)?Squares = [1 * 1, 3 * 3, 5 * 5]

That's better, but why didn't it work out that 1 * 1 = 1, 3 * 3
= 9, etc.?

Answer: because we didn't ask it to. In Prolog, in most
cases, evaluation of an arithmetic expression must be explicitly
called for using the built-in predicate `is`

.

square_3([], []). square_3([First | Rest], [Square | SquareRest]) :- FirstSquared is First * First, square_3(Rest, SquareRest), Square = FirstSquared.Try it:

:square_3([1, 3, 5], Squares)?Squares = [1, 9, 25]

Whee! It works. But it contains a stylistic problem. The final
goal `Square = FirstSquared`

is redundant - it can
be done better by simply writing `FirstSquared`

instead
of `Square`

in the head of the rule:

square_4([], []). square_4([First | Rest], [Firstsquared | SquareRest]) :- FirstSquared is First * First, square_4(Rest, SquareRest).Always try it out after any change:

:square_4([1, 3, 5], Squares)?Squares = [_R36, _R55, _R74]

Say what? Why doesn't it work any more? `FirstSquared`

as `Firstsquared`

in the head of the rule. Prolog cares desperately about upper and lower
case letters, and the "s" of Squared is lower case in the head of the
rule, but upper case in the first goal of the body. This can lead
to a range of mystifying error messages - the type above, with
one or more unresolved `_R…`

variables, is one possibility.

%% base case % nothing to square; result is empty list. square_5([], []). %% recursive case % square the First item, recursively square the Rest. square_5([First | Rest], [FirstSquared | SquareRest]) :- FirstSquared is First * First, square_5(Rest, SquareRest).

:What NOW!!!??? Oh. We mis-typedsqare_5([1, 3, 5], Squares)?ERROR: Undefined predicate. In: sqare_5([1, 3, 5], _R15) ?

`square_5`

as
`sqare_5`

in the :Whew!square_5([1, 3, 5], Squares)?Squares = [1, 9, 25]

© Bill Wilson, 2004-2005

Bill Wilson's contact info

UNSW's CRICOS Provider No. is 00098G

Last updated: