SWI-Prolog中的截?cái)鄼C(jī)制
在Prolog的遞歸中，我們經(jīng)常會(huì)用到截?cái)唷１M管回溯是Prolog中最有用的機(jī)制之一，但有時(shí)我們希望利用截?cái)鄟砜刂苹厮莸某绦?。Prolog的截?cái)鄼C(jī)制與謂詞failProlog為用戶提供了一種可存在于程
在Prolog的遞歸中，我們經(jīng)常會(huì)用到截?cái)?。盡管回溯是Prolog中最有用的機(jī)制之一，但有時(shí)我們希望利用截?cái)鄟砜刂苹厮莸某绦颉?/p>
Prolog的截?cái)鄼C(jī)制與謂詞fail
Prolog為用戶提供了一種可存在于程序中并控制回溯水平的機(jī)制，即所謂的“截?cái)啵╟ut）”。在Prolog中，截?cái)嗍褂脟@號(hào)“!”來表示。當(dāng)在幾個(gè)目標(biāo)合取中設(shè)置了截?cái)鄷r(shí)，它就像是放置了一扇單向門。截?cái)嘧鳛槟繕?biāo)總是成功的，并且不能重復(fù)滿足。
例如，考慮以下規(guī)則：
```prolog
example :- a, b, c, !, d, e, f.
```
在這個(gè)例子中，Prolog可以在目標(biāo)a、b、c之間任意回溯，但一旦目標(biāo)c被滿足后，通過截?cái)喾?hào)“!”，Prolog將繼續(xù)嘗試滿足目標(biāo)d、e、f，而不會(huì)回溯到c之前的目標(biāo)。即使導(dǎo)致整體目標(biāo)example失敗，也不會(huì)回溯到“!”的位置。
正確選擇遞歸規(guī)則和停止條件
在編寫Prolog程序時(shí)，一個(gè)謂詞通常以多種形式存在，其中一般至少有兩種不同形式的謂詞。這包括遞歸規(guī)則和停止條件。當(dāng)編寫這樣的謂詞時(shí)，必須確保Prolog總是選擇謂詞的正確形式。
例如，考慮以下用于計(jì)算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將以以下方式進(jìn)行操作：
```
Result 2 * 2 * 2,
4 * 2,
8.
```
但如果我們要求上述回答后繼續(xù)回溯，即在輸入分號(hào)時(shí)，Prolog將試圖在知識(shí)庫中尋找另一個(gè)事實(shí)或規(guī)則，使其與上面的目標(biāo)匹配。在這種情況下，Prolog將找到另一個(gè)遞歸規(guī)則，即：
```prolog
power(X, Y_tmp, Pow_tmp) :- power(X, Y_tmp, Pow_tmp), ...
```
Prolog將繼續(xù)匹配該規(guī)則，使X為2，Y_tmp為0，然后Prolog計(jì)算Y_tmp得到-1，并試圖滿足目標(biāo)：`power(X, Y_tmp, Pow_tmp)`。這等于在計(jì)算2的-1次冪，然后繼續(xù)計(jì)算2的-2次冪，2的-3次冪等等。這時(shí)無窮遞歸出現(xiàn)了，即遞歸目標(biāo)連續(xù)產(chǎn)生自身，而永遠(yuǎn)不能滿足停止條件，從而導(dǎo)致錯(cuò)誤。
使用截?cái)啾苊鉄o限遞歸
上述情況顯然不是我們所期望的。然而，可以通過在停止條件中設(shè)置截?cái)鄟肀苊膺@種情況的發(fā)生。下面給出了更加健全和可靠的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.
```
在這個(gè)新的謂詞形式中，截?cái)喾?hào)“!”表示“如果已經(jīng)選擇了某個(gè)規(guī)則，那么決不允許回溯并選擇同一謂詞的其他規(guī)則”。因此，這將產(chǎn)生合理的結(jié)果，并避免了無限遞歸的問題。
類似地，如果有其他遞歸規(guī)則可能產(chǎn)生類似不希望的結(jié)果，可以通過在它們的停止條件中分別添加截?cái)鄟肀苊膺@種情況的發(fā)生。
總結(jié)來說，如果在停止條件中可能需要使用遞歸規(guī)則，請(qǐng)務(wù)必在遞歸謂詞的停止條件中加入截?cái)喾?hào)，以避免無限遞歸的問題。