prolog - 递归谓词中的回溯

Question

假设我们有以下谓词(这是Programming in Prolog的示例):

[F0] isInteger(0).
[F1] isInteger(X):- isInteger(Y), X is Y+1.

查询的第一个结果是Integer(R)，标记位于F0，并将返回R = 0

如果用户按下; ，将标记放置在F1处，我们将移至subgoal(isInteger(Y)，满足F0)且R = 1。

我了解以上内容。现在这是我的问题:

如果用户按下;再次，标记在哪里？搜索如何返回R = 2？我试图理解本书第78-79页中的图像，但是我不清楚。我发现的在线教程在存在递归的情况下不处理回溯。

我正在寻找可以解释递归时回溯的任何教程，希望它们中的堆栈内容图像可以帮助我理解。

先感谢您
苏珊娜

Answer 1

通过图像了解回溯和递归仅适用于很小的示例，但不能扩展到较大的程序。此外，通过逐步执行程序，您很容易错过最有趣的属性。幸运的是，有比这更好的概念。让我们以isInteger/1为例。

解决方案/答案集

您的主要兴趣是确保描述正确的事情。在这里，第二条规则是最有趣的。按箭头:-的方向阅读。也就是说，从右到左:提供的Y是整数，然后X is Y+1也是X是整数。

然后，您可以估计在这种情况下无限的解集。

端接特性

下一个问题涉及谓词的终止属性。请注意，如果必须产生无限多个答案，它就不能终止-实际上一定不能-终止。另一方面，诸如isInteger(1)之类的地面查询要么没有解决方案，要么没有解决方案。因此，希望谓词在这种情况下终止。但是，您的定义不会在这里终止!

失败切片

为了更好地理解这一点，我将使用failure-slice。也就是说，我将目标 false 插入到您的程序中。如果生成的程序片段未终止，则原始程序片段不会终止。

？-isInteger(1)，否

isInteger(0):-否
isInteger(X):-
isInteger(Y)，false，
X是Y + 1。

只有很小一部分负责不终止!其余部分甚至根本不查看X的值。因此，您的程序永远不会终止。不管你怎么称呼它。

有关更多示例，请参见failure-slice。