Prolog DCG限制

Question

Prolog DCG限制

6

我希望使用DCGs作为生成器。目前的语法是

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

我想生成所有长度小于某个数字的a。使用?- phrase(a,X),length(X,Y),Y<4.，我可以获得所有少于4个项目的a。然而，当所有组合都用完时，系统（SWI-Prolog 6.2.5）似乎会停滞不前。之前有人在这里问过类似的问题。这里。但是，作为Prolog的新手，我无法使其与上面的语法一起工作。有什么想法吗？

更新：有一个被删除的评论（canrememberthename），建议使用between(1,4,Y),length(X,Y),phrase(a,X)来设置限制。更改我的代码为a-->c,a后，这个方法很好用。

- Ruben Real

我删除了答案，因为它是错误的。你在我调试的时候自己发现了问题... - CapelliC

2个回答

2

非终端符号a//0既是左递归，又是'epsilon'（生成空序列），并且empty production后phrase/2会立即循环。

您可以通过限制列表长度来解决问题：

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

并且，正如您已经做的那样，消除左递归。

- CapelliC

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- false · Accepted Answer

进入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.
   循环。
为了更好地阅读，我将仅使用一个false目标，并划掉查询的其余部分:

?- phrase(a,X),length(X,Y),false, Y<4.
   循环。


让我们进一步简化：

?- phrase(a,X),false,length(X,Y),Y<4.
   循环。


它们都循环！但是我们得到了一些有趣的见解：由于这些带有false的查询不会终止，因此原始程序也不会终止。因此，当您查看查询并且第一个目标本身不终止时，可以得出结论整个查询将不会终止（有关更多详细信息，请参见结尾的注释）。
因此：您必须以某种方式解决第一个目标！
我的第一次尝试是交换length和phrase：

?- length(X,Y), phrase(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.
   loops.

你可能想看实际答案：

?- between(1,3,Y), length(X,Y), phrase(a,X).
   Y = 1, X = [t1]
;  Y = 1, X = [t2]
;  resource_error(local_stack). % ERROR: Out of local stack

你可能会得出这种行为比原来的定义更糟糕的结论。毕竟，我们现在的答案比以前还要少。但正是这种推理方式不能帮助你改善终止：使用 false，两者都是同一种不正确的类型，你必须首先解决这个问题。因此，通过隐藏答案，您可以更好地集中精力处理其他问题。

但是，你的语法为什么有问题呢？我们可以继续使用插入目标false的技术来缩小范围。但这次是在你的语法内部。用目标false装饰的程序称为失败切片。

只是一个实际的备注：当我将false目标插入到您的程序中时，我会保存程序并在SWI中键入make：这样程序会快速重新编译。

尝试后，我得到了以下的最小失败片段。请注意，在DCG中，false必须写成{false}。

几乎你的整个代码库都属于false！因此，您必须解决微小且可见的剩余部分。更改其他地方是毫无意义的。a --> a,...必须更改！事实上，将其更改为a --> c，s可以解决问题。

你为什么首先写下了 a --> a, c. 呢？我怀疑你想公平地列举所有解决方案。但新版本不这样做：

?- phrase(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 的唯一正确响应是产生无限多个答案。因为如果它们是有限的，就会缺少某些列表！但当然，你想看到它们公平地列举出来。要实现这一点，只需编写：

?- length(X,N), phrase(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枚举答案的确切顺序。因为，如果一个程序具有更好的终止属性，使用它以公平的方式枚举所有解决方案几乎是微不足道的。但是：一个在终止上牺牲了而以公平的方式枚举无限多个解决方案的程序，在更有趣的情况下将无法使用。

_{细则
查看此答案。}