前言

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

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

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

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

原子（Atoms）

一個(gè)原子是以下情況之一：

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

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

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

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

數(shù)字（Numbers）

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

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

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

變量（Variables）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

listen2Music

happy

playsAirGuitar

使用正式的書(shū)寫(xiě)方式如下：

listen2Music/1

happy/1

playsAirGuitar/1

Prolog不會(huì)因?yàn)槎x了兩個(gè)loves謂詞而迷惑，它會(huì)區(qū)分loves/2和loves/3是不同的謂詞.
#e#

Prolog 的程序

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

我們首先寫(xiě)出一個(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)題都分行書(shū)寫(xiě)；規(guī)則和事實(shí)可連續(xù)排列在一起，其順序可隨意安排，但同一謂詞名的事實(shí)或規(guī)則必須集中排列在一起；問(wèn)題不能與規(guī)則及事實(shí)排在一起，它作為程序的目標(biāo)要么單獨(dú)列出，要么在程序運(yùn)行時(shí)臨時(shí)給出.

這個(gè)程序的事實(shí)描述了一些對(duì)象（包括人和事物）間的關(guān)系；而規(guī)則則描述了 John 交朋友的條件，即如果一個(gè)人喜歡讀書(shū)并且喜歡音樂(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ǔ)義.
#e#

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

1、領(lǐng)域

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

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

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

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

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

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

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

中的

sports（football， basketball， table_tennis）1

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

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

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

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

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

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

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

在程序中可說(shuō)明如下：

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 的項(xiàng)，一般要求同一個(gè)表的元素必須屬于同一領(lǐng)域.不含任何元素的表稱為空表，記為［］.例如下面就是一些合法的表.

［1，2，3］

［ apple， orange， banana， grape， cane］

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

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

［］12345

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

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

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

都是合法的表.后一個(gè)例子說(shuō)明，表也可以嵌套.

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

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

·（a， ［］）［a］

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

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

表的說(shuō)明方法是在其組成元素的說(shuō)明符后加一個(gè)星號(hào)*.如：

domains

lists = string*

predicates

pl（lists）1234

就說(shuō)明謂詞 pl 中的項(xiàng) lists 是一個(gè)由串 string 組成的表.

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

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

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

則需這樣說(shuō)明：

domains

rec=seg*

seg=name（string）; age（integer）

predicates

p（rec）12345

2、常量與變量

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

3、算術(shù)表達(dá)式

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

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

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

x + yzX + Y * Z

ab - c / dA * B - C / D

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

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

+（X， *（Y， Z））

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

mod（U， V）123

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

在 Turbo Prolog 程序中，如果一個(gè)算術(shù)表達(dá)式中的變?cè)勘粚?shí)例化（即被約束），則這個(gè)算術(shù)表達(dá)式的值就會(huì)被求出.求出的值可用來(lái)實(shí)例化某變量，也可用來(lái)同其他數(shù)量進(jìn)行比較，用一個(gè)算術(shù)表達(dá)式的值實(shí)例化一個(gè)變量的方法是用謂詞“is”或“=”來(lái)實(shí)現(xiàn)的.例如：

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

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

X = X + 11

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

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

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

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

Turbo Prolog 的關(guān)系表達(dá)式的形式和數(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 中的原子形式來(lái)表示，則上面的兩個(gè)例子為：

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

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

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

person（Name2， man， Age2），

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

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

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

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

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

機(jī)器回答“yes”，而對(duì)于：

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

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

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

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

?輸入與輸出

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

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

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

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

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

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

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

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

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

與

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

的效果完全一樣.

舉個(gè)例子：

用上面的輸入輸出謂詞編寫(xiě)一個(gè)簡(jiǎn)單的學(xué)生成績(jī)數(shù)據(jù)庫(kù)查詢程序.

PREDICATES

student（integer， string， real）

grade

GOAL

grade.

CLAUSES

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

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

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

grade ：- write（“請(qǐng)輸人姓名：”）， readln（Name），

student（_， Name， Score），

nl， write（Name， “的成績(jī)是”， Score）.

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

下面是程序運(yùn)行時(shí)的屏幕顯示

請(qǐng)輸入姓名：王五

王五的成績(jī)是96.412

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

Prolog 本來(lái)沒(méi)有分支和循環(huán)語(yǔ)句，但可以利用其邏輯機(jī)制實(shí)現(xiàn)分支和循環(huán)效果.

1、分支

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

IF X》0 THEN X：=1

ELSE X：=012

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

br ：- X》 0， X = 1.

br ：- X = 0.12

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

br ：- X》 0， X = 1.

br ：- X = 0， X = 0.

br ：- X 《 0， X = -1.123

2、循環(huán)

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

舉個(gè)例子：

下面的程序段就實(shí)現(xiàn)了循環(huán)，它使得 write 語(yǔ)句重復(fù)執(zhí)行了3次，而打印輸出了3個(gè)學(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 謂詞與第一個(gè)事實(shí)匹配，write 語(yǔ)句便輸出了張三同學(xué)的記錄.但當(dāng)程序執(zhí)行到最后一句時(shí)，由于 Number 不等于 3，則該語(yǔ)句失敗，于是，引起回溯.而 write 語(yǔ)句和 nl 語(yǔ)句均只能執(zhí)行一次，所以繼續(xù)向上回溯到 student 語(yǔ)句.這樣，student 謂詞則因失敗而重新匹配.這一次與第二個(gè)事實(shí)匹配，結(jié)果輸出了李四的記錄.同理，當(dāng)執(zhí)行到最后一句時(shí)又引起了回溯.write 語(yǔ)句第三次執(zhí)行后，由于 Number 已等于3，所以最后一個(gè)語(yǔ)句成功，程序段便運(yùn)行結(jié)束.

這個(gè)例子可以看做是計(jì)數(shù)循環(huán).當(dāng)然，也可以通過(guò)設(shè)置計(jì)數(shù)器而實(shí)現(xiàn)真正的計(jì)數(shù)循環(huán).下面的程序段實(shí)現(xiàn)的則是不計(jì)數(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

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

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

?動(dòng)態(tài)數(shù)據(jù)庫(kù)

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

asserta（《 fact》）

assertz（《 fact》）

retract（《 fact》）123

其中 fact 表示事實(shí).這 3 個(gè)謂詞的功能如下：

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

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

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

例如語(yǔ)句：

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

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

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

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

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

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

student（20， _， _）1

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

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

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

save（《 filename》）.

consult（《 filename》）.12

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

?表處理與遞歸

1、表頭與表尾

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

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

表表 頭表 尾

［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” ［］

［］無(wú)定義無(wú)定義

**表頭與表尾示例** 表 2、**表的匹配合一** 在程序中是用“|”來(lái)區(qū)分表頭和表尾的，而且還可以使用變量.例如一般地用“`［H|T］“`來(lái)表示一個(gè)表，其中 H、T 都是變量，H 為表頭，T為表尾.注意，此處 H 是一個(gè)元素（表中第一個(gè)元素），而 T 則是一個(gè)表（除第一個(gè)元素外表中的其余元素按原來(lái)順序組成的表）.表的這種表示法很有用，它為表的操作提供了極大的方便.如下面的表所示即為用這種表示法通過(guò)匹配合一提取表頭和表尾的例子. | 表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］］ |

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

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

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

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

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

接下來(lái)我們通過(guò)三個(gè)例子來(lái)更詳細(xì)地了解表的操作.

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

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

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

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

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

member（X， ［X | Tail］）.

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

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

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

則回答“yes”.同樣對(duì)于詢問(wèn)：

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

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

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

均回答“yes”.但若詢問(wèn)：

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

則回答“no”.如果我們這樣詢問(wèn)：

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

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

X = a1

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

例6-2：寫(xiě)一個(gè)表的拼接程序，即把兩個(gè)表連接成一個(gè)表.

append（［］， L， L）.

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

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

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

對(duì)于這個(gè)程序，如果我們?cè)儐?wèn)：

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

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

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

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

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：表的倒置，即求一個(gè)表的逆序表.

reverse（［］， ［］）.

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

這里，reverse的第一個(gè)項(xiàng)是輸入，即原表；第二個(gè)項(xiàng)是輸出，即原表的倒置.

?回溯控制

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

截?cái)嘀^詞的語(yǔ)法格式很簡(jiǎn)單，就是一個(gè)感嘆號(hào)“！”.！ 的語(yǔ)義如下.

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

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

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

舉個(gè)例子：

考慮下面的程序

p（a）. （7 - 1）

p（b）. （7 - 2）

q（b）. （7 - 3）

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

r（c）.12345

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

Y = b

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

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

時(shí)，卻無(wú)解.為什么？

這是由于添加了截?cái)嘀^詞“！”.因?yàn)槭剑? - 4’）中求解子目標(biāo) p（X） 時(shí)，X 被約束到 a，然后跳過(guò)“！”，但在求解子目標(biāo) q（a） 時(shí)遇到麻煩，于是又回溯到“！”，而“！”阻止了對(duì) p（X）的下一個(gè)子句 p（b） 和 r 的下一個(gè)定義子句 r（c） 的訪問(wèn).從而導(dǎo)致整個(gè)求解失敗.

再舉個(gè)例子：

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

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

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

八、程序舉例

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

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

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)，所以運(yùn)行時(shí)需給出外部目標(biāo).例如當(dāng)給出目標(biāo)：

path（a， e）.1

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

path（e， a）.1

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

run.1

且在程序中增加子句：

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

run.12

屏幕上將會(huì)輸出：

X = b

X = c

X = d

X = e

X = d

X = e

X = e1234567

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

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

/* 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

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

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

/* 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

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

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

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

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