谓语

Question

没有终止我有黑色和白色顶点的图的一些程序：

black(root). 
black(v1). 
black(v3). 
black(v4). 

edge(root,root). 
edge(v1,root). 
edge(v2,v1). 
edge(v3,v1). 
edge(v4,v3). 
edge(v5,v2). 
edge(v5,v4). 
edge(v6,v5). 

vertex(X) :- edge(X,_). 
vertex(X) :- edge(_,X). 

white(X) :- 
    vertex(X), 
    not(black(X)). 

foo(root). 
foo(X) :- 
    edge(X,Y), 
    black(Y), 
    foo(Y). 

当我运行的目标foo(X)我得到了一个问题： 如果我删除的事实edge(root,root)程序找到了一些解决方案（6种不同的解决方案）。否则，我会得到无限的解决方案，并且都是X=root。 这是为什么发生？

Answer 1

首先快速回答，它向您展示了Prolog程序员如何看待您的程序，其解释如下。你的程序不会终止，因为以下failure-slice不会终止：

 
black(root). 
black(v1) :- false. 
black(v3) :- false. 
black(v4) :- false. 

edge(root,root). 
edge(v1,root) :- false. 
edge(v2,v1) :- false. 
edge(v3,v1) :- false. 
edge(v4,v3) :- false. 
edge(v5,v2) :- false. 
edge(v5,v4) :- false. 
edge(v6,v5) :- false. 

foo(root) :- false. 
foo(X) :- X = root, Y = root, 
    edge(X,Y), 
    black(Y), 
    foo(Y), false. 

所有通striken文本无关了解未结束。正如你所看到的，其余部分相对较短，因此需要很快掌握。

Prolog无法直接检测到此循环。但是，您可以使用closure0/3定义here为了这个目的：

edge_toblack(X, Y) :- 
    edge(X, Y), 
    black(Y). 

foo(X) :- 
    closure0(edge_toblack, X,root). 

现在的细节。

在回答您的问题之前，为什么会发生这种情况，让我们退后一步。我们首先需要找到一个观察问题的好方法。目标foo(X)确实产生答案，实际上只有X = root。所以也许你只是不耐烦地等待Prolog完成？通过询问foo(X), false来代替，我们摆脱了这些令人烦恼的，令人eye目结舌的答案，我们将等待false作为回答。

我们仍然无法确定程序的非终止属性。但我们可以通过插入目标false（以及(=)/2）来缩小实际原因。在上面的失败片中，我插入了最大值。如果您刚刚开始，只需添加一个false，然后重新加载程序并重试查询。凭借一些经验，您很快就能够快速识别这些部件。所以，现在我们只需要了解

 
foo(root) :- 
    edge(root,root), % always true 
    black(root),  % always true 
    foo(root), false. 

，甚至更短的

 
foo(root) :- 
    foo(root). 

的Prolog的非常简单而有效的执行机制没有检测到这种循环。基本上有几种出路：

1. 手动添加循环检测。这通常是很容易出错

2. 使用closure0/3 - 见上

3. 写自己的元解释检测循环一般

4. 使用语言扩展一样桌游戏，在B-Prolog的提供或XSB-Prolog。