遞歸另外在Prolog中

Question

知識庫

add(0,Y,Y). // clause 1 
add(succ(X),Y,succ(Z)) :- add(X,Y,Z). // clause 2 

查詢

add(succ(succ(succ(0))), succ(succ(0)), R) 

痕量

Call: (6) add(succ(succ(succ(0))), succ(succ(0)), R) 
Call: (7) add(succ(succ(0)), succ(succ(0)), _G648) 
Call: (8) add(succ(0), succ(succ(0)), _G650) 
Call: (9) add(0, succ(succ(0)), _G652) 
Exit: (9) add(0, succ(succ(0)), succ(succ(0))) 
Exit: (8) add(succ(0), succ(succ(0)), succ(succ(succ(0)))) 
Exit: (7) add(succ(succ(0)), succ(succ(0)), succ(succ(succ(succ(0))))) 
Exit: (6) add(succ(succ(succ(0))), succ(succ(0)), succ(succ(succ(succ(succ(0)))))) 

我的問題

• 我看到如何在第遞歸調用2條的最外SUCC（） 在每個呼叫對參數1.
• 我看看它是如何在增加了一個外SUCC（）以3參數每次通話。
• 我看到當第一個參數作爲這些遞歸調用 的結果達到0.此時，我看到1st子句如何將第二個參數 複製到第三個參數。

這是我困惑的地方。

1. 一旦執行第1條款，並在第2條自動 得到執行爲好，然後加入SUCC（）第一個參數？

2. 另外，程序如何終止，爲什麼它不會僅僅保持 無限地爲第一個和第三個參數添加succ（）？

從LearnPrologNow.com解釋（我不知道）

讓我們通過使用方式的Prolog來處理這個查詢走一步看一步。下面給出了查詢的跟蹤和搜索樹的 。

第一個參數不是0，這意味着只能使用add/3的第二個子句 。這導致遞歸調用add/3。將 最外面的succ函數從原始查詢 的第一個參數中刪除，結果將成爲遞歸查詢的第一個參數。第二個參數不變地傳遞給 遞歸查詢，遞歸查詢的第三個參數是一個 變量，下面給出的跟蹤中的內部變量_G648。注意 _G648尚未實例化。但是它與R （我們用作原始 查詢中的第三個參數的變量）共享值，因爲當查詢是 與第二個子句的頭部統一時，R被實例化爲succ（_G648）。但這意味着R是 不再是一個完全沒有實際意義的變量。現在它是一個複雜的 術語，它有一個（未被證實的）變量作爲它的參數。

接下來的兩個步驟基本相同。隨着每一步的第一個參數變成一個succ小一層;下面給出的跟蹤和 搜索樹都很好地顯示了這一點。與此同時，在每一步都會向R添加一個仿函數，但始終將最內層的變量 變爲無實際意義。在第一次遞歸調用R之後是 succ（_G648）。在第二次遞歸調用之後，_G648被succ（_G650）實例化爲 ，所以R是succ（succ（_G650）。在第三次遞歸調用之後，_G650被succ（_G652）實例化並且因此 變爲succ（succ （SUCC（_G652）））。搜索樹顯示這一步 一步實例。

在這個階段，所有SUCC函子已經被扒掉第一 參數，我們可以應用基本條款。第三個參數是 等同於第二個參數，因此複數項R中的'hole'（未示例的 變量）最終被填充，並且我們通過。

Answer 1

讓我們從術語開始。

這些都是條款，爲你正確地指出：

 
add(0, Y, Y). 
add(succ(X), Y, succ(Z)) :- add(X, Y, Z). 

讓我們先查看這個程序聲明，只是爲了確保我們正確理解其含義：

1. 0加Y是Y。這是有道理的。
2. 如果這是真的，X加Y是Z然後這是事實的X加  Y的接班人是  Z的繼任者。

這是一個很好的方式來閱讀這個定義，因爲它是足夠一般的涵蓋各種使用模式。例如，讓我們先從最一般的查詢，所有的參數都是新鮮的變量：

 
?- add(X, Y, Z). 
X = 0, 
Y = Z ; 
X = succ(0), 
Z = succ(Y) ; 
X = succ(succ(0)), 
Z = succ(succ(Y)) . 

在這種情況下，有什麼可「帶」，因爲沒有一個參數被實例化。然而，Prolog仍然報告非常明智的答案，這些答案明確了關係擁有的條款。

在你的情況，你正在考慮不同的查詢（不是「謂詞定義」！），即查詢：

 
?- add(succ(succ(succ(0))), succ(succ(0)), R). 
R = succ(succ(succ(succ(succ(0))))). 

這是一個簡單的多特例上面顯示的一般查詢，以及程序的自然後果。

我們還可以去另一個方向和概括此查詢。例如，這是一個概括，因爲我們通過邏輯變量更換一個地說法：

 
?- add(succ(succ(succ(0))), B, R). 
R = succ(succ(succ(B))). 

如果您按照您發佈的解釋，你將使你的生活非常困難，到達在邏輯程序非常有限的觀點：實際上，你只能夠跟蹤模式中，你可以使用謂詞的一個小片段，因而程序讀取屬於很短的你實際上描述什麼。

如果您確實堅持程序性閱讀，請首先以開頭。例如，讓我們考慮：

 
?- add(succ(0), succ(0), R). 

要 「通過步」 程序上，我們可以進行如下操作：

1. 做的第一條比賽？ （請注意，「匹配」是已經閱讀有限：序言實際上應用統一和程序化的解讀，使我們遠離這個普遍性。）
2. 答：沒有，因爲s(_)不0統一。所以只有第二個條款適用。
3. 第二子句僅保持如果其主體保持，並且在這種情況下，如果add(0, succ(0), Z)成立。而這個持有（通過應用第一條）如果Z是succ(0)和R是succ(Z)。
4. 因此，一個答案是R = succ(succ(0)).。這個答案是據報道。
5. 是否有其他解決方案？這些僅在回溯時報告。
6. 答：沒有，有沒有其他的解決方案，因爲沒有進一步的這條規則。

我把它作爲一個練習，將這種艱辛的方法應用到本書中顯示的更復雜的查詢中。這樣做很簡單，但會越來越多地引導您遠離邏輯程序的最有價值的方面，它們的概括性和優雅的聲明性表達式。

你就終止問題是微妙和深刻見解。請注意，我們必須區分存在問題和通用在Prolog中終止。

例如，再上面顯示的最一般的查詢考慮：它得到答案，但它不會終止。對於要報告的答案，找到答案替換就足夠了，它使查詢  爲真。你的例子就是這種情況。替代方案，如果有可能仍然存在，則嘗試並報告回溯。

你總是可以嘗試以下方法來測試你的查詢終止：只需追加false/0，例如：

 
?- add(X, Y, Z), false. 
nontermination 

這可讓您專注於終端性能，而無需關心具體的答案。也

注意add/3是關係一個可怕的名字：一個必要總是意味着方向，但其實這是更一般，也可以使用，如果沒有的參數甚至實例！一個好的謂詞名稱應該反映這種一般性。