9

假设我们有以下谓词（这是Prolog中的一个示例）：

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

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

  2. 如果用户按下；，标记放置在F1，我们移动到子目标（isInteger（Y），满足F0）和R = 1。

我明白以上。现在这是我的问题：

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

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

提前谢谢苏珊娜

4

2 回答 2

8

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

一套解决方案/答案

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

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

终端属性

下一个问题涉及谓词的终止属性。请注意，如果它必须产生无限多的答案，它就不能——事实上绝不能——终止。另一方面，像地面查询这样isInteger(1)的问题要么有一个解决方案，要么没有解决方案。因此，对于这种情况，谓词终止是可取的。但是，您的定义不会在这里终止！

失败切片

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

?- isInteger(1), false

isInteger(0) :-假。
是整数（X）： -
   isInteger(Y), false ,
    X 是 Y+1。

只有极少部分负责不终止！剩下的部分根本不看值X。因此，您的程序永远不会终止。不管你怎么称呼它。

有关更多示例，请参见。

于 2013-01-02T01:45:28.403 回答
0

在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).

通过检查 2 是否为整数? - isInteger(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

非常好。

我将向当地团队解释这一点。这是一个带有一些“原始符号”的整数枚举过程的说明。希望不言自明。

整数枚举回溯图

于 2014-12-01T00:23:32.980 回答