問題タブ [difference-lists]

Prolog の文脈自由文法に関するこのチュートリアルを読んでいます。ページの下部で、Prolog の文脈自由文法を差分リストを使用して実装することに言及しており、次のコード ブロックが含まれています。

それは言及しています：

これらのルールを慎重に検討してください。たとえば、 s ルールは次のように述べています。 (1) X を消費して Y を残すことができ、 X と Y のペアが名詞句を表し、(2)次に、Z を残して Y を消費することができます。ペア YZ は動詞句を表します。np ルールと 2 番目の vp ルールは同様に機能します。

と

最初のリストは消費する必要があるもの (または必要に応じて入力リスト) と考え、2 番目のリストは残すもの (または出力リスト) と考えてください。この（むしろ手続き的な）観点から見ると、違いのリスト

は、女性が男性を撃つ文を表しています。なぜなら、次のように書かれているからです。左側のすべての記号を消費し、右側の記号を残す場合、私は興味のある文を持っています。つまり、私たちが興味を持っている文です。は、これら 2 つのリストの内容の違いです。

レコグナイザーを書き直すために違いリストについて知っておく必要があるのはこれだけです。何かを消費し、何かを置き去りにするという考えを単純に心に留めると、次の認識子が得られます。

説明として、しかし、それは私にこのコードを明確にするために何もしていません. を使用するよりも効率的であることは理解していますappend/3が、ものを消費して他のものを置き去りにするという概念に関しては、以前のappend/3実装よりもはるかに混乱しているようで、頭も尻尾もできません。さらに、そのコードをコピーしてProlog ビジュアライザーに貼り付けて理解しようとすると、ビジュアライザーにエラーがあると表示されます。誰かがこれに光を当てることができますか?

リストを使ってPrologプログラムを書いてみました。ただし、差分リストを使用する必要があり、出力は次のようになります。

リストの i^番目の要素はリストの (n-i+1)^番目の要素と同じで、n はリストの長さです。たとえば、 と[a,X,c,b,Y]を指定する必要がX = bありY = aます。他の質問で同様の回文の例を見つけることができませんでした。

これまでのところ、私は実装しました：

しかし、私は完了することができませんでした。私を助けてください！

差分リストは、プロローグで変数が不変であるという事実を「回避」する手段ですか?

つまり、差分リストを使用して追加を実装する場合:

そして実行します：

X は、ある意味で、変更可能な変数として使用されています。私たちの意図と目的のために、それは変更されましたか?

言い換えれば、新しいリスト、たとえば Z (不変) を作成する必要がなく、X (可変) を変更できるという事実が、違いリストを魅力的なものにしています。では、変更可能な変数だけを持たないのはなぜでしょうか?

アップデート：

のコストを避けたいのでappend/3、差分/オープン リストを使用します。

ただし、開いたリストの問題はmember/2、要素を末尾に追加することによって開いたリストに反応することです。例えば：

開いているリストには無制限の「テール」があり、member/2関数はこのテール/ホール (変数) を member の最初の引数と統合するため、これは正しい動作です。

ただし、開いているリストに特定の要素と等しい要素があるかどうかを確認できる方法を探しています。これどうやってするの？

私のような Prolog 初心者にとって、空のリストは...奇妙です。アトムを差分リストとして書くことができないのと同じように、空のリスト[]を差分リストとして書くことはできないと言えます。ただし、再帰を使用するには、差分リストの設定でT1-T2使用する方法が必要であると思います。[]私はこれについてGoogleに問い合わせましたが、答えが見つかりません.Bratko（AIのプロローグプログラミング）は、この主題に簡単に触れているだけです.

では、空のリストを Prolog の差分リストとして書くことは可能ですか? もしそうなら、いつ、どのように役立つのでしょうか?

この質問を差分リストとして空のリストに書き留めていたとき、それらの構造について知っていることをテストしたいと思いました。しかし、異なる記法を比較するという単純なことを試みたとき、私は間違っているように見え、違いリストで実際に何が起こっているのか理解していませんでした。

これを SWI-Prolog と SICStus でテストしました。Bratko の Prolog Programming for AI の 210 ページにこのように書かれているので、表記法を確認しましたが、どうやら統一はできないようです。何故ですか？これらの表記法は同じ宣言的な意味を持っていませんか?