递归谓词中的回溯技术

Question

假设我们有以下谓词（这是来自Prolog编程的示例）：

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

1. 查询结果的第一个是 isInteger(R)，标记放置在 F0 处，返回 R=0。

2. 如果用户按下 ; ，标记将移动到 F1，然后我们进入子目标 isInteger(Y)（该子目标使用 F0 满足），R=1。

我理解上述内容。现在我的问题是：

1. 如果用户再次按下 ; ，标记将在哪里？如何进行搜索以返回 R=2？我尝试理解书中第 78-79 页的图片，但对我来说不太清楚。我找到的在线教程没有处理递归存在情况下的回溯。

我正在寻找任何解释递归存在情况下的回溯的教程，希望能提供帮助我理解的栈内容的图像。

提前感谢！ Suzanne

- Suzanne L.

Answer 1

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

解集/答案集

您的主要兴趣是确保您正在描述正确的事物。在这里，第二条规则最有趣。按箭头:-的方向从右到左阅读它：如果Y是整数，并且X是Y+1，则X也是整数。

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

终止属性

下一个问题涉及谓词的终止属性。请注意，如果必须生成无限多个答案，则它不能（实际上不得）终止。另一方面，像isInteger(1)这样的ground查询只有一个或零个解。因此，对于这些情况，希望谓词终止。但是，您的定义在这里没有终止！

失败切片

为了更好地理解，我将使用一个失败切片。也就是说，我将在您的程序中插入目标false。如果结果程序片段不终止，则原始程序也不会终止。

？- isInteger(1),false

isInteger(0) :- false.
isInteger(X) ：
   isInteger(Y)，false，
   X is Y+1。

只有非常小的一部分负责非终止！其余部分甚至根本不看X的值。因此，您的程序永远不会终止。无论您如何调用它。

请参见失败切片以获取更多示例。

- false

Answer 2

在swish控制台中跟踪此内容：

% Handover to indenting predicate

isInteger(X) :- isInteger(X,0).

% As isInteger(), with printouts

isInteger(0,I) :- ws(I), format('0 reached\n').
isInteger(X,I) :- wrout('>', X,Y,I), ID is I+1, isInteger(Y,ID), wrout('<', X,Y,I), X is Y+1, wsucc(I).

% Writing out

wrout(C,X,Y,I) :-ws(I),format('~a X=',C),write(X),format(',Y='),write(Y),format('\n').

% Writing "success"

wsucc(I) :- ws(I),format('success\n').

% Indenting by 2*N underscores

ws(0).
ws(N) :- N>0, format('__'), ND is N-1, ws(ND).

通过? - isInteger(2)检查2是否为整数（但不要调用Next，否则会发生无限搜索！）

> X=2,Y=_G5707
__0 reached
< X=2,Y=0
__> X=_G5707,Y=_G6473
____0 reached
__< X=_G5707,Y=0
__success
< X=2,Y=1
success
true

使用?- isInteger(I)枚举整数

0 reached
I = 0

"

下一个

"

> X=_G5328,Y=_G5926
__0 reached
< X=_G5328,Y=0
success
I = 1

"下一个"（请注意，我们从缩进'__'重新开始）

__> X=_G5926,Y=_G391
____0 reached
__< X=_G289,Y=0
__success
< X=_G257,Y=1
success
I = 2

"下一个"（请注意，我们从缩进处重新开始）

____> X=_G391,Y=_G3260
______0 reached
____< X=_G391,Y=0
____success
__< X=_G289,Y=1
__success
< X=_G257,Y=2
success
I = 3

非常好。

我将向本地团队解释这个问题。这里有一个整数枚举过程的示例，带有一些“原始符号”。希望可以自我解释。

- David Tonhofer

---

你所调用的程序不适用于枚举自然数。 - false

@false 很好的观点！显然我错了。我需要更多地思考这个问题。 - David Tonhofer