Perché il mio predicato in Prolog Fib/2 dice sempre "fuori dallo stack locale"?

Question

Ho scritto un predicato fib/2 per calcolare i numeri di Fibonacci in Prolog. se funziona, si dice sempre "fuori pila locale" e l'errore si presenta come:

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

mia predicato è di seguito:

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. 

Chiunque sa perché questo è e come risolvere il problema alla ottenere le seguenti cose:

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

Grazie in anticipo!

Answer 1

L'errore out of local stack indica che il programma ha utilizzato troppa memoria e ha superato lo spazio allocato; questo si verifica spesso quando il programma cade in un ciclo infinito. Nel tuo caso, ecco la traccia:

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

come si può vedere, dopo aver constatato che il 2 ° Fibonacci è 1 (per la sua definizione) di chiedere una seconda soluzione; poiché non hai specificato che la terza clausola può essere usata solo quando N> 1 prolog cerca di trovare la seconda soluzione calcolando fib (-1), fib (-2), fib (-3) ecc.

per risolvere il problema, è necessario aggiungere N>1 o una regola simile alla terza clausola

Answer 2

Un problema che si potrebbe risolvere è il ricalcolo non necessario dei valori di Fibonacci. Ecco una piccola modifica al codice per affrontare questa carenza:

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

Per esempio, in SWI Prolog, è possibile calcolare

?- init_fib, fib(1000,F). 

molto rapidamente e senza scarico stack.

?- init_fib. 
true. 

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

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

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

Answer 3

Il codice non è tail-ricorsiva. una struttura correttamente ricorsiva alla coda consente di applicare TRO (ottimizzazione della ricorsione della coda). In pratica converte la ricorsione in iterazione, riutilizzando lo stack frame esistente per la chiamata ricorsiva. Con TRO applicato, ogni chiamata ricorsiva spinge un nuovo stack frame sullo stack delle chiamate. Si dovrebbe strutturare il vostro qualcosa predicato di simile (si noti che non ho effettivamente testato questo codice, ma dovrebbe fare il lavoro):

% ------------------------------------------------------ 
% 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

è più probabile che l'ordine (che è prima l'uovo o la gallina) molto probabilmente se fosse scritto in questo modo:

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

il problema sarà risolto.

Answer 5

Il motivo per cui il programma non termina può essere meglio visto da considerare solo un frammento del vostro programma, chiamato failure-slice che può essere ottenuto con l'aggiunta di false obiettivi nel vostro programma.

 
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. 

Tutti sciopero attraverso parti dei vostri programmi hanno alcuna influenza sulla terminazione.Possono avere altri impatti, come quando il tuo programma avrà successo o fallirà, ma nessuno alla risoluzione.

Per terminare il programma è necessario modificare qualcosa nella parte visibile. Evidentemente, il primo argomento diminuisce senza limiti.

Ma la sezione di errore implica anche molti altri programmi che effettivamente avranno lo stesso errore di sezione. Pensa per esempio a mettere i fatti per ultimi (come suggerito da @RicardoMojica). Tali fatti potrebbero essere rimossi con false nello stesso modo in cui risulta quindi lo stesso programma. Quindi:

La modifica dell'ordine di clausole non ha influenza sulla terminazione (universale).

---

^{Garanzia limitata
Tutte queste affermazioni si applicano solo programmi monotone puri. le caratteristiche impure non monotone e gli effetti collaterali distruggono queste proprietà.}