1、2022年11月14日星期一教师：教师：张荣华张荣华 华北电力大学计算机系软件教研室（保定）华北电力大学计算机系软件教研室（保定）逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第三部分第三部分第七章第七章 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-3参考文献参考文献nLearn Prolog Now!by Patrick Blackburn,Johan Bos,and Kristina Striegnitz nhttp:/www.coli.uni-saarland.de/kris/learn-prolog-now/逻辑程序
2、设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-4内容内容n1.Prolog语言概述n1.1 Prolog的基本元素n1.2 Prolog实验环境n2.合一n2.1 项的合一 n2.2 归结n2.3 基于合一编程n3.控制流 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-51.Prolog1.Prolog语言概述语言概述nProlog（ProProgramming in LogLogic）n诞生于20世纪70年代初n法国马赛大学作为自然语言理解项目的一部分研制成功n目前，爱丁堡大学开发的Prolog版本使用最为广泛。n迄今最能体
3、现逻辑程序设计思想的逻辑编程语言n“说明式”的语言；n采用一阶谓词演算说明（描述）问题n知识库（事实和规则）的描述采用子句（Clause）形式n控制流机制n置换、合一n归结n回溯、深度优先搜索n反向推理 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-6内容内容n1.Prolog语言概述n1.1 Prolog的基本元素n1.2 Prolog实验环境n2.合一n2.1 项的合一 n2.2 归结n2.3 基于合一编程n3.控制流 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-71.1 Prolog1.1 Prolog的基本元
4、素的基本元素n【例1】：水平线与垂直线问题。n使用两个谓词：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);no 逻辑程序设计语言范型逻辑程序设计语言范型Prol
5、og语言控制抽象语言控制抽象第七章-81.1 Prolog1.1 Prolog的基本元素的基本元素n【例2】求解以下六个英语单词的纵横字谜问题。nabalone,abandon,anagram,connect,elegant,enhance事实事实规则规则 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-91.1 Prolog1.1 Prolog的基本元素的基本元素nProlog程序的语句（子句子句）包括：n(1)事实（FactsFacts）n没有体部的horn子句，即被假定为真的命题。n n(2)规则（RulesRules）n有头和体的horn子句，只有体
6、部的每个项都为真，头部才为真。n father(john,jim).grandparent(Person1,Person2):-parent(Person3,Person2),parent(Person1,Person3).HeadBody 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-101.1 Prolog1.1 Prolog的基本元素的基本元素nProlog语句由项（term）构成n常量n原子（atom）：Prolog的符号值n以小写字母开始的一串字母、数字、下划线或用单引号界定的一串任何可打印的ASCII字符。n整数n变量n以大写字母开始一串字母、
7、数字和下划线；n下划线（_）表示匿名变量；n注意与命令式语言中变量的区别。n结构（谓词/复杂项）n vertical(line(point(X,Y),point(X,Z).逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-111.1 Prolog1.1 Prolog的基本元素的基本元素nProlog程序运行n通过提问查询知识库n使用分号（；）查询多个解（multiple answers）n分号有特定的语义：表示结束当前合一，回溯查找其它可满足的解。逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-12内容内容n1.Prolog
8、语言概述n1.1 Prolog的基本元素n1.2 Prolog实验环境n2.合一n2.1 项的合一 n2.2 归结n2.3 基于合一编程n3.控制流 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-131.2 Prolog1.2 Prolog实验环境实验环境nSWI-Prolog（推荐使用!）nhttp:/www.swi-prolog.org/n安装文件（注意顺序安装）n（1）SWI-Prolog for MS-Windows（version 5.10.15.10.1）n（2）SWI-Prolog-Editornhttp:/lakk.bildung.hess
9、en.de/netzwerk/faecher/informatik/swiprolog/indexe.html 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-14内容内容n1.Prolog语言概述n1.1 Prolog的基本元素n1.2 Prolog实验环境n2.合一n2.1 项的合一 n2.2 归结n2.3 基于合一编程n3.控制流 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-152.1 2.1 项的合一项的合一 n合一n如果Term1和Term2是常量，那么当且仅当Term1和 Term2是相同的原子或整数；n如
10、果Term1是变量，Term2是任何类型的项，那么 Term1实例化为Term2；n注：如果Term2也是变量，互相实例化，共享值。n如果Term1和Term2都是结构，两者合一，当且仅当n（a）两者有相同的算符（谓词）；n（b）两者对应的参数匹配，即能够递归地合一；n（c）变量实例化必须保持一致性；n当满足前面三种情况时，两者项合一。n?-a=a.yes /常量与自己合一n?-a=b.no /常量不能与其他常量合一n?-foo(a,b)=foo(a,b).yes /结构递归合一n?-X=a.X=a;/变量和常量合一no /仅此一次合一 n?-foo(a,b)=foo(X,b).X=a;/参数
11、合一no /只有是一种可能nProlog中的相等是基于“合一”的定义内部共享变量内部共享变量n?-A=B.A=_G206B=_G206;no 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-172.1 2.1 项的合一项的合一n【思考】nProlog实现合一操作时是否使用标准的合一算法？n n老版本的Prolog实现:nNot enough memory to complete query!n现代版本的Prolog实现：X=father(father(father(father(father(father(father(father(father(fathe
12、r(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(father(father(father(father(fatherX=father(father(father(father(father(father(.)X=father(*)SICS
13、tus Prolog SWI Prolog 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-18内容内容n1.Prolog语言概述n1.1 Prolog的基本元素n1.2 Prolog实验环境n2.合一n2.1 项的合一 n2.2 归结n2.3 基于合一编程n3.控制流 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-192.2 2.2 归结归结nProlog中的推理来自Robison归结原理n ，n在Prolog中，如果C1和C2都是子句，且C1的头部与C2的体中的一个项合一，那么就可以用C1的体取代C2里的那个项。n例
14、如：21EE 32EE 31EE).Z,Y(takes),Z,X(takes:)Y,X(classmates).254cs,mike(takes).302art,mike(takes).254cs,tom(takes).201his,tom(takescs254Z,tomX实例化为实例化为假设).254,(:),(csYtakesYtomclassmates 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-20内容内容n1.Prolog语言概述n1.1 Prolog的基本元素n1.2 Prolog实验环境n2.合一n2.1 项的合一 n2.2 归结n2.3
15、基于合一编程n3.控制流 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-212.3 2.3 基于合一编程基于合一编程n【例1】逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-222.3 2.3 基于合一编程基于合一编程n【例1】逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-232.3 2.3 基于合一编程基于合一编程n【例2】匹配失败匹配失败 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-242.3 2.3 基于合一编程基于合一编程n【例2】逻辑
16、程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-25n【例3】2.3 2.3 基于合一编程基于合一编程 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-26n【例3】2.3 2.3 基于合一编程基于合一编程DRNO/Title 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-27n【例3】2.3 2.3 基于合一编程基于合一编程DRNO/Title匹配失败匹配失败 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-28n【例3】2.3 2.3 基于合一编程基
17、于合一编程DRNO/Title310/Length 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-29n【例3】2.3 2.3 基于合一编程基于合一编程DRNO/Title310/Length 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-30内容内容n1.Prolog语言概述n2.合一n3.控制流n3.1 Prolog控制流设计问题n3.2 回溯n3.3 递归n3.4 Prolog程序的顺序性n3.5 cutn3.6 fail 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-313
18、.1 Prolog3.1 Prolog控制流设计问题控制流设计问题n问题：（基于合一的编程实例）n采用哪种搜索策略搜索（搜索方向、搜索类型）目标？n合一失败，如何控制程序继续进行求解问题？n需要搜索更多的解（使用分号；）时，如何控制程序继续进行求解问题？n结论（控制流）：nProlog采用基于目标导向的深度优先搜索策略。n回溯是Prolog内部最基本的自动的控制流机制。逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-323.1 Prolog3.1 Prolog控制流设计问题控制流设计问题目标导向的搜索有效地裁减了无关的搜索路径目标导向的搜索有效地裁减了无关的
19、搜索路径 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-33内容内容n1.Prolog语言概述n2.合一n3.控制流n3.1 Prolog控制流设计问题n3.2 回溯n3.3 递归n3.4 Prolog程序的顺序性n3.5 cutn3.6 fail 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-343.2 3.2 回溯回溯n【例1】使用与/或树解释合一失败后回溯搜索。).(),(:)().().().(XcoldXrainyXsnowyrochestercoldrochesterrainyseattlerainyC=X
20、=_G206seattle/_G206失败并回溯失败并回溯 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-353.2 3.2 回溯回溯n【例1】使用与/或树解释合一失败后回溯搜索。).(),(:)().().().(XcoldXrainyXsnowyrochestercoldrochesterrainyseattlerainyC=X=_G206seattle/_G206rochester/_G206 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-363.2 3.2 回溯回溯n【例2】使用与/或树解释利用回溯搜索多个解。
21、X=_G206,Y=_G207a/X,c/Za/Y解解1 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-373.2 3.2 回溯回溯n【例2】使用与/或树解释利用回溯搜索多个解。X=_G206,Y=_G207a/X,c/Za/Yb/Y解解2解解1 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-383.2 3.2 回溯回溯n【例2】使用与/或树解释利用回溯搜索多个解。X=_G206,Y=_G207a/X,c/Za/Yb/Y解解2解解1b/X,c/Za/Y解解3 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制
22、抽象语言控制抽象第七章-393.2 3.2 回溯回溯n【例2】使用与/或树解释利用回溯搜索多个解。X=_G206,Y=_G207a/X,c/Za/Yb/Y解解2解解1b/X,c/Za/Y解解3b/Y解解4 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-403.2 3.2 回溯回溯n【例3】求解以下六个英语单词的纵横字谜问题。nabalone,abandon,anagram,connect,elegant,enhance 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-413.2 3.2 回溯回溯aabloneanagra
23、mocnnectaadneeeathneaadnbonleeatngnehnecaaaoeaarmcnet 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-423.2 3.2 回溯回溯 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-43内容内容n1.Prolog语言概述n2.合一n3.控制流n3.1 Prolog控制流设计问题n3.2 回溯n3.3 递归n3.4 Prolog程序的顺序性n3.5 cutn3.6 fail 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-443.3 3.
24、3 递归递归n从过程的观点看子目标：n规则的体部含有对其它谓词的调用，这些谓词称为规则的子目标，子目标可能是：n事实；n其它的规则；n同一条规则（递归调用）递归子句基子句基子句递归子句递归子句 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-453.3 3.3 递归递归e/X,b/Y 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-463.3 3.3 递归递归e/X,b/Ye/X,b/Yd/Zd/Z 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-473.3 3.3 递归递归e/X,b/
25、Ye/X,b/Yd/Zd/Zd/X,b/Yc/Z 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-48内容内容n1.Prolog语言概述n2.合一n3.控制流n3.1 Prolog控制流设计问题n3.2 回溯n3.3 递归n3.4 Prolog程序的顺序性n3.5 cutn3.6 fail 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-493.4 Prolog3.4 Prolog程序的顺序性程序的顺序性nProlog程序查询目标时按照特定的顺序自动执行：n基于目标反向推理n深度优先n自上而下搜索知识库中的Horn子句；n
26、从左向右搜索规则体中的各个项；n使用回溯机制尝试新的搜索；nProlog是否是纯逻辑式编程语言？逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-503.4 Prolog3.4 Prolog程序的顺序性程序的顺序性nProlog程序控制流（suggested by Lawrence Byrd）GOALException(error)CALLFAILEXITREDO 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-51内容内容n1.Prolog语言概述n2.合一n3.控制流n3.1 Prolog控制流设计问题n3.2 回溯n3
27、.3 递归n3.4 Prolog程序的顺序性n3.5 cutn3.6 fail 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-523.5 cut3.5 cutnProlog cut（截断/阻止回溯）机制n使用内部无参谓词（！）；n可以作为子目标放在规则子句的体内；n n解释：n程序调用cut总是成功；n当某个子目标失败回溯时，不允许越过！回溯。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.立即失败SucceedFailRedoBacktrack 逻辑程序设计语言范型
28、逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-531/X1/X2/X3/X【例1】逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-541/X1/X【例2】逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-55【例3】1/X1/Y2/Y3/Y0/X,0/Y 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-563.5 cut3.5 cutn【例4】逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-573.5 cut3.5 cutn绿色截断（g
29、reen cut）n加入cut后，不改变程序的逻辑含义，效率更高。n红色截断（red cut）n加入cut后，改变程序的逻辑含义；n应当尽量避免。逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-583.5 cut3.5 cutncut谓词的几种使用：1.当获得正确答案时，立即停止求解并防止回溯。2.防止不必要的回溯所产生的意外。3.与预定义谓词fail结合，使得Prolog对一个目标求解立即失败，并放弃对其它规则的选择。逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-59内容内容n1.Prolog语言概述n2.合一n3.控
30、制流n3.1 Prolog控制流设计问题n3.2 回溯n3.3 递归n3.4 Prolog程序的顺序性n3.5 cutn3.6 fail 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-603.6 fail3.6 failnfailfailn是一个无参数的内部谓词；n当程序调用该谓词时，立即失败并强制回溯！n与cut结合，增加程序编写的灵活性；n可以在一般规则中，增加特殊性；cut-failcombination 12 逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-613.6 fail3.6 failn标准Prolog对“cut-fail”的语法包装：n内部谓词：+逻辑程序设计语言范型逻辑程序设计语言范型Prolog语言控制抽象语言控制抽象第七章-623.6 fail3.6 failn注意：ncut-fail的组合（失败时否定-negation as failurenegation as failure）并不等于逻辑否定。
