Here is the code with the bug.
% Version of factorial(N, FactorialN) with a bug in it. factorial(0, 1). factorial(N, Result) :- write("Entering recursive rule for factorial with N = "), write(N), nl, Nminus1 is N - 1, factorial(Nminus1, Nminus1Factorial), Result is N * Nminus1Factorial.
The challenge was:
Try copying and pasting this code into Prolog, and then typing the
factorial(5, Result)? and see what happens. Can you
figure out the bug?
When you run this query, it first computes the correct answer, then backtracks and looks for further solutions. This leads it to try computing factorial(-1), factorial(-2), ... and so on for ever, or in fact until the Prolog interpreter runs out of memory.
There are a couple of ways at least to fix the bug. You can either change the first rule to:
factorial(0, 1) :- !.
which explicitly says "don't backtrack after you've found the answer!", or you can change the second, recursive rule to:
factorial(N, Result) :- write("Entering recursive rule for factorial with N = "), write(N), nl, N > 0, Nminus1 is N - 1, factorial(Nminus1, Nminus1Factorial), Result is N * Nminus1Factorial.
which stops to second rule in its tracks if N is 0 (or less).
The first solution is more efficient, but doesn't solve the problem
if factorial is called with a negative argument because of a bug
in the calling program (or because the user makes a mistake, typing
factorial(-17, N)?, for instance. The second
solution involves a (small) extra test each time the recursive rule
is called, but it ensures correctness.
UNSW's CRICOS Provider No. is 00098G