Prolog 的程序

Prolog 程序一般由一組事實、規則和問題組成.問題是程序執行的起點，稱為程序的目標.

我們首先寫出一個 Prolog 的程序，如下：（為引用方便起見，我們把這個程序成為“程序0”）

likes（bell， sports）.

likes（mary， music）.

likes（mary， sports）.

likes（jane， smith）.

friend（john， X）：- likes（X， reading）， likes（X， music）.

friend（john， X） ：- likes（X， sports）， likes（X， music）. ？- friend（john， Y）.

接下來我們分析一下這個程序：

可以看出，這個程序中有四個事實、兩條規則和一個問題.其中事實、規則和問題都分行書寫；規則和事實可連續排列在一起，其順序可隨意安排，但同一謂詞名的事實或規則必須集中排列在一起；問題不能與規則及事實排在一起，它作為程序的目標要么單獨列出，要么在程序運行時臨時給出.

這個程序的事實描述了一些對象（包括人和事物）間的關系；而規則則描述了 John 交朋友的條件，即如果一個人喜歡讀書并且喜歡音樂（或者喜歡運動和喜歡音樂），那么這個人就是 John 的朋友（當然，這個規則也可看做 John 朋友的定義）；程序中的問題是“約翰的朋友是誰？”

Prolog 程序中的目標還可以變化，也可以含有多個語句（上例中只有一個）.如果有多個語句，則這些語句稱為子目標.例如對上面的程序，其問題也可以是：

？-likes（mary， X）.

或 ？-likes（mary， music）.

或 ？-friend（X， Y）.

或 ？-likes（bell， sports）， likes（mary， music）， friend（john， X）.

等.但對于不同的問題，程序運行的結果一般是不一樣的.

還需說明的是，Prolog程序中的事實或規則一般稱為它們對應謂詞的子句.例如，上面程序中的前4句都是謂詞 likes 的子句. Prolog 規定，同一謂詞的子句應排在一起.從語句形式和程序組成來看， Prolog 就是一種基于 Horn 子句的邏輯程序.這種程序要求用事實和規則來求證詢問，即證明所給出的條件子句和無條件子句與目標子句是矛盾的，或者說程序中的子句集是不可滿足的.這就是所謂的 Prolog 的說明性語義.

從 Prolog 的語句來看， Prolog 語言的文法結構相當簡單.但由于它的語句是 Horn 子句，而 Horn 子句的描述能力是很強的，所以 Prolog 的描述能力也是很強的.例如，當它的事實和規則描述的是某一學科的公理，那么問題就是待證的命題；當事實和規則描述的是某些數據和關系，那么問題就是數據查詢語句；當事實和規則描述的是某領域的知識，那么問題就是利用這些知識求解的問題；當事實和規則描述的是某初始狀態和狀態變化規律，那么問題就是目標狀態.所以， Prolog 語言實際是一種應用相當廣泛的智能程序設計語言.從上面最后一個目標可以看出，同過程性語言相比，對于一個 Prolog 程序，其問題就相當于主程序，其規則就相當于子程序，而其事實就相當于數據.

Prolog 程序的運行機理

要想了解 Prolog 的運行機理，首先需要了解幾個基本概念.

1、自由變量與約束變量

Prolog中把無值的變量稱為自由變量，有值的變量稱為約束變量.一個變量取了某值就說該變量約束于某值，或者說該變量被某值所約束，或者說該變量被某值實例化了.在程序運行期間，一個自由變量可以被實例化而成為約束變量，反之，一個約束變量也可被解除其值而成為自由變量.

2、匹配合一

兩個謂詞可匹配合一，是指兩個謂詞的名相同，參量項的個數相同，參量類型對應相同，并且對應參量項還滿足下列條件之一.

如果兩個都是常量，則必須完全相同.

如果兩個都是約束變量，則兩個約束值必須相同.

如果其中一個是常量，一個是約束變量，則約東值與常量必須相同.

至少有一個是自由變量.

例如下面的兩個謂詞：

prel（“ob1”， “ob2”， Z）

prel（“ob1”， X， Y）

只有當變量 X 被約束為”ob2”，且 Y、Z 的約束值相同或者至少有一個是自由變量時，它們才是匹配合一的.

Prolog 的匹配合一，與歸結原理中的合一的意思基本一樣，但這里的合一同時也是一種操作.這種操作可使兩個能匹配的謂詞合一起來，即為參加匹配的自由變量和常量，或者兩個自由變量建立一種對應關系，使得常量作為對應變量的約束值，使得兩個對應的自由變量始終保持一致，即若其中一個被某值約束，則另一個也被同一值約束；反之，若其中一個的值被解除，則另一個的值也被解除.

3、回溯

所謂回溯，就是在程序運行期間，當某一個子目標不能滿足（即謂詞匹配失?。r，控制就返回到前一個已經滿足的子目標（如果存在的話），并撤銷其有關變量的約束值，然后再使其重新滿足.成功后，再繼續滿足原來的子目標.如果失敗的子目標前再無子目標，則控制就返回到該子目標的上一級目標（即該子目標謂詞所在規則的頭部）使它重新匹配.回溯也是 Prolog 的一個重要機制.

不懂沒關系，下面有例子，看完這個 Prolog 程序的運行過程就懂了.

有了上面的基本概念，下面就介紹所 Prolog 程序的運行過程.我們仍以上面給出的 Prolog 程序“程序0”為例.

設所給的詢問是：

？-friend（john， Y）. （john和誰是朋友？）

則求解目標為：

friend（john， Y）.

這時，系統對程序進行掃描，尋找能與目標謂詞匹配合一的事實或規則頭部.顯然，程序中前面的 4 個事實均不能與目標匹配，而第 5 個語句的左端即規則為：

friend（john， Y） ：- likes（X， reading）， likes（X， music）.

的頭部可與目標謂詞匹配合一.但由于這個語句又是一個規則，所以其結論要成立則必須其前提全部成立.于是，對原目標的求解就轉化為對新目標：

likes（X， reading）， likes（X， music）.

的求解.這實際是經過歸結，規則頭部被消去，而目標子句變為：

？- likes（X， reading）， likes（X， music）.

現在依次對子目標：

likes（X， reading）和 likes（X， music）

求解.

子目標的求解過程與主目標完全一樣，也是從頭對程序進行掃描，不斷進行測試和匹配合一等，直到匹配成功或掃描完整個程序為止.

可以看出，對第一個子目標 like（X， reading）的求解因無可匹配的事實和規則而立即失敗，進而導致規則：

friend（john， X） ：- likes（X， reading）， likes（X， music）.

的整體失敗.于是，剛才的子目標：

likes（X， reading）和 likes（X， music）

被撤銷，系統又回溯到原目標 friend（john， X）.這時，系統從該目標剛才的匹配語句處（即第 5 句）向下繼續掃描程序中的子句，試圖重新使原目標匹配，結果發現第 6 條語句的左部，即規則

friend（john， X） ：- likes（X， sports）， likes（X， music）.

的頭部可與目標謂詞匹配.但由于這個語句又是一個規則，于是，這時對原目標的求解就又轉化為依次對子目標：

likes（X， sports）和 likes（X， music）

的求解.這次子目標 likes（X， sports）與程序中的事實立即匹配成功，且變量 X 被約束為 bell.于是，系統便接著求解第 2 個子目標.由于變量 X 已被約束，所以這時第 2 個子目標實際上已變成

likes（bell， music）.

由于程序中不存在事實 likes（bell， music），所以該目標的求解失敗.于是，系統就放棄這個子目標，并使變量 X 恢復為自由變量，然后回溯到第一個子目標，重新對它進行求解.由于系統已經記住了剛才已同第一子目標謂詞匹配過的事實的位置，所以重新求解時，便從下一個事實開始測試.易見，當測試到程序中的第 3 個事實時，第一個子目標便求解成功，且變量 X 被約束為 mary .這樣，第 2 個子目標也就變成：

likes（mary， music）.

再對它進行求解.這次很快成功.

由于兩個子目標都求解成功，所以，原目標 friend（john， Y）也成功，且變量 Y 被約束為 mary（由 Y 與 X 的合一關系）.于是，系統回答：

Y = mary

程序運行結束.上述程序的執行過程如圖下所示. 圖b

上述程序的運行是一個通過推理實現的求值過程.

從上述程序的運行過程來看， Prolog 程序的執行過程是一個（歸結）演繹推理過程.其推理方式為反向推理，控制策略是深度優先且有回溯機制，具體實現方法是：自上而下匹配子句；從左向右選擇子目標；（歸結后）產生的新子目標總是插入被消去的目標處（即目標隊列的左部）.Prolog 的這種歸結演繹方法被稱為 SLD（Linear resolution with Selection function for Definite clause）歸結， 或 SLD 反駁 - 消解法.這樣，SLD 歸結就是 Prolog 程序的運行機理，也就是所謂的 Prolog 語言的過程性語義.