Prolog 递归无限循环。

Question

inside(a,b).
inside(a,c).
inside(b,d).
r_inside(X,Y) :- inside(X,Y).
r_inside(X,Y) :- inside(X,Z), r_inside(Z,Y).

上面的代码很好用，当我尝试在一个with语句中查找任何内容时：r_inside(a,X)，我得到了X=b,c,d，这是正确的。 但是如果我将代码的最后一行改成：

r_inside(X,Y) :- r_inside(X,Z), inside(Z,Y).

然后我输入：r_inside(a,X)，程序会一直循环，为什么？

- leo

Answer 1

所以，明确一下，我们正在谈论这个程序：

inside(a,b).
inside(a,c).
inside(b,d).
r_inside(X,Y) :- inside(X,Y).
r_inside(X,Y) :- r_inside(X,Z), inside(Z,Y).

和查询：

?- r_inside(a, X).
X = b ;
X = c ;
X = d ;
不终止

为了突出查询的“不终止”方面（而不被任何具体解决方案所分散注意力），我们可以使用：

?- r_inside(a, X), false.
不终止

要找到不终止的原因，我们可以使用基于程序切片的强大声明式调试方法（请参见failure-slice）。思路是在程序中插入false/0，以便找到更小的（理想情况下：最小的）代码片段，它们仍然不会终止。

例如，考虑您代码的以下版本：

``` inside(a,b) :- false. inside(a,c) :- false. inside(b,d) :- false.

r_inside(X,Y) :- false, inside(X,Y). r_inside(X,Y) :- r_inside(X,Z), false, inside(Z,Y). ```

使用这个版本，我们仍然得到：

``` ?- r_inside(a, X), false. nontermination ```

现在我使用删除线来划掉先前版本中那些可以忽略的部分，因为它们不能导致非终止：

``` inside(a,b) :- false. inside(a,c) :- false. inside(b,d) :- false. r_inside(X,Y) :- false, inside(X,Y). r_inside(X,Y) :- r_inside(X,Z), false, inside(Z,Y). ```

因此，我们将其简化为以下关于非终止的解释，因为这是唯一剩下的片段：

``` r_inside(X,Y) :- r_inside(X,Z). ```

这个“片段”本身就会导致非终止。无论你添加什么事实，或者在单个剩余目标之后添加什么目标，都不能阻止这种情况发生。

因此，要解决这个问题，你必须改变这个“片段”。

你还可以通过考虑Prolog的实际执行策略来“操作性地”解释非终止。特别是，你可以使用其执行的“深度优先”方面进行论证。然而，为什么要费心去做这样低级的解释呢？你可以自动生成失败切片，它们让你更直接地看到非终止的实际原因。

- mat

---

谢谢你的调试建议！ 我发现无论是<br/> r_inside(X,Y) :- inside(X,Z), r_inside(Z,Y).<br/> 还是<br/> r_inside(X,Y) :- inside(Z,Y), r_inside(X,Z).<br/> 都可以很好地解决问题，只需要将它们写成“尾递归”形式，我仍在努力想象执行细节。 - leo

理解Prolog中精确的控制流非常困难，对于初学者来说太难了。如果你想尝试它，请从我的帖子中的最终片段开始，然后再使用前面的版本，最后使用原始代码。 - mat

Answer 2

Prolog是从语言处理研究中发明的，它表现出这样的遗产。你描述的问题被称为左递归。最近SWI-Prolog引入了tabling，跟随其他Prologs模型，作为一种通用工具来克服这种限制。

- CapelliC

---

谢谢！我是Prolog的新手，你能解释一下左递归的问题吗？我知道在其他编程语言中，左递归不可优化，但是允许使用。 - leo