prolog - 为什么这个简单的Prolog示例会导致堆栈溢出？

我正在学习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)

这个程序怎么了？

最佳答案

我在这里转载了您的条款，为方便起见编号:

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

因此，让我们弄清楚解释器将要做什么。

您询问了它lighter(mouse,horse).与X = mouse和Y = horse相匹配的3。

现在需要知道heavier(horse, mouse)是否为true。匹配 1 ，以及X = horse和Y = mouse。

现在需要知道lighter(mouse,horse)是否为true。匹配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).

这应该可以解决问题。