Why does this command cause a stack overflow in prolog?

Question

I have the following snippet of prolog code:

num(0).
num(X) :- num(X1), X is X1 + 1.

fact(0,1) :-!.
fact(X,Y) :- X1 is X-1, fact(X1,Y1), !, Y is Y1 * X.

fact(X) :- num(Y), fact(Y,X).

Can somebody please explain why the following command causes a stack overflow? Thanks in advance.

fact(6).

Answer 1

First, looking at the rules

  num(0).
  num(X) :- num(X1), X is X1 + 1.

the predicate num(Y) will be immediately valid for Y = 0.

Thus the rule

  fact(X) :- num(Y), fact(Y,X).

can be simplified as

  fact(X) :- fact(0,X).

that will find a match for fact(0,1). For X = 6, what happens instead is, as no rule defines a predicate for fact(0,6), a search is started with fact(-1,V1), followed with fact(-2,V2) etc... until a match occurs for a fact(-value, Var) where the local result would be the Var found.

This cannot happen, and an infinite loop consumes the whole stack, until an error is triggered.

Answer 2

The reason why fact(6) does not terminate can be found in the following failure-slice:

?- fact(6).

num(0) :- false.
num(X) :-
   num(X1), false,
   X is X1 + 1.

fact(X) :-
   num(Y), false,
   fact(Y,X).

Because this fragment does not terminate, also your original program does not terminate. Note that the non-termination is independent of the definition of fact/2! At best, your program might succeed, but it will never (finitely) fail.

Consider to use another definition of fact/2, which terminates also for fact(N, 6).