1、14 十月 2022程序設(shè)計語言范型Programming Languages Paradigms教師： 張榮華 華北電力大學(xué)計算機系軟件教研室（保定）11 十月 2022程序設(shè)計語言范型Programming 邏輯程序設(shè)計語言范型Prolog語言控制抽象第三部分第七章 邏輯程序設(shè)計語言范型Prolog語言控制抽象第三部分Prolog語言控制抽象第七章 - 3參考文獻Learn Prolog Now! by Patrick Blackburn, Johan Bos, and Kristina Striegnitz http:/www.coli.uni-saarland.de/kris/lear

2、n-prolog-now/ Prolog語言控制抽象第七章 - 3參考文獻Learn PProlog語言控制抽象第七章 - 4內(nèi)容1.Prolog語言概述1.1 Prolog的基本元素1.2 Prolog實驗環(huán)境2.合一2.1 項的合一 2.2 歸結(jié)2.3 基于合一編程3.控制流Prolog語言控制抽象第七章 - 4內(nèi)容1.Prolog語Prolog語言控制抽象第七章 - 51.Prolog語言概述Prolog（Programming in Logic）誕生于20世紀70年代初法國馬賽大學(xué)作為自然語言理解項目的一部分研制成功目前，愛丁堡大學(xué)開發(fā)的Prolog版本使用最為廣泛。迄今最能體現(xiàn)邏輯程

3、序設(shè)計思想的邏輯編程語言“說明式”的語言；采用一階謂詞演算說明（描述）問題知識庫（事實和規(guī)則）的描述采用子句（Clause）形式控制流機制置換、合一歸結(jié)回溯、深度優(yōu)先搜索反向推理Prolog語言控制抽象第七章 - 51.Prolog語言概Prolog語言控制抽象第七章 - 6內(nèi)容1.Prolog語言概述1.1 Prolog的基本元素1.2 Prolog實驗環(huán)境2.合一2.1 項的合一 2.2 歸結(jié)2.3 基于合一編程3.控制流Prolog語言控制抽象第七章 - 6內(nèi)容1.Prolog語Prolog語言控制抽象第七章 - 71.1 Prolog的基本元素【例1】：水平線與垂直線問題。使用兩個謂詞

4、：vertical/2 和 horizontal/2 vertical(line(point(X,Y),point(X,Z).horizontal(line(point(X,Y),point(Z,Y). vertical(line(point(1,1),point(1,3).yes事實查詢/目標(biāo)horizontal(line(point(1,1),point(2,Y).Y=1;nohorizontal(line(point(2,3),P).P=point(_G434,3);noProlog語言控制抽象第七章 - 71.1 Prolog的Prolog語言控制抽象第七章 - 81.1 Prolog

5、的基本元素【例2】求解以下六個英語單詞的縱橫字謎問題。abalone, abandon, anagram, connect, elegant, enhance事實規(guī)則Prolog語言控制抽象第七章 - 81.1 Prolog的Prolog語言控制抽象第七章 - 91.1 Prolog的基本元素Prolog程序的語句（子句）包括：(1)事實（Facts）沒有體部的horn子句，即被假定為真的命題。 (2)規(guī)則（Rules）有頭和體的horn子句，只有體部的每個項都為真，頭部才為真。 father( john, jim).grandparent( Person1, Person2 ) :- par

6、ent( Person3, Person2 ), parent( Person1, Person3 ).HeadBodyProlog語言控制抽象第七章 - 91.1 Prolog的Prolog語言控制抽象第七章 - 101.1 Prolog的基本元素Prolog語句由項（term）構(gòu)成常量原子（atom）：Prolog的符號值以小寫字母開始的一串字母、數(shù)字、下劃線或用單引號界定的一串任何可打印的ASCII字符。整數(shù)變量以大寫字母開始一串字母、數(shù)字和下劃線；下劃線（_）表示匿名變量；注意與命令式語言中變量的區(qū)別。結(jié)構(gòu)（謂詞/復(fù)雜項） vertical(line(point(X,Y),point(

7、X,Z).Prolog語言控制抽象第七章 - 101.1 PrologProlog語言控制抽象第七章 - 111.1 Prolog的基本元素Prolog程序運行通過提問查詢知識庫使用分號（ ；）查詢多個解（multiple answers）分號有特定的語義：表示結(jié)束當(dāng)前合一，回溯查找其它可滿足的解。Prolog語言控制抽象第七章 - 111.1 PrologProlog語言控制抽象第七章 - 12內(nèi)容1.Prolog語言概述1.1 Prolog的基本元素1.2 Prolog實驗環(huán)境2.合一2.1 項的合一 2.2 歸結(jié)2.3 基于合一編程3.控制流Prolog語言控制抽象第七章 - 12內(nèi)容1

8、.PrologProlog語言控制抽象第七章 - 131.2 Prolog實驗環(huán)境SWI-Prolog（推薦使用!）/安裝文件（注意順序安裝）（1）SWI-Prolog for MS-Windows（version 5.10.1 ）（2）SWI-Prolog-Editorhttp:/lakk.bildung.hessen.de/netzwerk/faecher/informatik/swiprolog/indexe.html Prolog語言控制抽象第七章 - 131.2 PrologProlog語言控制抽象第七章 - 14內(nèi)容1.Prolog語言概述1.1 Prolog的基本元素1.2 Pr

9、olog實驗環(huán)境2.合一2.1 項的合一 2.2 歸結(jié)2.3 基于合一編程3.控制流Prolog語言控制抽象第七章 - 14內(nèi)容1.PrologProlog語言控制抽象第七章 - 152.1 項的合一 合一如果Term1和Term2是常量，那么當(dāng)且僅當(dāng)Term1和 Term2是相同的原子或整數(shù)；如果Term1是變量， Term2是任何類型的項，那么 Term1實例化為Term2；注：如果Term2也是變量，互相實例化，共享值。如果Term1和Term2都是結(jié)構(gòu)，兩者合一，當(dāng)且僅當(dāng)（a）兩者有相同的算符（謂詞）；（b）兩者對應(yīng)的參數(shù)匹配，即能夠遞歸地合一；（c）變量實例化必須保持一致性；當(dāng)滿足前

10、面三種情況時，兩者項合一。Prolog語言控制抽象第七章 - 152.1 項的合一 合?- a=a. yes /常量與自己合一?- a=b.no /常量不能與其他常量合一?- foo(a,b)=foo(a,b).yes /結(jié)構(gòu)遞歸合一?- X=a.X=a; /變量和常量合一no /僅此一次合一 ?- foo(a,b)=foo(X,b).X=a; /參數(shù)合一no /只有是一種可能Prolog中的相等是基于“合一”的定義內(nèi)部共享變量?- A=B.A = _G206B = _G206;no ?- a=a. Prolog中的相等是基于“合一”的定義內(nèi)部Prolog語言控制抽象第七章 - 172.1 項

11、的合一【思考】Prolog實現(xiàn)合一操作時是否使用標(biāo)準的合一算法？ 老版本的Prolog實現(xiàn):Notenoughmemorytocompletequery!現(xiàn)代版本的Prolog實現(xiàn)：X=father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(fath

12、er(father(father(father(father(father(father(father(father(father(father(father(father(father(fatherX=father(father(father(father(father(father(.)X = father(*) SICStus Prolog SWI Prolog Prolog語言控制抽象第七章 - 172.1 項的合一【思Prolog語言控制抽象第七章 - 18內(nèi)容1.Prolog語言概述1.1 Prolog的基本元素1.2 Prolog實驗環(huán)境2.合一2.1 項的合一 2.2 歸結(jié)2.

13、3 基于合一編程3.控制流Prolog語言控制抽象第七章 - 18內(nèi)容1.PrologProlog語言控制抽象第七章 - 192.2 歸結(jié)Prolog中的推理來自Robison歸結(jié)原理 ，在Prolog中，如果C1和C2都是子句，且C1的頭部與C2的體中的一個項合一，那么就可以用C1的體取代C2里的那個項。例如：Prolog語言控制抽象第七章 - 192.2 歸結(jié)ProlProlog語言控制抽象第七章 - 20內(nèi)容1.Prolog語言概述1.1 Prolog的基本元素1.2 Prolog實驗環(huán)境2.合一2.1 項的合一 2.2 歸結(jié)2.3 基于合一編程3.控制流Prolog語言控制抽象第七章

14、- 20內(nèi)容1.PrologProlog語言控制抽象第七章 - 212.3 基于合一編程【例1】Prolog語言控制抽象第七章 - 212.3 基于合一編程Prolog語言控制抽象第七章 - 222.3 基于合一編程【例1】Prolog語言控制抽象第七章 - 222.3 基于合一編程Prolog語言控制抽象第七章 - 232.3 基于合一編程【例2】匹配失敗Prolog語言控制抽象第七章 - 232.3 基于合一編程Prolog語言控制抽象第七章 - 242.3 基于合一編程【例2】Prolog語言控制抽象第七章 - 242.3 基于合一編程Prolog語言控制抽象第七章 - 25【例3】2.

15、3 基于合一編程Prolog語言控制抽象第七章 - 25【例3】2.3 基于Prolog語言控制抽象第七章 - 26【例3】2.3 基于合一編程DR NO/TitleProlog語言控制抽象第七章 - 26【例3】2.3 基于Prolog語言控制抽象第七章 - 27【例3】2.3 基于合一編程DR NO/Title匹配失敗Prolog語言控制抽象第七章 - 27【例3】2.3 基于Prolog語言控制抽象第七章 - 28【例3】2.3 基于合一編程DR NO/Title310/LengthProlog語言控制抽象第七章 - 28【例3】2.3 基于Prolog語言控制抽象第七章 - 29【例3

16、】2.3 基于合一編程DR NO/Title310/LengthProlog語言控制抽象第七章 - 29【例3】2.3 基于Prolog語言控制抽象第七章 - 30內(nèi)容1.Prolog語言概述2.合一3.控制流3.1 Prolog控制流設(shè)計問題3.2 回溯3.3 遞歸3.4 Prolog程序的順序性3.5 cut3.6 failProlog語言控制抽象第七章 - 30內(nèi)容1.PrologProlog語言控制抽象第七章 - 313.1 Prolog控制流設(shè)計問題問題：（基于合一的編程實例） 采用哪種搜索策略搜索（搜索方向、搜索類型）目標(biāo)？合一失敗，如何控制程序繼續(xù)進行求解問題？需要搜索更多的解（

17、使用分號；）時，如何控制程序繼續(xù)進行求解問題？結(jié)論（控制流）：Prolog采用基于目標(biāo)導(dǎo)向的深度優(yōu)先搜索策略。回溯是Prolog內(nèi)部最基本的自動的控制流機制。Prolog語言控制抽象第七章 - 313.1 PrologProlog語言控制抽象第七章 - 323.1 Prolog控制流設(shè)計問題目標(biāo)導(dǎo)向的搜索有效地裁減了無關(guān)的搜索路徑Prolog語言控制抽象第七章 - 323.1 PrologProlog語言控制抽象第七章 - 33內(nèi)容1.Prolog語言概述2.合一3.控制流3.1 Prolog控制流設(shè)計問題3.2 回溯3.3 遞歸3.4 Prolog程序的順序性3.5 cut3.6 failP

18、rolog語言控制抽象第七章 - 33內(nèi)容1.PrologProlog語言控制抽象第七章 - 343.2 回溯【例1】使用與/或樹解釋合一失敗后回溯搜索。C=X=_G206seattle/_G206失敗并回溯Prolog語言控制抽象第七章 - 343.2 回溯【例1】Prolog語言控制抽象第七章 - 353.2 回溯【例1】使用與/或樹解釋合一失敗后回溯搜索。C=X=_G206seattle/_G206rochester/_G206Prolog語言控制抽象第七章 - 353.2 回溯【例1】Prolog語言控制抽象第七章 - 363.2 回溯【例2】使用與/或樹解釋利用回溯搜索多個解。X=_

19、G206, Y=_G207a/X, c/Za/Y解1Prolog語言控制抽象第七章 - 363.2 回溯【例2】Prolog語言控制抽象第七章 - 373.2 回溯【例2】使用與/或樹解釋利用回溯搜索多個解。X=_G206, Y=_G207a/X, c/Za/Yb/Y解2解1Prolog語言控制抽象第七章 - 373.2 回溯【例2】Prolog語言控制抽象第七章 - 383.2 回溯【例2】使用與/或樹解釋利用回溯搜索多個解。X=_G206, Y=_G207a/X, c/Za/Yb/Y解2解1b/X, c/Za/Y解3Prolog語言控制抽象第七章 - 383.2 回溯【例2】Prolog語

20、言控制抽象第七章 - 393.2 回溯【例2】使用與/或樹解釋利用回溯搜索多個解。X=_G206, Y=_G207a/X, c/Za/Yb/Y解2解1b/X, c/Za/Y解3b/Y解4Prolog語言控制抽象第七章 - 393.2 回溯【例2】Prolog語言控制抽象第七章 - 403.2 回溯【例3】求解以下六個英語單詞的縱橫字謎問題。abalone, abandon, anagram, connect, elegant, enhanceProlog語言控制抽象第七章 - 403.2 回溯【例3】Prolog語言控制抽象第七章 - 413.2 回溯aabloneanagramocnnect

21、aadneeeathneaadnbonleeatngnehnecaaaoeaarmcnetProlog語言控制抽象第七章 - 413.2 回溯aablProlog語言控制抽象第七章 - 423.2 回溯Prolog語言控制抽象第七章 - 423.2 回溯Prolog語言控制抽象第七章 - 43內(nèi)容1.Prolog語言概述2.合一3.控制流3.1 Prolog控制流設(shè)計問題3.2 回溯3.3 遞歸3.4 Prolog程序的順序性3.5 cut3.6 failProlog語言控制抽象第七章 - 43內(nèi)容1.PrologProlog語言控制抽象第七章 - 443.3 遞歸從過程的觀點看子目標(biāo)：規(guī)則的

22、體部含有對其它謂詞的調(diào)用，這些謂詞稱為規(guī)則的子目標(biāo)，子目標(biāo)可能是：事實；其它的規(guī)則；同一條規(guī)則（遞歸調(diào)用）遞歸子句基子句遞歸子句Prolog語言控制抽象第七章 - 443.3 遞歸從過程的Prolog語言控制抽象第七章 - 453.3 遞歸e/X, b/ YProlog語言控制抽象第七章 - 453.3 遞歸e/X,Prolog語言控制抽象第七章 - 463.3 遞歸e/X, b/ Ye/X, b/Yd/Zd/ZProlog語言控制抽象第七章 - 463.3 遞歸e/X,Prolog語言控制抽象第七章 - 473.3 遞歸e/X, b/ Ye/X, b/Yd/Zd/Zd/X, b/Yc/ZPr

23、olog語言控制抽象第七章 - 473.3 遞歸e/X,Prolog語言控制抽象第七章 - 48內(nèi)容1.Prolog語言概述2.合一3.控制流3.1 Prolog控制流設(shè)計問題3.2 回溯3.3 遞歸3.4 Prolog程序的順序性3.5 cut3.6 failProlog語言控制抽象第七章 - 48內(nèi)容1.PrologProlog語言控制抽象第七章 - 493.4 Prolog程序的順序性Prolog程序查詢目標(biāo)時按照特定的順序自動執(zhí)行：基于目標(biāo)反向推理深度優(yōu)先自上而下搜索知識庫中的Horn子句；從左向右搜索規(guī)則體中的各個項；使用回溯機制嘗試新的搜索；Prolog是否是純邏輯式編程語言？Pr

24、olog語言控制抽象第七章 - 493.4 PrologProlog語言控制抽象第七章 - 503.4 Prolog程序的順序性Prolog程序控制流（suggested by Lawrence Byrd）GOALException (error)CALLFAILEXITREDOProlog語言控制抽象第七章 - 503.4 PrologProlog語言控制抽象第七章 - 51內(nèi)容1.Prolog語言概述2.合一3.控制流3.1 Prolog控制流設(shè)計問題3.2 回溯3.3 遞歸3.4 Prolog程序的順序性3.5 cut3.6 failProlog語言控制抽象第七章 - 51內(nèi)容1.Pro

25、logProlog語言控制抽象第七章 - 523.5 cutProlog cut（截斷/阻止回溯）機制使用內(nèi)部無參謂詞（！）；可以作為子目標(biāo)放在規(guī)則子句的體內(nèi)； 解釋：程序調(diào)用cut總是成功；當(dāng)某個子目標(biāo)失敗回溯時，不允許越過！回溯。a:- b, c, d, e, !, f, g, h, I, j. a:- b, c, d, e, !, f, g, h, I, j .a:- b, c, d, e, !, f, g, h, I, j .立即失敗SucceedFailRedoBacktrackProlog語言控制抽象第七章 - 523.5 cutProProlog語言控制抽象第七章 - 531/X1/X2/X3/X【例1】Prolog語言控制抽象第七章 - 531/X1/X2/X3Prolog語言控制抽象第七章 - 541/X1/X【例2】Prolog語言控制抽象第七章 - 541/X1/X【例2】Prolog語言控制抽象第七章 - 55【例3】1/X1/Y2/Y3/Y0/X, 0/YProlo