第7章逻辑程序设计语言范型Prolog语言控制抽象课件

1、14 十月 2022程序设计语言范型Programming Languages Paradigms教师： 张荣华 华北电力大学计算机系软件教研室（保定）11 十月 2022程序设计语言范型Programming 逻辑程序设计语言范型Prolog语言控制抽象第三部分第七章 逻辑程序设计语言范型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内容1.Prolog语言概述1.1 Prolog的基本元素1.2 Prolog实验环境2.合一2.1 项的合一 2.2 归结2.3 基于合一编程3.控制流Prolog语言控制抽象第七章 - 4内容1.Prolog语Prolog语言控制抽象第七章 - 51.Prolog语言概述Prolog（Programming in Logic）诞生于20世纪70年代初法国马赛大学作为自然语言理解项目的一部分研制成功目前，爱丁堡大学开发的Prolog版本使用最为广泛。迄今最能体现逻辑程

3、序设计思想的逻辑编程语言“说明式”的语言；采用一阶谓词演算说明（描述）问题知识库（事实和规则）的描述采用子句（Clause）形式控制流机制置换、合一归结回溯、深度优先搜索反向推理Prolog语言控制抽象第七章 - 51.Prolog语言概Prolog语言控制抽象第七章 - 6内容1.Prolog语言概述1.1 Prolog的基本元素1.2 Prolog实验环境2.合一2.1 项的合一 2.2 归结2.3 基于合一编程3.控制流Prolog语言控制抽象第七章 - 6内容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事实查询/目标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事实规则Prolog语言控制抽象第七章 - 81.1 Prolog的Prolog语言控制抽象第七章 - 91.1 Prolog的基本元素Prolog程序的语句（子句）包括：(1)事实（Facts）没有体部的horn子句，即被假定为真的命题。 (2)规则（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）构成常量原子（atom）：Prolog的符号值以小写字母开始的一串字母、数字、下划线或用单引号界定的一串任何可打印的ASCII字符。整数变量以大写字母开始一串字母、数字和下划线；下划线（_）表示匿名变量；注意与命令式语言中变量的区别。结构（谓词/复杂项） vertical(line(point(X,Y),point(

7、X,Z).Prolog语言控制抽象第七章 - 101.1 PrologProlog语言控制抽象第七章 - 111.1 Prolog的基本元素Prolog程序运行通过提问查询知识库使用分号（ ；）查询多个解（multiple answers）分号有特定的语义：表示结束当前合一，回溯查找其它可满足的解。Prolog语言控制抽象第七章 - 111.1 PrologProlog语言控制抽象第七章 - 12内容1.Prolog语言概述1.1 Prolog的基本元素1.2 Prolog实验环境2.合一2.1 项的合一 2.2 归结2.3 基于合一编程3.控制流Prolog语言控制抽象第七章 - 12内容1

8、.PrologProlog语言控制抽象第七章 - 131.2 Prolog实验环境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内容1.Prolog语言概述1.1 Prolog的基本元素1.2 Pr

9、olog实验环境2.合一2.1 项的合一 2.2 归结2.3 基于合一编程3.控制流Prolog语言控制抽象第七章 - 14内容1.PrologProlog语言控制抽象第七章 - 152.1 项的合一 合一如果Term1和Term2是常量，那么当且仅当Term1和 Term2是相同的原子或整数；如果Term1是变量， Term2是任何类型的项，那么 Term1实例化为Term2；注：如果Term2也是变量，互相实例化，共享值。如果Term1和Term2都是结构，两者合一，当且仅当（a）两者有相同的算符（谓词）；（b）两者对应的参数匹配，即能够递归地合一；（c）变量实例化必须保持一致性；当满足前

10、面三种情况时，两者项合一。Prolog语言控制抽象第七章 - 152.1 项的合一 合?- a=a. yes /常量与自己合一?- a=b.no /常量不能与其他常量合一?- foo(a,b)=foo(a,b).yes /结构递归合一?- X=a.X=a; /变量和常量合一no /仅此一次合一 ?- foo(a,b)=foo(X,b).X=a; /参数合一no /只有是一种可能Prolog中的相等是基于“合一”的定义内部共享变量?- A=B.A = _G206B = _G206;no ?- a=a. Prolog中的相等是基于“合一”的定义内部Prolog语言控制抽象第七章 - 172.1 项

11、的合一【思考】Prolog实现合一操作时是否使用标准的合一算法？ 老版本的Prolog实现:Notenoughmemorytocompletequery!现代版本的Prolog实现：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内容1.Prolog语言概述1.1 Prolog的基本元素1.2 Prolog实验环境2.合一2.1 项的合一 2.2 归结2.

13、3 基于合一编程3.控制流Prolog语言控制抽象第七章 - 18内容1.PrologProlog语言控制抽象第七章 - 192.2 归结Prolog中的推理来自Robison归结原理 ，在Prolog中，如果C1和C2都是子句，且C1的头部与C2的体中的一个项合一，那么就可以用C1的体取代C2里的那个项。例如：Prolog语言控制抽象第七章 - 192.2 归结ProlProlog语言控制抽象第七章 - 20内容1.Prolog语言概述1.1 Prolog的基本元素1.2 Prolog实验环境2.合一2.1 项的合一 2.2 归结2.3 基于合一编程3.控制流Prolog语言控制抽象第七章

14、- 20内容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内容1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 failProlog语言控制抽象第七章 - 30内容1.PrologProlog语言控制抽象第七章 - 313.1 Prolog控制流设计问题问题：（基于合一的编程实例） 采用哪种搜索策略搜索（搜索方向、搜索类型）目标？合一失败，如何控制程序继续进行求解问题？需要搜索更多的解（

17、使用分号；）时，如何控制程序继续进行求解问题？结论（控制流）：Prolog采用基于目标导向的深度优先搜索策略。回溯是Prolog内部最基本的自动的控制流机制。Prolog语言控制抽象第七章 - 313.1 PrologProlog语言控制抽象第七章 - 323.1 Prolog控制流设计问题目标导向的搜索有效地裁减了无关的搜索路径Prolog语言控制抽象第七章 - 323.1 PrologProlog语言控制抽象第七章 - 33内容1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 failP

18、rolog语言控制抽象第七章 - 33内容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内容1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 failProlog语言控制抽象第七章 - 43内容1.PrologProlog语言控制抽象第七章 - 443.3 递归从过程的观点看子目标：规则的

22、体部含有对其它谓词的调用，这些谓词称为规则的子目标，子目标可能是：事实；其它的规则；同一条规则（递归调用）递归子句基子句递归子句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内容1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 failProlog语言控制抽象第七章 - 48内容1.PrologProlog语言控制抽象第七章 - 493.4 Prolog程序的顺序性Prolog程序查询目标时按照特定的顺序自动执行：基于目标反向推理深度优先自上而下搜索知识库中的Horn子句；从左向右搜索规则体中的各个项；使用回溯机制尝试新的搜索；Prolog是否是纯逻辑式编程语言？Pr

24、olog语言控制抽象第七章 - 493.4 PrologProlog语言控制抽象第七章 - 503.4 Prolog程序的顺序性Prolog程序控制流（suggested by Lawrence Byrd）GOALException (error)CALLFAILEXITREDOProlog语言控制抽象第七章 - 503.4 PrologProlog语言控制抽象第七章 - 51内容1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 failProlog语言控制抽象第七章 - 51内容1.Pro

25、logProlog语言控制抽象第七章 - 523.5 cutProlog cut（截断/阻止回溯）机制使用内部无参谓词（！）；可以作为子目标放在规则子句的体内； 解释：程序调用cut总是成功；当某个子目标失败回溯时，不允许越过！回溯。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