当前位置：网站首页 > 创业 > 正文

SWI-Prolog的截断机制

张子豪 2025-10-11 15:16 1

我们经常会在Prolog的递归顶用到截断。尽管回溯是Prolog中最有效的机制之一，但有时我们但愿操纵截断节制回溯的法式。在这篇经验中，我将介绍截断机制与谓词fail。

1的递归

1的算术运算

东西/原料

电脑
SWI-Prolog

包管准确地选择法则

1
Prolog为用户供给了一种可存在于法式中并节制回溯程度的机制，即所谓的“截断（cut）”。Porlog顶用叹号“!”暗示截断。当在几个方针合取中设置了截断时，其感化就恰似安上了一扇单标的目的门。截断作为方针老是当作功的，且不克不及反复知足。例如，下面的法则：
example :- a, b, c, !, d, e, f.
Prolog可以在方针a、b、c之间肆意回溯，但一旦方针c一经知足，将经由过程截断符号，然后Prolog继续沿着方针链试图知足方针d、e、f，回溯可能在d、e、f之进步行，然而不克不及经由过程“!”回溯前面的，即使导致总体方针example掉败也是如斯。
2
法式中一个谓词经常以多种形式存在，此中一般至少有两种分歧形式的谓词丰硕，即递归法则和遏制前提。当编写如许的谓词时，必需包管Prolog老是选择谓词的准确形式。如当Prolog该当采用遏制前提时，就不该选择递归法则，不然会导致无限递归。例如，下面这个法式是用于计较X的Y次幂。
2的根基概念和语律例则
1的递归
3
若是我们对Prolog提出扣问：
?- power(2,3,Result).
将会以以下体例进行操作：
2³ = 2² * 2，2² = 2¹ * 2，2¹ = 2⁰ * 2，且2⁰ = 1。
4
但若是我们要求上例在给出回覆后继续回溯，即键入分号，则会试图在常识库中寻找到另一个事实或法则，使其与上面的方针匹配。这就是说，Prolog搜刮到的另一个Prolog谓词即是递归法则。Prolog与之匹配，使X为2，Y为0，然后Prolog计较Y_tmp获得-1，并试图知足方针：
power(X, Y_tmp, Pow_tmp),
这等于在计较2⁻¹，依次进行下去，将试图计较2⁻²，2⁻³，等等。这时无限递归呈现了，即递归方针持续发生本身，而永远不克不及知足遏制前提，起头报错。
5
上面的环境显然不是我们所期望的，它可以经由过程在遏制前提中设置截断而得以避免，如许就获得了下列新的、加倍健全和靠得住的power谓词形式：
power(_, 0, 1). :- !.
power(X, Y, Pow) :- Y_tmp is Y - 1, power(X, Y_tmp, Pow_tmp),
Pow is Pow_tmp * X.
这里截断符号暗示“若是已经选择了某个法则，那么决不许可回溯并选择统一谓詞的其他法则”。是以，这将会发生合理成果。
6
此时我们可能已经意识到上一节中给出的两递归法则也会发生近似的、不但愿的成果，而这可以经由过程在它们的遏制前提平分别插手截断而加以避免。插手截断后的法式如图所示。
总而言之，若是在遏制前提处可能用到递归法则，那么必需在递归谓词的遏制前提中插手截断符号。

截断与谓词fail的联用

1
截断的另一个常用体例是与谓词fail联用。fail是一个Prolog尺度谓词，因为它老是掉败，因而可引起回溯。截断可设置在fail前面，以防止掉败后的回溯。
考虑图中的法式。这里截断与fail联用可以包管当一个雇员知足某个表白其不合适候选前提的法则时，在其它任何法则都不再考虑。例如，一个员工小于50岁，谓词fail将使方针eligible掉败，而截断则包管在其它两个eligible法则中都不考虑他。
2
该当注重，截断与fail联用凡是可用否认谓词“\+”取代，\+是Prolog另一个尺度谓词，若是方针X掉败，则方针\+(X)当作功；若是X当作功，则会掉败。是以上面法式可以重写为图片中的形式。
这里把三个eligible法则合当作为一个法则，这两种编程体例中哪种可读性更高呢？关于这一问题存在争议，因为这取决于对截断的理解水平。
2的根基概念和语律例则

操纵截断节制回溯水平的原因

尽管回溯是Prolog说话中最有效的机制之一，但基于下述来由，有时我们但愿节制回溯的水平：
❶我们可能不但愿Prolog得出问题的全数解，因为有些解对我们来说可能没有任何用处；
❷一旦找到一个特心猿意马的解，就没有需要去找其它更多的解，而其它解可能现实上是不准确的；
❸年夜量回溯会使法式运行的效率很低，此中有两个原因，一是回溯要破费一些时候才能完当作，二是回溯中Prolog所做的标识表记标帜要占用年夜量的计较机内存。