Next: Fail Goal Now Up: A Special Control Previous: Commit

## Make Determinate

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).

sum(N,Ans):-

NewN is N-1,

sum(NewN,Ans1),

Ans is Ans1+N.
[-5pt]

```
together with the goal
```
?- 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:
```
3

no

```
Alas, here is the result using Edinburgh Prolog.
```
3

(a very very long wait)

```
We have a runaway recursion. Figure 9.2 shows the execution tree for the goal sum(2,Ans).

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)

Next: Fail Goal Now Up: A Special Control Previous: Commit

Paul Brna
Mon May 24 20:14:48 BST 1999