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 語言的過程性語義.
評論