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 ref-sem-con, and bas-eff-cdi, for more information on optimization using conditionals).