逻辑程序设计语言范型Prolog语言控制抽象.ppt

《逻辑程序设计语言范型Prolog语言控制抽象.ppt》由会员分享，可在线阅读，更多相关《逻辑程序设计语言范型Prolog语言控制抽象.ppt（62页珍藏版）》请在三一办公上搜索。

1、,2023年10月31日星期二,程序设计语言范型Programming Languages Paradigms,教师：张荣华 华北电力大学计算机系软件教研室（保定）,逻辑程序设计语言范型,Prolog语言控制抽象,第三部分,第七章,Prolog语言控制抽象,第七章-3,参考文献,Learn Prolog Now!by Patrick Blackburn,Johan Bos,and Kristina Striegnitz http:/www.coli.uni-saarland.de/kris/learn-prolog-now/,Prolog语言控制抽象,第七章-4,内容,1.Prolog语言概述

2、1.1 Prolog的基本元素1.2 Prolog实验环境2.合一2.1 项的合一 2.2 归结2.3 基于合一编程3.控制流,Prolog语言控制抽象,第七章-5,1.Prolog语言概述,Prolog（Programming in Logic）诞生于20世纪70年代初法国马赛大学作为自然语言理解项目的一部分研制成功目前，爱丁堡大学开发的Prolog版本使用最为广泛。迄今最能体现逻辑程序设计思想的逻辑编程语言“说明式”的语言；采用一阶谓词演算说明（描述）问题知识库（事实和规则）的描述采用子句（Clause）形式控制流机制置换、合一归结回溯、深度优先搜索反向推理,Prolog语言控制抽象,第七

3、章-6,内容,1.Prolog语言概述1.1 Prolog的基本元素1.2 Prolog实验环境2.合一2.1 项的合一 2.2 归结2.3 基于合一编程3.控制流,Prolog语言控制抽象,第七章-7,1.1 Prolog的基本元素,【例1】：水平线与垂直线问题。使用两个谓词：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

4、(line(point(1,1),point(2,Y).Y=1;no,horizontal(line(point(2,3),P).P=point(_G434,3);no,Prolog语言控制抽象,第七章-8,1.1 Prolog的基本元素,【例2】求解以下六个英语单词的纵横字谜问题。abalone,abandon,anagram,connect,elegant,enhance,事实,规则,Prolog语言控制抽象,第七章-9,1.1 Prolog的基本元素,Prolog程序的语句（子句）包括：(1)事实（Facts）没有体部的horn子句，即被假定为真的命题。(2)规则（Rules）有头和体的

5、horn子句，只有体部的每个项都为真，头部才为真。,father(john,jim).,grandparent(Person1,Person2):-parent(Person3,Person2),parent(Person1,Person3).,Head,Body,Prolog语言控制抽象,第七章-10,1.1 Prolog的基本元素,Prolog语句由项（term）构成常量原子（atom）：Prolog的符号值以小写字母开始的一串字母、数字、下划线或用单引号界定的一串任何可打印的ASCII字符。整数变量以大写字母开始一串字母、数字和下划线；下划线（_）表示匿名变量；注意与命令式语言中变量的区

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

7、WI-Prolog（推荐使用!）安装文件（注意顺序安装）（1）SWI-Prolog for MS-Windows（version）（2）SWI-Prolog-Editor,Prolog语言控制抽象,第七章-14,内容,1.Prolog语言概述1.1 Prolog的基本元素1.2 Prolog实验环境2.合一2.1 项的合一 2.2 归结2.3 基于合一编程3.控制流,Prolog语言控制抽象,第七章-15,2.1 项的合一,合一如果Term1和Term2是常量，那么当且仅当Term1和 Term2是相同的原子或整数；如果Term1是变量，Term2是任何类型的项，那么 Term1实例化为Ter

8、m2；注：如果Term2也是变量，互相实例化，共享值。如果Term1和Term2都是结构，两者合一，当且仅当（a）两者有相同的算符（谓词）；（b）两者对应的参数匹配，即能够递归地合一；（c）变量实例化必须保持一致性；当满足前面三种情况时，两者项合一。,?-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=_G20

9、6B=_G206;no,Prolog语言控制抽象,第七章-17,2.1 项的合一,【思考】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(f

10、ather(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father,X=father(father(father(father(father(father(.),X=father(*),SICStus Prolog,SWI Prolog,Prolog语言控制抽象,第七章-18,内容,1.Prolog语言概述1.1 Prolog的基本元素1.2 Prolog实验环境2.合一2.1 项的合一

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

12、一编程,【例1】,Prolog语言控制抽象,第七章-23,2.3 基于合一编程,【例2】,匹配失败,Prolog语言控制抽象,第七章-24,2.3 基于合一编程,【例2】,Prolog语言控制抽象,第七章-25,【例3】,2.3 基于合一编程,Prolog语言控制抽象,第七章-26,【例3】,2.3 基于合一编程,DR NO/Title,Prolog语言控制抽象,第七章-27,【例3】,2.3 基于合一编程,DR NO/Title,匹配失败,Prolog语言控制抽象,第七章-28,【例3】,2.3 基于合一编程,DR NO/Title,310/Length,Prolog语言控制抽象,第七章-2

13、9,【例3】,2.3 基于合一编程,DR NO/Title,310/Length,Prolog语言控制抽象,第七章-30,内容,1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 fail,Prolog语言控制抽象,第七章-31,3.1 Prolog控制流设计问题,问题：（基于合一的编程实例）采用哪种搜索策略搜索（搜索方向、搜索类型）目标？合一失败，如何控制程序继续进行求解问题？需要搜索更多的解（使用分号；）时，如何控制程序继续进行求解问题？结论（控制流）：Prolog采用基于目标导向的深度优

14、先搜索策略。回溯是Prolog内部最基本的自动的控制流机制。,Prolog语言控制抽象,第七章-32,3.1 Prolog控制流设计问题,目标导向的搜索有效地裁减了无关的搜索路径,Prolog语言控制抽象,第七章-33,内容,1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 fail,Prolog语言控制抽象,第七章-34,3.2 回溯,【例1】使用与/或树解释合一失败后回溯搜索。,C=X=_G206,seattle/_G206,失败并回溯,Prolog语言控制抽象,第七章-35,3.2 回

15、溯,【例1】使用与/或树解释合一失败后回溯搜索。,C=X=_G206,seattle/_G206,rochester/_G206,Prolog语言控制抽象,第七章-36,3.2 回溯,【例2】使用与/或树解释利用回溯搜索多个解。,X=_G206,Y=_G207,a/X,c/Z,a/Y,解1,Prolog语言控制抽象,第七章-37,3.2 回溯,【例2】使用与/或树解释利用回溯搜索多个解。,X=_G206,Y=_G207,a/X,c/Z,a/Y,b/Y,解2,解1,Prolog语言控制抽象,第七章-38,3.2 回溯,【例2】使用与/或树解释利用回溯搜索多个解。,X=_G206,Y=_G207,

16、a/X,c/Z,a/Y,b/Y,解2,解1,b/X,c/Z,a/Y,解3,Prolog语言控制抽象,第七章-39,3.2 回溯,【例2】使用与/或树解释利用回溯搜索多个解。,X=_G206,Y=_G207,a/X,c/Z,a/Y,b/Y,解2,解1,b/X,c/Z,a/Y,解3,b/Y,解4,Prolog语言控制抽象,第七章-40,3.2 回溯,【例3】求解以下六个英语单词的纵横字谜问题。abalone,abandon,anagram,connect,elegant,enhance,Prolog语言控制抽象,第七章-41,3.2 回溯,a,a,b,l,o,n,e,a,n,a,g,r,a,m,o

17、,c,n,n,e,c,t,a,a,d,n,e,e,e,a,t,h,n,e,a,a,d,n,b,o,n,l,e,e,a,t,n,g,n,e,h,n,e,c,a,a,a,o,e,a,a,r,m,c,n,e,t,Prolog语言控制抽象,第七章-42,3.2 回溯,Prolog语言控制抽象,第七章-43,内容,1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 fail,Prolog语言控制抽象,第七章-44,3.3 递归,从过程的观点看子目标：规则的体部含有对其它谓词的调用，这些谓词称为规则的子目

18、标，子目标可能是：事实；其它的规则；同一条规则（递归调用）递归子句,基子句,递归子句,Prolog语言控制抽象,第七章-45,3.3 递归,e/X,b/Y,Prolog语言控制抽象,第七章-46,3.3 递归,e/X,b/Y,e/X,b/Y,d/Z,d/Z,Prolog语言控制抽象,第七章-47,3.3 递归,e/X,b/Y,e/X,b/Y,d/Z,d/Z,d/X,b/Y,c/Z,Prolog语言控制抽象,第七章-48,内容,1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 fail,Pro

19、log语言控制抽象,第七章-49,3.4 Prolog程序的顺序性,Prolog程序查询目标时按照特定的顺序自动执行：基于目标反向推理深度优先自上而下搜索知识库中的Horn子句；从左向右搜索规则体中的各个项；使用回溯机制尝试新的搜索；Prolog是否是纯逻辑式编程语言？,Prolog语言控制抽象,第七章-50,3.4 Prolog程序的顺序性,Prolog程序控制流（suggested by Lawrence Byrd）,GOAL,Exception(error),CALL,FAIL,EXIT,REDO,Prolog语言控制抽象,第七章-51,内容,1.Prolog语言概述2.合一3.控制流3

20、.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 fail,Prolog语言控制抽象,第七章-52,3.5 cut,Prolog 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.,立即失败,Prolog语言控制抽象,第七章-53,1/X,1/X,2/X,3/X,【例1】,Prolog语

21、言控制抽象,第七章-54,1/X,1/X,【例2】,Prolog语言控制抽象,第七章-55,【例3】,1/X,1/Y,2/Y,3/Y,0/X,0/Y,Prolog语言控制抽象,第七章-56,3.5 cut,【例4】,Prolog语言控制抽象,第七章-57,3.5 cut,绿色截断（green cut）加入cut后，不改变程序的逻辑含义，效率更高。,红色截断（red cut）加入cut后，改变程序的逻辑含义；应当尽量避免。,Prolog语言控制抽象,第七章-58,3.5 cut,cut谓词的几种使用：,当获得正确答案时，立即停止求解并防止回溯。防止不必要的回溯所产生的意外。与预定义谓词fail结

22、合，使得Prolog对一个目标求解立即失败，并放弃对其它规则的选择。,Prolog语言控制抽象,第七章-59,内容,1.Prolog语言概述2.合一3.控制流3.1 Prolog控制流设计问题3.2 回溯3.3 递归3.4 Prolog程序的顺序性3.5 cut3.6 fail,Prolog语言控制抽象,第七章-60,3.6 fail,fail是一个无参数的内部谓词；当程序调用该谓词时，立即失败并强制回溯！与cut结合，增加程序编写的灵活性；可以在一般规则中，增加特殊性；,cut-fail combination,1,2,Prolog语言控制抽象,第七章-61,3.6 fail,标准Prolog对“cut-fail”的语法包装：内部谓词：+,Prolog语言控制抽象,第七章-62,3.6 fail,注意：cut-fail的组合（失败时否定-negation as failure）并不等于逻辑否定。,