爲什麼這個簡單的Prolog示例會導致堆棧溢出？

Question

我正在學習Prolog。我寫了幾個簡單的事實和規則：

heavier(X,Y) :- lighter(Y,X). 
heavier(horse,mouse). 
lighter(X,Y) :- heavier(Y,X). 

然後我問這個查詢：

lighter(mouse,horse). 

而且我得到了以下錯誤：

Fatal Error: local stack overflow (size: 16384 Kb, reached: 16383 Kb, environment variable used: LOCALSZ) 

什麼不對的計劃？

Answer 1

我轉載你的條款在這裏，編號爲方便起見：

heavier(X,Y) :- lighter(Y,X). %1 
heavier(horse,mouse).   %2 
lighter(X,Y) :- heavier(Y,X). %3 

因此，讓我們找出解釋器將要做什麼。

1. 你問它lighter(mouse,horse).匹配3，用X = mouse和Y = horse。
2. 現在需要知道heavier(horse, mouse)是否爲真。匹配，與X = horse和Y = mouse。
3. 現在需要知道lighter(mouse,horse)是否爲真。這匹配3，與X = mouse和Y = horse。 嘿，等一下！

由於解釋在頂部，評估heavier/2時啓動，它總是與第一條，這使得它要評估lighter/2，這使得它要評估heavier/2，它與第一條開始啓動...你可能會看到它在哪裏。

但它不只是無限循環。你看，當口譯員決定採用第一個條款時，知道還有另一個子句匹配。每次決定評估第一個條款時，它都會記住其他選項。未使用的選項堆棧會不斷增長並增長......直到堆棧流逝。

---

所以直接的問題是第1及第2的順序如果您切換的，它首先試圖評估事實heavier(horse, mouse).它成功，這樣你的查詢lighter(mouse,horse).回報true。大！

但這只是它的一半。讓我們重新排序這些條款，並詢問是否lighter(bird, horse).

需要一段時間，不是嗎？那是因爲無限循環仍在發生。現在這個事實從來沒有匹配過，因爲它涉及老鼠而不是鳥類，而解釋者只是在循環定義中循環。它沒有任何選項可以記住，所以棧不會溢出（或至少不會那麼快），但我們仍然沒有得到答案。

解決方法是將您的事實與您的定義分開。

heavier(X, Y) :- is_heavier(X, Y). 
heavier(X, Y) :- is_lighter(Y, X). 

lighter(X, Y) :- heavier(Y, X). 

is_heavier(horse, mouse). 
is_lighter(bird, horse). 

而這應該是一個竅門。

Answer 2

您可以使用trace/0檢查程序是如何工作的，以及你會知道，簡單的說，規則heavier(X,Y) :- lighter(Y,X).是heavier(horse,mouse).那麼第二條規則將永遠不會達到之前和這就是爲什麼你的計劃僅僅是無限循環