Geek Answers Handbook

Why does this command cause a stack overflow in the prolog?

I have the following piece 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 someone explain why the following command causes a stack overflow? Thanks in advance.

 fact(6).
+7
source share
2 answers

Let's look at the rules first

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

which will find a match for fact(0,1) . For X = 6 , what happens instead, since no rule defines a predicate for fact(0,6) , the search starts with fact(-1,V1) , and then with fact(-2,V2) , etc. .... until a match for fact(-value, Var) , where Var will be found as the local result.

This cannot be, and an infinite loop consumes the entire stack until an error is raised.

+2
source

The reason why fact(6) does not end 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) .

Since this fragment does not end, your original program does not end. Please note that the exception does not depend on the definition of fact/2 ! At best, your program may succeed, but it will never (permanently) fail.

Suppose we use a different definition of fact/2 , which also ends with fact(N, 6).

+2
source

More articles:


All Articles