0

Prolog で次の関数を書き直しています。

V1:

f(X,Y):- X < 2, Y is X+1.
f(X,3):- 2 =< X, X < 5.
f(X,Y):- 5 =< X, Y is 8-X.

V2 として:

f(X,Y) :-
    X < 2,
    Y is X + 1. 
f(X,Y) :-
    X >= 2,
    X < 5,
    Y is 3.
f(X,Y) :-
    X >= 5,
    Y is 8-X.

次に、カットを試してみたいと思いました。グリーン カット (V3) の場合:

f(X,Y) :-
    X < 2, !,
    Y is X + 1.
f(X,Y) :-
    X >= 2,
    X < 5, !,
    Y is 3.
f(X,Y) :-
    X >= 5,
    Y is 8-X.

レッド カット (V4) の場合:

f(X,Y) :-
    X < 2, !,
    Y is X + 1.
f(X,Y) :-
    X < 5, !,
    Y is 3.
f(X,Y) :-
    Y is 8-X.

ただし、カットを削除するとコードの同じ動作が可能になるため、それらの利点がわかりません...何か助けはありますか?

4

2 に答える 2

1

すべてのバージョン V1..V4 は観測的に同等であるため、ある程度の推論は正しいです。それでも違いはあります。

余分な選択ポイントを避ける

多くの実装では、V1 と V2 は特に効率が悪い可能性があります。これは、内部的に「選択の余地が残されている」ためです。これは、そのようなプロローグが他のルールをこれ以上見ないためです。したがって、各ゴールf(1,X)は、バックトラック (または ! の使用) でのみ解放できるメモリを少し消費します。これを自分で試す簡単な方法を次に示します。

loop(Goal) :-
   Goal,
   loop(Goal).

SWIで得られるものは次のとおりです。

?- time(loop(f1(1,2))).
% 5,991,554 inferences, 81.282 CPU in 81.443 seconds (100% CPU, 73713 Lips)
ERROR: Out of local stack
?- time(loop(f2(1,2))).
% 5,991,553 inferences, 85.032 CPU in 85.212 seconds (100% CPU, 70462 Lips)
ERROR: Out of local stack

V3 と V4 は無期限に実行されるようですが、少なくとも 85 秒よりもはるかに長くなります。このような実験は、非常に小さなプログラムでは面白いですが、大きなプログラムではあまり実用的ではありません。幸いなことに、多くのプロローグでは、クエリが確定的に実行されるかどうかを判断する簡単な方法があります。システムがこれを行うかどうかを確認するには、次のように入力します。

?- X = 1.
X = 1.

あなたのバリエーションのために：

?- f1(1,2).
true ;        % <== Prolog asked for another answer
false.        % <== only to conclude that there is none.

?- f2(1,2).
true ;        % same again
false.

?- f3(1,2).
true.         % <== Prolog knows there will be no further answer

?- f4(1,2).
true.

再計算の回避 - カットを赤くする

V3 では余分な選択ポイントが回避されますが、V4 では余分な計算も回避されるようになりました。したがって、最も効率的である必要があります。しかし、節の順序を固定する代償が伴います。

ただし、グリーン カットに必要な 2 つの条件が一致したため、V3 のみが可能でした。

  1. 重複しない条件。それはあなたには明らかなはずです。

  2. インスタンス化の安全なテスト。これは明らかではありません。X < 2ゴールには、正しいインスタンス化の暗黙のテストが添付されていることに注意してください! インスタンス化エラーが生成されます。インスタンス化されてXいない変数である必要があります。V3 のカットがたまたまグリーン カットになるのは、まさにこのテストのためです。そのテストがなければ、レッドカットになります。

また、2 番目の規則が単独である場合、V1 と V2 は同等ではないことに注意してください。ゴールf(X,5).は V1 では失敗しますが、V2 ではエラーになります。

于 2014-06-02T00:07:59.373 に答える