邏輯型程序設(shè)計語言PROLOG詳細教程

邏輯型程序設(shè)計語言PROLOG詳細教程邏輯型程序設(shè)計語言PROLOG詳細教程邏輯型程序設(shè)計語言PROLOG詳細教程xxx公司邏輯型程序設(shè)計語言PROLOG詳細教程文件編號：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計，管理制度邏輯型程序設(shè)計語言PROLOG教程2.3.1PROLOG的語句PROLOG語言只有三種語句，分別稱為事實、規(guī)則和問題。

1.事實(fact)格式:<謂詞名>(<項表>).功能一般表示對象的性質(zhì)或關(guān)系。其中謂詞名是以小寫英文字母打頭的字母、數(shù)字、下劃線等組成的字符串，項表是以逗號隔開的項序列。例如：student(john).like(mary,music).表示“約翰是學(xué)生”和“瑪麗喜歡音樂”。2.規(guī)則(rule)格式:<謂詞名>(<項表>):-<謂詞名>(<項表>){,<謂詞名>(<項表>)}.功能:一般表示對象間的因果關(guān)系、蘊含關(guān)系或?qū)?yīng)關(guān)系。其中“:-”號表示“if”（也可以直接寫為if），其左部的謂詞是規(guī)則的結(jié)論（亦稱為頭），右部的謂詞是規(guī)則的前提（亦稱為體），{}表示零次或多次重復(fù)，逗號表示and(邏輯與),即規(guī)則的形式是一個邏輯蘊含式。例如：bird(X):-animal(X),has(X,feather).grandfather(X,Y):-father(X,Z),father(Z,Y).第一條規(guī)則表示“如果X是動物，并且X有羽毛，則X是鳥”；第二條規(guī)則就表示“X是Y的祖父，如果存在Z，X是Z的父親并且Z又是Y的父親”。3.問題(question)格式:-<謂詞名>(<項表>){,<謂詞名>(<項表>)}.功能表示用戶的詢問，它就是程序運行的目標(biāo)。例如：-student(john).-like(mary,X).2.3.2PROLOGPROLOG程序一般由一組事實、規(guī)則和問題組成。問題是程序執(zhí)行的起點，稱為程序的目標(biāo)。例如下面就是一個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ī)則及事實排在一起，它作為程序的目標(biāo)要么單獨列出，要么在程序運行時臨時給出。這個程序的事實描述了一些對象（包括人和事物）間的關(guān)系；而規(guī)則則描述了john交朋友的條件，即如果一個人喜歡讀書并且喜歡音樂（或者喜歡運動和喜歡音樂），則這個人就是john的朋友（當(dāng)然，這個規(guī)則也可看作是john朋友的定義）；程序中的問題是“約翰的朋友是誰”當(dāng)然，PROLOG程序中的目標(biāo)可以變化，也可以含有多個語句(上例中只有一個)。如果有多個語句，則這些語句稱為子目標(biāo)。例如對上面的程序，其問題也可以是-likes(mary,X).或-likes(mary,music).或-friend(X,Y).或-likes(bell,sports),likes(mary,music),friend(john,X).等等。當(dāng)然，對于不同的問題，程序運行的結(jié)果一般是不一樣的。2.3.3PROLOG程序的運行機理PROLOG程序的運行是從目標(biāo)出發(fā)，并不斷進行匹配、合一、歸結(jié)，有時還要回溯，直到目標(biāo)被完全滿足或不能滿足時為止。1.自由變量與約束變量PROLOG中稱無值的變量為自由變量，有值的變量為約束變量。一個變量取了某值就說該變量約束于某值，或者說該變量被某值所約束，或者說該變量被某值實例化了。2.匹配合一兩個謂詞可匹配合一，是指兩個謂詞的名相同，參量項的個數(shù)相同，參量類型對應(yīng)相同，并且對應(yīng)參量項還滿足下列條件之一：(1)如果兩個都是常量，則必須完全相同。(2)如果兩個都是約束變量，則兩個約束值必須相同。(3)如果其中一個是常量，一個是約束變量，則約束值與常量必須相同。(4)至少有一個是自由變量。例如：下面的兩個謂詞pre1("ob1","ob2",Z)pre1("ob1",X,Y)只有當(dāng)變量X被約束為"ob2"，且Y、Z的約束值相同或者至少有一個是自由變量時，它們才是匹配合一的。3.回溯所謂回溯，就是在程序運行期間，當(dāng)某一個子目標(biāo)不能滿足（即謂詞匹配失?。r，控制就返回到前一個已經(jīng)滿足的子目標(biāo)（如果存在的話），并撤消其有關(guān)變量的約束值，然后再使其重新滿足。成功后，再繼續(xù)滿足原子目標(biāo)。如果失敗的子目標(biāo)前再無子目標(biāo)，則控制就返回到該子目標(biāo)的上一級目標(biāo)（即該子目標(biāo)謂詞所在規(guī)則的頭部）使它重新匹配。回溯也是PROLOG的一個重要機制。下面，我們介紹PROLOG程序的運行過程。我們?nèi)砸陨厦娴某绦驗槔?。設(shè)所給的詢問是-friend(john,Y).(john和誰是朋友)則求解目標(biāo)為friend(john,Y).這時，系統(tǒng)對程序進行掃描，尋找能與目標(biāo)謂詞匹配合一的事實或規(guī)則頭部。顯然，程序中前面的四條事實均不能與目標(biāo)匹配，而第五個語句的左端即規(guī)則friend(john,X):-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)?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)剛才的匹配語句處（即第五句）向下繼續(xù)掃描程序中的子句，試圖重新使原目標(biāo)匹配，結(jié)果發(fā)現(xiàn)第六條語句的左部，即規(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)便接著求解第二個子目標(biāo)。由于變量X已被約束，所以這時第二個子目標(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)測試到程序中第三個事實時，第一個子目標(biāo)便求解成功，且變量X被約束為mary。這樣，第二個子目標(biāo)也就變成了likes(mary,music).再對它進行求解。這次很快成功。由于兩個子目標(biāo)都求解成功，所以，原目標(biāo)friend(john,Y)也成功，且變量Y被約束為mary(由Y與X的合一關(guān)系)。于是，系統(tǒng)回答：Y=mary程序運行結(jié)束。上面只給出了問題的一個解。如果需要和可能的話，系統(tǒng)還可把john的所有朋友都找出來。我們把上述程序的運行過程再用示意圖（圖2─1）描述如下：圖2─1PROLOG程序運行機理示例上述程序的運行是一個通過推理實現(xiàn)的求值過程。我們也可以使它變?yōu)樽C明過程。例如，把上述程序中的詢問改為 friend(john,mary)則系統(tǒng)會回答:yes若將詢問改為： riend(john,smith)則系統(tǒng)會回答:no從上述程序的運行過程可以看出，PROLOG程序的執(zhí)行過程是一個（歸結(jié)）演繹推理過程。其特點是：推理方式為反向推理，控制策略是深度優(yōu)先，且有回溯機制。其具體實現(xiàn)方法是：匹配子句的順序是自上而下；子目標(biāo)選擇順序是從左向右；（歸結(jié)后）產(chǎn)生的新子目標(biāo)總是插入被消去的目標(biāo)處（即目標(biāo)隊列的左部）。PROLOG的這種歸結(jié)演繹方法被稱為SLD(LinearresolutionwithSelectionfunctionforDefiniteclause)歸結(jié)，或SLD反駁-消解法。SLD歸結(jié)就是PROLOG程序的運行機理，它也就是所謂的PROLOG語言的過程性語義。TurboPROLOG程序設(shè)計2.4.1TurboPROLOG的程序結(jié)構(gòu)一個完整的TurboPROLOG版)程序一般包括常量段、領(lǐng)域段、數(shù)據(jù)庫段、謂詞段、目標(biāo)段和子句段等六個部分。各段以其相應(yīng)的關(guān)鍵字constants、domains、database、predicates、goal和clauses開頭加以標(biāo)識。：另外，在程序的首部還可以設(shè)置指示編譯程序執(zhí)行特定任務(wù)的編譯指令；在程序的任何位置都可設(shè)置注解?？傊?，一個完整的TurboPROLOG版)程序的結(jié)構(gòu)如下/*<注釋>*/<編譯指令>constants<常量說明>domains<域說明>database<數(shù)據(jù)庫說明>predicates<謂詞說明>goal<目標(biāo)語句>clauses<子句集>當(dāng)然，一個程序不一定要包括上述所有段，但一個程序至少要有一個predicates段、clauses段和goal段。在大多數(shù)情形中，還需要一個domains段，以說明表、復(fù)合結(jié)構(gòu)及用戶自定義的域名。如若省略goal段，則可在程序運行時臨時給出，但這僅當(dāng)在開發(fā)環(huán)境中運行程序時方可給出。若要生成一個獨立的可執(zhí)行文件，則在程序中必須包含goal段。另一方面，一個程序也只能有一個goal段。例如果把上節(jié)中的程序要作為TurboPROLOG程序，則應(yīng)改寫為：/*例子程序-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).結(jié)合上例，我們再對上述程序結(jié)構(gòu)中的幾個主要段的內(nèi)容和作用加以說明(其余段在后面用到時再作說明)：領(lǐng)域段該段說明程序謂詞中所有參量項所屬的領(lǐng)域。領(lǐng)域的說明可能會出現(xiàn)多層說明，直到最終說明到TurboPROLOG的標(biāo)準(zhǔn)領(lǐng)域為止(如上例所示)。TurboPROLOG的標(biāo)準(zhǔn)領(lǐng)域即標(biāo)準(zhǔn)數(shù)據(jù)類型，包括整數(shù)、實數(shù)、符號、串和符號等，其具體說明如表所示。

表TurboPROLOG的標(biāo)準(zhǔn)領(lǐng)域謂詞段：該段說明程序中用到的謂詞的名和參量項的名(但TurboPROLOG的內(nèi)部謂詞無須說明)。子句段：該段是TurboPROLOG程序的核心，程序中的所有事實和規(guī)則就放在這里，系統(tǒng)在試圖滿足程序的目標(biāo)時就對它們進行操作。目標(biāo)段：該段是放置程序目標(biāo)的地方。目標(biāo)段可以只有一個目標(biāo)謂詞，例如上面的例子中就只有一個目標(biāo)謂詞；也可以含有多個目標(biāo)謂詞，如：goalreadint(X),Y=X+3,write("Y=",Y).就有三個目標(biāo)謂詞。這種目標(biāo)稱為復(fù)合目標(biāo)。另外，一般稱程序目標(biāo)段中的目標(biāo)為內(nèi)部目標(biāo)，而稱在程序運行時臨時給出的目標(biāo)為外部目標(biāo)。2.4.2TurboPROLOG的數(shù)據(jù)與表達式1.領(lǐng)域1)標(biāo)準(zhǔn)領(lǐng)域TurboPROLOG中不定義變量的類型，只說明謂詞中各個項的取值域。2)結(jié)構(gòu)結(jié)構(gòu)也稱復(fù)合對象，它是TurboPROLOG謂詞中的一種特殊的參量項（類似于謂詞邏輯中的函數(shù)）。結(jié)構(gòu)的一般形式為<函子>(<參量表>)其中函子及參量的標(biāo)識符與謂詞相同。注意，這意味著結(jié)構(gòu)中還可包含結(jié)構(gòu)。所以，復(fù)合對象可表達樹形數(shù)據(jù)結(jié)構(gòu)。例如下面的謂詞likes(Tom,sports(football,basketball,table-tennis)).中的sports(football,basketball,table-tennis)就是一個結(jié)構(gòu),即復(fù)合對象。又如：person("張華",student("西安石油學(xué)院"),address("中國","陜西","西安")).

reading("王宏",book("人工智能技術(shù)基礎(chǔ)教程","西安電子科技大學(xué)出版社")).

friend(father("Li"),father("Zhao")).這幾個謂詞中都有復(fù)合對象。復(fù)合對象在程序中的說明，需分層進行。例如，對于上面的謂詞likes(Tom,sports(football,basketball,table-tennis)).在程序中可說明如下：domains name=symbol sy=symbol sp=sports(sy,sy,sy)predicates likes(name,sp)3)表表的一般形式是［x1,x2,…,xn］其中xi(i=1,2,…,n)為PROLOG的項，一般要求同一個表的元素必須屬于同一領(lǐng)域。不含任何元素的表稱為空表，記為［］。例如下面就是一些合法的表。［1,2,3］［apple,orange,banana,grape,cane］［"PROLOG","MAENS","PROGRAMMING","inlogic"］［［a,b］,［c,d］,［e］］［］表的最大特點是其元素個數(shù)可在程序運行期間動態(tài)變化。表的元素也可以是結(jié)構(gòu)或表，且這時其元素可以屬于不同領(lǐng)域。例如：name("LiMing"),age(20),sex(male),address(xian)］［［1,2］,［3,4,5］,［6,7］］都是合法的表。后一個例子說明，表也可以嵌套。實際上，表是一種特殊的結(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］表的說明方法是在其組成元素的說明符后加一個星號*。如：domainslists=string*predicatespl(lists)就說明謂詞pl中的項lists是一個由串string組成的表。對于由結(jié)構(gòu)組成的表，至少得分三步說明。例如對于下面謂詞p中的表p(［name("Liming"),age(20)］)則需這樣說明:domainsrec=seg*seg=name(string);age(integer)predicatesp(rec)2.常量與變量由上面的領(lǐng)域可知，TurboPROLOG的常量有整數(shù)、實數(shù)、字符、串、符號、結(jié)構(gòu)、表和文件這八種數(shù)據(jù)類型。同理，TurboPROLOG的變量也就有這八種取值。另外，變量名要求必須是以大寫字母或下劃線開頭的字母、數(shù)字和下劃線序列，或者只有一個下劃線。這后一種變量稱為無名變量。3.算術(shù)表達式TurboPROLOG提供了五種最基本的算術(shù)運算：加、減、乘、除和取模，相應(yīng)運算符號為+、-、*、/、mod。這五種運算的順序為：*、/、mod優(yōu)先于+、-。同級從左到右按順序運算，括號優(yōu)先。算術(shù)表達式的形式與數(shù)學(xué)中的形式基本一樣。例如：數(shù)學(xué)中的算術(shù)表達式PROLOG中的算術(shù)表達式x+yzX+Y*Zab-c/dA*B-C/DumodvUmodV(表示求U除以V所得的余數(shù))即是說，TurboPROLOG中算術(shù)表達式采用通常數(shù)學(xué)中使用的中綴形式。這種算術(shù)表達式為PROLOG的一種異體結(jié)構(gòu)，若以PROLOG的結(jié)構(gòu)形式來表示，則它們應(yīng)為+(X,*(Y,Z))-(*(A,B),/(C,D))mod(U,V)所以，運算符+、-、*、/和mod實際也就是PROLOG內(nèi)部定義好了的函數(shù)符。在TurboPROLOG程序中，如果一個算術(shù)表達式中的變元全部被實例化（即被約束）的話，則這個算術(shù)表達式的值就會被求出。求出的值可用來實例化某變量，也可用來同其他數(shù)量進行比較，用一個算術(shù)表達式的值實例化一個變量的方法是用謂詞“is”或“=”來實現(xiàn)。例如：YisX+5或Y=X+5(*)就使變量Y實例化為X+5的值(當(dāng)然X也必須經(jīng)已被某值實例化)，可以看出，這里對變量Y的實例化方法類似于其他高級程序語言中的“賦值”，但又不同于賦值。例如，在PROLOG中下面的式子是錯誤的:X=X+14.關(guān)系表達式TurboPROLOG提供了六種常用的關(guān)系運算，即小于、小于或等于、等于、大于、大于或等于和不等于，其運算符依次為<,<=,=,>,>=,<>TurboPROLOG的關(guān)系表達式的形式和數(shù)學(xué)中的也基本一樣，例如： 數(shù)學(xué)中的關(guān)系式TurboPROLOG中的關(guān)系式X+1≥YX+1>=YX≠YX<>Y即是說，TurboPROLOG中的關(guān)系式也用中綴形式。當(dāng)然，這種關(guān)系式為TurboPROLOG中的異體原子。若按TurboPROLOG中的原子形式來表示，則上面的兩個例子為>=(X+1,Y)和<>(X,Y)所以上述六種關(guān)系運算符，實際上也就是TurboPROLOG內(nèi)部定義好了的六個謂詞。這六個關(guān)系運算符可用來比較兩個算術(shù)表達式的大小。例如：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.當(dāng)變量X、Y、Z全部被實例化時，“=”就是比較符。如：對于問題Goal:p(3,5,8).機器回答：yes。而對于Goal:p(3,5,7).機器回答：no。即這時機器把X+Y的值，與Z的值進行比較。(例二)但當(dāng)X,Y被實例化，為Z未被實例化時，“=”號就是約束符。如：Goal:p(3,5,Z).機器回答：Z=8這時，機器使Z實例化為X+Y的結(jié)果。2.4.3輸入與輸出雖然PROLOG能自動輸出目標(biāo)子句中的變量的值，但這種輸出功能必定有限，往往不能滿足實際需要；另一方面，對通常大多數(shù)的程序來說，運行時從鍵盤上輸入有關(guān)數(shù)據(jù)或信息也是必不可少的。為此每種具體PROLOG一般都提供專門的輸入和輸出謂詞，供用戶直接調(diào)用。例如，下面就是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)的值顯示在屏幕上或者打印在紙上，當(dāng)有某個Xi未實例化時，該謂詞失敗，其中的Xi可以是變量，也可以是字符串或數(shù)字。(6)nl換行謂詞。它使后面的輸出(如果有的話)另起一行。另外，利用write的輸出項"\n"也同樣可起換行作用。例如：write("name"),nl,write("age")與write("name","\n","age")的效果完全一樣。例用上面的輸入輸出謂詞編寫一個簡單的學(xué)生成績數(shù)據(jù)庫查詢程序。PREDICATESstudent(integer,string,real)gradeGOALgrade.CLAUSESstudent(1,"張三",.student(2,"李四",.student(3,"王五",.grade:-write("請輸入姓名:"),readln(Name),student(-,Name,Score),nl,write(Name,"的成績是",Score).grade:-write(“對不起，找不到這個學(xué)生!”).grade:-write("對不起，找不到這個學(xué)生!").下面是程序運行時的屏幕顯示:請輸入姓名：王五王五的成績是。2.4.4分支與循環(huán)PROLOG中并無專門的分支和循環(huán)語句，但PROLOG也可實現(xiàn)分支和循環(huán)程序結(jié)構(gòu)。1.分支對于通常的IF-THEN-ELSE分支結(jié)構(gòu)，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語句重復(fù)執(zhí)行了三次，而打印輸出了三個學(xué)生的記錄。student(1,"張三",.student(2,"李四",.student(3,"王五",.print:-student(Number,Name,Score),write(Number,Name,Score),nl,Number=3.這個例子可以看作是計數(shù)循環(huán)。當(dāng)然，也可以通過設(shè)置計數(shù)器而實現(xiàn)真正的計數(shù)循環(huán)。下面的程序段實現(xiàn)的則是不計數(shù)的DO循環(huán)。student(1,"張三",.student(2,"李四",.student(3,"王五",.print:-student(Number,Name,Score),write(Number,Name,Score),nl,fail.print:-.這個程序段中的fail是一個內(nèi)部謂詞，它的語義是恒失敗。這個程序段與上面的程序段的差別僅在于把原來用計數(shù)器（或標(biāo)記數(shù)）循環(huán)控制語句變成了恒失敗謂詞fail，另外再增加了一個print語句。增加這個語句的目的是為程序設(shè)置一個出口。因為fail是恒失敗，下面若無出口的話，將引起print本身的失敗。進而又會導(dǎo)致程序中的連鎖失敗。2.4.5動態(tài)數(shù)據(jù)庫動態(tài)數(shù)據(jù)庫就是在內(nèi)存中實現(xiàn)的動態(tài)數(shù)據(jù)結(jié)構(gòu)。它由事實組成，程序可以對它操作，所以在程序運行期間它可以動態(tài)變化。TurboPROLOG提供了三個動態(tài)數(shù)據(jù)庫操作謂詞:asserta(<fact>).assertz(<fact>).retract(<fact>).其中fact表示事實。這三個謂詞的功能是：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,"李明",).將在內(nèi)存的謂詞名為student的事實前插入一個新事實： student(20,"李明",如果內(nèi)存中還沒有這樣的事實，則它就是第一個。又如語句 retract(student(20,-,-)).將從內(nèi)存的動態(tài)數(shù)據(jù)庫中的刪除事實 student(20,-,-)它可解釋為學(xué)號為20的一個學(xué)生的記錄。注意，這里用了無名變量-?？梢钥闯?，PROLOG提供的動態(tài)數(shù)據(jù)庫機制，可非常方便地實現(xiàn)堆棧、隊列等動態(tài)數(shù)據(jù)結(jié)構(gòu)，提供的數(shù)據(jù)庫操作謂詞大大簡化了編程。另外，PROLOG還提供了謂詞save(<filename>).consult(<filename>).前者可將當(dāng)前的動態(tài)數(shù)據(jù)庫存入磁盤文件，后者則可將磁盤上的一個事實數(shù)據(jù)文件調(diào)入內(nèi)存。2.4.6表處理與遞歸表是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“［］［］無定義無定義在程序中是用豎線“|”來區(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］另外，豎杠的前面和后面也可以是常量，例如［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］。例設(shè)計一個能判斷對象X是表L的成員的程序。我們可以這樣設(shè)想：(1)如果X與表L中的第一個元素（即表頭）是同一個對象，則X就是L的成員;(2)如果X是L的尾部的成員，則X也就是L的成員。根據(jù)這種邏輯關(guān)系，于是有下面的PROLOG程序：member(X,［X|Tail］).member(X,［Head|Tail］):-member(X,Tail).其中第一個子句的語義就是上面的第一句話，第二個子句的語義就是上面的第二句話?？梢钥闯?，這個程序中使用了遞歸技術(shù)，因為謂詞member的定義中又含有它自身。利用這個程序我們就可以判定任意給定的一個對象和一個表之間是否具有member（成員）關(guān)系。例如，我們?nèi)”鞮為［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的其他所有值。例表的拼接程序，即把兩個表連接成一個表。

append(［］,L,L).append(［H|T］,L2,［H|Tn］):-append(T,L2,Tn).程序中第一個子句的意思是空表同任一表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).則系統(tǒng)便三次遞歸調(diào)用程序中的第二個子句，最后從第一個子句終止，然后反向依次求出每次的拼接表，最后輸出L=［1,2,3,4,5］當(dāng)然，對于這個程序也可以給出其他各種詢問，如：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］…等等（如果需要所有解的話）。例表的輸出。print(［］).print(［H|T］):-write(H),print(T).例表的倒置，即求一個表的逆序表。reverse(［］,［］).reverse(［H|T］,L):-reverse(T,L1),append(L1,［H］,L).這里，reverse的第一個項是輸入，即原表，第二個項是輸出，即原表的倒置。2.4.7回溯控制PROLOG在搜索目標(biāo)解的過程中，具有回溯機制，即當(dāng)某一個子目標(biāo)Gi不能滿足時，就返回到該子目標(biāo)的前一個子目標(biāo)Gi-1，并放棄Gi-1的當(dāng)前約束值，使它重新匹配合一。在實際問題中，有時卻不需要回溯，為此PROLOG中就專門定義了一個阻止回溯的內(nèi)部謂詞——“!”，稱為截斷謂詞。截斷謂詞的語法格式很簡單，就是一個感嘆號“!”。!的語義是：(1)若將“!”插在子句體內(nèi)作為一個子目標(biāo)，它總是立即成功；(2)若“!”位于子句體的最后，則它就阻止對它所在子句的頭謂詞的所有子句的回溯訪問，而讓回溯跳過該頭謂詞(子目標(biāo))，去訪問前一個子目標(biāo)（如果有的話）；(3)若“!”位于其他位置，則當(dāng)其后發(fā)生回溯且回溯到“!”處時，就在此處失敗，并且“!”還使它所在子句的頭謂詞（子目標(biāo)）整個失?。醋柚乖偃ピL問頭謂詞的其余子句（如果有的話），即迫使系統(tǒng)直接回溯到該頭謂詞(子目標(biāo))的前一個子目標(biāo)(如果有的話)）。例考慮下面的程序：p(a).(2─1)p(b).(2─2)q(b).(2─3)r(X):-p(X),q(X).(2─4)r(c).對于目標(biāo):r(Y).可有一個解Y=b但當(dāng)我們把式(2─4)改為r(X):-p(X),!,q(X).(2─4′)時，卻無解。這是由于添加了截斷謂詞“!”。因為式(2─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.(2─5)g0:-g14.(2─6)g12:-g21,!,g23.(2─7)g12:-g24,g25.(2─8).........給出目標(biāo):g0.假設(shè)運行到子目標(biāo)g23時失敗，這時如果子句(2─7)中無!的話，則會回溯到g21，并且，如果g21也失敗的話，則會訪問下面的子句(2─8)。但由于有!存在，所以不能回溯到g21，而直接宣告g12失敗。于是，由子句(2─5)，這時則回溯到g11。如果我們把子句(2─7)改為 g12:-g21,g23,!.(2─9)當(dāng)然這時若g23失敗時，便可回溯到g21，而當(dāng)g21也失敗時，便回溯到g12，即子句(2─8)被“激活”。但對于修改后的程序，如果g13失敗，則雖然可回溯到g12，但對g12不做任何事情，便立即跳過它，而回溯到g11，如果子句(2─9)中無!，則當(dāng)g13失敗時，回溯到g12便去考慮子句(2─8)，只有當(dāng)子句(2─8)再失敗時才回溯到g11。2.4.8程序舉例下面我們給出幾個簡單而又典型的例子程序。通過這些程序，讀者可以進一步體會和理解PROLOG程序的風(fēng)格和能力，也可以掌握一些基本的編程技巧。例下面是一個簡單的路徑查詢程序。程序中的事實描述了如圖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).程序中未含目標(biāo)，所以運行時需給出外部目標(biāo)。例如當(dāng)給目標(biāo)：path(a,e).系統(tǒng)將回答:yes但當(dāng)給目標(biāo):path(e,a).時，系統(tǒng)則回答：no如果給出目標(biāo)：run.且在程序中增加子句run:-path(a,X),write("X=",X),nl,fail.run.屏幕上將會輸出:X=bX=cX=dX=eX=dX=eX=e即從a出發(fā)到其他節(jié)點的全部路徑。例下面是一個求階乘程序，程序中使用了遞歸。/*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ù)。例下面是一個表的排序程序，采用插入排序法。/*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.程序中對表處理使用了遞歸。程序中也未給出目標(biāo)，需要在運行時臨時給出。例如當(dāng)給目標(biāo)：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］例下面是一個簡單的通信錄管理程序，其中用到輸入輸出、動態(tài)數(shù)據(jù)庫等。通過閱讀這個程序，我們還可以掌握循環(huán)結(jié)構(gòu)和簡單的菜單程序編寫方法。/*通信錄*/databaseperson(string,integer)predicatesaddress-bookchose(integer)inputqueryrepeatgoaladdress-book.clausesaddress-book:-repeat,clearwindow,write("=============="),nl,write("1--錄入"),nl,write("2--查詢"),nl,write("3--退出"),nl,write("=============="),nl,write("請選擇:-"),readint(N),chose(N).chose(1):-input,fail.chose(2):-query,fail.chose(3):-clearwindow,!.input:-clearwindow,write("姓名:"),readln(Name),write("電話:"),readint(Tel),assertz(person(Name,Tel)),!.query:-clearwindow,write("姓名:"),readln(Name),person(Name,Tel),write("電話:",Tel),readchar(-),!.repeat.repeat:-repeat.程序中的repeat恒成功。它與內(nèi)部謂詞fail配合實現(xiàn)了循環(huán)。需說明的是，這僅是一個演示性程序，還不能實用。因為這里的通信錄并未存入磁盤文件。用謂詞save就可方便地把通信錄存入磁盤文件。例如用語句save("")就可把已插入內(nèi)存的person事實存入文件中。而語句consult("")則可又將該文件中的事實裝入內(nèi)存。函數(shù)型程序設(shè)計語言LISPLISP語言的主要特點是：(1)LISP程序由一組函數(shù)組成，程序的執(zhí)行過程是函數(shù)的調(diào)用過程。(2)程序和數(shù)據(jù)在形式上是相同的，即都是符號表達式，簡稱為S─表達式。(3)遞歸是LISP語言的主要控制結(jié)構(gòu)。(4)程序以交互方式運行。2.2.1LISP的程序結(jié)構(gòu)與運行機制LISP的程序一般由函數(shù)的定義和函數(shù)的調(diào)用兩部分組成。其一般格式為：(DEFUN(<函數(shù)名>(<形參表>)<函數(shù)體>)(<函數(shù)名>(〖WB〗<形參表>)<函數(shù)體>)

…(<函數(shù)名>(<形參表>)<函數(shù)體>))

(<函數(shù)名><實參表>)(<函數(shù)名><實參表>)…(<函數(shù)名><實參表>)其中的“DEFUN”是定義函數(shù)的關(guān)鍵字，“函數(shù)名”可以是系統(tǒng)的內(nèi)部函數(shù)(名)，也可以是用戶用DEFUN定義的函數(shù)(名)。例如下面就是一個LISP程序。(DEFUNHANOI(abcn)(COND((=n1)(MOVE-DISKac))(T(HANOI(MOVE-DISKac)(HANOIbac(-n1))))(DEFUNMOVE-DISK(fromto)(TERPRI)(PRINC″MoveDiskFrom″)(PRINCfrom)(PRINC"To")(PRINCto))

(HANOI′a′b′c3)2.2.2S─表達式從語法上看，LISP程序的基本單位是S─表達式。S─表達式又可分為原子和表兩大類。原子(atom)是由字母和數(shù)字組成的字符串，是S─表達式的最簡單情況。原子又可分為文字原子、串原子和數(shù)字原子三種。文字原子又稱符號（symbol），是以字母開頭的字母數(shù)字串，用來表示常量、變量和函數(shù)的名字等。例如：ABC、X1等。

串原子是由雙引號括起來的一串字符。如"LISPProgram"。數(shù)字原子由數(shù)字串組成。在其前面可以有符號“-”或“+”，中間可出現(xiàn)“.”，用來表示整數(shù)和實數(shù)。例如：256、-66、等。S─表達式可以遞歸定義如下：(1)原子是S─表達式。(2)若S1和S2是S─表達式，則(S1·S2)也是S─表達式。由定義，下面的式子都是S─表達式：X2123(A·B)(A·(B·C))表(list)是LISP語言中最常用的數(shù)據(jù)類型，也是主要的處理對象。表是由圓括號括起來的由空格分開的若干個元素的集合。表的一般形式為：(<S─表達式><S─表達式>…<S─表達式>)例如：(XYZ),(+12),(A(BC))左括號后面的第一個元素稱為表頭，其余的元素組成的表稱為表尾。例如，對于表(+12)的頭為+，尾為(12)。特別地，元素個數(shù)為零的表為空表，記為()或NIL。表是一種特殊的S─表達式，每一個表都對應(yīng)著一個S─表達式。二者的關(guān)系由下面的例子說明。表←——————————————→S-表達式(A)(A·NIL)(AB)(A·(B·NIL))(ABC)(A·(B·(C·NIL)))((AB)CD)((A·(B·NIL))·(C·(D·NIL)))可以看出，表的S─表達式的結(jié)構(gòu)實際是一棵二叉樹。2.2.3基本函數(shù)LISP的函數(shù)都以表的形式出現(xiàn)，并一律使用前綴表示方式，即表頭為函數(shù)名，并且每個函數(shù)都有一個返回值。LISP的函數(shù)可分為語言自身提供的內(nèi)部函數(shù)(稱為基本函數(shù)或系統(tǒng)函數(shù))和用戶自定義函數(shù)兩類?；竞瘮?shù)的種類有十多個，下面僅給出其中主要的幾類。

1.表處理函數(shù)表處理是LISP的主要特色，表處理的函數(shù)也很多，下面僅給出最常用的幾個。1)CAR函數(shù)格式(CAR<表>)其中CAR為函數(shù)名，它是一個保留字（下同）。功能取出表中的表頭。例如：(CAR′(LISPLanguageProgram))返回值為：LISP

2)CDR函數(shù)格式(CDR<表>)功能取出表中的表尾。例如：(CDR′(LISPLanguageProgram))返回值為：(LanguageProgram)3)CONS函數(shù)格式(CONS<S─表達式><表>)功能將S─表達式作為一個元素加到表中去，并作為所構(gòu)成新表中的第一個元素。例如：(CONS′My′(LISPLanguageProgram))返回值為：(MyLISPLanguageProgram)4)APPEND函數(shù)格式(APPEND<表1><表2>…<表n>)功能將n個表中的元素合并成一個新表。例如：(APPEND′(TIGERLION)′(DOGCAT))返回值為：(TIGERLIONDOGCAT)5)LIST函數(shù)格式(LIST<S─表達式1><S─表達式2>…<S表達式n>)功能把n個S─表達式作為元素括在一起構(gòu)成一張新表。例如：(LIST′YELLOW′RED′BLUE)返回值為：(YELLOWREDBLUE)2.算術(shù)函數(shù)LISP的算術(shù)表達式也是用函數(shù)表示的，稱為算術(shù)函數(shù)。下面我們僅舉例說明。(+25)表示2+5，返回值為7。(-(*48)(/105))表示4×8-10/5，返回值為30。3.求值與賦值函數(shù)在上面的函數(shù)中多次出現(xiàn)撇號′，它的意思是禁止求值。為什么要禁止求值呢原來，LISP總是試圖對一切S─表達式求值。表的值是通過函數(shù)運算而得到的，原子的值則是通過賦值函數(shù)實現(xiàn)的。撇號′也是一個函數(shù)，它實際是禁止求值函數(shù)QUOTE的簡寫形式。

賦值函數(shù)有多個，其中SET函數(shù)是一個最基本的賦值函數(shù)。格式(SET<變量><S─表達式>)功能把S─表達式賦給變量。例如：(SET′X′8);X得到值8(SET′Y′(abc));Y得到值(abc)(SET′Z(CDRY);Z得到值(bc)另外，賦值函數(shù)還有SETQ、SETF(COMMONLISP)，其功能是類似的。4.謂詞函數(shù)返回值為邏輯值真或假的函數(shù)稱為謂詞函數(shù)，簡稱謂詞。LISP中真和假分別用T和NIL表示，當(dāng)函數(shù)的返回值為非NIL時，也表示為真。另外，NIL也表示空表。謂詞函數(shù)也有多個，下面我們僅給出常用的幾個。(1)原子謂詞ATOM格式(ATOM<參數(shù)>)功能檢測其參數(shù)是否為原子，是則返回T，否則返回NIL。例如：(ATOM′a);返回T(ATOM′(ab));返回NIL

(2)相等