Prolog 的程序

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

我們首先寫出一個(gè) Prolog 的程序，如下：（為引用方便起見(jiàn)，我們把這個(gè)程序成為“程序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）.

接下來(lái)我們分析一下這個(gè)程序：

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

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

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

？-likes（mary， X）.

或 ？-likes（mary， music）.

或 ？-friend（X， Y）.

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

等.但對(duì)于不同的問(wèn)題，程序運(yùn)行的結(jié)果一般是不一樣的.

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

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

Prolog 程序的運(yùn)行機(jī)理

要想了解 Prolog 的運(yùn)行機(jī)理，首先需要了解幾個(gè)基本概念.

1、自由變量與約束變量

Prolog中把無(wú)值的變量稱為自由變量，有值的變量稱為約束變量.一個(gè)變量取了某值就說(shuō)該變量約束于某值，或者說(shuō)該變量被某值所約束，或者說(shuō)該變量被某值實(shí)例化了.在程序運(yùn)行期間，一個(gè)自由變量可以被實(shí)例化而成為約束變量，反之，一個(gè)約束變量也可被解除其值而成為自由變量.

2、匹配合一

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

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

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

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

至少有一個(gè)是自由變量.

例如下面的兩個(gè)謂詞：

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

prel（“ob1”， X， Y）

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

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

3、回溯

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

不懂沒(méi)關(guān)系，下面有例子，看完這個(gè) Prolog 程序的運(yùn)行過(guò)程就懂了.

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

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

？-friend（john， Y）. （john和誰(shuí)是朋友？）

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

friend（john， Y）.

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

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

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

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

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

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

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

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

求解.

子目標(biāo)的求解過(guò)程與主目標(biāo)完全一樣，也是從頭對(duì)程序進(jìn)行掃描，不斷進(jìn)行測(cè)試和匹配合一等，直到匹配成功或掃描完整個(gè)程序?yàn)橹?

可以看出，對(duì)第一個(gè)子目標(biāo) like（X， reading）的求解因無(wú)可匹配的事實(shí)和規(guī)則而立即失敗，進(jìn)而導(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）.這時(shí)，系統(tǒng)從該目標(biāo)剛才的匹配語(yǔ)句處（即第 5 句）向下繼續(xù)掃描程序中的子句，試圖重新使原目標(biāo)匹配，結(jié)果發(fā)現(xiàn)第 6 條語(yǔ)句的左部，即規(guī)則

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

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

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

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

likes（bell， music）.

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

likes（mary， music）.

再對(duì)它進(jìn)行求解.這次很快成功.

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

Y = mary

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

上述程序的運(yùn)行是一個(gè)通過(guò)推理實(shí)現(xiàn)的求值過(guò)程.

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