prolog - プロローグ プログラムが誤った結果を返すクエリの検索

Question

この Prolog プログラムでは、3 番目の引数が最初の 2 つの数値引数の最大値になるように定義しています。

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

このプログラムはうまく機能すると思います。しかし、それは間違った結果をもたらす可能性があると言われています。いつ、なぜなのか分かりますか？

Answer 1

これは教科書の例です。

?- max(5,1,1).
true.

宿題: プログラムが間違っているのはなぜですか? プログラムを正しくするにはどうすればよいでしょうか。

編集

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

私たちの意図は次のとおりです。

X が Y より大きい場合、 Max は X です。それ以外の場合、Max は Y でなければなりません。

代わりに、言うことは次のとおりです。

1 番目と 3 番目の引数 (X と Max) が一致し、X が Y より大きい場合、成功します。そうでなく、第 2 引数と第 3 引数 (Y と Max) が統一できれば成功。

明らかな問題が発生すると、1 番目と 3 番目の引数は統合できませんが、2 番目と 3 番目の引数は統合できます。

その代わり：

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

また

max(X, Y, Max) :- X >= Y, !, Max = X.
max(_, Max, Max).

Answer 2

3 番目の引数がインスタンス化されていなければ、問題なく動作します。ここで危険なのは、2 番目のルールに戻る方法があった場合、または 3 番目の引数が 2 番目と同じ値にインスタンス化された場合です。何も考えずに結果を2番目の値に設定するだけなので、見た目は特に安全でmax(X, Y, Y).はありません。max(_, Y, Y)最初のルールの最後のカットは、X >= Y の場合にバックトラッキングが開始されないようにするため、2 番目のルールは X < Y で Z が Y に等しくない場合にのみ入力する必要があります。

ほとんどの場合はうまくいきますが、慣れるのは良い習慣ではありません。Prolog に慣れていない人は、手続き的に考える傾向があり、このようなカットを利用して、手続き的な策略によって特定の結果を確実にすることは、最終的にあなたを妨げ、さまざまな興味深い方法で駆動することができない複雑な Prolog につながります。この述語を書く方法は他にもいくつかありますが、同じように機能しますが、動作を確実にするためにカットに依存しません。たとえば、次のようになります。

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

また

max(X, Y, Z) :- X >= Y -> Z = X ; Z = Y.

これらはいずれも、インスタンス化される 3 番目の問題に対して脆弱ではありません。興味深いことに、これはレッド カットとグリーン カットの違いをよく表しています。あなたのコードには、動作がカットに依存する赤いカットがありますが、最初のソリューションをこれに単純に変更すると:

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y) :- X < Y.

動作はカットに依存しないため、これはグリーン カットですが、Prolog のパフォーマンスは、2 番目の句に戻って試行しないため、わずかに改善される可能性があります。ここでは、失敗することがわかっているので、両方とも次のチェックを行わないように Prolog に明示的に伝えています。赤いカットがあれば、失敗するチェックは他にありません。

残念なことに、条件を 2 回記述するのは冗長に感じられますが、1 つのルールに依存するのはぎこちなく感じられます。実際には、私の経験では、このようなシナリオは最終的にそれほど一般的ではありません。通常、節の先頭に一致させることができる原子または構造があり、最初の置換でのような動作を作成しますが、本体は必要ありません。例えば：

perform(scan(target, X, Y)) :- ...
perform(scan(calibration, X)) :- ...

これには同じ効果があります。Prolog は統合に成功するまでバックトラックし、その後再びバックトラックしますが、マッチングの排他的な性質により、別のボディが実行されるのを防ぎます。バックトラックに時間がかかりすぎていることがわかった場合は、カットを追加してパフォーマンスを向上させることができますが、実際には問題になることはほとんどありません。