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