邏輯程序設計語言

第2章邏輯程序設計語言2.1基本PROLOG2.2TurboPROLOG程序設計習題二2.1基本PROLOG2.1.1PROLOG的語句1.事實(fact)格式[HTSS]〈謂詞名〉(〈項表〉).其中謂詞名是以小寫英文字母打頭的字母、數(shù)字、下劃線等組成的字符串,項表是以逗號隔開的項序列。PROLOG中的項包括由常量或變量表示的簡單對象以及函數(shù)、結構和表等,即事實的形式是一個原子謂詞公式。

例如：student(john).like(mary,music).就是PROLOG中的兩個合法事實。

可以看出,在這里事實就是Horn子句邏輯中的無條件子句,但形式略有不同。

功能一般表示對象的性質或關系。例如上面的兩個事實就分別表示“約翰是學生”和“瑪麗喜歡音樂”。作為特殊情形,一個事實也可以只有謂詞名而無參量。例如：abc.repeat.等也是允許的。2.規(guī)則(rule)格式〈謂詞名〉(〈項表〉):-〈謂詞名〉(〈項表〉){,〈謂詞名〉(〈項表〉)}.其中“:-”號表示“if”(也可以直接寫為if),其左部的謂詞是規(guī)則的結論(亦稱為頭),右部的謂詞是規(guī)則的前提(亦稱為體),{}表示零次或多次重復,逗號表示and(邏輯與),即規(guī)則的形式是一個邏輯蘊含式。例如：bird(X):-animal(X),has(X,feather).grandfather(X,Y):-father(X,Z),father(Z,Y).就是PROLOG的合法規(guī)則。功能一般表示對象間的因果關系、蘊含關系或對應關系。例如,上面的第一條規(guī)則就表示“如果X是動物,并且X有羽毛,則X是鳥”；第二條規(guī)則就表示“X是Y的祖父,如果存在Z,X是Z的父親并且Z又是Y的父親”。作為特殊情形,規(guī)則中的謂詞也可以只有謂詞名而無參量。例如：run:-start,step1(X),step2(X),end.也是一個合法規(guī)則。

3.問題(question)格式?-〈謂詞名〉(〈項表〉){,〈謂詞名〉(〈項表〉)}.例如：?-student(john).?-like(mary,X).就是兩個合法的問題。可以看出,這里的問題也就是Horn子句邏輯中的目標子句,只是形式略有不同。功能問題表示用戶的詢問,它就是程序運行的目標。問題可以與規(guī)則及事實同時一起給出,也可以在程序運行時臨時給出。例如,上面的第一個問題的意思是“約翰是學生嗎？”,第二個問題的意思是“瑪瑪麗喜歡誰？”2.1.2PROLOG的程序PROLOG程序一般由一組事實、規(guī)則和問題組成。問題是程序執(zhí)行的起點,稱為程序的目標。例如下面就是一個PROLOG程序。 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ī)則及事實排在一起,它作為程序的目標要么單獨列出,要么在程序運行時臨時給出。這個程序的事實描述了一些對象(包括人和事物)間的關系；而規(guī)則則描述了john交朋友的條件,即如果一個人喜歡讀書并且喜歡音樂(或者喜歡運動和喜歡音樂),則這個人就是john的朋友(當然,這個規(guī)則也可看作是john朋友的定義)；程序中的問題是“約翰的朋友是誰？”。當然,PROLOG程序中的目標可以變化,也可以含有多個語句(上例中只有一個)。如果有多個語句,則這些語句稱為子目標。例如對上面的程序,其問題也可以是?-likes(mary,X).或?-likes(mary,music).或?-friend(X,Y).或?-likes(bell,sports),likes(mary,music),friend(john,X).等等。當然,對于不同的問題,程序運行的結果一般是不一樣的。還需說明的是,PROLOG程序中的事實或規(guī)則一般稱為它們對應謂詞的子句。例如上面程序中的前四句都是謂詞likes的子句。PROLOG規(guī)定,同一謂詞的子句應排在一起。從語句形式和程序組成來看,PROLOG就是一種基于Horn子句的邏輯程序。這種程序要求用事實和規(guī)則來求證詢問,即證明所給出的條件子句和無條件子句與目標子句是矛盾的,或者說程序中的子句集是不可滿足的。這就是所謂的PROLOG的說明性語義。從PROLOG的語句來看,PROLOG語言的文法結構相當簡單。但由于它的語句是Horn子句,而Horn子句的描述能力是很強的,所以PROLOG的描述能力也是很強的。例如,當它的事實和規(guī)則描述的是某一學科的公理,那么問題就是待證的命題；當事實和規(guī)則描述的是某些數(shù)據(jù)和關系,那么問題就是數(shù)據(jù)查詢語句；當事實和規(guī)則描述的是某領域的知識,那么問題就是利用這些知識求解的問題；當事實和規(guī)則描述的是某初始狀態(tài)和狀態(tài)變化規(guī)律,那么問題就是目標狀態(tài)。所以,PROLOG語言實際是一種應用相當廣泛的智能程序設計語言。從上面最后一個目標可以看出,同過程性語言相比,一個PROLOG程序,其問題就相當于主程序,其規(guī)則就相當于子程序,而其事實就相當于數(shù)據(jù)。2.1.3PROLOG程序的運行機理1.自由變量與約束變量

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

2.匹配合一兩個謂詞可匹配合一,是指兩個謂詞的名相同,參量項的個數(shù)相同,參量類型對應相同,并且對應參量項還滿足下列條件之一：(1)如果兩個都是常量,則必須完全相同。(2)如果兩個都是約束變量,則兩個約束值必須相同。(3)如果其中一個是常量,一個是約束變量,則約束值與常量必須相同。(4)至少有一個是自由變量。例如：下面的兩個謂詞pre1(″ob1″,″ob2″,Z)pre1(″ob1″,X,Y)只有當變量X被約束為″ob2″,且Y、Z的約束值相同或者至少有一個是自由變量時,它們才是匹配合一的?？梢奝ROLOG的匹配合一,與歸結原理中的合一的意思基本一樣。但這里的合一同時也是一種操作。這種操作可使兩個能匹配的謂詞合一起來,即為參加匹配的自由變量和常量,或者兩個自由變量建立一種對應關系,使得常量作為對應變量的約束值,使得兩個對應的自由變量始終保持一致,即若其中一個被某值約束,則另一個也被同一值約束；反之,若其中一個的值被解除,則另一個的值也被解除。合一操作是PROLOG的一個特有機制。3.回溯所謂回溯,就是在程序運行期間,當某一個子目標不能滿足(即謂詞匹配失敗)時,控制就返回到前一個已經(jīng)滿足的子目標(如果存在的話),并撤消其有關變量的約束值,然后再使其重新滿足。成功后,再繼續(xù)滿足原子目標。如果失敗的子目標前再無子目標,則控制就返回到該子目標的上一級目標(即該子目標謂詞所在規(guī)則的頭部)使它重新匹配?；厮菀彩荘ROLOG的一個重要機制。下面,我們介紹PROLOG程序的運行過程。我們仍以上面的程序為例。設所給的詢問是?-friend(john,Y).(john和誰是朋友?)則求解目標為friend(john,Y).這時,系統(tǒng)對程序進行掃描,尋找能與目標謂詞匹配合一的事實或規(guī)則頭部。顯然,程序中前面的四條事實均不能與目標匹配,而第五個語句的左端即規(guī)則friend(john,X):-likes(X,reading),likes(X,music).的頭部可與目標謂詞匹配合一。但由于這個語句又是一個規(guī)則,所以其結論要成立則必須其前提全部成立。于是,對原目標的求解就轉化為對新目標likes(X,reading),likes(X,music).的求解。這實際是經(jīng)歸結,規(guī)則頭部被消去,而目標子句變?yōu)?-likes(X,reading),likes(X,music).現(xiàn)在依次對子目標likes(X,reading)和likes(X,music)求解。子目標的求解過程與主目標完全一樣,也是從頭對程序進行掃描,不斷進行測試和匹配合一等,直到匹配成功或掃描完整個程序為止?？梢钥闯?對第一個子目標like(X,reading)的求解因無可匹配的事實和規(guī)則而立即失敗,進而導致規(guī)則friend(john,X):-likes(X,reading),likes(X,music).的整體失敗。于是,剛才的子目標likes(X,reading)和likes(X,music)被撤消,系統(tǒng)又回溯到原目標friend(john,X)。這時,系統(tǒng)從該目標剛才的匹配語句處(即第五句)向下繼續(xù)掃描程序中的子句,試圖重新使原目標匹配,結果發(fā)現(xiàn)第六條語句的左部,即規(guī)則friend(john,X):-likes(X,sports),likes(X,music).的頭部可與目標為謂詞匹配。但由于這個語句又是一個規(guī)則,于是,這時對原目標的求解,就又轉化為依次對子目標likes(X,sports)和likes(X,music)的求解。這次子目標likes(X,sports)與程序中的事實立即匹配成功,且變量X被約束為bell。于是,系統(tǒng)便接著求解第二個子目標。由于變量X已被約束,所以這時第二個子目標實際上已變成了likes(bell,music).由于程序中不存在事實likes(bell,music),所以該目標的求解失敗。于是,系統(tǒng)就放棄這個子目標,并使變量X恢復為自由變量,然后回溯到第一個子目標,重新對它進行求解。由于系統(tǒng)已經(jīng)記住了剛才已同第一子目標謂詞匹配過的事實的位置,所以重新求解時,便從下一個事實開始測試。易見,當測試到程序中第三個事實時,第一個子目標便求解成功,且變量X被約束為mary。這樣,第二個子目標也就變成了likes(mary,music).再對它進行求解。這次很快成功。由于兩個子目標都求解成功,所以,原目標friend(john,Y)也成功,且變量Y被約束為mary(由Y與X的合一關系)。于是,系統(tǒng)回答：Y=mary程序運行結束。圖2-1PROLOG程序運行機理示例上述程序的運行是一個通過推理實現(xiàn)的求值過程。我們也可以使它變?yōu)樽C明過程。例如,把上述程序中的詢問改為friend(john,mary)則系統(tǒng)會回答:yes若將詢問改為：friend(john,smith)則系統(tǒng)會回答:no從上述程序的運行過程可以看出,PROLOG程序的執(zhí)行過程是一個(歸結)演繹推理過程。其特點是：推理方式為反向推理,控制策略是深度優(yōu)先,且有回溯機制。其具體實現(xiàn)方法是：匹配子句的順序是自上而下；子目標選擇順序是從左向右；(歸結后)產(chǎn)生的新子目標總是插入被消去的目標處(即目標隊列的左部)。PROLOG的這種歸結演繹方法被稱為SLD(LinearresolutionwithSelectionfunctionforDefiniteclause)歸結,或SLD反駁-消解法。SLD歸結就是PROLOG程序的運行機理,它也就是所謂的PROLOG語言的過程性語義。2.2TurboPROLOG程序設計2.2.1程序結構一個完整的TurboPROLOG(2.0版)程序一般包括常量段、領域段、數(shù)據(jù)庫段、謂詞段、目標段和子句段等六個部分。各段以其相應的關鍵字constants、domains、database、predicates、goal和clauses開頭加以標識。另外,在程序的首部還可以設置指示編譯程序執(zhí)行特定任務的編譯指令；在程序的任何位置都可設置注解?？傊?一個完整的TurboPROLOG(2.0版)程序的結構如下：/*〈注釋〉*/〈編譯指令〉constants〈常量說明〉domains〈域說明〉database〈數(shù)據(jù)庫說明〉predicates〈謂詞說明〉goal〈目標語句〉clauses〈子句集〉當然,一個程序不一定要包括上述所有段,但一個程序至少要有一個predicates段、clauses段和goal段。在大多數(shù)情形中,還需要一個domains段,以說明表、復合結構及用戶自定義的域名。如若省略goal段,則可在程序運行時臨時給出,但這僅當在開發(fā)環(huán)境中運行程序時方可給出。若要生成一個獨立的可執(zhí)行文件,則在程序中必須包含goal段。另一方面,一個程序也只能有一個goal段。在模塊化程序設計中,可以在關鍵字domains,predicates及database前加上global,以表明相應的說明是全局的,以便作用于幾個程序模塊。

例2.1如果把上節(jié)中的程序要作為TurboPROLOG程序,則應改寫為：/*例子程序-1*/DOMAINSname=symbolPREDICATESlikes(name,name).friend(name,name)GOALfriend(john,Y),write(″Y=″,Y).CLAUSESlikes(bell,sports).likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,sports),likes(X,music).friend(john,X):-likes(X,reading),likes(X,music).

領域段該段說明程序謂詞中所有參量項所屬的領域。領域的說明可能會出現(xiàn)多層說明,直到最終說明到TurboPROLOG的標準領域為止(如上例所示)。TurboPROLOG的標準領域即標準數(shù)據(jù)類型,包括整數(shù)、實數(shù)、符號、串和符號等,其具體說明如表2.1所示。表2.1TurboPROLOG的標準領域

謂詞段該段說明程序中用到的謂詞的名和參量項的名(但TurboPROLOG的內部謂詞無須說明)。

子句段該段是TurboPROLOG程序的核心,程序中的所有事實和規(guī)則就放在這里,系統(tǒng)在試圖滿足程序的目標時就對它們進行操作。

目標段該段是放置程序目標的地方。目標段可以只有一個目標謂詞,例如上面的例子中就只有一個目標謂詞；也可以含有多個目標謂詞,如goalreadint(X),Y=X+3,write(″Y=″,Y).就有三個目標謂詞。這種目標稱為復合目標。2.2.2數(shù)據(jù)與表達式1.領域1)標準領域TurboPROLOG中不定義變量的類型,只說明謂詞中各個項的取值域。由上節(jié)我們知道,TurboPROLOG有整數(shù)、實數(shù)、字符、串和符號等五種標準域。另外,它還有結構、表和文件等三種復合域。2)結構結構也稱復合對象,它是TurboPROLOG謂詞中的一種特殊的參量項(類似于謂詞邏輯中的函數(shù))。結構的一般形式為〈函子〉(〈參量表〉)其中函子及參量的標識符與謂詞相同。注意,這意味著結構中還可包含結構。所以,復合對象可表達樹形數(shù)據(jù)結構。例如下面的謂詞likes(″Tom″,sports(football,basketball,table_tennis)).中的sports(football,basketball,table_tennis)就是一個結構,即復合對象。又如：person(″張華″,student(″西安石油大學″),address(″中國″,″陜西″,″西安″)).reading(″王宏″,book(″人工智能技術導論″,″西安電子科技大學出版社″)).friend(father(″Li″),father(″Zhao″)).這幾個謂詞中都有復合對象。[HJ*5/9]復合對象在程序中的說明,需分層進行。例如,對于上面的謂詞likes(″Tom″,sports(football,basketball,table_tennis)).在程序中可說明如下：domainsname=symbolsy=symbolsp=sports(sy,sy,sy)predicates likes(name,sp)3)表表的一般形式是［x1,x2,…,xn］其中xi(i=1,2,…,n)為PROLOG的項,一般要求同一個表的元素必須屬于同一領域。不含任何元素的表稱為空表,記為［］。例如下面就是一些合法的表:［1,2,3］［apple,orange,banana,grape,cane］［″PROLOG″,″MAENS″,″PROGRAMMING″,″inlogic″］［［a,b］,［c,d］,［e］］［］表的最大特點是其元素個數(shù)可在程序運行期間動態(tài)變化。表的元素也可以是結構或表,且這時其元素可以屬于不同領域。例如：［name(″LiMing″),age(20),sex(male),address(xian)］［［1,2］,［3,4,5］,［6,7］］都是合法的表。后一個例子說明,表也可以嵌套。實際上,表是一種特殊的結構。它是遞歸結構的另一種表達形式。這個結構的函數(shù)名取決于具體的PROLOG版本。這里我們就用一個圓點來表示。下面就是一些這樣的結構及它們的表表示形式： 結構形式表形式·(a,［］)［a］·(a,·(b,［］))［a,b］·(a,·(b,·(c,［］)))［a,b,c］表的說明方法是在其組成元素的說明符后加一個星號*。如：domainslists=string*predicatespl(lists)就說明謂詞pl中的項lists是一個由串string組成的表。對于由結構組成的表,至少分三步說明。例如對于下面謂詞p中的表p(［name(″Liming″),age(20)］)則需這樣說明:domainsrec=seg*seg=name(string);age(integer)predicatesp(rec)

2.常量與變量由上面的領域可知,TurboPROLOG的常量有整數(shù)、實數(shù)、字符、串、符號、結構、表和文件這八種數(shù)據(jù)類型。同理,TurboPROLOG的變量也就有這八種取值。另外,變量名要求必須是以大寫字母或下劃線開頭的字母、數(shù)字和下劃線序列,或者只有一個下劃線。這后一種變量稱為無名變量。

3.算術表達式TurboPROLOG提供了五種最基本的算術運算：加、減、乘、除和取模,相應運算符號為+、-、*、/、mod。這五種運算的順序為：*、/、mod優(yōu)先于+、-。同級從左到右按順序運算,括號優(yōu)先。算術表達式的形式與數(shù)學中的形式基本一樣。例如：數(shù)學中的算術表達式PROLOG中的算術表達式x+yzX+Y*Zab-c/dA*B-C/DumodvUmodV(表示求U除以V所得的余數(shù))即是說,TurboPROLOG中算術表達式采用通常數(shù)學中使用的中綴形式。這種算術表達式為PROLOG的一種異體結構,若以PROLOG的結構形式來表示,則它們應為+(X,*(Y,Z))-(*(A,B),/(C,D))mod(U,V)所以,運算符+、-、*、/和mod實際也就是PROLOG內部定義好了的函數(shù)符。在TurboPROLOG程序中,如果一個算術表達式中的變元全部被實例化(即被約束),則這個算術表達式的值就會被求出。求出的值可用來實例化某變量,也可用來同其他數(shù)量進行比較,用一個算術表達式的值實例化一個變量的方法是用謂詞“is”或“=”來實現(xiàn)。例如：YisX+5或Y=X+5 (*)就使變量Y實例化為X+5的值(當然X也必須經(jīng)已被某值實例化),可以看出,這里對變量Y的實例化方法類似于其他高級程序語言中的“賦值”,但又不同于賦值。例如,在PROLOG中下面的式子是錯誤的:X=X+1需要說明的是,雖然PROLOG是一種邏輯程序設計語言,但在目前的硬件條件下卻非突破邏輯框架不可。這是因為有些實用操作是無法用邏輯描述的(如輸入輸出),有些算術運算在原則上可用邏輯描述,但這樣做效率太低。為此,PROLOG提供了若干內部謂詞(亦稱預定義謂詞),來實現(xiàn)算術運算、輸入輸出等操作。所謂內部謂詞,就是PROLOG的解釋程序中,預先用實現(xiàn)語言定義好的用戶可直接作為子目標調用的謂詞。一般的PROLOG實用系統(tǒng)都配有100個以上的內部謂詞,這些內部謂詞涉及輸入輸出、算術運算、搜索控制、文件操作和圖形聲音等方面,它們是實用PROLOG程序設計所必不可少的。這樣,上面的(*)式以及下面的關系表達式稱為異體謂詞。

4.關系表達式TurboPROLOG提供了六種常用的關系運算,即小于、小于或等于、等于、大于、大于或等于和不等于,其運算符依次為<,<=,=,>,>=,<>TurboPROLOG的關系表達式的形式和數(shù)學中的也基本一樣,例如：數(shù)學中的關系式TurboPROLOG中的關系式X+1≥YX+1>=YX≠YX<>Y即是說,TurboPROLOG中的關系式也用中綴形式。當然,這種關系式為TurboPROLOG中的異體原子。若按TurboPROLOG中的原子形式來表示,則上面的兩個例子為>=(X+1,Y)和<>(X,Y)所以上述六種關系運算符,實際上也就是TurboPROLOG內部定義好了的六個謂詞。這六個關系運算符可用來比較兩個算術表達式的大小。例如：brother(Name1,Name2):-person(Name1,man,Age1),person(Name2,man,Age2),mother(Z,Name1),mother(Z,Name2),Age1>Age2.需要說明的是,“=”的用法比較特殊,它既可以表示比較,也可以表示約束值,即使在同一個規(guī)則中的同一個“=”也是如此。例如：p(X,Y,Z):-Z=X+Y.當變量X、Y、Z全部被實例化時,“=”就是比較符。如：對于問題Goal:p(3,5,8).機器回答：yes。而對于Goal:p(3,5,7).機器回答：no。即這時機器把X+Y的值與Z的值進行比較。但當X,Y被實例化,而Z未被實例化時,“=”號就是約束符。如：Goal:p(3,5,Z).機器回答：Z=8這時,機器使Z實例化為X+Y的結果。2.2.3輸入與輸出雖然PROLOG能自動輸出目標子句中的變量的值,但這種輸出功能必定有限,往往不能滿足實際需要；另一方面,對通常大多數(shù)的程序來說,運行時從鍵盤上輸入有關數(shù)據(jù)或信息也是必不可少的。為此每種具體PROLOG一般都提供專門的輸入和輸出謂詞,供用戶直接調用。例如,下面就是TorboPROLOG的幾種輸入輸出謂詞：(1)readln(X)。這個謂詞的功能是從鍵盤上讀取一個字符串,然后約束給變量X。(2)readint(X)。這個謂詞的功能是從鍵盤上讀取一個整數(shù),然后約束給變量X,如果鍵盤上打入的不是整數(shù)則該謂詞失敗。(3)readreal(X)。這個謂詞的功能是從鍵盤上讀取一個實數(shù),然后約束給變量X,如果鍵盤上打入的不是實數(shù)則該謂詞失敗。(4)readchar(X)。這個謂詞的功能是從鍵盤上讀取一個字符,然后約束給變量X,如果鍵盤上打入的不是單個字符,則該謂詞失敗。(5)write(X1,X2,…,Xn)。這個謂詞的功能是把項Xi(i=1,2,…,n)的值顯示在屏幕上或者打印在紙上,當有某個Xi未實例化時,該謂詞失敗,其中的Xi可以是變量,也可以是字符串或數(shù)字。例如：write(″computer″,″PROLOG″,Y,1992)(6)nl(換行謂詞)。它使后面的輸出(如果有的話)另起一行。另外,利用write的輸出項″＼n″也同樣可起換行作用。例如：write(″name″),nl,write(″age″)與write(″name″,″＼n″,″age″)的效果完全一樣。

例2.2用上面的輸入輸出謂詞編寫一個簡單的學生成績數(shù)據(jù)庫查詢程序。PREDICATESstudent(integer,string,real)gradeGOALgrade.CLAUSESstudent(1,″張三″,90.2).student(2,″李四″,95.5).student(3,″王五″,96.4).grade:-write(″請輸入姓名:″),readln(Name),student(_,Name,Score),nl,write(Name,″的成績是″,Score).grade:-write(″對不起,找不到這個學生!″).下面是程序運行時的屏幕顯示:請輸入姓名：王五王五的成績是96.4。2.2.4分支與循環(huán)1.分支對于通常的IF-THEN-ELSE分支結構,PROLOG可用兩條同頭的并列規(guī)則實現(xiàn)。例如,將IFx>0THENx:=1ELSEx:=0用PROLOG實現(xiàn)則是br:-x>0,x=1.br:-x=0.類似地,對于多分支,可以用多條規(guī)則實現(xiàn)。例如：br:-x>0,x=1.br:-x=0,x=0.br:-x<0,x=-1.

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語句重復執(zhí)行了三次,而打印輸出了三個學生的記錄。student(1,″張三″,90.2).student(2,″李四″,95.5).student(3,″王五″,96.4).print:-student(Number,Name,Score),write(Number,Name,Score),nl,Number=3.可以看出,程序第一次執(zhí)行,student謂詞與第一個事實匹配,write語句便輸出了張三同學的記錄。但當程序執(zhí)行到最后一句時,由于Number不等于3,則該語句失敗,于是,引起回溯。而write語句和nl語句均只能執(zhí)行一次,所以繼續(xù)向上回溯到student語句。這樣,student謂詞則因失敗而重新匹配。這一次與第二個事實匹配,結果輸出了李四的記錄。同理,當執(zhí)行到最后一句時又引起了回溯。write語句第三次執(zhí)行后,由于number已等于3,所以最后一個語句成功,程序段便運行結束。這個例子可以看做是計數(shù)循環(huán)。當然,也可以通過設置計數(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:-.這個程序段中的fail是一個內部謂詞,它的語義是恒失敗。這個程序段與上面的程序段的差別僅在于把原來用計數(shù)器(或標記數(shù))循環(huán)控制語句變成了恒失敗謂詞fail,另外再增加了一個print語句。增加這個語句的目的是為程序設置一個出口。因為fail是恒失敗,下面若無出口的話,將引起print本身的失敗。進而又會導致程序中的連鎖失敗。還需說明的是,用PROLOG的遞歸機制也可以實現(xiàn)循環(huán),不過用遞歸實現(xiàn)循環(huán)通常需與表相配合。另外,遞歸的缺點是容易引起內存溢出。故通常的循環(huán)多是用上述方法實現(xiàn)的。2.2.5動態(tài)數(shù)據(jù)庫動態(tài)數(shù)據(jù)庫就是在內存中實現(xiàn)的動態(tài)數(shù)據(jù)結構。它由事實組成,程序可以對它操作,所以在程序運行期間它可以動態(tài)變化。TurboPROLOG提供了三個動態(tài)數(shù)據(jù)庫操作謂詞:asserta(〈fact〉).assertz(〈fact〉).retract(〈fact〉).其中fact表示事實。這三個謂詞的功能是：asserta(〈fact〉).把fact插入當前動態(tài)數(shù)據(jù)庫中的同名謂詞的事實之前；assertz(〈fact〉).把fact插入當前動態(tài)數(shù)據(jù)庫中的同名謂詞的事實之后；retract(〈fact〉).把fact從當前動態(tài)數(shù)據(jù)庫中刪除。例如語句asserta(student(20,″李明″,90.5)).將在內存的謂詞名為student的事實前插入一個新事實：student(20,″李明″,90.5)如果內存中還沒有這樣的事實,則它就是第一個。又如語句retract(student(20,_,_)).將從內存的動態(tài)數(shù)據(jù)庫中的刪除事實student(20,_,_)它可解釋為學號為20的一個學生的記錄。注意,這里用了無名變量_。可以看出,PROLOG提供的動態(tài)數(shù)據(jù)庫機制,可非常方便地實現(xiàn)堆棧、隊列等動態(tài)數(shù)據(jù)結構,提供的數(shù)據(jù)庫操作謂詞大大簡化了編程。另外,PROLOG還提供了謂詞save(〈filename〉).consult(〈filename〉).2.2.6表處理與遞歸表是PROLOG中一種非常有用的數(shù)據(jù)結構。表的表述能力很強,數(shù)字中的序列、集合,通常語言中的數(shù)組、記錄等均可用表來表示。表的最大特點是其長度不固定,在程序的運行過程中可動態(tài)地變化。具體來講,就是在程序運行時,可對表施行一些操作,如給表中添加一個元素,或從中刪除一個元素,或者將兩個表合并為一個表等等。用表還可以方便地構造堆棧、隊列、鏈表、樹等動態(tài)數(shù)據(jù)結構。表還有一個重要特點,就是它可分為頭和尾兩部分。表頭是表中第一個元素,而表尾是表中除第一個元素外的其余元素按原來順序組成的表。例如下面的表2.2就是一個例子：表2.2表的示例在程序中是用豎線“|”來區(qū)分表頭和表尾的,而且還可以使用變量。例如一般地用［H|T］來表示一個表,其中H、T都是變量,H為表頭,T為表尾。注意,此處H是一個元素(表中第一個元素),而T則是一個表(除第一個元素外的表中其余元素按原來順序組成的表)。表的這種表示法很有用,它為表的操作提供了極大的方便。表2.3即為用這種表示法通過匹配合一提取表頭和表尾的例子。表2.3表的匹配合一示例還需說明的是,表中的豎杠“|”后面只能有一個變量。例如寫法［X|Y,Z］就是錯誤的。但豎杠的前面的變量可以多于一個。例如寫法［X,Y|Z］是允許的。這樣,這個表同［a,b,c］匹配合一后,有X=a,Y=b,Z=［c］另外,豎杠的前面和后面也可以是常量,例如［a|Y］和［X|b］都是允許的,但注意,后一個表稱為無尾表,如果它同表［a|Y］匹配,則有X=a,Y=b(而不是Y=［b］)如果無豎杠“|”,則不能分離出表尾。例如,表［X,Y,Z］與［a,b,c］合一后得X=a,Y=b,Z=c。其中變量Z并非等于［c］。例2.3設計一個能判斷對象X是表L的成員的程序。我們可以這樣設想：(1)如果X與表L中的第一個元素(即表頭)是同一個對象,則X就是L的成員。(2)如果X是L的尾部的成員,則X也就是L的成員。根據(jù)這種邏輯關系,于是有下面的PROLOG程序：member(X,［X|Tail］).member(X,［Head|Tail］):-member(X,Tail).其中第一個子句的語義就是上面的第一句話,第二個子句的語義就是上面的第二句話?？梢钥闯?這個程序中使用了遞歸技術,因為謂詞member的定義中又含有它自身。利用這個程序我們就可以判定任意給定的一個對象和一個表之間是否具有member(成員)關系。例如,我們取表L為［a,b,c,d］,取X為a,對上面的程序提出如下詢問:Goal:member(a,［a,b,c,d］).則有回答:yes同樣對于詢問:Goal:member(b,［a,b,c,d］).Goal:member(c,［a,b,c,d］).Goal:member(d,［a,b,c,d］).都有回答:yes但若詢問Goal:member(e,［a,b,c,d］).則回答:no如果我們這樣詢問Goal:member(X,［a,b,c,d］).意思是要證明存在這樣的X,它是該表的成員,這時系統(tǒng)返回X的值,即X=a如果需要的話,系統(tǒng)還會給出X的其他所有值。

例2.4表的拼接程序,即把兩個表連接成一個表。append(［］,L,L).append(［H|T］,L2,［H|Tn］):-append(T,L2,Tn).程序中第一個子句的意思是空表同任一表L拼接的結果仍為表L;第二個子句的意思是說,一個非空的表L1與另一個表L2拼接的結果L3是這樣一個表,它的頭是L1的頭,它的尾是由L1的尾T同L2拼接的結果Tn。這個程序刻劃了兩個表與它們的拼接表之間的邏輯關系?？梢钥闯?謂詞append是遞歸定義的,子句append(［］,L,L).為終結條件,即遞歸出口。對于這個程序,如果我們詢問Goal:append(［1,2,3］,［4,5］,L).則系統(tǒng)便三次遞歸調用程序中的第二個子句,最后從第一個子句終止,然后反向依次求出每次的拼接表,最后輸出L=［1,2,3,4,5］當然,對于這個程序也可以給出其他各種詢問,如：Goal:append(［1,2,3］,［4,5］,［1,2,3,4,5］).系統(tǒng)回答:yesGoal:append(［1,2,3］,［4,5］,［1,2,3,4,5,6］).系統(tǒng)回答:noGoal:append(［1,2,3］,Y,［1,2,3,4,5］).系統(tǒng)回答:Y=［4,5］Goal:append(X,［4,5］,［1,2,3,4,5］).系統(tǒng)回答:X=［1,2,3］Goal:append(X,Y,［1,2,3,4,5］).系統(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］等等(如果需要所有解的話)?！?.5表的輸出。print(［］).print(［H|T］):-write(H),print(T).[KH*4]例2.6表的倒置,即求一個表的逆序表。[KH*4]reverse(［］,［］).reverse(［H|T］,L):-reverse(T,L1),append(L1,［H］,L).這里,reverse的第一個項是輸入,即原表;第二個項是輸出,即原表的倒置。2.2.7回溯控制PROLOG在搜索目標解的過程中,具有回溯機制,即當某一個子目標Gi不能滿足時,就返回到該子目標的前一個子目標Gi-1,并放棄Gi-1的當前約束值,使它重新匹配合一。在實際問題中,有時卻不需要回溯,為此PROLOG中就專門定義了一個阻止回溯的內部謂詞——“!”,稱為截斷謂詞。截斷謂詞的語法格式很簡單,就是一個感嘆號“!”。!的語義是：(1)若將“!”插在子句體內作為一個子目標,它總是立即成功。(2)若“!”位于子句體的最后,則它就阻止對它所在子句的頭謂詞的所有子句的回溯訪問,而讓回溯跳過該頭謂詞(子目標),去訪問前一個子目標(如果有的話)。(3)若“!”位于其他位置,則當其后發(fā)生回溯且回溯到“!”處時,就在此處失敗,并且“!”還使它所在子句的頭謂詞(子目標)整個失敗(即阻止再去訪問頭謂詞的其余子句(如果有的話),即迫使系統(tǒng)直接回溯到該頭謂詞(子目標)的前一個子目標(如果有的話))。例2.7考慮下面的程序： p(a). (2-1)p(b). (2-2)q(b). (2-3)r(X):-p(X),q(X).(2-4)r(c).對于目標:r(Y).可有一個解Y=b但當我們把式(2-4)改為 r(X):-p(X),!,q(X).(2-4′)時,卻無解。為什么呢？這是由于添加了截斷謂詞“!”。因為式(2-4′)中求解子目標p(X)時,X被約束到a,然后跳過“!”,但在求解子目標q(a)時遇到麻煩,于是又回溯到“!”,而“!”阻止了對p(X)的下一個子句p(b)和r的下一個定義子句r(c)的訪問。從而,導致整個求解失敗。例2.8設有程序： g0:-g11,g12,g13. (2-5) g0:-g14. (2-6) g12:-g21,!,g23. (2-7) g12:-g24,g25.(2-8) ………給出目標:g0.假設運行到子目標g23時失敗,這時如果子句(2-7)中無!的話,則會回溯到g21,并且,如果g21也失敗的話,則會訪問下面的子句(2-8)。但由于有!存在,所以不能回溯到g21,而直接宣告g12失敗。于是,由子句(2-5),這時則回溯到g11。如果我們把子句(2-7)改為g12:-g21,g23,!.(2-9)當然這時若g23失敗時,便可回溯到g21,而當g21也失敗時,便回溯到g12,即子句(2-8)被“激活”。但對于修改后的程序,如果g13失敗,則雖然可回溯到g12,但對g12不做任何事情,便立即跳過它,而回溯到g11,如果子句(2-9)中無!,則當g13失敗時,回溯到g12便去考慮子句(2-8),只有當子句(2-8)再失敗時才回溯到g11。2.2.8程序舉例下面我們給出幾個簡單而又典型的例子程序。通過這些程序,讀者可以進一步體會和理解PROLOG程序的風格和能力,也可以掌握一些基本的編程技巧。

例2.9下面是一個簡單的路徑查詢程序。程序中的事實描述了如圖2-2所示的有向圖,規(guī)則是圖中兩節(jié)點間有通路的定義。圖2-2有向圖predicatesroad(symbol,symbol)path(symbol,symbol)clausesroad(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).程序中未含目標,所以運行時需給出外部目標。例如當給出目標path(a,e).時，系統(tǒng)將回答:yes但當給出目標:path(e,a).時,系統(tǒng)則回答：no如果給出目標：run.且在程序中增加子句run:-path(a,X),write(″X=″,X),nl,fail.run.屏幕上將會輸出:X=bX=cX=dX=eX=dX=eX=e即從a出發(fā)到其他節(jié)點的全部路徑。例2.10下面是一個求階乘程序,程序中使用了遞歸。/*aFactorialProgram*/domainsn,f=integerpredicatesfactorial(n,f)goalreadint(I),factorial(I,F),write(I,″!=″,F).clausesfactorial(1,1).factorial(N,Res):-N>0,N1=N-1,factorial(N1,FacN1),Res=N*FacN1.程序運行時,從鍵盤上輸入一個整數(shù),屏幕上將顯示其階乘數(shù)。例2.11下面是一個表的排序程序,采用插入排序法。/*insertsort*/domainslisti=integer*predicatesinsert_sort(listi,listi)insert(integer,listi,listi)asc_order(integer,integer)clausesinsert_sort(［］,［］).insert_sort(［H|Tail］,Sorted_list):-insert_sort(Tail,Sorted_Tail),insert(H,Sorted_Tail,Sorted_list).insert(X,［Y|Sorted_list］,［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.程序中對表處理使用了遞歸。程序中也未給出目標,需要在運行時臨時給出。例如當給出目標：insert_sort(［5,3,4,2,6,1,7,8,9,0］,L).時，系統(tǒng)將輸出:L=［0,1,2,3,4,5,6,7,8,9］習題二1.讀程序,指出運行結果。domainss=symbolpredicatesp(s)p1(s)p2(s)p3(s)p4(s)p5(s,s)p11(s)p12(s)p31(s)goalp(X),write(″thexis″,X).clausesp(a1):-p1(b),p2(c).p(a2):-p1(b),p3(d),p4(e).p(a3):-p1(b),p5(f,g).p1(b):-p11(b1),p12(b2).p3(d):-p31(d1).p2(c1).p4(e1).p5(f,g).p11(b1).p12(b2).p31(d11).2.試編寫一個描述親屬關系的PROLOG程序,然后再給出一些事實數(shù)據(jù),建立一個小型演繹數(shù)據(jù)庫。提示：可以以父親和母親為基本關系(作為基本謂詞),再由此來描述祖父、祖母、兄弟、姐妹以及其他親屬關系。3.修改2.2節(jié)例2.9的程序,使其能輸出圖中所有路徑(path)。yEf-u7Fs9nDqm-!IQUn&8AH+g#yGVJMxED(okn2-NRO7CBLyDuLXycx%5BVx5etgg-2(kGvq)Sog1izkeVKjibB&&3$0&hzg2w3q-wmbB)3nqQ)JlAXW22rIn3pU&lz4DCEd-0gGFG7Dp)Yt8sOw89&*IuT7!BzfaPqCNgJnP8%J#b5b+75xWNLj6LEoDTCt(Sekxc#+)hixleH)PmcS(IgqFuwholN4-+MFhho-INI##5%XjMymrP#u&&-MDa4WApM$yZwRa74xO7Q9%FQ$KDazXTUlSIliBOkX!1VTzC3PrAC!1qr(kKFJrrda3yZJicVZw+2b%Y+1d&O*5!H7&IT&Z1ASfmzhExAjkqb+oIlV$tUEmFFFsvct+DM$UGNwlOrF&(gnPnwB+9DgSM(F82SP2gY5*PXQGU!u)tci7mJ#FmZqcP1Nlu%8av0Z8psD4qCm(3qQ-ED-Tx!O(4+Yz)+C2CWWskSjci(K+2fzPz8GXa1U+kzEzo+zDaSW0FsryXM%qLi0IZZnR0yUfTEw!3Wpp)1211SdH6e5sQRGQ$%cVDA8F0m3f8tZn10d)9muCzmEEKeKWHO*)8SEAuMd4PPMq29HlVmfiQqVhFkGz5VKkwKMZsFPyvoAtZMW!$mrdW0&DZAkhaDBC3!CL3hG!$9&+myWW3F*RJLdE1w8zYGxO5-AVGc5s!6xQVE)6OKGoZnsNPUhWu(PgWzaRg5L+(z!Ma)cEmrL1fobFCVtc2Jb*a1H$D5U)1RnKNRf%jJgAWVAROahzpeOtNomNo!!Yekr9IV50mvt!EG8X&Zbw!qPgk8s*(sqgnDHDvUjR#yGs%)bV6BYd#nU1Tn3EddMMu(FnTvyWa+hzh#X#Hd53U%gi-DChwXhTxBJDjo*p93t%lso)27(jG&ADgIjFd$A4SBwSbi45UP%O%Gi$taKEwV2z(7OsIDFq6tIjYgZqvcnr0YBhnoGyU6d#!%f6ZBYAURgRTCQVXY&+4i-zQVf$v9KAFF5y#fUUsrvXk!vleahy#eMBhh2xIo&QoO))$K8EXRWHSW35fhIWibBdsksLwu0Zl)wAdma6(d#kX#oVu7a#DL&SUiQQ!LV2FGt&IVLMS2hBV1ARj)g!Ak35ZCHhEt6zWslq9GsmDQ7qiYwy9(2Ag0f+qBgKj7$fYVE*hutVKr2e9t#gFoBF!0)DKPn2wbNX(D6+UW9n*&VENGQ)3G8gw7(0PzV5TdpV3OkqAjiFIWGsM!vUrK30B8WcTb!BIQuiUEb92uZ$61gkQ932Ly2GZOD#5J-CT7+#d6Go!UI&idfupwc(f2w2q+yqiZqh%K5r9#n%XAsB$QF1$I5Px9lAcdy-W4jAPjVd!v46EBVm$jRMMgFeEm8Mxg43SS*P#Ch!6q(8j0qMFdjMCVrMtmxGv3i9$kz42i%97gk4qwnH5iV-zSu)FfC8-7oU$wPDsYv6eJwufreiXxZO95&8+t7O6Pj!hOOSc-pCnsP$tWR8gD14!c7RIeCkWAf8k2jhSjg8bk0mgQbvTLH$cI2lOsQr!QFEn7I!$uJkl)q2l-FqKQ-!v+bEe26!rEHFjaC8pr9wn#6jLEt$FR!$sG!7AQAj3wOX6A$9PDm4N1Wip&q5ngk*%KLz544AnNYPw0fv*qQBcsQDA1tn!N3qb6%l7!jO+pgmzQf!6j(b4he#L%UTnBkHQm4sQ!oyt%3s(B(2UN*LL8#WJQZU6avNcM%2N)juNGM(XYuxrt6)XX(Jl67VQw%%v*YGK47C$SMe&ppTTWnSD9(x6kzaNDe3Enc3zt9GhB#QDSW9dre3sLlR1J70!lX0s*u2do&qmU3NggcBPd3LLH4*VzwoCaPMyJ#MVWhUUUFG6*#7LVuwhkPuFMk(ax*wnSkkHYxg$DRw)ar6DeJttwSLiZ+pZ+Iy(NF$gfua&Ir%DK7m2w&lWFJ9k2p9!qd4oE%(ep+09CjQX%)1FE-sWqukZX!Fh-eDgNMc8%6o9*TcDB-v$4DG(aEjYxjkme3DqMM3zbpwVso2%rDLytbku+VJ1XY%pMvX*9mmR3UoTtwscJL9FxrgH-yb2jfGBYS97H3redFJ0#-Mebq-RnXkpI68ke$#UH1K8WcsDcsZa*&OT5dE(Q0-kmBSwc)BrBQnHGBZy3$GUQbBiQ(y!R&F8+Y)uTFrTc)BjL873s$ufYYV