Prolog 的程序

Prolog 程序一般由一組事實、規(guī)則和問題組成.問題是程序執(zhí)行的起點，稱為程序的目標(biāo).

我們首先寫出一個 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）.

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

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

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

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

？-likes（mary， X）.

或 ？-likes（mary， music）.

或 ？-friend（X， Y）.

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

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

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

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

Prolog 程序的運行機理

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

1、自由變量與約束變量

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

2、匹配合一

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

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

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

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

至少有一個是自由變量.

例如下面的兩個謂詞：

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

prel（“ob1”， X， Y）

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

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

3、回溯

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

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

有了上面的基本概念，下面就介紹所 Prolog 程序的運行過程.我們?nèi)砸陨厦娼o出的 Prolog 程序“程序0”為例.

設(shè)所給的詢問是：

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

則求解目標(biāo)為：

friend（john， Y）.

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

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

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

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

的求解.這實際是經(jīng)過歸結(jié)，規(guī)則頭部被消去，而目標(biāo)子句變?yōu)椋?/p>

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

現(xiàn)在依次對子目標(biāo)：

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

求解.

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

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

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

的整體失敗.于是，剛才的子目標(biāo)：

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

被撤銷，系統(tǒng)又回溯到原目標(biāo) friend（john， X）.這時，系統(tǒng)從該目標(biāo)剛才的匹配語句處（即第 5 句）向下繼續(xù)掃描程序中的子句，試圖重新使原目標(biāo)匹配，結(jié)果發(fā)現(xiàn)第 6 條語句的左部，即規(guī)則

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

的頭部可與目標(biāo)謂詞匹配.但由于這個語句又是一個規(guī)則，于是，這時對原目標(biāo)的求解就又轉(zhuǎn)化為依次對子目標(biāo)：

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

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

likes（bell， music）.

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

likes（mary， music）.

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

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

Y = mary

程序運行結(jié)束.上述程序的執(zhí)行過程如圖下所示. 圖b

上述程序的運行是一個通過推理實現(xiàn)的求值過程.

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