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 扩展不坚定，则不允许
将 [41|B] 放在 expr 调用的第三个参数中。

但我想踏实已经到位，所以一切都应该没问题吧？

再见

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
定句语法规则
Klaus Daessler
2012 年 11 月 20 日
N238 DIN Draft 2012-11-20

4

1 回答 1

4

您的翻译是有效的。它不影响坚定性。但是，它仍然可能不是很理想。但这取决于您使用的精确实现。考虑：

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

将 Prolog 标志double_quotes设置为chars，第二个子句现在可以扩展为

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，并且调用堆栈将再次为空。实际上，上述实现无法检测到目标是确定的，因此它们会留下一个选择点。你可以在顶层看到这个：

?- 短语(opcl,"(((())))")。
真的 ;
错误的。

可以使用 干净、安全地删除这个选择点call_semidet/1。

opcl2

opcl2将在需要被 GC 回收的堆上创建四个 [')'|_] 实例。但是他们正在保存调用堆栈。也就是说，只有尾递归调用在 WAM 上得到了非常有效的处理，在 TOAM Jr. 上的处理效率最低，在 SWI 上的处理成本相对较高。

当我们考虑使用发生检查执行时，事情变得更加昂贵。在 Qu-Prolog 中它始终处于开启状态，而在 SWI、XSB 和 CX 中，您可以使用如下标志启用它：

?- 短语（opcl，Xs，Xs）。
真的 ;
Xs = ['(',')'|Xs] ;
Xs = ['(','(',')',')'|Xs] ...

?- set_prolog_flag(occurs_check,true)。
真的。

?- 短语（opcl，Xs，Xs）。
真的 ;
**循环**

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 回答