递归谓词中的回溯 [英] Backtracking in recursive predicates

问题描述

假设我们有以下谓词(这是来自 在 Prolog 中编程):

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

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

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

我明白了上面的内容.下面是我的问题:

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

我正在寻找任何解释存在递归时回溯的教程，希望能提供有助于我理解的堆栈内容图像.

先谢谢你苏珊

解决方案

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

解决方案/答案集

您的主要兴趣是确保您描述的是正确的事情.在这里，第二条规则最有趣.按照箭头 :- 的方向阅读.也就是说，从右到左:如果 Y 是一个整数，并且 X 是 Y+1 那么X 也是一个整数.

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

终止属性

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

失败切片

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

<预>?- isInteger(1), falseisInteger(0) :- false.isInteger(X) :-isInteger(Y), false,X 是 Y+1.

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

参见failure-slice更多示例.

Assume we have the following predicates (This is an example from Programming in Prolog):

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

1. The first result for query isInteger(R), the marker is placed at F0, and will return R=0

2. If user presses ; , the marker is placed at F1, we move to subgoal(isInteger(Y), which is satisfied with F0) and R=1.

I understand the above. Now here are my questions:

1. If user presses ; again, where is the marker? How does the search proceed to return R=2? I have tried to understand the images in page 78-79 of the book, but it is not clear to me. The online tutorials that I found, do not handle backtracking in presence of recursion.

I am looking for any tutorials that explain backtracking in presence of recursion, hopefully with images of stack contents that helps me understand.

Thank you in advance Suzanne

解决方案

Understanding backtracking and recursion by using images works for very tiny examples, but it does not scale to larger programs. Also, by stepping through a program you easily miss the most interesting properties. Fortunately, there are better notions than that. Let's take your example isInteger/1.

Set of solutions/answers

Your primary interest is to ensure that you are describing the right thing. Here, the second rule is most interesting. Read it in the direction of the arrow :-. That is, right-to-left: Provided Y is an integer, and X is Y+1 then also X is an integer.

Then, you can estimate the set of solutions which is infinite in this case.

Termination properties

The next question concerns the termination properties of the predicate. Note, that it cannot – in fact must not – terminate, if it has to produce infinitely many answers. On the other hand, ground queries like isInteger(1) have either one or no solution. So it is desirable that the predicate terminates for such cases. However, your definition does not terminate here!

Failure slices

To better understand this, I will use a failure-slice. That is, I will insert goals false into your program. If the resulting program fragment does not terminate, then the original doesn't.

?- isInteger(1), false

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

Only a very small part is responsible for non-termination! The remaining part does not even look at the value of X at all. Therefore your program terminates never. No matter how you call it.

See failure-slice for more examples.

这篇关于递归谓词中的回溯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！