4

次の Prolog プログラムを考えてみましょう (「The Art of Prolog」より):

natural_number(0).
natural_number(s(X)) :- natural_number(X).

plus(X, 0, X) :- natural_number(X).
plus(X, s(Y), s(Z)) :- plus(X, Y, Z).

そしてクエリ：

?- plus(s(s(s(0))), s(0), Z).

SICStus と SWI の両方が期待されるZ = s(s(s(s(0))))回答を生成しますが、ユーザーに次の回答 (正解no/false回答) を問い合わせます。ただし、唯一のゴールが見つかった後、なぜ SLD ツリーに開いたブランチがあるのか​​ 理解できません。SICStus と SWI の両方でデバッグを試みましたが、まだ結果を解釈することができません。私が理解できる限り、どちらもplus(s(s(s(0))), 0, _Z2). 誰かがこの動作を理解するのを手伝ってくれますか?

4

3 に答える 3

2

多くの Prolog システムは、私たちが期待するほどスマートではありません。これにはいくつかの理由がありますが、主に実装者のトレードオフの選択によるものです。ある人にとって重要に見えることは、他の人にとってはそれほど重要ではないかもしれません。

結果として、これらの残りの選択ポイントは時間の経過とともに蓄積し、補助データの解放を妨げる可能性があります。たとえば、長いテキスト リストを読み上げたい場合。一度にメモリに収まらないほど長いリストですが、 で効率的に処理できますlibrary(pio)。

正確に 1 つの答えを期待する場合は、 を使用call_semidet/1して決定的にすることができます。その定義とユースケースについては、この回答を参照してください。

?- plus(s(s(s(0))), s(0), Z)。
Z = s(s(s(s(0)))) ;
間違い。

?- call_semidet(plus(s(s(s(0))), s(0), Z))。
Z = s(s(s(s(0))))。

しかし、より楽観的な側面からもそれを見ることができます: 現代のトップレベル (SWI のような) は、残っている選択ポイントがある場合に表示されます。などの対策が考えられますcall_semidet/1。

関連する回答を次に示します。

于 2012-10-31T19:14:26.290 に答える
1

Prologシステムは、説明したように先読み方式でSLDツリーを構築しないため、この問題はSLDツリーに直接関係していません。しかし、特定の Prolog システムで見られるいくつかの最適化には、本質的にこの効果があり、ブラインド ブルート フォース ヘッド マッチングが変更されます。つまり、索引付けと選択ポイントの排除です。

現在、SWI-Prolog には既知の制限があります。複数引数のインデックス作成は行いますが、最初の引数以外のインデックスのカスケード インデックス作成の選択ポイントの削除は行いません。1 つの引数のみを選択することを意味しますが、それ以上は選択しません。複数引数のインデックス付けとカスケード インデックス付けを行う Prolog システムがいくつかあります。たとえば、Jekejeke Prologには No/false がありません。

ペアノ・カスケード

さよなら

PS: Jekejeke Prolog の最新バージョンは、最初の引数インデックスに感度がないことを検出するため、文字通りカスケードしません。したがって、実際の呼び出しパターンにより、最初の引数のインデックスを作成しますが、最初の引数のインデックスをスキップして使用せず、2 番目の引数のみを使用します。スキップすると少し速度が上がります。:-)

スキップはdump/1、開発環境バージョンのコマンドで確認できます。

?- dump(plus/3).
-------- plus/3 ---------
length=2
arg=0
  =length=2
arg=1
  0=length=1
  s=length=1
Yes

したがって、そこに降りてインデックスarg=0を構築するのarg=1 ではなく、並行しarg=0てarg=1インデックスを構築します。個々のクエリが複数のインデックスにつながるため、このヒューリスティック カスケードと呼ぶこともできますが、実際にはカスケードの形をしていません。

于 2012-10-31T18:10:47.053 に答える
0

私たちにとって、plusの2つの節が「選言的」であることは明らかです。私たちはそれを知っているのでそれを言うことができます0 \= s(Y)。しかし（私は）そのような分析は一般に法外であり、Prologはそのようなブランチがまだ証明されていないと見なします：ここでは、最初の解決策が見つかった後、呼び出し（7）がまだ代替案に対して「オープン」であることを示すトレースです。

ここに画像の説明を入力してください

于 2012-10-31T17:23:29.530 に答える