Chapter Aims
After reading this chapter you should be able to:
• 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
satisfied
• Define a predicate which searches a database to find all the clauses with a
specified property.
PART 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
PART 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.
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
Using the 'repeat' Predicate
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.
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
Goals to the left of repeat in the body of a clause will never be reached on backtracking.
The next program reads a sequence of terms from a specified file and outputs
them to the current output stream until the term end is encountered.
readterms(Infile):-
seeing(S),see(Infile),
repeat,read(X),write(X),nl,X=end,
seen,see(user).
In a similar way to the previous program, this effectively defines a loop
between the goals repeat and X=end.
If file myfile.txt contains the lines
'first term'. 'second term'.
'third term'. 'fourth term'.
'fifth term'. 'sixth term'.
'seventh term'.
'eighth term'.
end.
calling readterms will produce the following output
?- readterms('myfile.txt').
first term
second term
third term
fourth term
fifth term
sixth term
seventh term
eighth term
end
yes
This program shows how to implement a menu structure which loops back repeatedly to request more input. Entering go at the prompt causes Prolog to output a menu from which the user can choose activities one at a time until option d is chosen. Note that all inputs are terms and so must be followed by a full stop character.
go:- write('This shows how a repeated menu works'),
menu.
menu:-nl,write('MENU'),nl,
write('a. Activity A'),nl,write('b. Activity B'),nl,
write('c. Activity C'),nl,write('d. End'),nl,
read(Choice),nl,choice(Choice).
choice(a):-write('Activity A chosen'),menu.
choice(b):-write('Activity B chosen'),menu.
choice(c):-write('Activity C chosen'),menu.
choice(d):-write('Goodbye!'),nl.
choice(_):-write('Please try again!'),menu.
?- go.
This shows how a repeated menu works
MENU
a. Activity A
b. Activity B
c. Activity C
d. End
: b.
Activity B chosen
MENU
a. Activity A
b. Activity B
c. Activity C
d. End
: xxx.
Please try again!
MENU
a. Activity A
b. Activity B
c. Activity C
d. End
: d.
Goodbye!
yes
PART 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.
Searching the Prolog Database
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
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(_,_).
CHAPTER SUMMARY
This chapter describes how a set of goals can be evaluated repeatedly in Prolog, either a fixed number of times or until a specified condition is met, and how multiple solutions can be arrived at using the technique of 'backtracking with failure'.
yeaaahhh .. just enjoying this tutorial .. make it easy for you ..
![]()
even maybe make you so confuse actually
![]()
hahahhaa just enjoy it readers ...
