1

这是我的程序：

depends(apple, tree).
depends(cider, apple).

depends(X,Y) :- X\==Y, depends(Z,Y),depends(X,Y).

如果我问以下问题：

depends(cider, tree).

我得到：

GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- [apples].
apples.pro for byte code...
apples.pro compiled, 4 lines read - 765 bytes written, 28 ms

yes
| ?- depends(cider, tree).

Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ)

如果我运行“跟踪”，我可以看到对 X\==Y 的评估一遍又一遍地重复......

我在这里做错了什么？（除了买一本《七周内的七种语言》:-)）

编辑：

所以这要归功于下面 Daniel Lyons 的注释：将事实的名称与规则的名称区分开来防止递归：

depends(apple, tree).
depends(cider, apple).

depends_on(X,Y) :- depends(X,Z),depends(Z,Y).

给出以下内容（打开“跟踪”）：

{trace}
| ?- depends_on(cider, tree).
      1    1  Call: depends_on(cider,tree) ? 
      2    2  Call: depends(cider,_79) ? 
      2    2  Exit: depends(cider,apple) ? 
      3    2  Call: depends(apple,tree) ? 
      3    2  Exit: depends(apple,tree) ? 
      1    1  Exit: depends_on(cider,tree) ? 

yes
4

1 回答 1

4

首先，您有一个单例变量：

depends(X,Y) :- X\==Y, depends(Z,Y),depends(X,Y).

相当于：

depends(X,Y) :- X\==Y, depends(_,Y), depends(X,Y).

Prolog 会“警告”您有关单例变量的信息，但您应该始终将其视为严重错误，因为它几乎总是意味着您的代码没有按照您认为的那样做。在这种情况下，我怀疑您认为 Prolog 会自动使 X 和 Z 不同，但事实并非如此，而且这里没有其他内容可以指示 Prolog 对 Z 做某事，所以这只是浪费时间或复制真正的问题。

真正的问题是这段代码简化为：

depends(X,Y) :- X\==Y, depends(X,Y).

这是无限递归。我可以给予depends(chickens, eggs_and_flapjacks)，Prolog 只会说，“嗯，chickens不一样eggs_and_flapjacks，我接下来要做的事情是什么？” 然后跳回到开头只是再次问这个问题。这会导致堆栈溢出异常。如果你追溯，你会清楚地看到错误：

?- trace, depends(eggs, chickens).
Call: (7) depends(eggs, chickens) ? 
Call: (8) eggs\==chickens ? 
Exit: (8) eggs\==chickens ? 
Call: (8) depends(eggs, chickens) ? 
Call: (9) eggs\==chickens ? 
Exit: (9) eggs\==chickens ? 
Call: (9) depends(eggs, chickens) ? 
Call: (10) eggs\==chickens ? 
Exit: (10) eggs\==chickens ? 
Call: (10) depends(eggs, chickens) ? 
Call: (11) eggs\==chickens ? 
Exit: (11) eggs\==chickens ? 
Call: (11) depends(eggs, chickens) ? 
Call: (12) eggs\==chickens ? 
Exit: (12) eggs\==chickens ? 
Call: (12) depends(eggs, chickens) ?

等等等等

所以这就是你的全部问题。除了循环之外，您的代码还没有做任何事情。

编辑图遍历

对于这个特定问题，您将需要将事实与谓词分开。情况并非总是如此。你会想要这个：

depends_on(X, Y) :- depends(X, Y).
depends_on(X, Z) :- depends(X, Y), depends_on(Y, Z).

这为您提供了有界递归。如果你试图用一个谓词来做，你会得到无限递归：

depends(X,Z) :- depends(X,Y), depends(Y,Z).

有几种方法可以解决这个问题，最简单的方法是将事实与谓词分开，就像我们上面所做的那样。一些 Prolog 实现支持表格，我相信这也解决了这个问题（我高吗？）；否则，您可以跟踪您已经遍历了哪些关系并避免以这种方式循环（这是处理无向图时的常用方法）。

于 2013-05-17T18:53:24.810 回答