Why does this command cause a stack overflow in prolog?
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).
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.
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).