Node:Making Predicates Determinate, Next:Placement of Cuts, Previous:Cut Overview, Up:The Cut

Consider the following predicate, which calculates the factorial
of a number:

fac(0, 1). fac(N, X) :- N1 is N - 1, fac(N1, Y), X is N * Y.

The factorial of 5 can be found by typing:

| ?-fac(5, X).X = 120

However, backtracking into the above predicate by typing a
semicolon at this point, causes an infinite loop because the system
starts attempting to satisfy the goals `fac(-1, X).`

,
`fac(-2, X).`

, etc. The problem is that there are two
clauses that match the goal `fac(0, F).`

, but the
effect of the second clause on backtracking has not been
taken into account. There are at least three possible ways of fixing
this:

- Efficient solution: rewrite the first clause as
fac(0,1) :- !.

Adding the cut essentially makes the first solution the only one for the factorial of 0 and hence solves the immediate problem. This solution is space-efficient because as soon as Prolog encounters the cut, it knows that the predicate is determinate. Thus, when it tries the second clause, it can throw away the information it would otherwise need in order to backtrack to this point. Unfortunately, if this solution is implemented, typing

`fac(-1, X)`

still generates an infinite search. - Robust solution: rewrite the second clause as
fac(N, X) :- N > 0, N1 is N - 1, fac(N1, Y), X is N * Y.

This also solves the problem, but it is a more robust solution because this way it is impossible to get into an infinite loop.

This solution makes the predicate

*logically*determinate--there is only one possible clause for any input--but the Prolog system is unable to detect this and must waste space for backtracking information. The space-efficiency point is more important than it may at first seem; if`fac/2`

is called from another determinate predicate, and if the cut is omitted, Prolog cannot detect the fact that`fac/2`

is determinate. Therefore, it will not be able to detect the fact that the calling predicate is determinate, and space will be wasted for the calling predicate as well as for`fac/2`

itself. This argument applies again if the calling predicate is itself called by a determinate predicate, and so on, so that the cost of an omitted cut can be very high in certain circumstances. - Preferred solution: rewrite the entire predicate as the single
clause
fac(N, X) :- ( N > 0 -> N1 is N - 1, fac(N1, Y), X is N * Y ; N =:= 0 -> X = 1 ).

This solution is as robust as solution 2, and more efficient than solution 1, since it exploits conditionals with arithmetic tests (see Conditionals and Disjunction for more information on optimization using conditionals).