6

次のDCGルールがあると仮定します。

 factor(X) --> "(", expr(X), ")".

通常、これは次のように変換されます。

 factor(X, A, B) :-
    [40|C] = A, expr(X, C, D), [41|B] = D.

Prologシステムはそれを次のように翻訳することを許可されますか？つまり
、統一を頭と目標に統合することはできますか？

 factor(X, [40|A], B) :-
    expr(X, A, [41|B]).

DCG拡張が安定しない場合
、expr呼び出しの3番目の引数に[41|B]を入れることは許可されません。

しかし、私は不動が整っていると思うので、すべてが大丈夫なはずですか？

さよなら

PS：不動の非公式な定義については、以下を参照してください
。Richard O'Keefe、2009年：
「Prologプログラミングにおける「不動」という用語の発明者として、
私はそれを支持する必要があります。不動は、基本的に
、述語を強制的に下げることができないことを意味します。
出力引数を間違って入力することによる間違ったパス。」
http://blog.gmane.org/gmane.comp.ai.prolog.swi/month=20090301

PSS：他のDCG変換については、たとえば最新の
DCG標準提案を参照してください。付録には、DCGトランスレータの
ソースコードが含まれています
。ISO/ IEC DTR 13211–3：2006
明確な句の文法規則
KlausDaessler
2012年11月20日
N238DINドラフト2012-11-20

4

1 に答える 1

4

あなたの翻訳は有効なものです。安定性には影響しません。ただし、それでもあまり望ましくない場合があります。ただし、これは使用する正確な実装によって異なります。検討：

opcl --> "".
opcl --> "(", opcl, ")".

Prologフラグdouble_quotesをに設定するcharsと、2番目の句が次のように展開される可能性があります

opcl1(['('|S0],S) :-
   opcl1(S0,S1),
   S1 = [')'|S].

また

opcl2(['('|S0],S) :-
   opcl2(S0,[')'|S]).

ここで、目標について考えてみましょうphrase(opcl,"(((())))"。

WAM（YAP、SICStusなど）、ZIP（SWI）、TOAM Jr.（B）などの一般的なマシンの場合：

opcl1

opcl1手続き型制御のコールスタックを使用して、リストの有効性をテストするだけです。成功すると、cons-cellは作成されず、call-stackは再び空になります。実際、上記の実装では、目標が確定していることを検出できないため、1つの選択ポイントを開いたままにします。これはトップレベルで確認できます。

？-phrase（opcl、 "（（（（））））"）。
true;
false。

この選択ポイントは、を使用してクリーンかつ安全に削除できますcall_semidet/1。

opcl2

opcl2GCによって再利用される必要があるヒープ上に['）'|_]の4つのインスタンスを作成します。しかし、彼らはコールスタックを保存しています。つまり、WAMで非常に効率的に処理され、TOAM Jr.で最小限の効率で処理され、SWIで比較的コストがかかる末尾再帰呼び出しのみが存在します。

発生チェックを使用した実行を検討すると、事態はさらにコストがかかります。Qu-Prologでは常にオンになっており、SWI、XSB、CXでは次のようなフラグで有効にできます。

？-フレーズ（opcl、Xs、Xs）。
true;
Xs = ['（'、'）' | Xs];
Xs = ['（'、'（'、'）'、'）' |Xs]..。

？-set_prolog_flag（occurs_check、true）。
本当。

？-フレーズ（opcl、Xs、Xs）。
true;
**ループ**

SWIは単一の発生を実行する必要はありません-を確認してくださいopcl1。しかし、それはのそれぞれに対してそうし)ますopcl2。

したがって、これらのマシンの場合、翻訳は適切に表示されません。ただし、個別のコールスタックがなく、継続に基づいていない別のマシンでは興味深い場合があります。

電話//1

翻訳すると、内の正確な接続が変更されますcall//1。ただし、内の目標call//1は常にそれが不動であるような方法で書かれなければなりません！そうしないと、呼び出し時に違いがすでに見られる可能性がありますphrase(call(Cont),Xs0,Xs)。適合の場合、Contこれはと同じになりますphrase(call(Cont),Xs0,XsC), XsC=Xs

不動性についてのあなたの引用に関して：それは概念の非常に非公式な定義です。結局のところ、「間違って」とはどういう意味ですか？

phrase/3これまでのところ、不動の最良の定義は次のとおりです。

phrase(NT, Xs0,Xs)そしてphrase(NT, Xs0, XsC), XsC = Xs、XsC新しい変数を使用すると、常に同じになります。

于 2012-10-27T21:25:56.317 に答える