12

カット演算子で追加を使用すると、どのような問題が発生する可能性がありますか?

   append2([],L,L):-!.
   append2([H|T],L,[H|TL]):-append2(T,L,TL).

いくつかの異なる入力を試しましたが、常に成功します。

?- append2([1,2],[5],L).
L = [1, 2, 5].

?- append2([1,2],[1,2],L).
L = [1, 2, 1, 2].

?- append2([],[1,2],L).
L = [1, 2].

?- append2([1,2],[],L).
L = [1, 2].
4

4 に答える 4

8

グリーン カットを導入することが本当に理にかなっている場合もappend/3ありますが、そのようなカットがグリーン カットのままであることに注意する必要があります。つまり、効率を (一定のレベルで) 向上させ、回答に影響を与えないカットです。

グリーン カットを導入するための非常に簡単な経験則があります。ガードのない純粋で単調なプログラムにカットを追加すると、プログラムの意味を破壊するレッド カットになることはほぼ確実です。

この経験則には例外はほとんどありません。たとえば、可変フリー ゴールの後にカットを追加することもできますが、それ以上のルールなどはありません。カットの影響を受けるケースを把握するための良いトレーニングになることは間違いありません。

しかし、あなたのプログラムに戻りましょうappend2/3。現在、代替ルールが適用される場合でも、カットは常にカットされます。

では、最初の節だけが関連するのはいつになるのでしょうか?

最初の引数が の場合[]、したがってappend2([], Xs, Ys).- だけでなく、最後の引数が の[]場合も (より複雑なケースがさらに多くあります)。元のカットフリー定義で両方のケースを試してみましょう:

?- append([], Ys, Zs)。
Ys = Zs。

?- append(Xs, Ys, [])。
Xs = Ys、Ys = [] ;
間違い。

したがって、最初のケースでは、システムは答えを生成しながら、ただちに単一の解があると判断できました。しかし、2 番目のケースでは、Prolog システムは別の回答が必要かどうか確信が持てませんでした。この場合も答えが 1 つしか存在しないことを判断するのはかなり簡単なので、これは残念です。ここでカットが役立つのは理想的でした。しかし、無防備なカットは、役立つよりも害を及ぼします。

3 番目の引数が[]:

append3(Xs, Ys, Zs) :-
   (  Zs == [] -> ! ; true ),
   Xs = [],
   Ys = Zs.
append3([X|Xs], Ys, [X|Zs]) :-
   append3(Xs, Ys, Zs).

このプログラムは、3 番目の引数だけがわかっている場合に選択ポイントを開いたままにしないという意味で、より効率的になりました。

?- append(Xs,Ys,[1])。
Xs = []、
Ys = [1] ;
Xs = [1]、
Ys = [] ;
間違い。

?- append3(Xs,Ys,[1])。
Xs = []、
Ys = [1] ;
Xs = [1]、
イース = []。

テスト自体にコストがかかる可能性があるため、プログラムが必ずしも高速であるとは限りません。理想的には、Prolog システムはそのようなことを内部的に行うことができますが、プログラマーが少し手伝わなければならない場合もあります。

于 2012-10-03T14:46:52.913 に答える
6

カットには2種類あります。グリーンカットとレッドカット。グリーン カットは、効率を向上させるためだけに挿入され、プログラムのセマンティクスを変更しません。一方、レッドカットはそうです。定義上、グリーン カットは問題を引き起こしません。

では、カットがなければ動作が変わる方法はありますか?

どれどれ; 最初の句が一致するためには、L1 は [] で単一化可能、L2 は L で単一化可能、L3 は L で単一化可能、つまり L2 は L3 で単一化可能である必要があります。

L1 が [] の場合、2 番目の句は一致しません。だからカットは何の効果もありません

L1 がインスタンス化されていない場合: この時点で L2 と L3 の長さがわかっている場合、それらは等しくなければなりません。そうでない場合、最初の節は一致しません。したがって、各ステップで L3 の長さが 1 ずつ減少し、終了する唯一の方法は L2=L3 を必要とするため、2 番目の句は一致しません。

L3 または L2 の長さが不明な場合: 2 番目の節が解を生成する可能性があるため、問題が発生します。

それはそう：

    3 ?- append2(L1,L2,[1,2,3]).
    L1 = [],
    L2 = [1, 2, 3].

    4 ?- append2(L1,[1,2,3],L3).
    L1 = [],
    L3 = [1, 2, 3].

    5 ?- append2(L1,L2,L3).
    L1 = [],
    L2 = L3.

    6 ?- append2(L1,[E1,E2],L3).
    L1 = [],
    L2 = [E1, E2].

    7 ?- append2(L1,L2,[E1,E2]).
    L1 = [],
    L2 = [E1, E2].

私たちが期待している間：

8 ?- append(L1,L2,[1,2,3]).
L1 = [],
L2 = [1, 2, 3] ;
L1 = [1],
L2 = [2, 3] ;
L1 = [1, 2],
L2 = [3] ;
L1 = [1, 2, 3],
L2 = [] ;
false.

9 ?- append(L1,[1,2,3],L3).
L1 = [],
L3 = [1, 2, 3] ;
L1 = [_G24],
L3 = [_G24, 1, 2, 3] ;
L1 = [_G24, _G30],
L3 = [_G24, _G30, 1, 2, 3] ;
L1 = [_G24, _G30, _G36],
L3 = [_G24, _G30, _G36, 1, 2, 3] ;
L1 = [_G24, _G30, _G36, _G42],
L3 = [_G24, _G30, _G36, _G42, 1, 2, 3] ;
...

10 ?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;
L1 = [_G22],
L3 = [_G22|L2] ;
L1 = [_G22, _G28],
L3 = [_G22, _G28|L2] ;
....

11 ?- append(L1,[E1,E2],L3).
L1 = [],
L3 = [E1, E2] ;
L1 = [_G78],
L3 = [_G78, E1, E2] ;
L1 = [_G78, _G84],
L3 = [_G78, _G84, E1, E2] ;
L1 = [_G78, _G84, _G90],
L3 = [_G78, _G84, _G90, E1, E2] ;
...

12 ?- append(L1,L2,[E1,E2]).
L1 = [],
L2 = [E1, E2] ;
L1 = [E1],
L2 = [E2] ;
L1 = [E1, E2],
L2 = [] ;
false.
于 2012-07-06T10:40:33.240 に答える
5

たとえば、最も一般的なクエリを試してください。

?- append2(X, Y, Z).
于 2012-07-06T11:49:53.487 に答える
3

最初の 2 つの引数が変数の場合は機能しません。

?- append(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3] ;
X = [1, 2],
Y = [3] ;
X = [1, 2, 3],
Y = [] ;
false.

?- append2(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3].
于 2012-07-06T10:18:12.403 に答える