DCG扩展:坚定不移被忽视了吗？

Question

假设我有以下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草案2012-11-20

Answer 1

您的翻译是有效的.它不会影响坚定性.但是,它仍然可能不是很理想.但这取决于您采用的精确实施.考虑:

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,并且call-stack将再次为空.实际上,上述实现无法检测到目标是确定的,因此它们将保留一个选择点.你可以在顶层看到这个:

?- phrase(opcl,"(((())))").
true ;
false.

这个选择点可以干净利落地安全移除call_semidet/1.

opcl2

opcl2将在堆上创建需要由GC回收的四个[')'| _]实例.但是他们正在保存调用堆栈.也就是说,只有尾部递归调用在WAM上非常有效地处理,在TOAM Jr上效率最低,在SWI上相对昂贵.

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

?- phrase(opcl,Xs,Xs).
true ;
Xs = ['(',')'|Xs] ;
Xs = ['(','(',')',')'|Xs] ...

?- set_prolog_flag(occurs_check,true).
true.

?- phrase(opcl,Xs,Xs).
true ;
**LOOPS**

SWI不需要执行单次发生检查opcl1.但它确实适用于每个)人opcl2.

因此,对于这些机器,您的翻译似乎并不合适.但它可能对另一台机器感兴趣,因为没有单独的调用堆栈,而且它不是基于continuation.

调用// 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新的新变量,总是一样的.