6

DCGをジェネレーターとして使用したいと思います。現在のところ、構文は次のとおりです。

s-->a,b.
a-->[].
a-->a,c.
c-->[t1].
c-->[t2].
b-->[t3].
b-->[t4].

sの長さがであるaすべてを生成したいと思い< someNumberます。

?- phrase(a,X),length(X,Y),Y<4.iを 使用するaと、4つ未満のアイテムですべてを取得できます。ただし、すべての組み合わせが使い果たされると、システム（SWI-Prolog 6.2.5）が停止しているように見えます。時々前に、同様の質問がここで尋ねられました。ただし、Prologを初めて使用するため、上記の文法で機能させることはできません。何か案は？

更新：どういうわけか削除された（canrememberthename）によるコメントがありました。とにかく、between(1,4,Y),length(X,Y),phrase(a,X).制限を設定するために使用することが提案されました。コードを次のように変更した後、これはうまく機能しましたa-->c,a.

4

2 に答える 2

5

Prologへの最初のステップはしばしば少し難しいです。しかし、あなたは正しい方向に進んでいます：

現在、問題は、期待どおりにいくつかの回答/解決策が得られるが、システムが停止することです。実際、それは無限ループにあります。あなたは辛抱強く打つことによってそれを見つけましたSPACE。これは、小さなソリューションセットでは機能する可能性がありますが、より大きなソリューションでは面倒になります。20より短いすべての文を見ると考えてください。

打撃スペースをシミュレートするためのシンプルなキーボードと手根管に優しい方法があります。次falseのように最後にゴールを追加するだけです。

？-phrase（a、X）、length（X、Y）、Y <4、false。

Prologはそのような質問に何に答えることができますか？最後にあるのでfalse、Prologには多くの選択肢がありませんfalse。または、ループします（または、エラーが発生したり、何らかの副作用が発生したりします）。そしてこの場合、それはループします。

falseこれで、プログラムにさらに目標を追加することで、問題を絞り込むことができます。

？-phrase（a、X）、length（X、Y）、false、Y <4、false。
**ループ**

これを読みやすくするために、1つのfalse目標のみを使用して、クエリの残りの部分を取り消します。

？-phrase（a、X）、length（X、Y）、false、Y<4。
**ループ**

それをさらに減らしましょう：

？-phrase（a、X）、false、length（X、Y）、Y<4。
**ループ**

それらはすべてループします！しかし、興味深い洞察が得られます。これらのfalse装飾されたクエリは終了しないため、元のプログラムも終了しません。したがって、クエリを見て、最初の目標がそれ自体で終了しない場合、クエリ全体が終了しないことになります（詳細については、最後の詳細を参照してください）。

したがって：あなたはどういうわけか最初の目標に取り組む必要があります！

length私の最初の試みは交換することですphrase：

？-長さ（X、Y）、フレーズ（a、X）、Y<4。

これは機能しますか？ループする最初の目標を見てください。

？-length（X、Y）、false、phrase（a、X）、Y<4。

したがって、これも終了しません。

プログラムを再度変更する必要があります。

？-between（1,3、Y）、length（X、Y）、false、phrase（a、X）。
false。

したがって、これは終了します。そして、終了の問題が発生する場合はphrase(a,X)、責任を負う必要があります。

？-between（1,3、Y）、length（X、Y）、phrase（a、X）、false。
**ループ**

あなたは実際の答えを見たくなるかもしれません：

？-between（1,3、Y）、length（X、Y）、phrase（a、X）。
Y = 1、
X = [t1];
Y = 1、
X = [t2];
エラー：ローカルスタックが不足しています

そして、この振る舞いは元の定義よりも悪いと結論付けるかもしれません。結局のところ、今では以前よりも回答が少なくなっています。しかし、まさにその種の推論は、終了を改善するのに役立ちません。どちらも同じ種類の誤りであり、最初にこれに対処する必要があります。したがって、答えを非表示にすることで、残りの部分に集中することができます。false

しかし、なぜあなたの文法は問題があるのですか？目標を挿入falseして絞り込む手法を継続できます。しかし、今回はあなたの文法の範囲内です。目標で飾られたプログラムは、falseと呼ばれます。

実用的な注意：プログラムに目標falseを挿入すると、プログラムを保存しmakeてSWIと入力します。このようにして、プログラムは迅速に再コンパイルされます。

少し試してみたところ、次の最小限の失敗スライスが得られました。DCG内でfalseは、として記述する必要があることに注意してください{false}。

？-between（1,3、Y）、length（X、Y）、phrase（a、X）、false

s-> {false}、a、b。

a-> []、{false}。
a-> a、{false}、c。

c-> {false}、[t1]。
c-> {false}、[t2]。

b-> {false}、[t3]。
b-> {false}、[t4]。

ほとんどすべてのコードベースはfalse！したがって、目に見える小さな残りの部分に対処する必要があります。他の場所で何かを変更するのは無意味です。これa --> a, ...は変更する必要があります！そして実際にa --> c, sは、問題を解決するためにそれを変更します。

a --> a, c.そもそもなぜ書いたのですか？あなたはすべての解決策を公正に列挙したかったのではないかと思います。新しいバージョンはしません：

？-フレーズ（a、X）。
X = [];
X = [t1];
X = [t1、t1];
X = [t1、t1、t1];
X = [t1、t1、t1、t1];
X = [t1、t1、t1、t1、t1];
X = [t1、t1、t1、t1、t1、t1];
X = [t1、t1、t1、t1、t1、t1、t1]..。

それは非常に恐ろしいように見えます。実際、それは間違っているように見えます。そうですね。しかし、これで混乱させないでください。ここには無限の文のセットがあります。したがって、Prologによる唯一の正しい応答は、無限に多くの答えを生成することです。なぜなら、それらが有限である場合、いくつかのリストが欠落しているからです！しかしもちろん、それらが公正に列挙されるのを見たいと思います。これを取得するには、次のように記述します。

？-長さ（X、N）、フレーズ（a、X）。
X = []、
N = 0;
X = [t1]、
N = 1;
X = [t2]、
N = 1;
X = [t1、t1]、
N = 2;
X = [t1、t2]、
N = 2;
X = [t2、t1]、
N = 2;
X = [t2、t2]、
N = 2;
X = [t1、t1、t1]、
N =3..。

これは、Prologプログラムの重要なポイントです。常に最初に最良の（可能な）終了プロパティを探してください。そして、Prologが答えを列挙する正確な順序を見ないでください。なぜなら、プログラムがより良い終了特性を持っている場合、それを使用してすべてのソリューションを公正な方法で列挙することは簡単です。しかし：終了を犠牲にして公正な方法で無限に多くの解決策を列挙するプログラムは、より興味深い場合には使用できません。

ファインプリント
この回答を参照してください。

于 2013-01-09T17:13:26.117 に答える
2

非終端記号a//0は再帰的であり、「イプシロン」（空のシーケンスを生成）の両方であり、phrase/2は空の生成の直後にループします。

問題の境界リストの長さを解決できます。

?- between(1,4,Y),length(X,Y),phrase(a,X).

そして、すでに行ったように、左再帰を削除します。

于 2013-01-09T15:47:15.517 に答える