Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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).
like image 533
rookie Avatar asked Jan 29 '11 09:01

rookie


1 Answers

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.

like image 84
Déjà vu Avatar answered Sep 30 '22 17:09

Déjà vu