Summary Bab 6 Loop

Chapter Aims
After reading this chapter you should be able to:
1. Define a predicate which causes a sequence of goals to be evaluated
repeatedly, either a fixed number of times or until a specified condition is
2. satisfied
Define a predicate which searches a database to find all the clauses with a
specified property.

Introduction
Most conventional programming languages have a looping facility that enables a
set of instructions to be executed repeatedly either a fixed number of times or until
a given condition is met. Prolog has no looping facilities, similar effects can be obtained that enable asequence of goals to be evaluated repeatedly. This can be done in a variety of ways, using backtracking, recursion, built-in predicates, or a combination of these.

6.1 Looping a Fixed Number of Times

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



6.2 Looping Until a Condition Is Satisfied

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.

go:-loop(start). /* start is a dummy value used to get
the looping process started.*/
loop(end).
loop(X):-X\=end,write('Type end to end'),read(Word),
write('Input was '),write(Word),nl,loop(Word).

?- go.

Type end to end: university.

Input was university

Type end to end: of.

Input was of

Type end to end: portsmouth.

Input was portsmouth

Type end to end: end.

Input was end

Yes

Using the disjunction operator ;/2 which was defined in Section 4.4 the above
program can be rewritten as a single clause.

loop:-write('Type end to end'),read(Word),
write('Input was '),write(Word),nl,
(Word=end;loop).

The 'disjunctive goal' (Word=end;loop) succeeds if variable Word is bound to
the atom end. If not, the system attempts to satisfy the goal loop recursively.

?- loop.

Type end to end: university.

Input was university

Type end to end: of.

Input was of

Type end to end: portsmouth.

Input was portsmouth

Type end to end: end.

Input was end
yes
This recursive program repeatedly prompts the user to enter a term until either
yes or no is entered.

get_answer(Ans):-write('Enter answer to question'),
nl,get_answer2(Ans).
get_answer2(Ans):-
write('answer yes or no'),
read(A),
((valid(A),Ans=A,write('Answer is '),
write(A),nl);get_answer2(Ans)).
valid(yes). valid(no).

?- get_answer(Myanswer).

Enter answer to question

answer yes or no: maybe.

answer yes or no: possibly.

answer yes or no: yes.

Answer is yes

Myanswer = yes

6.2.2 Using the 'repeat' Predicate

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.

get_answer(Ans):-
write('Enter answer to question'),nl,
repeat,write('answer yes or no'),read(Ans),
valid(Ans),write('Answer is '),write(Ans),nl.
valid(yes). valid(no).



The first five goals in the body of get_answer will always succeed. Evaluating
the fifth goal: read(Ans) will prompt the user to enter a term. If the term input is
anything but yes or no, say unsure, the following goal valid(Ans) will fail. Prolog
will then backtrack over read(Ans) and write('answer yes or no'), both of which
are unresatisfiable, i.e. will always fail on backtracking.
Backtracking will then reach the predicate repeat and succeed, causing
evaluation to proceed forward (left-to-right) again, with write('answer yes or no')
and read(Ans) both succeeding, followed by a further evaluation of valid(Ans).
Depending on the value of Ans, i.e. the user's input, the valid(Ans) goal will
either fail, in which case Prolog will backtrack as far as repeat, as before, or it will
succeed in which case the final three goals write('Answer is'), write(Ans) and nl
will all succeed. The overall effect is that the two goals write('answer yes or no')
and read(Ans) are called repeatedly until the terminating condition valid(Ans) is
satisfied, effectively creating a loop between repeat and valid(Ans).

?- get_answer(X).

Enter answer to question

answer yes or no: unsure.

answer yes or no: possibly.

answer yes or no: no.

answer is no

X = no

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









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(_,_).