問題タブ [prolog-cut]

免責事項：これは、私自身の時間に行う非公式で評価されていないコースワークです。私はそれを自分で試しましたが、失敗し、現在いくつかのガイダンスを探しています。

リストのメンバーを1回だけ返すバージョンのmember/2関数を実装しようとしています。

例えば：

各番号を最大1回だけ印刷してほしい。

カット「！」でこれを行うように言われました。オペレーターですが、私は自分のコースのメモを調べてカットやオンラインを増やしましたが、それでも頭の中でクリックすることはできません！

これまでのところ、私はなんとか取得できました：

これは1を返し、それ以外は何も返しません。カットが間違った場所にあり、可能な試合ごとにバックトラックを妨げているように感じますが、次にどこに行くのか本当にわかりません。

コースノートと、http：//www.cs.ubbcluj.ro/~csatol/log_funk/prolog/slides/5-cuts.pdfおよびProgramming in Prolog（Googleブックス）も確認しました。

カットを論理的に適用する方法についてのガイダンスが最も役立ちますが、答えは私がそれを自分で理解するのに役立つかもしれません。

また、失敗による'\ +'否定を使用する別の方法を実行するように言われましたが、カットが私のために小刻みに動いたら、これはもっと簡単かもしれませんか？

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

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

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

そしてクエリ：

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

Prolog でグリーン カットを理解するために、後継演算の合計の標準定義にそれらを追加しようとしています (このクエリの SLD ツリーとは? のplus述語を参照してください)。考えられるのは、すべての無駄なバックトラックを排除する (つまり、 no ) ことによって出力を可能な限り「クリーンアップ」することですが、引数のインスタンス化のすべての可能な組み合わせ (すべてインスタンス化されたもの、1 つまたは 2 つまたは 3 つが完全にインスタンス化されていないもの、およびすべてのバリエーション) で同一の動作を維持することです。部分的にインスタンス化された引数を含みます。... ; false

これは、この理想にできるだけ近づけようとしているときに私ができたことです（ソースとしてグリーンカットを挿入する方法append/3に対する偽の答えを認めます）：

SWI では、 SWI の述語記述の表記法と?- plus(+X, -Y, +Z).同様に、shape を除くすべてのクエリでうまく機能するようです。たとえば、利回り. 私の質問は次のとおりです。?- plus(s(s(0)), Y, s(s(s(0)))).Y = s(0) ; false.

• 上記のカットがグリーンである (またはそうでない) ことをどのように証明しますか?
• 他のグリーン カットを追加することで、上記のプログラムよりもうまくやり、最後のバックトラックもなくすことができるでしょうか?
• はいの場合、どのように？

私のコードは、次の方法で、リストの2つのリストをアイテムごとにマージします。

そして、これは私が使用するコードです：

これは機能しているようですが、同じサイズの2つのリストで呼び出すと、3つの結果が繰り返されます。例（両方のリストに含まれる要素は1つだけです）：

この出力を1つのソリューションのみにするクリーンな方法はありますか？

次のナレッジ ベースがある場合、X が既に父親であると判断されている場合に、プロローグが X が母親でもあるかどうかを「チェック」しようとしないように、parent_of 用語にカットを追加するにはどうすればよいですか?

たとえば、私は欲しい：

parent_of(max,Y) は次のようになります: Y=john, Y=james, Y=gabe

parent_of(jun,Y) は次のようになります: Y=john, Y=james

最初のものについては、プロローグが max が Mother_of であるかどうかをチェックしようとさえしたくありません。

私はすでに次のような多くの組み合わせを試しました：

これは可能ですか？

プロローグ、再帰関数: リストの各要素を含む C を出力する必要があります。たとえば、C=30 および [H|T]= [-9,-10,-30] です。

リストの先頭が空でないことを最初に確認します。それは私にこの出力を与えます

この出力は私が望むものですが、親関数も失敗するため、最後に「いいえ」を取得したくありません! どうすればそれを削除して代わりに「はい」を入れることができますか?

私は Python で PEG パーサー ジェネレーターを実装していますが、Prolog を知っている人なら誰でも知っているはずの「カット」機能を除いて、これまでのところ成功しています。

カット ( !) 記号が解析された後は、同じレベルで代替オプションを試行すべきではないという考え方です。

(が見られた後、解析が成功するか、2 番目のオプションを試さずに失敗する必要があることを意味します。

バックトラックを強制するために Python の (非常に効率的な) 例外システムを使用しているのでFailedCut、囲んでいる選択を中止する特別な例外を設定しようとしましたが、うまくいきませんでした。

この機能が他のパーサー ジェネレーターでどのように実装されているかについてのポインターは役に立ちます。

多分私が抱えていた問題は、地域性の欠如でした. ルールの左側の部分に対して生成されるコードは次のようになります。

次に、choice( |) 演算子用に生成されたコードは、FailedCut. 局所性の欠如とは、キャッチする選択肢FailedCutが呼び出しの奥深くにある可能性があり、その結果、識別が困難すぎるということです。

シーケンス用に生成されたコードに、カットの囲まれた選択肢を知らせようとする代わりに、選択肢用に生成されたコードにそれらを認識させることができます。これにより、Prolog とは異なり、カットの範囲が非常にローカルになりますが、特定のトークン シーケンスが表示された後にオプションにコミットするという PEG パーサーで必要なものには十分なので、エラー レポートはその場所を参照します。他のオプションが利用可能だった可能性のある別の場所ではなく、ソースで。

ルール/述語用に生成されたコードがそれをキャッチFailedCutして通常の例外に変換する場合FailedParse、カットには適切なスコープがあることに気づきました。

@falseの質問を参照して、私がやりたいことの完全な例を次に示します。

その文法では、 orwordを介して到達できますが、パーサーが.namedtermnamed:

ソリューション

公平を期すために、これまでの作品をhttps://bitbucket.org/apalala/grako/で公開しました。

最終的な解決策では、シーケンスは次のコンテキスト マネージャーで囲まれます。

また、choice 関数のオプションは次のように囲みます。

これは、次のオプションを試すために戻るのではなく、選択肢から抜け出すことを強制します。

カット自体は次のように実装されます。

完全なソース コードはBitbucketで見つけることができます。

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

次のコードを検討してください。

クエリa(X).は生成します

しかし、このコードで

クエリのa(X).結果は次のとおりです。

だから私の質問は、なぜfail/1生成がfalseになるのですか? バックトラックを強制するはずですよね？次にb(1)、c(1).チェックされると思いますが、なぜ失敗するのですか?