Dlaczego mój predykat w Prolog Fib/2 zawsze mówi "z lokalnego stosu"?

Question

Napisałem predykat fib/2 do obliczenia liczb Fibonacciego w Prologu. Choć to działa, to zawsze mówi „z lokalnego stosu”, a błąd wygląda tak:

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

mój orzecznikiem jest poniżej:

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. 

Ktoś wie dlaczego tak jest i jak to naprawić je Uzyskaj następujące informacje:

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

Z góry dziękuję!

Answer 1

Błąd out of local stack oznacza, że ​​program użył zbyt dużej ilości pamięci i przekroczył przydzieloną przestrzeń; zdarza się to często, gdy program wpada w nieskończoną pętlę. W twoim przypadku, tutaj jest ślad:

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

jak widać, po stwierdzeniu, że 2nd Fibonacci jest 1 (według definicji) poprosisz o drugiego roztworu; ponieważ nie podano, że trzecia klauzula może być użyta tylko wtedy, gdy N> 1 prolog próbuje znaleźć drugie rozwiązanie, obliczając fib (-1), fib (-2), fib (-3) itp.

aby to naprawić, musisz dodać N>1 lub podobną regułę do trzeciej klauzuli:

Answer 2

Jednym z problemów, które możesz rozwiązać, jest niepotrzebne rekomputacja wartości fibonacci. Oto niewielka zmiana w kodzie, aby rozwiązać ten niedobór:

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

na przykład w SWI Prolog, możliwe jest obliczenie

?- init_fib, fib(1000,F). 

bardzo szybko i bez spalin stosu.

?- init_fib. 
true. 

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

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

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

Answer 3

Twój kod nie jest ogon rekurencyjnej. właściwie rekurencyjna struktura ogonowa oznacza, że ​​można zastosować TRO (optymalizację rekursji ogona). To zasadniczo przekształca rekurencję w iterację, ponownie wykorzystując istniejącą ramkę stosu dla wywołania rekursywnego. Po zastosowaniu TRO każde wywołanie rekurencyjne przesuwa nową ramkę stosu na stosie wywołań. Należy uporządkować swoją orzecznik coś takiego (zauważ, że nie zostały faktycznie przetestowane ten kod, ale powinien wykonać zadanie):

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

najprawdopodobniej kolejności (który jest po pierwsze jajko czy kura) najprawdopodobniej, gdyby było napisane tak:

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

problem zostanie rozwiązany.

Answer 5

Powodem dlaczego program nie kończy najlepiej widać rozważając jedynie fragment programu, zwany failure-slice którą można uzyskać poprzez dodanie false cele do swojego programu.

 
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. 

Wszystko strajk poprzez części programów mają żadnego wpływu na zakończenie.Mogą mieć inne skutki, jak wtedy, gdy twój program się powiedzie lub zawiedzie, ale nie zakończy się.

Aby zakończyć program, należy zmienić coś w widocznej części. Najwyraźniej pierwszy argument zmniejsza się bez granic.

Ale plasterek porażki implikuje również wiele innych programów, które skutecznie będą miały ten sam segment awarii. Pomyśl na przykład o tym, aby ostatnie fakty (zgodnie z sugestią @RicardoMojica). Takie fakty można usunąć za pomocą false w ten sam sposób, co spowoduje ten sam program. Tak więc:

Zmiana kolejności klauzul nie ma wpływu na zakończenie (uniwersalne).

---

^{Ograniczona gwarancja
Wszystkie te stwierdzenia odnoszą się tylko do czystych programów monotonicznych. nieczyste niemonotoniczne cechy i efekty uboczne niszczą te właściwości.}