Prolog でフィボナッチ数を計算する述語 fib/2 を書きました。動作しますが、常に「ローカルスタック外」と表示され、エラーは次のようになります。
?- fib(10, F).
F = 55 ;
ERROR: Out of local stack
私の述語は以下です：
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.
これがなぜなのか、次のものを得るためにそれを修正する方法は誰でも知っています::
% or the search might stop immediately, without pressing space.
?- fib2(10, F).
F = 55 ;
false.
前もって感謝します！
この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
...
ご覧のとおり、2番目のフィボナッチが1（定義上）であることを確認した後、2番目の解決策を求めます。N> 1のプロローグがfib（-1）、fib（-2）、fib（-3）などを計算して2番目の解を見つけようとする場合にのみ、3番目の句を使用できるように指定していないためです。
これを修正するにはN>1、3番目の句にまたは同様のルールを追加する必要があります
対処する可能性のある問題の1つは、フィボナッチ値の不必要な再計算です。この欠陥に対処するためのコードの小さな変更は次のとおりです。
:- 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プロローグでは、計算することが可能です
?- init_fib, fib(1000,F).
非常に迅速で、スタックの排気がありません。
?- init_fib.
true.
?- fib(10,A).
A = 55.
?- fib(100,A).
A = 354224848179261915075.
?- fib(1000,A).
A = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.
あなたのコードは末尾再帰ではありません。適切な末尾再帰構造は、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
.
プログラムが終了しない理由は、プログラムにゴールを追加することによって得られる失敗スライスと呼ばれる、プログラムの断片のみを考慮することによって最もよく理解できます。false
fib(0, 0) :- false.fib(1, 1) :- false。 fib(N, NF) :- A は N - 1、 B は N - 2、 fib(A, AF), false ,fib(B, BF),NF は AF + BF.
プログラムのすべての取り消し線部分は、終了にはまったく影響しません。プログラムが成功または失敗するが、終了時には影響しない場合など、他の影響を与える可能性があります。
プログラムを終了させるには、目に見える部分で何かを変更する必要があります。明らかに、最初の引数は際限なく減少します。
しかし、障害スライスは、事実上まったく同じ障害スライスを持つ他の多くのプログラムも意味します。たとえば、事実を最後に置くことを考えてください (@RicardoMojica で提案されているように)。このような事実は、まったく同じ方法で削除できfalse、結果として同じプログラムになります。したがって：
句の順序を変更しても、(普遍的な) 終了には影響しません。
限定保証
これらの記述はすべて、純粋なモノトニック プログラムにのみ適用されます。不純な非単調な機能と副作用は、これらのプロパティを破壊します。