为什么我得到一个无限循环（Prolog）

Question

我刚开始学习 Prolog，并且玩了一下。现在我到了一个我卡住了的地步。当我请求

时，我编写的程序进入无限循环

?- q(b).

我不明白为什么会这样。如果有人可以向我解释，那就太好了。

p(a).    
p(b).
q(Y) :- r(X), r(Y).    
r(X) :- r(f(X)).    
r(a) :- p(c).    
r(a) :- p(a).    
r(b) :- p(b).

Answer 1

正如评论中所说，循环是由r/1引起的。要说明原因，请输入 ?- trace, q(b). 查看跟踪（现在忽略单例警告）：

 Call:q(b)
 Call:r(_4244)
 Call:r(f(_4162))
 Call:r(f(f(_4162)))
 Call:r(f(f(f(_4162))))
 Call:r(f(f(f(f(_4162)))))
 Call:r(f(f(f(f(f(_4162))))))
 Call:r(f(f(f(f(f(f(_4162)))))))
 Call:r(f(f(f(f(f(f(f(_4162))))))))

现在你可以看到它试图导出 r/1 进入一个循环。您还可以查看以获得更深入的解释。

请注意，在序言中，子句的顺序很重要。只需尝试将行 r(X) :- r(f(X)). 放在程序的底部。现在尝试 ?- q(b). 在第一个答案上你得到 true 因为序言在进入循环之前将 X 与 a 和 Y 与 b 统一。

Answer 2

另一种确定 non-termination 原因的方法是通过将目标 false 添加到程序中来减少程序执行的推理次数：

q(Y) :- r(X), <b>false</b>, <s>r(Y)</s>.

r(X) :- r(f(X)), <b>false</b>.
<s>r(a) :- <b>false</b>, p(c)</s>.
<s>r(a) :- <b>false</b>, p(a)</s>.
<s>r(b) :- <b>false</b>, p(b)</s>.

?- q(Y).
** LOOPS **

由于这个程序还在循环，你需要在可见部分修改一些东西。请注意有多少东西已被完全删除！不管p/1怎么定义，这个问题都会存在。

如果您仔细查看 q/1，您会发现问题之一：

q(Y) :- r(X), false, r(Y).

可见部分完全没有使用变量Y。 X 只出现一次。因此，r(X) 将是最通用的查询，因此它将有最坏的终止属性可能（这取决于 r/1 的定义，确实如此）。无论如何，q/1的参数对终止没有影响！

还有一个属性结论：子句的顺序对终止没有任何影响属性！很容易看出：用false完全去掉的子句无论出现在什么地方，都可以去掉。

有关更多信息，请参阅 failure-slice。

为什么我得到一个无限循环（Prolog）

Why do I get a Infinite Loop (Prolog)

prolog

infinite-loop