Making Predicates Determinate

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:

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

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

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