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