4

私はPrologでfindall述語を実装しようとしています（そうです、それが組み込まれていることは知っています、これは割り当て用です）。

それは次のように書かれています：

my_findall(N,P,Pred,L) :- Pred, not(new(N,P)), !, assert(new(N,P)), my_findall(N1,P1,Pred,L1), L=[N,P,L1], retract(new(N,P)).
my_findall(_,_,_,  []).

何らかの理由で、my_findallへの2番目の呼び出しが失敗したかのように、最初の解決策が得られ、そこで停止します。私が理解しているように、バックトラッキングメカニズムは、Pred（N、P）を呼び出すためのすべてのオプションを含む、すべての可能なオプションを調べる必要があります。したがって、2番目の呼び出しは最初の試行で失敗するはずです（Predに対して試行された最初のオプションはすでに主張されている）、それはあきらめてmy_findall（（、）、_、[]）に行く前に、最初に他のすべてのオプションを試す必要があります。

それが機能しない場合、ソリューションを完全に書き直すことなく、この種の動作を強制する方法はありますか？

4

1 に答える 1

5

Pred にはバインドされていない変数が含まれています。最初の繰り返しで Pred を呼び出すと、これらの変数は最初に可能な値にバインドされます。再帰的なステップでは、Pred には既に変数がバインドされており、値を変更することはできません。だから...この解決策はうまくいきません。

SWI-Prolog からのトレース (何らかの理由で、new/2 を item/2 に名前変更する必要がありました):

第 1 レベル (呼び出し: my_findall(A,B,member(p(A,B), [p(1,2), p(3,4)]), L). )。

   Call: (7) my_findall(_G819, _G820, member(p(_G819, _G820), [p(1, 2), p(3, 4)]), _G840) ? creep
   Call: (8) lists:member(p(_G819, _G820), [p(1, 2), p(3, 4)]) ? creep
   Exit: (8) lists:member(p(1, 2), [p(1, 2), p(3, 4)]) ? creep

p(A,B) = p(1,2) を得ました。この時点で、A は 1 にバインドされ、B は 2 にバインドされます。

^  Call: (8) not(item(1, 2)) ? creep
   Call: (9) item(1, 2) ? creep
   Fail: (9) item(1, 2) ? creep
^  Exit: (8) not(item(1, 2)) ? creep

OK、データベースに項目 (1,2) はありません。

^  Call: (8) assert(item(1, 2)) ? creep
^  Exit: (8) assert(item(1, 2)) ? creep

これで、item(1,2) が真になります。再帰呼び出し:

   Call: (8) my_findall(_L215, _L216, member(p(1, 2), [p(1, 2), p(3, 4)]), _L199) ? creep

Pred を実行する別のソリューションを取得しましょう。

   Call: (9) lists:member(p(1, 2), [p(1, 2), p(3, 4)]) ? creep
                          ^^^^^^^

下線部が見えますか？

この手法を機能させるには、おそらく Pred をコピーして、N と P を再帰的に新しい変数に変更する必要があります。繰り返しごとに、N と P の新しいペアを「作成」する必要があります。copy_term/2 ( http://www.swi-prolog.org/pldoc/doc_for?object=copy_term%2f2 ) を確認してください。

于 2009-07-08T15:20:41.410 に答える