0

最近プロローグをやっています。そしてThe Art Of Prologの本を読みました。そこには Nim ゲームの実装があります。だから私はそれをSWI-Prologに書き直しました。そして、このOut of local stackエラー以外はすべて問題ないようです。デバッグ後、プログラムのこの部分で永遠にループしているように見えることがわかりました。

nim_sum([N|Ns],Bs,Sum):-
      binary(N,Ds), nim_add(Ds,Bs,Bs1), nim_sum(Ns,Bs1,Sum).
nim_sum([],Sum,Sum).

nim_add(Bs,[],Bs).
nim_add([],Bs,Bs).
nim_add([B|Bs],[C|Cs],[D|Ds]):-
    D is (B+C) mod 2, nim_add(Bs,Cs,Ds).

誰かがこの種の問題に遭遇しましたか？代替実装の提案はありますか?

4

1 に答える 1

2

「スタック外」の問題を回避するために、再帰述語を「最後の呼び出しの最適化」または「末尾再帰」形式で記述する必要があることがよくあります。

ここでは、nim_sum/3の 2 つの節を逆にする必要があるようです (終了条件である「事実」節を最初に置きます)。次に、本体を持つ句でnim_sum/3がそれ自体に対して行う呼び出しは、バックトラック ポイントを開くことなく行われます ( binary/2とnim_add/3が決定論的であると仮定します)。

これらの 2 つの句をnim_sumに置き換えてみて、その仕組みをお知らせください。

追加: nim_add/3 についてさらに検討した結果、Prolog エンジンは決定論的であること、つまり 1 つの方法でしか成功しないことをおそらく検出しないのではないかと思います。カットのお仕事です！オペレーター。最も簡単な解決策は、nim_sum/3がそれ自体を呼び出す場所の直前にカットを 1 つ追加することです。これにより、再帰呼び出しが行われた時点でバックトラック ポイントが開かれることはありません。ただし、これは Prolog の「精神に沿った」ものです。

nim_sum([],Sum,Sum).  
nim_sum([N|Ns],Bs,Sum):-  
    binary(N,Ds),  
    nim_add(Ds,Bs,Bs1),  
    nim_sum(Ns,Bs1,Sum).  

nim_add(Bs,[],Bs) :- !.  
nim_add([],Bs,Bs) :- !.  
nim_add([B|Bs],[C|Cs],[D|Ds]):-  
    D is (B+C) mod 2,  
    nim_add(Bs,Cs,Ds).

繰り返しますが、これはbinary/2が決定論的であると想定しており、おそらく整数 (非負?) を 0 と 1 のリストに変換し、最下位ビットが最初になります。

于 2011-02-11T13:58:42.867 に答える