44

私はいくつかのプロローグを学んだコースを受講しました。カットの使い方や使い方がわかりませんでした。カットの一般的な考え方はわかりますが、うまく使えないようです。誰かがそれを簡単に説明したり、彼らが推奨できる「カット」についての良いチュートリアル（learnprolognow.orgではない）を与えることができますか？

4

5 に答える 5

26

TL; DR：しないでください。

カットはPrologの検索ツリーを削除します。つまり、カットのない純粋なPrologプログラムと、カットのある同じプログラムが与えられた場合、唯一の違いは、カットのあるプログラムが無駄なブランチで費やす時間が少なくなり、したがってより効率的であるということです。答えが少ないかもしれません; また、元のプログラムが終了しないのに対して、終了する可能性があります。

かなり無害に聞こえます...あるいは便利ですよね？まあ、ほとんどの場合、物事はもっと複雑です。

赤いカット

カットは、カットのないプログラムがまったく意味をなさないような方法で使用されることがよくあります。このようなカットは、レッドカットと呼ばれます。より良いケースでは、非単調否定の大まかな形式を実装するために使用されます。そして、他のいくつかのケースでは、それは半分の否定であり、半分は理解するのが非常に難しい手続き上の意味です。プログラムの読者だけでなく、その作者にとっても。実際、多くの場合、そのような使用は意図せずに安定性を欠いています。いずれの場合も、これらのカットは既存のプログラムには配置されません。彼らは最初からそのプログラムに参加することを意図しています。

このような赤いカットのより構造化された使用法については、代わりonce/1に、、(\+)/1または(;)/2–if-then-elseを使用することをお勧め( If -> Then ; Else )します。さらに良いことに、sを発行して、そのような構成を意図しない使用から保護するようにしてくださいinstantiation_error。またはiwhen/2、インスタンス化エラーを生成するか、when/2（SWI、YAP、SICStusで提供される）目標を遅らせる使用。

グリーンカット

役に立たない選択ポイント（および冗長な回答）を削除するカットは、グリーンカットと呼ばれます。ただし、注意してください。とを押すだけでプログラムに配置することはできませ!ん#00ff00。ほとんどの場合、このカットが回転しないようにするために、クリーンな読み取り専用ガードが必要です#ff0000。残りの選択ポイントを安全に削除する簡単な方法もありますcall_semidet/1。関連するケースを次に示します。

カットはコミットされません

最後に、カットはコミット演算子ではないことを指摘しておきます。それは時々それのように振る舞いますが、1つになるには多くの制限が必要になります。commit-operatorを（ab）使用して実装することはできません(\+)/1。コミットでは、各句が互いに独立して試行される必要があります。したがって、各句には完全なガードが必要です。他のいくつかの句が最初に試行された後にのみ試行されることに依存することはできません。また、述語の各節でコミットを行う必要があります。カットはどこでも発生する可能性があります。

于 2013-01-28T05:34:41.437 に答える
14

カットを使用する前に、述語が次の 2 つの基準を満たす必要があります。

  • それはカットなしで正解を与える
  • 節を並べ替えると正しい答えが得られる

述語がそのように動作したら、不要な非決定性を取り除くためにカットを追加することがあります。

たとえば、数値が正か負かゼロかをテストする述語です。

sign(N, positive) :-
    N > 0.
sign(N, negative) :-
    N < 0.
sign(N, zero) :-
    N =:= 0.

各句は、他の句から完全に独立しています。これらの句を並べ替えたり、句を削除したりしても、残りの句は期待どおりの回答を返します。この場合、Prolog システムに、他の節を調べてもこれ以上解決策が見つからないことを伝えるためだけに、 positiveand節の最後にカットを入れることができます。negative

を使用してカットせずに同様の述語を書くこともできますが、-> ;見た目が気に入らない人もいます:

sign(N, Sign) :-
    (   N > 0 -> Sign=positive
    ;   N < 0 -> Sign=negative
    ;            Sign=zero
    ).
于 2013-01-28T16:16:49.597 に答える
14

カットは、Prolog の目標が証明され、行われた選択にコミットします。

利用可能な代替手段を試してはならないことをプログラマーが知っている場合は、それを使用する必要があります。

最も顕著な用途は、失敗による否定の実装です。

fact(a).
fact(b).

/* 1 */ neg(X) :- call(X), !, fail.
/* 2 */ neg(_).

ここで、標準の否定演算子を (再) 定義しました。通常は ( \+ )/1です。

?- neg(fact(c)).
true.

call(fact(c))ルール 1 では証明できず、代わりのルール 2 が成功します。

?- neg(fact(a)).
false.

は証明fact(a) できるため、カットは失敗する前に代替案を破棄します。

?- neg(fact(X)).
false.

事実 (X) が成功する未知の X が少なくとも存在します。

?- neg(neg(fact(X))).
true.

二重否定には、変数が束縛されないという効果があります。これは、メタ プログラミングを行うときに、「構造」を変更せずに句を取得するのに役立ちます。操作の観点からは、何が起こっているかは明らか (?) ですが、プログラムは宣言型のプロパティを失います。

初歩的なインタープリターでのみ役立つ別の使用法は、再帰呼び出しの前にカットを付けて、システムに最後の呼び出し最適化を実行するように指示することでした。これにより、システムは代替ポイントを追跡するために通常必要なスタック領域を割り当てることを回避できます。ダミーの例:

print_list([E|Es]) :- print_element(E), !, print_list(Es).
print_list([]).

チュートリアルについての編集: William Clocksin による「条項と効果」には、カットに関連する詳細な調査が含まれていることがわかりました: 第 4 章「選択とコミットメント」では、長所と短所をカットすることに完全に専念しています。要するに、主に短所...

于 2013-01-27T00:53:47.933 に答える