Why my predicate in Prolog Fib/2 always says “out of local stack”?

Question

I wrote a predicate fib/2 to calculate the Fibonacci numbers in Prolog. Though it works, it always says "out of local stack" and the error looks like:

?- fib(10, F).
F = 55 ;
ERROR: Out of local stack

my predicate is below:

fib(0, 0).
fib(1, 1).
fib(N, NF) :-
    A is N - 1, 
    B is N - 2,
    fib(A, AF), 
    fib(B, BF),
    NF is AF + BF.

Anyone knows why this is and how to fix it to get the following stuff::

% or the search might stop immediately, without pressing space.
?- fib2(10, F).
F = 55 ;
false. 

Thanks in advance!

Answer 1

The out of local stack error means that the program used too much memory and exceeded the allocated space; this occurs often when the program falls in an infinite loop. In your case, here is the trace:

[trace] 2 ?- fib(2,M).
   Call: (6) fib(2, _G671) ? creep
^  Call: (7) _G746 is 2+ -1 ? creep
^  Exit: (7) 1 is 2+ -1 ? creep
^  Call: (7) _G749 is 2+ -2 ? creep
^  Exit: (7) 0 is 2+ -2 ? creep
   Call: (7) fib(1, _G747) ? creep
   Exit: (7) fib(1, 1) ? creep
   Call: (7) fib(0, _G747) ? creep
   Exit: (7) fib(0, 0) ? creep
^  Call: (7) _G671 is 1+0 ? creep
^  Exit: (7) 1 is 1+0 ? creep
   Exit: (6) fib(2, 1) ? creep
M = 1 ;
   Redo: (7) fib(0, _G747) ? creep
^  Call: (8) _G752 is 0+ -1 ? creep
^  Exit: (8) -1 is 0+ -1 ? creep
^  Call: (8) _G755 is 0+ -2 ? creep
^  Exit: (8) -2 is 0+ -2 ? creep
   Call: (8) fib(-1, _G753) ? creep
^  Call: (9) _G758 is -1+ -1 ? creep
^  Exit: (9) -2 is -1+ -1 ? creep
^  Call: (9) _G761 is -1+ -2 ? creep
^  Exit: (9) -3 is -1+ -2 ? creep
   Call: (9) fib(-2, _G759) ? creep
^  Call: (10) _G764 is -2+ -1 ? creep
^  Exit: (10) -3 is -2+ -1 ? creep
...

as you can see, after finding that the 2nd fibonacci is 1 (by your definition) you ask for a second solution; since you haven't specified that the third clause may only be used when N>1 prolog tries to find the second solution by calculating fib(-1), fib(-2), fib(-3) etc.

to fix it, you have to add N>1 or a similar rule to the third clause

Answer 2

One problem you might address is the unnecessary recomputation of fibonacci values. Here is a small change to your code to address this deficiency:

:- dynamic db_fib/2.

init_fib :-
    assertz( db_fib(0, 0) ),
    assertz( db_fib(1, 1) ).

fib(N, NF) :-
    A is N - 1,
    B is N - 2,
    get_fib(A, AF),
    get_fib(B, BF),
    NF is AF + BF.

get_fib(A, F) :-
    db_fib(A, F),
    !.

get_fib(A, F) :-
    fib(A, F),
    assertz( db_fib(A, F) ).

For example, in SWI Prolog, it is possible to compute

?- init_fib, fib(1000,F).

very quickly and with no stack exhaust.

?- init_fib.
true.

?- fib(10,A).
A = 55.

?- fib(100,A).
A = 354224848179261915075.

?- fib(1000,A).
A = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.

Answer 3

Your code isn't tail-recursive. a properly tail-recursive structure means that TRO (tail recursion optimization) can be applied. That essentially converts your recursion into iteration, by reusing the existing stack frame for the recursive call. With TRO applied, each recursive call pushes a new stack frame on the call stack. You should structure your predicate something like this (note that I haven't actually tested this code, but it should do the job):

% ------------------------------------------------------
% the public interface predicate
% ------------------------------------------------------
fib(1,1).          % first  element in the sequence is 1
fib(2,1).          % second element in the sequence is 1
fib(N,X) :-        % subsequent elements
  N > 2 ,          %   where N > 2
  fib(1,1,3,N,X)   %   are computed
  .

% --------------------------------------
% the private worker predicate for N > 2
% this predicate maintains a sliding 'window' on the fibonacci sequence
% as it computes it
% --------------------------------------
fib( V1 , V2 , N , N , X ) :- % compute the element at position N
  N > 2 ,                     % ensure N > 2
  X is V1 + V2                % value is the sum of the 2 prior elements
  .
fib( V1 , V2 , T , N , X ) :- % on backtracking, slide the window to the right:
  T > 2         ,             %  ensure N > 2
  T1 is T  + 1  ,             %  increment N
  V3 is V1 + V2 ,             %  compute the next value (V1+V2)
  fib(V2,V3,T1,N,X)           %  recurse
  .

Answer 4

The reason why your program does not terminate can be best seen by considering only a fragment of your program, called a failure-slice which can be obtained by adding false goals into your program.

fib(0, 0) :- false.
fib(1, 1) :- false.
fib(N, NF) :-
    A is N - 1, 
    B is N - 2,
    fib(A, AF), false,
    fib(B, BF),
    NF is AF + BF.

All strike through parts of your programs have no influence whatsoever on termination. They may have other impacts, as when your program will succeed or fail but none on termination.

To make the program terminate it is necessary to change something in the visible part. Evidently, the first argument decreases without bounds.

But the failure slice implies also many other programs that effectively will have the very same failure slice. Think for example to put the facts last (as suggested by @RicardoMojica). Such facts could be remove with false in the very same way thus resulting in the same program. Thus:

Changing the order of clauses has no influence on (universal) termination.

---

^{Limited Warranty
All these statements apply to pure monotonic programs only. impure non-monotonic features and side-effects destroy these properties.}

Answer 5

Is most likely the order(who is first the chicken or the egg) most likely if it was write like these:

fib(N, NF) :- 
  A is N - 1, 
  B is N - 2,
  fib(A, AF), 
  fib(B, BF),
  NF is AF + BF.
fib(1, 1).
fib(0, 0).

the problem will be solve.