謂語

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。