前言

如果你是一位prolog的新手，希望你首先閱讀這篇文章，好對prolog的全局有個了解，本文將詳細介紹prolog學(xué)習(xí)流程編程思路上以及prolog語法細節(jié)。

首先，問一個基礎(chǔ)的問題：我們已經(jīng)在Prolog程序中看到了很多類型的表達式（比如，jody，playsAirGuitar（mia），和X），但這些僅僅只是例子，是時候更加深入了，到底事實、規(guī)則和查詢是由什么構(gòu)成的？

答案就是語句（terms），在Prolog中一共存在四種類型的語句：原子，數(shù)字，變量和復(fù)雜語句（或者稱為結(jié)構(gòu)）.原子和數(shù)字統(tǒng)稱為常量，常量和變量統(tǒng)稱簡單語句.

首先要明確基礎(chǔ)的字符的范圍：大寫字母：A，B，...，Z；小寫字母：a，b，...，z；數(shù)字：0，1，2，...，9.另外還包括“_”，即英文下劃線字符；和其他一些特殊英文字符，比如：+，-，*，/，《，》，=，：，.，&，~；空格也是字符，但是不常用，并且也不可見.字符串是指沒有切斷的字符序列.

原子（Atoms）

一個原子是以下情況之一：

1. 由字符構(gòu)成的字符串，其中有效字符包括：大字字母，小寫字母，數(shù)字，和下劃線，并且是小寫字母作為頭字符.一些例子：butch，big_kahuna_burger，listen2Music，playsAirGuitar.

2. 使用單引號封裝的字符序列.比如：‘Vincent’，‘The Gimp’，‘Five_Dollar_Shake’，‘&^%%@# *’，‘ ’.被單引號封裝的字符序列被稱為原子名.注意我們已經(jīng)使用了空格字符，

事實上，使用單引號封裝，其中的一個作用就是可以在原子中精確地使用類似空格字符這樣的特殊字符.

3. 特殊字符組成的字符串.比如：@=，====》，;，：-等都是原子.正如我們看到的，一些特殊原子，比如;（邏輯或），：-（規(guī)則中連接頭部和主干的符號）已經(jīng)有預(yù)定義的含義.

數(shù)字（Numbers）

在典型的Prolog程序中，實數(shù)并不是很有用武之地.所以雖然大多數(shù)Prolog的實現(xiàn)都支持浮點數(shù)，但是本文不討論.

但是整數(shù)（比如：-2，-1，0，1，2，...）卻十分有用，比如在計算列表的元素數(shù)目之類的工作時候，我們將會在第5章詳細介紹.Prolog中數(shù)字的表示很簡單，沒有什么特殊，如下：

23， 1001， 0， -365， 等等.

變量（Variables）

變量是由大寫字母，小寫字母，數(shù)字和下劃線組成的字符串，并且頭字母必須是大寫字母或者下劃線.比如：

X， Y， Variable， _tag， X_526， List， List24， _head， Tail， _input， Output

都是Prolog中有效的變量.變量”_“是一個特例，它被稱為匿名變量，我們將會在第4章中介紹.

復(fù)雜語句（Complex Terms）

常量，數(shù)字，和變量都是構(gòu)建語句的模塊，現(xiàn)在我們學(xué)習(xí)如何將它們組成復(fù)雜語句.復(fù)雜語句也稱為結(jié)構(gòu)體.

復(fù)雜語句由一個函子（functor，也可以理解為函數(shù)名）和一個參數(shù)序列構(gòu)成.參數(shù)序列放在小括號內(nèi)，由英文逗號分隔，并且是放在函子后面.請注意函子后面必須緊跟參數(shù)序列，

中間不能有空格.函子必須是一個原子，即，變量不能用作函子.另一方面，參數(shù)序列可以是任何類型的語句.

從KB1到KB5，我們已經(jīng)看到了許多復(fù)雜語句的例子.比如，playsAirGuitar（jody）就是一個復(fù)雜語句，其中playsAirGuitar是函子，jody是參數(shù)序列（只有一個參數(shù)）.另一個

例子是loves（vincent， mia），loves是函子，vincent和mia是參數(shù)序列；再比如一個包含了變量的例子：jealous（marsellus， W）.

（注：函子和謂詞由一定區(qū)別，我的理解是：函子是謂詞的名字，謂詞包含了函子及其參數(shù)序列，是整個邏輯的實現(xiàn)統(tǒng)一體.）

但是，復(fù)雜語句的定義可以允許更為復(fù)雜的情況.事實上，在復(fù)雜語句中，也可以內(nèi)嵌其他復(fù)雜語句（就是說，復(fù)雜語句允許遞歸）.比如：

hide（X， father（father（father（butch））））.

就是一個完美的符合定義的復(fù)雜語句.它的函子是hide，有兩個參數(shù)：一個是變量X，另外一個是復(fù)雜語句，father（father（father（butch）））.這個復(fù)雜語句組成是：函子是father，

另外一個復(fù)雜語句，father（father（butch））是其唯一的參數(shù).里層的復(fù)雜語句的參數(shù)依然是一個復(fù)雜語句：father（butch）.但是到了嵌套的最里層，參數(shù)就是一個常量：butch.

實際上，這種嵌套（遞歸結(jié)構(gòu)）使得我們可以自然地描述很多問題，而且這種遞歸結(jié)構(gòu)和變量合一之間的互相作用，正是Prolog強有力的武器.

復(fù)雜語句的參數(shù)個數(shù)稱為元數(shù)（arity）.比如，woman（mia）是一個元數(shù)為1的復(fù)雜語句，loves（vincent， mia）是一個元數(shù)為2的復(fù)雜語句.

元數(shù)對于Prolog很重要.Prolog允許定義函子相同但是元數(shù)不同的復(fù)雜語句.比如，我們可以定義兩個參數(shù)的loves謂詞，loves（vincent， mia）；也可以定義三個參數(shù)的loves謂詞，

loves（vincent， marsellus， mia）.如果我們這么做了，Prolog會認為這兩個謂詞是不同的.在第5章中，我們將會看到定義相同函子但是元數(shù)不同的具體應(yīng)用.

當(dāng)我們需要提及定義的謂詞，介紹如何使用它們的時候（比如，在文檔中），慣例是”函子/元數(shù)“這種形式.回到KB2，我們有三個謂詞，之前的表達如下：

listen2Music

happy

playsAirGuitar

使用正式的書寫方式如下：

listen2Music/1

happy/1

playsAirGuitar/1

Prolog不會因為定義了兩個loves謂詞而迷惑，它會區(qū)分loves/2和loves/3是不同的謂詞.
#e#

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

?數(shù)據(jù)與表達式

1、領(lǐng)域

（1）標(biāo)準(zhǔn)領(lǐng)域.

Turbo prolog中不定義變量的類型，只說明謂詞中各個項的取值域.由上面我們知道， Turbo prolog 有整數(shù)、實數(shù)、字符、串 和 符號這5種標(biāo)準(zhǔn)域.另外，它還有結(jié)構(gòu)、表和文件這3種復(fù)合域.

（2）結(jié)構(gòu).

結(jié)構(gòu)也稱復(fù)合對象，它是 Turbo prolog 謂詞中的一種特殊的參量項（類似于謂詞邏輯中的函數(shù)）.結(jié)構(gòu)的一般形式為：

《函子》（《參量表》）1

其中函子及參量的標(biāo)識符與謂詞相同.注意，這意味著結(jié)構(gòu)中還可包含結(jié)構(gòu).所以，復(fù)合對象可表達樹形數(shù)據(jù)結(jié)構(gòu).例如下面的謂詞：

likes（“Tom”， sports（football， basketball， table_tennis））.1

中的

sports（football， basketball， table_tennis）1

就是一個結(jié)構(gòu)，即復(fù)合對象.又如：

person（“張華”， student（“清華大學(xué)”）， address（“中國”， “北京”））.

reading（“王宏”， book（“人工智能技術(shù)導(dǎo)論”， “西安電子科技大學(xué)出版社”））.

friend（father（“Li”）， father（“Zhao”））.123

這幾個謂詞中都有復(fù)合對象.

復(fù)合對象在程序中的說明，需分層進行.例如，對于上面的謂詞：

likes（“Tom”， sports（football， basketball， table_tennis））.1

在程序中可說明如下：

domains

name = symbol

sy = symbol

sp = sports（sy， sy， sy）

predicates

likes（name， sp）123456

（3）表.

表的一般形式是：

［x1， x2， ...， xn］1

其中xi（i=1，2，...，n）為 Prolog 的項，一般要求同一個表的元素必須屬于同一領(lǐng)域.不含任何元素的表稱為空表，記為［］.例如下面就是一些合法的表.

［1，2，3］

［ apple， orange， banana， grape， cane］

［“Prolog”， “MAENS”， “PROGRAMMING”， “in logic”］

［［a， b］， ［c， d］， ［e］］

［］12345

表的最大特點是其元素個數(shù)可在程序運行期間動態(tài)變化.表的元素也可以是結(jié)構(gòu)或表，且這時其元素可以屬于不同領(lǐng)域.例如：

［name（“LiMing”）， age（20）， sex（male）， address（xian）］

［［1， 2］， ［3， 4， 5］， ［6， 7］］12

都是合法的表.后一個例子說明，表也可以嵌套.

實際上，表是一種特殊的結(jié)構(gòu)，它是遞歸結(jié)構(gòu)的另一種表達形式.這個結(jié)構(gòu)的函數(shù)名取決于具體的 Prolog 版本，這里我們就用一個圓點來表示.下面就是一些這樣的結(jié)構(gòu)及它們的表的表示形式：

結(jié)構(gòu)形式表形式

·（a， ［］）［a］

·（a， ·（b， ［］））［a， b］

·（a， ·（b， ·（c， ［］）））［a， b， c］

表的說明方法是在其組成元素的說明符后加一個星號*.如：

domains

lists = string*

predicates

pl（lists）1234

就說明謂詞 pl 中的項 lists 是一個由串 string 組成的表.

對于由結(jié)構(gòu)組成的表，至少分3步說明.例如對于下面謂 p 中的表

對于由結(jié)構(gòu)組成的表，至少分3步說明.例如對于下面謂 p 中的表

p（［name（“Liming”）， age（20）］）1

則需這樣說明：

domains

rec=seg*

seg=name（string）; age（integer）

predicates

p（rec）12345

2、常量與變量

由上面的領(lǐng)域可知， Turbo Prolog的常量有整數(shù)、實數(shù)、字符、串、符號、結(jié)構(gòu)、表 和 文件 這8種數(shù)據(jù)類型.同理， Turbo Prolog 的變量也就有這8種取值.另外，變量名要求必須是以大寫字母或下劃線開頭的字母、數(shù)字和下劃線 序列，或者只有一個下劃線（這種變量稱為無名變量）.

3、算術(shù)表達式

Turbo Prolog 提供了 5 種最基本的算術(shù)運算：加、減、乘、除 和 取模，相應(yīng)運算符號為“+”、“-”、“*”、“/”、“mod”.這 5 種運算的順序為：“*”、“/”、“mod”優(yōu)先于“+”、“-”.同級從左到右按順序運算，括號優(yōu)先.

算術(shù)表達式的形式與數(shù)學(xué)中的形式基本一樣.例如：

數(shù)學(xué)中的算術(shù)表達式Turbo Prolog 中的算術(shù)表達式

x + yzX + Y * Z

ab - c / dA * B - C / D

u mod vU mod V（表示求U除以V所得的余數(shù)）

即， Turbo Prolog 中算術(shù)表達式采用通常數(shù)學(xué)中使用的中綴形式.這種算術(shù)表達式為 Prolog 的一種異體結(jié)構(gòu)，若以 Prolog 的結(jié)構(gòu)形式來表示，則它們應(yīng)為：

+（X， *（Y， Z））

-（*（A， B）， /（C， D））

mod（U， V）123

所以，運算符“+”、“-”、“*”、“/”和“mod”實際也就是 Prolog 內(nèi)部定義好了的函數(shù)符.

在 Turbo Prolog 程序中，如果一個算術(shù)表達式中的變元全部被實例化（即被約束），則這個算術(shù)表達式的值就會被求出.求出的值可用來實例化某變量，也可用來同其他數(shù)量進行比較，用一個算術(shù)表達式的值實例化一個變量的方法是用謂詞“is”或“=”來實現(xiàn)的.例如：

Y is X + 5或Y = X + 5 （*）123

就使變量 Y 實例化為 X+5 的值（當(dāng)然 X 也必須經(jīng)已被某值實例化），可以看出，這里對變量 Y 的實例化方法類似于其他高級程序語言中的“賦值”，但又不同于賦值.例如，在 Prolog 中下面的式子是錯誤的：

X = X + 11

需要說明的是，雖然 Prolog 是一種邏輯程序設(shè)計語言，但在目前的硬件條件下卻非突破邏輯框架不可.這是因為有些實用操作是無法用邏輯描述的（如輸入與輸出），有些算術(shù)運算在原則上可用邏輯描述，但這樣做效率太低.為此， Prolog 提供了若干內(nèi)部謂詞（亦稱 預(yù)定義謂詞），來實現(xiàn)算術(shù)運算、輸入與輸出等操作.所謂內(nèi)部謂詞，就是 Prolog 的解釋程序中，預(yù)先用實現(xiàn)語言定義好的用戶可直接作為子目標(biāo)調(diào)用的謂詞.一般的 Prolog 實用系統(tǒng)都配有 100 個以上的內(nèi)部謂詞，這些內(nèi)部謂詞涉及輸入輸出、算術(shù)運算、搜索控制、文件操作和圖形聲音等方面，它們是實用 Prolog 程序設(shè)計所必不可少的.這樣，上面的（*）式以及下面的關(guān)系表達式稱為異體謂詞.

4、關(guān)系表達式

Turbo Prolog 提供了 6 種常用的關(guān)系運算，即 小于、小于或等于、等于、大于、大于或等于、不等于，其運算符依次為：

《， 《=， =，》，》=， 《》1

Turbo Prolog 的關(guān)系表達式的形式和數(shù)學(xué)中的也基本一樣，例如：

數(shù)學(xué)中的關(guān)系式Turbo Prolog 中的關(guān)系式

X + 1 ≥ YX + 1》= Y

X ≠ YX 《》 Y

即， Turbo Prolog 中的關(guān)系式也用中綴形式.當(dāng)然，這種關(guān)系式為 Turbo Prolog 中的異體原子.若按 Turbo Prolog 中的原子形式來表示，則上面的兩個例子為：

》=（X +1， Y） 和 《》（X， Y）1

所以上述 6 種關(guān)系運算符，實際上也就是 Turbo Prolog 內(nèi)部定義好了的 6 個謂詞.這 6 個關(guān)系運算符可用來比較兩個算術(shù)表達式的大小.例如：

brother（Name1， Name2） ：- person（Name1， man， Age1），

person（Name2， man， Age2），

mother（Z， Name1）， mother（Z， Name2）， Age1》 Age2.123

需要說明的是，“=”的用法比較特殊，它既可以表示比較，也可以表示約束值，即使在同一個規(guī)則中的同一個“=”也是如此.例如：

p（X， Y， Z） ：- Z = X + Y.1

當(dāng)變量 X、Y、Z全部被實例化時，“=”就是比較符.如對于問題：

Goal： p（3， 5， 8）.1

機器回答“yes”，而對于：

Goal： p（3， 5， 7）.1

機器回答“no”.即這時機器把 X+Y 的值與Z的值進行比較.但當(dāng) X，Y 被實例化，而 Z 未被實例化時， “=”號就是約束符，如：

Goal： P（3， 5， Z）.1

機器回答“Z = 8”.這時，機器使 Z 實例化為 X+Y 的結(jié)果.

?輸入與輸出

雖然 Prolog 能自動輸出目標(biāo)子句中的變量的值，但這種輸出功能必定有限，往往不能滿足實際需要；另外，對通常大多數(shù)的程序來說，運行時從鍵盤上輸人有關(guān)數(shù)據(jù)或信息也是必不可少的.為此每種具體 Prolog 一般都提供專門的輸人和輸出謂詞，供用戶直接調(diào)用.例如，下面就是 Turbo Prolog 的幾種輸入輸出謂詞：

readin（X）.這個謂詞的功能是從鍵盤上讀取一個字符串，然后約束給變量 X .

readint（X）.這個謂詞的功能是從鍵盤上讀取一個整數(shù)，然后約束給變量 X，如果鍵盤上打入的不是整數(shù)，則該謂詞失敗.

readreal（X）.這個謂詞的功能是從鍵盤上讀取一個實數(shù)，然后約束給變量 X，如果鍵盤上打入的不是實數(shù)，則該謂詞失敗.

readchar（X）.這個謂詞的功能是從鍵盤上讀取一個字符，然后約束給變量 X，如果鍵盤上打入的不是單個字符，則該謂詞失敗.

write（X1， X2， …， Xn）.這個謂詞的功能是把項 Xi（i=1，2，…，n） 的值顯示在屏幕上或者打印在紙上，當(dāng)有某個 Xi 未實例化時，該謂詞失敗.其中的 Xi 可以是變量，也可以是字符串或數(shù)字.例如：

write（“computer”， “Prolog”， Y， 1992）

nl（換行謂詞）.它使后面的輸出（如果有的話）另起一行.另外，利用 write的輸出項“ ”也同樣可起到換行作用.例如：

write（“name”）， nl， write（“age”）

與

write（“name”， “ ”， “age”）

的效果完全一樣.

舉個例子：

用上面的輸入輸出謂詞編寫一個簡單的學(xué)生成績數(shù)據(jù)庫查詢程序.

PREDICATES

student（integer， string， real）

grade

GOAL

grade.

CLAUSES

student（1， “張三”， 90.2）.

student（2， “李四”， 95.5）.

student（3， “王五”， 96.4）.

grade ：- write（“請輸人姓名：”）， readln（Name），

student（_， Name， Score），

nl， write（Name， “的成績是”， Score）.

grade ：- write（“對不起，找不到這個學(xué)生！”）.12345678910111213

下面是程序運行時的屏幕顯示

請輸入姓名：王五

王五的成績是96.412

四、分支與循環(huán)

Prolog 本來沒有分支和循環(huán)語句，但可以利用其邏輯機制實現(xiàn)分支和循環(huán)效果.

1、分支

對于通常的 IF-THEN-ELSE 分支結(jié)構(gòu)，Prolog可用兩條同頭的（同頭即指結(jié)論相同）并列規(guī)則實現(xiàn).例如，將：

IF X》0 THEN X：=1

ELSE X：=012

用 Prolog實現(xiàn)則是：

br ：- X》 0， X = 1.

br ：- X = 0.12

類似地，對于多分支，可以用多條規(guī)則實現(xiàn).例如：

br ：- X》 0， X = 1.

br ：- X = 0， X = 0.

br ：- X 《 0， X = -1.123

2、循環(huán)

Prolog 可以實現(xiàn)計循環(huán)次數(shù)的 FOR 循環(huán)，也可以實現(xiàn)不計循環(huán)次數(shù)的 DO 循環(huán).

舉個例子：

下面的程序段就實現(xiàn)了循環(huán)，它使得 write 語句重復(fù)執(zhí)行了3次，而打印輸出了3個學(xué)生的記錄：

student（1， “張三”， 90.2）.

student（2， “李四”， 95.5）.

student（3， “王五”， 96.4）.

print ：- student（Number， Name， Score），

write（Number， Name， Score）， nl，

Number = 3.123456

可以看出，程序第一次執(zhí)行，student 謂詞與第一個事實匹配，write 語句便輸出了張三同學(xué)的記錄.但當(dāng)程序執(zhí)行到最后一句時，由于 Number 不等于 3，則該語句失敗，于是，引起回溯.而 write 語句和 nl 語句均只能執(zhí)行一次，所以繼續(xù)向上回溯到 student 語句.這樣，student 謂詞則因失敗而重新匹配.這一次與第二個事實匹配，結(jié)果輸出了李四的記錄.同理，當(dāng)執(zhí)行到最后一句時又引起了回溯.write 語句第三次執(zhí)行后，由于 Number 已等于3，所以最后一個語句成功，程序段便運行結(jié)束.

這個例子可以看做是計數(shù)循環(huán).當(dāng)然，也可以通過設(shè)置計數(shù)器而實現(xiàn)真正的計數(shù)循環(huán).下面的程序段實現(xiàn)的則是不計數(shù)的 DO 循環(huán)：

student（1， “張三”， 90.2）.

student（2， “李四”， 95.5）.

student（3， “王五”， 96.4）.

print ：- student（Number， Name， Score），

write（Number， Name， Score）， nl，

fail.

print ：-.1234567

這個程序段中的 fail 是一個內(nèi)部謂詞，它的語義是恒失敗.這個程序段與上面的程序段的差別僅在于把原來用計數(shù)器（或標(biāo)記數(shù)）進行循環(huán)控制的語句變成了恒失敗謂詞 fail，另外又增加了一個 print 語句，增加這個語句的目的是為程序設(shè)置一個出口.因為 fail 是恒失敗，下面若無出口的話，將引起 print 本身的失敗，進而又會導(dǎo)致程序的連鎖失敗.

還需說明的是，用 Prolog的遞歸機制也可以實現(xiàn)循環(huán)，不過用遞歸實現(xiàn)循環(huán)通常需與表相配合.另外，遞歸的缺點是容易引起內(nèi)存溢出，故通常的循環(huán)多是用上述方法實現(xiàn)的.

?動態(tài)數(shù)據(jù)庫

動態(tài)數(shù)據(jù)庫就是在內(nèi)存中實現(xiàn)的動態(tài)數(shù)據(jù)結(jié)構(gòu).它由事實組成，程序可以對它操作，所以在程序運行期間它可以動態(tài)變化.Turbo Prolog 提供了 3 個動態(tài)數(shù)據(jù)庫操作謂詞，即：

asserta（《 fact》）

assertz（《 fact》）

retract（《 fact》）123

其中 fact 表示事實.這 3 個謂詞的功能如下：

asserta（《 fact》） 把 fact 插入當(dāng)前動態(tài)數(shù)據(jù)庫中的同名謂詞的事實之前.

assertz（《 fact》） 把 fact 插入當(dāng)前動態(tài)數(shù)據(jù)庫中的同名謂詞的事實之后.

retract（《 fact》） 把 fact 從當(dāng)前動態(tài)數(shù)據(jù)庫中刪除.

例如語句：

asserta（student（20， “李明”， 90.5））.1

將在內(nèi)存的謂詞名為 student 的事實前插入一個新事實：

student（20， ‘’李明“， 90.5）1

如果內(nèi)存中還沒有這樣的事實，則它就是第一個.又如語句：

retract（student（20， _， _））.1

將從內(nèi)存的動態(tài)數(shù)據(jù)庫中的刪除事實：

student（20， _， _）1

它可解釋為學(xué)號為 20 的一個學(xué)生的記錄.注意，這里用了無名變量 “_”.

可以看出，Turbo Prolog 提供的動態(tài)數(shù)據(jù)庫機制，可非常方便地實現(xiàn)堆棧、隊列等動態(tài)數(shù)據(jù)結(jié)構(gòu)，提供的數(shù)據(jù)庫操作謂詞大大簡化了編程.

另外，Turbo Prolog 還提供了兩個文件操作謂詞：

save（《 filename》）.

consult（《 filename》）.12

其中 save 可將當(dāng)前內(nèi)存中的事實存入文件“filename”中，consult 則將文件“filename”中的事實調(diào)入內(nèi)存.
#e#

?表處理與遞歸

1、表頭與表尾

表是 Prolog 中一種非常有用的數(shù)據(jù)結(jié)構(gòu).表的表述能力很強，數(shù)字中的序列、集合，通常語言中的數(shù)組、記錄等均可用表來表示.表的最大特點是其長度不固定，在程序的運行過程中可動態(tài)地變化.具體來講，就是在程序運行時，可對表施行一些操作，如給表中添加一個元素，或從中刪除一個元素，或者將兩個表合并為一個表等.用表還可以方便地構(gòu)造堆棧、隊列、鏈表、樹等動態(tài)數(shù)據(jù)結(jié)構(gòu).

表還有一個重要特點，就是它可分為頭和尾兩部分.表頭是表中第一個元素，而表尾是表中除第一個元素外的其余元素按原來順序組成的表.例如下面的表所示就是一個例子.

表表 頭表 尾

［1， 2， 3， 4， 5］ 1 2， 3， 4， 5］

［apple， orange， banana］ apple ［orange， banana］

［［a， b］， ［c］， ［d， e］］ ［a， b］ ［［c］， ［d， e］］

［“Prolog”］ “Prolog” ［］

［］無定義無定義

**表頭與表尾示例** 表 2、**表的匹配合一** 在程序中是用“|”來區(qū)分表頭和表尾的，而且還可以使用變量.例如一般地用“`［H|T］“`來表示一個表，其中 H、T 都是變量，H 為表頭，T為表尾.注意，此處 H 是一個元素（表中第一個元素），而 T 則是一個表（除第一個元素外表中的其余元素按原來順序組成的表）.表的這種表示法很有用，它為表的操作提供了極大的方便.如下面的表所示即為用這種表示法通過匹配合一提取表頭和表尾的例子. | 表1 | 表2 | 合一后的變量值 | |：————-：|：————-：|：————-：| | ［X | Y］ | ［a， b， c］ | X = a， Y = ［b， c］ | | ［X | Y］ | ［a］ | X = a， Y = ［］ | | ［a | Y］ | ［X， b］ | X = a， Y = ［b］ | | ［X， Y， Z］ | ［a， b， c］ | X = a， Y = b， Z = c | | ［［a， Y］ | Z］ | ［［X， b］， ［c］］ | X = a， Y = b， Z = ［［c］］ |

**表的匹配合一示例** 表 還需說明的是，表中的“|”后面只能有一個變量.例如寫法 ［X | Y， Z］ 就是錯誤的.但豎杠前面的變量可以多于一個.例如寫法 ［ X， Y | Z］ 是允許的.這樣，這個表同 ［a， b， c］ 匹配合一后，有：

X = a， Y = b， Z = ［c］1

另外，豎杠的前面和后面也可以是常量，例如 ［a | Y］ 和 ［X | b］ 都是允許的，但需要注意，后一個表稱為無尾表，如果它同表 ［a | Y］ 匹配，則有：

X = a， Y = b （而不是 Y = ［b］）1

如果無“|”，則不能分離出表尾.例如，表 ［X， Y， Z］ 與 ［a， b， c］ 合一后得 X = a，Y = b，Z = c，其中變量 Z 并非等于 ［c］ .

接下來我們通過三個例子來更詳細地了解表的操作.

例6-1：設(shè)計一個能判斷對象 X 是表 L 的成員的程序.

我們可以這樣設(shè)想：

如果 X 與表 L 中的第一個元素（即表頭）是同一個對象，則 X 就是 L的成員；

如果 X 是 L 的尾部的成員，則 X 也就是 L 的成員.

根據(jù)這種邏輯關(guān)系，有下面的 Prolog 程序：

member（X， ［X | Tail］）.

member（X， ［Head | Tail］） ：- member（X， Tail）.12

其中第一個子句的語義就是上面的第一句話；第二個子句的語義就是上面的第二句話.可以看出，這個程序中使用了遞歸技術(shù)，因為謂詞 member 的定義中又含有它自身.利用這個程序就可以判定任意給定的一個對象和一個表之間是否具有 member（成員）關(guān)系.例如，取表 L 為 ［a， b， c， d］，取 X 為 a，對上面的程序提出如下詢問：

Goal ： member（a， ［a， b， c， d］）.1

則回答“yes”.同樣對于詢問：

Goal ： member（b， ［a， b， c， d］）.

Goal ： member（c， ［a， b， c， d］）.

Goal ： member（d， ［a， b， c， d］）.123

均回答“yes”.但若詢問：

Goal ： member（e， ［a， b， c， d］）.1

則回答“no”.如果我們這樣詢問：

Goal ： member（X， ［a， b， c， d］）.1

意思是要證明存在這樣的 X，它是該表的成員，這時系統(tǒng)返回 X 的值，即：

X = a1

如果需要的話，系統(tǒng)還會給出 X 的其他所有值.

例6-2：寫一個表的拼接程序，即把兩個表連接成一個表.

append（［］， L， L）.

append（［H | T］， L2， ［H | Tn］） ：- append（T， L2， Tn）.12

程序中第一個子句的意思是空表同任一表 L 拼接的結(jié)果仍為表 L；第二個子句的意思是說，一個非空的表 L1 與另一個表 L2 拼接的結(jié)果 L3 是這樣一個表，它的頭是 L1 的頭，它的尾是由 L1 的尾 T 同 L2 拼接的結(jié)果 Tn.這個程序刻畫了兩個表與它們的拼接表之間的邏輯關(guān)系.

可以看出，謂詞 append 是遞歸定義的，子句append（［］， L， L）.為終結(jié)條件即遞歸出口.

對于這個程序，如果我們詢問：

Goal ： append（［1， 2， 3］， ［4， 5］， L）.1

則系統(tǒng)便三次遞歸調(diào)用程序中的第二個子句，最后從第一個子句終止，然后反向依次求出每次的拼接表，最后輸出：

L=［1， 2， 3， 4， 5］1

當(dāng)然，對于這個程序也可以給出其他各種詢問，如：

Goal ： append（［1， 2， 3］， ［4， 5］， ［1， 2， 3， 4， 5］）.1

系統(tǒng)回答yes.

Goal ： append（［1， 2， 3］， ［4， 5］， ［1， 2， 3， 4， 5， 6］）.1

系統(tǒng)回答no.

Goal ： append（［1， 2， 3］， Y， ［1， 2， 3， 4， 5］）.1

系統(tǒng)回答X = ［4， 5］.

Goal ： append（X， ［4， 5］， ［1， 2， 3， 4， 5］）.1

系統(tǒng)回答X = ［1， 2， 3］.

Goal ： append（X， Y， ［1， 2， 3， 4， 5］）.1

系統(tǒng)回答

X = ［］， Y = ［1， 2， 3， 4， 5］

X = ［1］， Y = ［2， 3， 4， 5］

X = ［1， 2］， Y = ［3， 4， 5］

X = ［1， 2， 3］， Y = ［4， 5］

等（如果需要所有解的話）.12345

例6-3：表的輸出

print（［］）.

print（［H | T］） ：- write（H）， print（T）.12

例6-4：表的倒置，即求一個表的逆序表.

reverse（［］， ［］）.

reverse（［H | T］， L） ：- reverse（T， L1）， append（L1， ［H］， L）.12

這里，reverse的第一個項是輸入，即原表；第二個項是輸出，即原表的倒置.

?回溯控制

Prolog 在搜索目標(biāo)解的過程中，具有回溯機制，即當(dāng)某一個子目標(biāo)“Gi”不能滿足時，就返回到該子目標(biāo)的前一個子目標(biāo)“Gi-1”，并放棄“Gi-1”的當(dāng)前約束值，使它重新匹配合一.在實際問題中，有時卻不需要回溯，為此 Prolog 中就專門定義了一個阻止回溯的內(nèi)部謂同——“！”，稱為截斷謂詞.

截斷謂詞的語法格式很簡單，就是一個感嘆號“！”.！ 的語義如下.

若將“！”插在子句體內(nèi)作為一個子目標(biāo)，它總是立即成功.

若“！”位于子句體的最后，則它就阻止對它所在子句的頭謂詞的所有子句的回溯訪向，而讓回溯跳過該頭謂詞（子目標(biāo)），去訪問前一個子目標(biāo)（如果有的話）.

若“！”位于其他位置，則當(dāng)其后發(fā)生回溯且回溯到“！”處時，就在此處失敗，并且“！”還使它所在子句的頭謂詞（子目標(biāo)）整個失敗（即阻止再去訪問頭謂詞的其余子向（如果有的話），即迫使系統(tǒng)直接回溯到該頭謂詞（子目標(biāo)）的前一個子目標(biāo)（如果有的話））.

舉個例子：

考慮下面的程序

p（a）. （7 - 1）

p（b）. （7 - 2）

q（b）. （7 - 3）

r（X） ：- p（X）， q（X）. （7 - 4）

r（c）.12345

對于目標(biāo)：r（X）.可有一個解：

Y = b

但當(dāng)我們把式（7 - 4）改為：

r（X） ：- p（X）， ！， q（X）. （7 - 4‘）1

時，卻無解.為什么？

這是由于添加了截斷謂詞“！”.因為式（7 - 4’）中求解子目標(biāo) p（X） 時，X 被約束到 a，然后跳過“！”，但在求解子目標(biāo) q（a） 時遇到麻煩，于是又回溯到“！”，而“！”阻止了對 p（X）的下一個子句 p（b） 和 r 的下一個定義子句 r（c） 的訪問.從而導(dǎo)致整個求解失敗.

再舉個例子：

設(shè)有程序：

g0 ：- g11， g12， g13. （7 - 5）

g0 ：- g14. （7 - 6）

g12 ：- g21， ！， g23. （7 - 7）

g12 ：- g24， g25. （7 - 8）

... ...12345

給出目標(biāo)：g0.

假設(shè)運行到子目標(biāo) g23 時失敗，這時如果子句（7 - 7）中無“！”的話，則會回溯到 g21，并且如果 g21 也失敗的話，則會訪問下面的子句（7 - 8）.但由于有“！”存在，所以不能回溯到 g21，而直接宣告 g12 失敗.于是由子句（7 - 5），這時則回溯到 g11.如果我們把子句（7 - 7）改為：

g12 ：- g21， g23， ！. （7 - 9）1

當(dāng)然這時若 g23 失敗時，便可回溯到 g21，而當(dāng) g21 也失敗時，便回溯到 g12，即子句（7 - 8）被“激活”.但對于修改后的程序，如果 g13 失敗，則雖然可回溯到 g12，但對 g12 不做任何事情便立即跳過它，而回溯到 g11.如果子句（7 - 9）中無“！”，則當(dāng) g13 失敗時，回溯到 g12 便去考慮子句（7 - 8），只有當(dāng)子句（7 - 8）再失敗時才回溯到 g11.

八、程序舉例

下面給出幾個簡單而又典型的程序?qū)嵗?通過這些程序，讀者可以進一步體會和理解 Prolog 程序的風(fēng)格和能力，也可以掌握一些基本的編程技巧.

例8-1：下面是一個簡單的路徑查詢程序.程序中的事實描述了如下圖所示的有向圖，規(guī)則是圖中兩節(jié)點間有通路的定義.

predicates

road（symbol， symbol）

path（symbol， symbol）

clauses

road（a， b）.

road（a， c）.

road（b， d）.

road（c， d）.

road（d， e）.

road（b， e）.

path（X， Y） ：- road（X， Y）.

path（X， Y） ：- road（X， Z）， path（Z， Y）.123456789101112

程序中未含目標(biāo)，所以運行時需給出外部目標(biāo).例如當(dāng)給出目標(biāo)：

path（a， e）.1

時，系統(tǒng)將回答yes，但當(dāng)給出目標(biāo)：

path（e， a）.1

時，系統(tǒng)則回答no，如果給出目標(biāo)：

run.1

且在程序中增加子句：

run ：- path（a， X）， write（”X =“， X）， nl， fail.

run.12

屏幕上將會輸出：

X = b

X = c

X = d

X = e

X = d

X = e

X = e1234567

即從 a 出發(fā)到其他節(jié)點的全部路徑.

例8-2：下面是一個求階乘程序，程序中使用了遞歸.

/* a Factorial Program */

domains

n， f = integer

predicates

factorial（n， f）

goal

readint（I），

factorial（I， F），

write（I， ”！=“， F）.

clauses

factorial（1， 1）.

factorial（N， Res） ：-

N》 0，

N1 = N - 1，

factorial（N1， FacN1），

Res = N * FacN1.12345678910111213141516

程序運行時，從鍵盤上輸入一個整數(shù)，屏幕上將顯示其階乘數(shù).

例8-3：下面是一個表的排序程序，采用插入排序法.

/* insert sort */

domains

listi = integer*

predicates

insert_sort（listi， listi）

insert（integer， listi， listi）

asc_order（integer， integer）

clauses

insert_sort（［］， ［］）.

insert\_sort（［H | Tail］， Sorted_list） ：-

insert_sort（Tail， Sorted\_Tail），

insert（H， Sorted_Tial， Sorted\_list）.

insert（X， ［Y | Sorted_list1］） ：-

asc_order（X， Y）， ！，

insert（X， Sorted_list， Sorted\_list1）.

insert（X， Sorted_list， ［X | Sorted\_list］）.

asc_order（X， Y） ：- X》 Y.1234567891011121314151617

程序中對表的處理使用了遞歸.程序中也未給出目標(biāo)，需要在運行時臨時給出.例如當(dāng)給出目標(biāo)：

insert_sort（［5， 3， 4， 2， 6， 1， 7， 8， 9， 0］， L）.1

時，系統(tǒng)將輸出：

L = ［0， 1， 2， 3， 4， 5， 6， 7， 8， 9］1