Prolog Fib/2の私の述語が、常に "out of local stack"と言うのはなぜですか？

Question

Prologでフィボナッチ数を計算するために、述語fib/2を書き​​ました。 は、それはそれは常に「ローカル・スタックの外」と言い、働くものの、エラーは次のようになります。これはなぜ

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. 

誰もが知っているし、それを修正する方法：

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

私の述語は以下の通りです次のものを入手してください::

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

ありがとうございます！

Answer 1

out of local stackエラーは、プログラムがあまりにも多くのメモリを使用して割り当てられた領域を超えたことを意味します。これは、プログラムが無限ループに陥ったときによく発生します。あなたのケースでは、ここでのトレースは、次のとおりです。

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

あなたが見ることができるように、第二フィボナッチは（あなたの定義による）1であることを発見した後、あなたが第二の溶液を求めます。もし第三節はN> 1つのプロローグ等FIB（-1）、FIB（-2）、FIB（-3）

を計算することによって、第二の溶液を見つけようとするときにのみ使用することができることを指定していないのでそれを修正するには、N>1または同様のルールを3番目の句に追加する必要があります。

Answer 2

フィボナッチ値の不必要な再計算が問題になります。ここでは、この欠点を解決するためにあなたのコードを少し変更です：

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

例えば、SWI Prologで、非常に迅速かつ無スタック排気と

?- init_fib, fib(1000,F). 

を計算することが可能です。

?- init_fib. 
true. 

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

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

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

Answer 3

あなたのコードは、末尾再帰ではありません。適切なテール再帰的構造は、TRO（テール再帰最適化）を適用できることを意味する。つまり、再帰呼び出しに既存のスタックフレームを再利用することによって、再帰を反復に変換します。 TROが適用されると、各再帰呼び出しは呼び出しスタック上に新しいスタックフレームをプッシュします。

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

が最も可能性の高い順（最初鶏が先か卵が先かである）です：あなたは、この（私は実際にこのコードをテストしていませんが、それは仕事をする必要があることに注意してください）のようなあなたの述語何かを構築する必要がありますほとんどの場合、次のように書く：

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

問題は解決されます。

Answer 5

あなたのプログラムが最良のあなたのプログラムの断片のみを考慮することによって見ることができます終了しない理由は、あなたのプログラムにfalse目標を添加することにより得ることができるfailure-sliceと呼ばれます。あなたのプログラムの部分を通して

 
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. 

すべてストライキが終了に一切影響を与えません。あなたのプログラムが成功するか失敗するかのように、他の影響があるかもしれませんが、終了時には影響しません。

プログラムを終了させるには、可視部分の内容を変更する必要があります。明らかに、最初の引数は境界なしで減少します。

しかし、障害スライスには、実質的に同じ障害スライスを持つ他の多くのプログラムも含まれます。たとえば事実を最後に置くと考えてください（@ RicardoMojicaの示唆どおり）。そのような事実は、全く同じ方法でfalseで取り除くことができ、したがって同じプログラムが得られる。したがって：

句の順序を変更しても、（汎用）終了には影響しません。

---

^{限定保証
全てのこれらの記述は、純粋な単調なプログラムにのみ適用されます。非単調な非単調な特徴および副作用がこれらの特性を破壊する。}