prolog - 为什么这个简单的 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) 是否为真。这与 1 匹配，X = horse 和 Y = mouse。
3. 它现在需要知道 lighter(mouse,horse) 是否为真。匹配 3，X = mouse 和 Y = horse。 嘿，等一下!

由于解释器从顶部开始，在评估heavier/2时，它总是从第一个子句开始，这使得它想要评估lighter/2，这使得它想要评估 heavier/2，它从第一个子句开始......你可能会看到它的标题。

但这不仅仅是无限循环。你看，当解释器决定使用第一个子句时，它知道还有另一个匹配的子句。每次它决定评估第一个子句时，它也会记住另一个选项。未使用选项的堆栈不断增长……直到堆栈溢出。

---

所以直接的问题是子句 1 和 2 的顺序。如果你交换它们，它首先尝试评估事实 较重(马，老鼠)。这会成功，因此您的查询 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).

这应该可以解决问题。