SWI-Prolog中的截断机制
在Prolog的递归中，我们经常会用到截断。尽管回溯是Prolog中最有用的机制之一，但有时我们希望利用截断来控制回溯的程序。
Prolog的截断机制与谓词fail
Prolog为用户提供了一种可存在于程序中并控制回溯水平的机制，即所谓的“截断（cut）”。在Prolog中，截断使用叹号“!”来表示。当在几个目标合取中设置了截断时，它就像是放置了一扇单向门。截断作为目标总是成功的，并且不能重复满足。
例如，考虑以下规则：
```prolog
example :- a, b, c, !, d, e, f.
```
在这个例子中，Prolog可以在目标a、b、c之间任意回溯，但一旦目标c被满足后，通过截断符号“!”，Prolog将继续尝试满足目标d、e、f，而不会回溯到c之前的目标。即使导致整体目标example失败，也不会回溯到“!”的位置。
正确选择递归规则和停止条件
在编写Prolog程序时，一个谓词通常以多种形式存在，其中一般至少有两种不同形式的谓词。这包括递归规则和停止条件。当编写这样的谓词时，必须确保Prolog总是选择谓词的正确形式。
例如，考虑以下用于计算X的Y次幂的程序：
```prolog
power(_, 0, 1).
power(X, Y, Pow) :- Y_tmp is Y - 1, power(X, Y_tmp, Pow_tmp), Pow is Pow_tmp * X.
```
如果我们向Prolog提出询问：
```prolog
?- power(2, 3, Result).
```
Prolog将以以下方式进行操作：
```
Result 2 * 2 * 2,
4 * 2,
8.
```
但如果我们要求上述回答后继续回溯，即在输入分号时，Prolog将试图在知识库中寻找另一个事实或规则，使其与上面的目标匹配。在这种情况下，Prolog将找到另一个递归规则，即：
```prolog
power(X, Y_tmp, Pow_tmp) :- power(X, Y_tmp, Pow_tmp), ...
```
Prolog将继续匹配该规则，使X为2，Y_tmp为0，然后Prolog计算Y_tmp得到-1，并试图满足目标：`power(X, Y_tmp, Pow_tmp)`。这等于在计算2的-1次幂，然后继续计算2的-2次幂，2的-3次幂等等。这时无穷递归出现了，即递归目标连续产生自身，而永远不能满足停止条件，从而导致错误。
使用截断避免无限递归
上述情况显然不是我们所期望的。然而，可以通过在停止条件中设置截断来避免这种情况的发生。下面给出了更加健全和可靠的power谓词形式：
```prolog
power(_, 0, 1) :- !.
power(X, Y, Pow) :- Y_tmp is Y - 1, power(X, Y_tmp, Pow_tmp), Pow is Pow_tmp * X.
```
在这个新的谓词形式中，截断符号“!”表示“如果已经选择了某个规则，那么决不允许回溯并选择同一谓词的其他规则”。因此，这将产生合理的结果，并避免了无限递归的问题。
类似地，如果有其他递归规则可能产生类似不希望的结果，可以通过在它们的停止条件中分别添加截断来避免这种情况的发生。
总结来说，如果在停止条件中可能需要使用递归规则，请务必在递归谓词的停止条件中加入截断符号，以避免无限递归的问题。
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
