7

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).
false
  • 10,264
  • 13
  • 101
  • 209
rookie
  • 7,723
  • 15
  • 49
  • 59

2 Answers2

2

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

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

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
2

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.

Déjà vu
  • 28,223
  • 6
  • 72
  • 100
  • 3
    Perhaps you should point out to rookie that the problem you analyzed can be prevented by adding `X > 0` to the body of the 2nd clause for **fact/2**. – hardmath Jan 29 '11 at 13:13