回溯递归谓词

Question

假设我们有以下谓词(这是Prolog中编程的一个例子):

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

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

2. 如果用户按下; ,标记放在F1,我们移动到subgoal(isInteger(Y),满足F0)和R = 1.

我理解上面的内容.现在我的问题是:

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

我正在寻找任何解释存在递归的回溯的教程,希望能够帮助我理解堆栈内容的图像.

提前谢谢Suzanne

Answer 1

通过使用图像来理解回溯和递归适用于非常小的示例,但它不能扩展到更大的程序.此外,通过单步执行程序,您很容易错过最有趣的属性.幸运的是,有更好的概念.让我们举个例子吧isInteger/1.

一套解决方案/答案

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

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

终止属性

下一个问题涉及谓词的终止属性.注意,它不能 - 实际上不能 - 终止,如果它必须产生无限多的答案.另一方面,地面查询isInteger(1)有一个或没有解决方案.因此,期望谓词终止于这种情况.但是,您的定义不会在此终止!

失败切片

为了更好地理解这一点,我将使用故障片.也就是说,我会false在你的程序中插入目标.如果生成的程序片段没有终止,则原始程序片段不会终止.

?- isInteger(1), false

isInteger(0) :- false.
isInteger(X) :-
   isInteger(Y), false,
   X is Y+1.

只有很小一部分负责不终止!剩下的部分甚至都没有看到它的价值X.因此,您的程序永远不会终止.不管你怎么称呼它.

有关更多示例,请参阅failure-slice.