We now go onto the key problem of making our programs determinate. That is if they succeed then they succeed precisely once unless we really want them to generate alternative solutions. Many programmers find taming backtracking to be a major problem.
Consider the problem raised by this program:
sum(1 1).together with the goalsum(N Ans):-
NewN is N-1
sum(NewN Ans1)
Ans is Ans1+N. [-5pt]
?- sum(2 X).The meaning of sum/2 is that for the first argument N (a positive integer) there is some integer the second argument which is the sum of the first N positive integers.
We know that for the mode sum(+ -) there is only one such result. Therefore if we try to redo a goal such as sum(2 Ans) it should fail. We could test that this is so with:
?- sum(2 Ans) write(Ans) nl fail.We would like the result:
3Alas here is the result using Edinburgh Prolog.no
3We have a runaway recursion. Figure 9.2 shows the execution tree for the goal sum(2 Ans).(a very very long wait)
Figure 9.2: The First Solution to the Goal sum(2
Ans)
Now look at the goal:
?- sum(2 X) fail.and the resulting fragment of the execution tree which is shown in figure 9.3.
Figure 9.3: Resatisfying the Goal sum(2
Ans)
Prolog goes into a non terminating computation. We want to make sure that having found a solution Prolog never looks for another solution via Redoing the goal. Figure 9.4 shows the consequence when the cut ( !/0) is used.
sum(1 1):-
.
sum(N Ans):-
NewN is N-1
sum(NewN Ans1)
Ans is Ans1+N.
Figure 9.4: The Effect of the cut on the Goal sum(2
Ans)