3

私はGNU Prologの動作を掘り下げようとしています:

test(X,I,O) :- phrase(X,I,O).
?- test(("a",!,"b"),"ab","").

フレーズ/3 が何に変換されるかを確認する標準的な方法はありますか?

ISO DCG 提案 (*) によると、expand_term/2 が必要です。これで、次のことを確認できます。

?- expand_term((foo --> "a", !, "b"),X).
X = (foo([97|A],B):-!,A=[98|B])

これは、フレーズ/3 が私のテスト/3 でどのように使用されているかを教えてくれますか?

(*) ISO/IEC DTR 13211–3:2006 確定
節文法規則
Klaus Daessler
2012 年 11 月 20 日
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dcgs/dcgsdin121120.pdf

4

2 に答える 2

3

フレーズ/3 が翻訳するものを確認する標準的な方法はありますか?

いいえ。 の意味phrase/3は定義されていますが、背後にある実際の実装にはアクセスできません。いくつかの異なる方法があり、どのphrase/3ように定義することができます。それはYAP のように単純かもしれません:

phrase(P, S0, S) :-
        call(P, S0, S).

または、（またはそのようなもの）を使用できますexpand_term/2。あれは：

phrase(P, S0, S) :-
   expand_term(( pseudont --> P ), ( pseudont(CS0, CS) :- Goal) )),
   S0 = CS0,
   S = CS,
   Goal.

を呼び出した後、最終的な統合を実行できGoalます。

phrase(P, S0, S) :-
   expand_term(( pseudont --> P ), ( pseudont(CS0, CS) :- Goal) )),
   S0 = CS0,
   Goal,
   S = CS.

そして、それによって、セミコンテキストの存在下で末尾再帰を許可する最後の引数で、展開された述語が常にインスタンス化されておらず、エイリアス化されていない変数で呼び出されるという (実装に依存する) 規則が導入されます。

それはすべて実装者次第です。

これは、フレーズ/3 が私のテスト/3 でどのように使用されているかを教えてくれますか?

いいえ、言うまでもありません。

しかし、なぜあなたは尋ねるのですか？または、言い換えると：

の異なるが適合する実装は、どのような影響を与える可能性がありphrase/3ますか?

リソース消費

これは明らかなはずです。?- phrase([],Xs).どちらが YAP のヒープ上に項を作成しないが、上記の単純な拡張では作成するかを検討してくださいexpand_term。ただし、リソース消費は現在の基準の範囲外です。

変数の順序付け

..., phrase([], Xs, Xs), ...YAPのルールの本体を考えてみましょう。Xsローカル変数のままですが、expand_termベースのフレーズはそれをグローバルにします。多くの実装では、これは変数の相対的な順序に影響します。現在、標準は 7.2.1 で明示的に述べています。

X と Y が同一でない変数である場合、
X term_precedes Y は
、ソートされたリスト (
7.1.6.5、8.10.3.1 j) の作成中に順序が一定のままであることを除いて、実装に依存するものとします。

したがって、これも問題ではありませんが、それでも煩わしい場合があります。

NSTO プロパティ

Prolog 標準 (つまり、パート 1 ISO/IEC 13211-1) は、NSTO の場合の実行のみを定義します。つまり、実行中に発生するすべての統合が NSTO である場合 — 発生チェックの対象ではありません (7.3.3 を参照)。

ここで、あなたのケースを考えてみましょう: phrase(("a",!,"b"), Xs, Ys). 一見すると、これは と同等phrase("ab", Xs, Ys)です。しかし、ここで仮定を考えてみましょうset_prolog_flag(double_quotes,chars)

?- Xs = [c|_], Xs = Ys, phrase(("a",!,"b"), Xs, Ys).

このクエリは間違いなく失敗するはずです。しかし、それはNSTOですか？単純に、これを次のように置き換えることができると仮定できます。

?- Xs = [c|_], Xs = Ys, Xs = [a,b|Ys].

これは次のことと同じです:

?- Xs = [c|_], Xs = [a,b|Xs].

明らかに、Xs = [a,b|Xs]単独で STO (発生チェックの対象) です。しかし、両方一緒でもSTOです！これを理解するには、7.3.2 の Herbrand アルゴリズムを検討してください。本質的に、それは方程式を「任意の順序で」非決定論的に書き換えます。そのような派生の 1 つを次に示します。

          Xs = [c|Zs], Xs = [a,b|Xs].
(7.3.2 f) Xs = [c|Zs], [c|Zs] = [a,b,c|Zs].
(7.3.2 d) Xs = [c|Zs], c = a, Zs = [b,c|Zs].
(7.3.2 g) failure (not unifiable, positive occurs-check)

もちろん、この派生は異常です。通常、 が存在するとすぐに失敗しますc = aが、アルゴリズムはこの点で非決定論的です。そして、すべての可能な派生が 7.3.2 g につながらない場合にのみ、一連の方程式が NSTO になります。7.3.3 を引用するには:

一連の方程式 (または 2 つの項) は、 7.3.2 g が発生する ように Herbrand アルゴリズムのステップ
を進める方法が存在しない場合、「発生チェックの対象外」(NSTO)です。

freeze/2 と when/2

これらの構造も影響を受ける可能性があります。それらは現在、既存の標準文書ではカバーされていませんが、潜在的な影響を理解することは依然として重要です。検討：

?- freeze(L, (X=1;X=2)), phrase(("a",!,"b"),L).
L = [a, b],
X = 1.

B、SICStus、SWI、YAP はすべて、この 1 つの答えを生成します。だから、カットは重要です。

いずれにせよ、お問い合わせいただきありがとうございます。質問に回答している間だけ、NSTO の問題を理解しました。これは明らかに、DCG 変換の定式化に何らかの影響を与えます。

于 2013-01-04T02:30:43.253 に答える
1

ISO DCGは、実行された用語としてどのphrase / 3が使用されているかを把握する方法を定義していないため、それを把握する唯一の方法は、ソースコードを参照することです。それはここにあります：

http://sourceforge.net/projects/gprolog/

phrase / 3述語は、expand.plというファイルで定義されています。その定義は'$dcg_trans_body'/4を使用します。私たちはそれをチェックすることができます：

GNU Prolog 1.4.2
By Daniel Diaz
Copyright (C) 1999-2012 Daniel Diaz
| ?- '$dcg_trans_body'(("a",!,"b"), In, Out1, Body).

Body = (!,A=[98|Out1])
In = [97|A]

したがって、最初の端末は、fooルールの場合と同様に、実際にInパラメーターにマージされます。これはphrase/3が呼び出されたときに行われるため、問題にはなりません。

于 2013-01-04T03:51:47.497 に答える