6.1 Looping a Fixed Number of Times
Many programming languages provide 'for loops' which enable a set of instructions
to be executed a fixed number of times. No such facility is available in Prolog
(directly), but a similar effect can be obtained using recursion, as shown in the
example programs below.
Example 1
The following program outputs integers from a specified value down to 1.
loop(0).
loop(N):-N>0,write('The value is: '),write(N),nl,
M is N-1,loop(M).
The loop predicate is defined in terms of itself. The second clause can be
thought of as: 'to loop from N, first write the value of N, then subtract one to give
M, then loop from M'. This process clearly needs to be terminated and this is
achieved by the first clause: 'when the argument is zero, do nothing (and hence
stop)'. The first clause can be regarded as a terminating condition for the recursion.
?- loop(6).
The value is: 6
The value is: 5
The value is: 4
The value is: 3
The value is: 2
The value is: 1
yes
Note the use of the two goals M is N-1,loop(M) in the second clause for the
loop predicate. The obvious alternative of loop(N-1) will not work. Prolog only
evaluates expressions such as N-1 when evaluating goals with functor is or one of
the relational operators, as described in Chapter 4. If N-1 is used as an argument of
a predicate it is taken to mean the term with infix operator - (i.e. a minus sign) and
arguments N and 1. This is most unlikely to be what is intended!
Example 2
The next program outputs integers from First to Last inclusive.
/* output integers from First to Last inclusive */
output_values(Last,Last):- write(Last),nl,
write('end of example'),nl.
output_values(First,Last):-First=\=Last,write(First),
nl,N is First+1,output_values(N,Last).
Here output_values has two arguments, which can be read as 'output the
integers from First to Last inclusive'. The loop terminates when both arguments are
the same.
?- output_values(5,12).
56789
10
11
12
end of example
yes
Example 3
Define a predicate to find the sum of the integers from 1 to N (say for N = 100).
It is natural to think of this procedurally, i.e. start with 1, then add 2, then add 3,
then add 4, … , then add 100. However the process is much easier to program if reexpressed
declaratively in terms of itself.
The sum of the first 100 integers is the sum of the first 99 integers, plus 100.
The sum of the first 99 integers is the sum of the first 98 integers, plus 99.
The sum of the first 98 integers is the sum of the first 97 integers, plus 98.
…………………………………………………………………………….
The sum of the first 3 integers is the sum of the first 2 integers, plus 3.
The sum of the first 2 integers is the sum of the first 1 integers, plus 2.
The sum of the first 1 integers is one.
There are two distinct cases to consider: the general case: 'the sum of the first
N integers is the sum of the first N-1 integers, plus N' and the terminating case: 'the
sum of the first 1 integers is 1'. This leads directly to the recursive definition:
/* sum the integers from 1 to N (the first argument)
inclusive */
sumto(1,1).
sumto(N,S):-N>1,N1 is N-1,sumto(N1,S1),S is S1+N.
?- sumto(100,N).
N = 5050
?- sumto(1,1).
yes
Note that using the additional variable N1 for holding the value of N-1 is
essential. Writing sumto(N-1,S1) etc. instead would not work correctly. N-1 is a
term, not a numerical value.
Example 4
Define a predicate to output the squares of the first N integers, one per line.
This can most easily be programmed if first recast in a recursive form, as
follows.
To output the squares of the first N integers, output the squares of the first N-1 and
then output N2
To output the squares of the first N-1 integers, output the squares of the first N-2
and then output (N-1)2
To output the squares of the first N-2 integers, output the squares of the first N-3
and then output (N-2)2
……………………………………………………………………………………….
To output the squares of the first 3 integers, output the squares of the first 2 and
then output 32
To output the squares of the first 2 integers, output the squares of the first 1 and
then output 22
To output the squares of the first 1 integers, output the number 1
Here the general case is 'to output the squares of the first N integers, output the
squares of the first N-1 and then output N2' and the terminating case is 'to output
the squares of the first 1 integers, output the number 1'. This leads to the following
two-clause program.
/* output the first N squares, one per line */
writesquares(1):-write(1),nl.
writesquares(N):-N>1,N1 is N-1,writesquares(N1),
Nsq is N*N,write(Nsq),nl.
?- writesquares(6).
149
16
25
36
yes
Example 5
The following program reads the first 6 terms from a specified file and writes them
to the current output stream. It uses a 'counting down' method, in a similar way to
Example 1.
read_six(Infile):-seeing(S),see(Infile),
process_terms(6),seen,see(S).
process_terms(0).
process_terms(N):-N>0,read(X),write(X),nl,N1 is N-1,
process_terms(N1).
6.2 Looping Until a Condition Is Satisfied
Many languages have an 'until loop' which enables a set of instructions to be
executed repeatedly until a given condition is met. Again, no such facility is
available directly in Prolog, but a similar effect can be obtained in several ways.
6.2.1 Recursion
The first example below shows the use of recursion to read terms entered by the
user from the keyboard and output them to the screen, until end is encountered.
6.2.2 Using the 'repeat' Predicate
Although it can often be used to great effect, recursion is not always the easiest
way to provide the types of looping required in Prolog programs. Another method
that is often used is based on the built-in predicate repeat.
The name of this predicate is really a misnomer. The goal repeat does not
repeat anything; it merely succeeds whenever it is called. The great value of repeat
is that it also succeeds (as many times as necessary) on backtracking. The effect of
this, as for any other goal succeeding, is to change the order of evaluating goals
from 'right to left' (i.e. backtracking) back to 'left-to-right'. This can be used to
create a looping effect, as shown in the examples below.
This program repeatedly prompts the user to enter a term until either yes or no
is entered. It is an alternative to the recursive program shown at the end of the
previous section. In this case it is debatable whether using repeat is an
improvement on using recursion, but the example is included for purposes of
illustration.
6.3 Backtracking with Failure
As the name implies, the predicate fail always fails, whether on 'standard'
evaluation left-to-right or on backtracking. Advantage can be taken of this,
combined with Prolog's automatic backtracking, to search through the database to
find all the clauses with a specified property.
6.3.1 Searching the Prolog Database
Supposing the database contains clauses such as
dog(fido).
dog(fred).
dog(jonathan).
Each dog clause can be processed in turn using the alldogs predicate defined
below.
alldogs:-dog(X),write(X),write(' is a dog'),nl,fail.
alldogs.
Calling alldogs will cause dog(X) to be matched with the dog clauses in the
database. Initially X will be bound to fido and 'fido is a dog' will be output. The
final goal in the first clause of the alldogs predicate will then cause evaluation to
fail. Prolog will then backtrack over nl and the two write goals (all of which are
unresatisfiable) until it reaches dog(X). This goal will succeed for a second time
causing X to be bound to fred.
This process will continue until fido, fred and jonathan have all been output,
when evaluation will again fail. This time the call to dog(X) will also fail as there
are no further dog clauses in the database. This will cause the first clause for
alldogs to fail and Prolog to examine the second clause of alldogs. This will
succeed and evaluation will stop.
The effect is to loop through the database finding all possible values of X that
satisfy the goal dog(X).
?- alldogs.
fido is a dog
fred is a dog
jonathan is a dog
yes
Note the importance of the second clause of the alldogs predicate. It is there to
ensure that, after the database has been searched, the goal succeeds. With only the
first line, any call to alldogs will eventually fail.
alldogs:-dog(X),write(X),write(' is a dog'),nl,fail.
?- alldogs.
fido is a dog
fred is a dog
jonathan is a dog
no
The next program is designed to search a database containing clauses
representing the name, age, place of residence and occupation of a number of
people.
If the database contains these five clauses
person(john,smith,45,london,doctor).
person(martin,williams,33,birmingham,teacher).
person(henry,smith,26,manchester,plumber).
person(jane,wilson,62,london,teacher).
person(mary,smith,29,glasgow,surveyor).
The names of all the teachers can be found using the allteachers predicate.
allteachers:-person(Forename,Surname,_,_,teacher),
write(Forename),write(' '),write(Surname),nl,
fail.
allteachers.
The effect of using backtracking with failure in this case is to find all the
teachers in the database.
?- allteachers.
martin williams
jane wilson
yes
If the second clause of allteachers were omitted, both teachers would still be
found but the evaluation of allteachers would end with failure. This is of little or
no importance when a goal is entered at the system prompt, but if allteachers were
used as a goal in the body of a rule it would obviously be desirable to ensure that it
always succeeded.
It should be noted that it is not always necessary to use 'backtracking with
failure' to search the database. For example, the predicate somepeople/0 defined
below will find all the people in the database given previously, down to williams,
using only standard backtracking.
somepeople:-person(Forename,Surname,_,_,_),
write(Forename),write(' '),write(Surname),nl,
Surname=williams.
somepeople.
The goal Surname=williams succeeds if the variable Surname is bound to
williams. If not, it fails. The effect is to search the database down to and including
the person clause with second argument williams.
?- somepeople.
john smith
martin williams
yes
6.3.2 Finding Multiple Solutions
Backtracking with failure can also be used to find all the ways of satisfying a goal.
Suppose that a predicate findroute(Town1,Town2,Route) finds a route Route
between two towns Town1 and Town2. The details of this predicate are irrelevant
here. It may be assumed that Town1 and Town2 are atoms and that Route is a list.
Backtracking with failure can then be used to find all possible routes between
Town1 and Town2 and write out each one on a separate line, as follows:
find_all_routes(Town1,Town2):-
findroute(Town1,Town2,Route),
write('Possible route: '),write(Route),nl,fail.
find_all_routes(_,_).
