SWI-Prolog的截斷機制

我們經常會在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).
將會以以下體例進行操作：
23 = 22 * 2，22 = 21 * 2，21 = 2? * 2，且2? = 1。
4
但若是我們要求上例在給出回覆后繼續回溯，即鍵入分號，則會試圖在常識庫中尋找到另一個事實或法則，使其與上面的方針匹配。這就是說，Prolog搜刮到的另一個Prolog謂詞即是遞歸法則。Prolog與之匹配，使X為2，Y為0，然后Prolog計較Y_tmp獲得-1，并試圖知足方針：
power(X, Y_tmp, Pow_tmp),
這等于在計較2?1，依次進行下去，將試圖計較2?2，2?3，等等。這時無限遞歸呈現了，即遞歸方針持續發生本身，而永遠不克不及知足遏制前提，起頭報錯。
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所做的標識表記標幟要占用年夜量的計較機內存。