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

Question

我正在学习序言。我写了几个简单的事实和规则：

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

你可以使用 trace/0 来检查程序是如何工作的，你会知道，简单地说，规则 heavier(X,Y) :- lighter(Y,X). 在 heavier(horse,mouse). 之前，所以第二条规则永远不会达到，这就是为什么你的程序只是无限循环

Answer 2

我在此处复制了您的条款，为方便起见编号：

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

所以让我们弄清楚解释器要做什么。

你问的 lighter(mouse,horse). 匹配 3，X = mouse 和 Y = horse。
现在需要知道 heavier(horse, mouse) 是否为真。这与 1、X = horse 和 Y = mouse 匹配。
现在需要知道 lighter(mouse,horse) 是否为真。匹配 3，X = mouse 和 Y = horse。 嘿，等一下！

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

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

所以直接的问题是子句 1 和 2 的顺序。如果你切换它们，它首先尝试评估 fact heavier(horse, mouse). 成功，所以您的查询 lighter(mouse,horse). returns 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).

这应该可以解决问题。

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

Why does this simple Prolog example cause a stack overflow?

stack-overflow

prolog