序言遞歸和終止

Question

第一個StackOverflow問題。

我在prolog中寫了一個帶三個參數的謂詞。它們分別是一個字符，一個字符串列表，最後一個參數是第二個參數中以第一個參數開頭的所有字符串的列表。我的寫作陳述取代了我完全缺乏關於如何在SWI-Prolog中追蹤的知識。無論如何，在代碼！

---

startString(C, [H1|T1], [H2|T2]) :- 
    atom_chars(H1, [C| _ ]), 
    H2 = H1, 
    startString(C, T1, T2). 

startString(C, [ _ |T1], Y) :- 
    startString(C, T1, Y), 
    write(foo). 

startString(_, [], []) :- 
    write(foo). 

---

，輸出：

---

foofoofoo 

X = [some, simple] 

---

我的方法是正確的，但謂語不終止（後缺乏時期寫X不是一個錯誤）。我的問題是，爲什麼不呢？從我在互聯網上發現的遞歸的有限範例中，我的謂詞的第三個版本應該終止謂詞並使x成爲一個確定的答案。

當我按回車時，我可以輸入另一個查詢，但我在同一個程序中編寫的另一個謂詞中有同樣的小問題。對這個謂詞的任何幫助也應該延續到另一個。謝謝！

Answer 1

爲了擴大在您的意見@ScottHunter你的問題，

我想我的問題是，爲什麼我的其他謂詞「知道」他們有正確的答案，而這一點，多一個不？

答案與堆棧中選擇點的存在有關。考慮這種情況：

reasonably_big(L, X) :- member(X, L), X > 100. 

?- reasonably_big([105, 2], X). 
X = 105 ; 
false. 
?- 

與此相比，這樣的：

?- reasonably_big([2, 105], X). 
X = 105. 
?- 

在第二種情況下，Prolog的 「知道」，有沒有更多的解決方案;在第一種情況下它沒有。這兩種情況的不同之處在於，在第一種情況下，member在堆棧上留下了選擇點：列表中還有另一項可以考慮找到另一個答案。在第二種情況下，列表的其餘部分是空的，並且SWI-Prolog的member足夠聰明，在這種情況下不會留下選擇點，所以它從來沒有問您是否需要其他解決方案。

如果您得到無關的選擇點，它通常指向一個邏輯錯誤。例如，考慮min這個定義：

min(X, Y, X) :- X =< Y. 
min(X, Y, Y). 

這是有缺陷的，因爲你總是可以原路返回並得到其他值;即：

?- min(3,4, X). 
X = 3 ; 
X = 4. 

第二種解決方案存在錯誤。但您仍可以通過做出錯誤的改進風與不必要的選擇點：

min(X, Y, X) :- X =< Y. 
min(X, Y, Y) :- Y =< X. 

看到，當我們嘗試不同的價值觀會發生什麼：

?- min(4,3,X). 
X = 3. 
?- 

?- min(3,4,X). 
X = 3 ; 
false. 
?- 

第一個工作得很好，但第二個左通過擁有第二個身體在堆棧上的選擇點。你可以用綠色切割來消除它：

min(X,Y,X) :- X =< Y, !. 
min(X,Y,Y) :- Y =< X. 

?- min(3,4,X). 
X = 3. 
?- 

?- min(4,3,X). 
X = 3. 
?- 

切割提交Prolog到一個特定的解決方案。它說，一旦你完成了這個任務，就不需要爲這個謂詞嘗試任何其他的解決方案，因爲我們找到了唯一一個我們想要的。瞭解如何應用剪切是一個複雜的話題，但消除不良選擇點是一個重要的用途。

Answer 2

你必須小心你在Prolog中的「terminate」是什麼意思。事實上，當你要求序言證明startString（'s'，some-list，X）時，你得到了一個綁定到X的值，這意味着它終止了（否則它仍然會搜索X的值）。但從另一個角度來看，它沒有，因爲你可以問（通常通過輸入一個分號）Prolog試圖找到另一個解決方案，並可以不斷詢問，直到它耗盡這樣做的可能性。聽起來您的控制檯正在等待您告訴您是否要嘗試尋找其他解決方案，或者您已完成（當您按Enter鍵時發生的情況，並且解釋器允許您輸入新的查詢）。