Prolog findallの実装

Question

私はPrologの組み込み関数を使わずにPrologでfindallのバージョンを実装することを任されています。

私は私がこれまで持っていることであるリスト内のすべての直接の子孫のツリーを検索し、結果を返すために

parent(a, b). 
parent(b, c). 
parent(b, d). 
parent(e, d). 

をしようとしている：

find(X, L) :- find2(X, [], L). 
find2(X, Acc, L) :- parent(Y, X), find2(Y, [Y|Acc], L). 
find2(_, Acc, Acc). 

私が取得することにしたいどのような私は、例えば、入力したとき：

find(a,X). 

は次のようになります。

X = [b, c, d] 

（注文は重要ではない）

しかし代わりに私が取得しています：

X = [b, c] ; 
X = [b, d] ; 
X = [b] ; 
X = []. 

を私はプロローグに新たなんだので、この上の任意の助けもいただければ幸いです。

おかげ

Answer 1

皆さんありがとうございます。私は、現在のリストに照らして各項目をチェックする述語を追加することにより、最終的にそれをsovleことに成功し、それがすでに存在していた場合は失敗しました。ここで

find(X, Loa) :- find(X, [], Loa), !. 
find(X, Acc, Loa) :- dec(Y, X), uList(Y, Acc, AccNew), find(X, AccNew, Loa). 
find(_, Acc, Acc). 

dec(X,Y) :- parent(X,Y). 
dec(X,Y) :- parent(X,Z), dec(Z,Y). 

uList(X, [], [X]) :- !. 
uList(H, [H|_], _) :- !, fail. 
uList(X, [H|T], L) :- uList(X, T, Rtn), L = [H|Rtn]. 

Answer 2

はthis solutionを見てみましょう。 このソリューションでは、すべての可能性がなくなるまですべてのソリューションをキャッシュするために、キューという動的述部を使用しています。いったん解決策がなくなると、実装はすべての事実を取り消し、リストを作成します。

これはもちろん、少し単純化された解決策です.2つのfindallが同時にアクティブになるとどうなるか想像してみてください。特定のプロローグの実装の場合、アサートとリトラクトの正確なセマンティクスでは少し壊れやすい

Answer 3

nb_setarg/3のような余分な論理述語を使用することもできます。親が見つかると、nb_setargを元に戻って別の親を探します。以前に見つかったすべてのソリューションは、nb_setargを実行した期間にとどまり、すべての結果が使い果たされた後、nb_setargという用語が答えになります。 SWI-Prologの例は良いですが、単なるカウンタです。あなたが行くにつれて構築されるリスト（またはより良いのは：差異リスト）でそれをやってみてください。

Answer 4

はSWI-Prologのキューとスレッドを使用するソリューションです。それは古い既存のAPIを使用し、Tarau's Enginesに沿って何かをします。私は、スレッドの作成がテンプレートと目標をコピーすると仮定します。そして、私は、キューの送信が再び各ソリューションのコピーを行うと仮定します。

古典的なfindallと比較すると、1つのテンプレートと目標のコピーに余剰がありますが、それ以外の場合は、それぞれの解決策を古典的なfindallとしてコピーします。要点のソースhere。しかし、コレクションを行うthreadall2を修正することによって、すべての種類の集約を実装することもできます。

% threadall(+Term, +Goal, -List) 
threadall(T, G, L) :- 
    message_queue_create(J, [max_size(1)]), 
    thread_create(threadall3(T, G, J), _, [detached(true)]), 
    thread_get_message(J, A), 
    threadall2(J, A, L), 
    message_queue_destroy(J). 

% threadall3(+Term, +Goal, +Queue) 
threadall3(T, G, J) :- 
    G, thread_send_message(J, the(T)), fail. 
threadall3(_, _, J) :- 
    thread_send_message(J, no). 

% threadall2(+Queue, +Term, -List) 
threadall2(J, the(T), [T|L]) :- !, 
    thread_get_message(J, A), 
    threadall2(J, A, L). 
threadall2(_, no, []). 

ここでは実行例を示します。私は正しく帳簿をやりました。スレッドはdetach（true）で作成されたので、スレッドが終了するときにハンドルは必要ありません。メッセージキューは明示的に破棄されます。

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.23) 
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam 

?- threadall(X, between(0, 5, X), L). 
L = [0, 1, 2, 3, 4, 5]. 

?- threadall(X-Y, (between(0, 2, X), 
        threadall(Z, between(0, 2, Z), Y)), L). 
L = [0-[0, 1, 2], 1-[0, 1, 2], 2-[0, 1, 2]]. 

私たちのコードのみが通常の幸せなパスを実装しています：私たちはthe/1とno/0メッセージを実装ここではいくつかの例では、我々が期待どおりに動作することがわかり、SWI-Prologで実行されています。さらに、setup_call_cleanup/3を使用しないので、割り込み付きのソリューションを使用することも安全ではありません。また、最後の議論は不動ではありません。これは、読者がこれらの追加の要件と対応する代替パスを実装するための練習として残されています。