,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Prolog,语言控制抽象,第七章,-,*,逻辑程序设计语言范型,19 十一月 2024,程序设计语言范型,Programming Languages Paradigms,教师：,张荣华,华北电力大学计算机系软件教研室（保定）,07 十月 2023程序设计语言范型Programming,逻辑程序设计语言范型,Prolog,语言控制抽象,第三部分,第七章,逻辑程序设计语言范型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语言控制抽象第七章 - 3参考文献Learn P,Prolog,语言控制抽象,第七章,-,4,内容,1.,Prolog,语言概述,1.1 Prolog,的基本元素,1.2 Prolog,实验环境,2.,合一,2.1,项的合一,2.2,归结,2.3,基于合一编程,3.,控制流,Prolog语言控制抽象第七章 - 4内容1.Prolog语,Prolog,语言控制抽象,第七章,-,5,1.Prolog语言概述,Prolog,（,Pro,gramming in,Log,ic,）,诞生于,20,世纪,70,年代初,法国马赛大学作为自然语言理解项目的一部分研制成功,目前，爱丁堡大学开发的,Prolog,版本使用最为广泛。,迄今最能体现,逻辑程序设计思想,的逻辑编程语言,“,说明式,”,的语言；,采用一阶谓词演算说明（描述）问题,知识库（事实和规则）的描述采用,子句,（,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,语言控制抽象,第七章,-,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(line(point(1,1),point(2,Y).Y=1;no,horizontal(line(point(2,3),P).P=point(_G434,3);no,Prolog语言控制抽象第七章 - 71.1 Prolog的,Prolog,语言控制抽象,第七章,-,8,1.1 Prolog的基本元素,【,例,2】,求解以下六个英语单词的纵横字谜问题。,abalone, abandon, anagram, connect, elegant, enhance,事实,规则,Prolog语言控制抽象第七章 - 81.1 Prolog的,Prolog,语言控制抽象,第七章,-,9,1.1 Prolog的基本元素,Prolog,程序的语句（,子句,）包括：,(1),事实（,Facts,）,没有体部的,horn,子句，即被假定为真的命题。,(2),规则（,Rules,）,有头和体的,horn,子句，只有体部的每个项都为真，头部才为真。,father( john, jim).,grandparent( Person1, Person2 ) :-,parent( Person3, Person2 ),parent( Person1, Person3 ).,Head,Body,Prolog语言控制抽象第七章 - 91.1 Prolog的,Prolog,语言控制抽象,第七章,-,10,1.1 Prolog,的基本元素,Prolog,语句由,项（,term,）,构成,常量,原子（,atom,）：,Prolog,的符号值,以小写字母开始的一串字母、数字、下划线或用单引号界定的一串任何可打印的,ASCII,字符。,整数,变量,以大写字母开始一串字母、数字和下划线；,下划线（,_,）表示,匿名变量,；,注意与命令式语言中变量的区别。,结构（谓词,/,复杂项）,vertical(line(point(X,Y),point(X,Z).,Prolog语言控制抽象第七章 - 101.1 Prolog,Prolog,语言控制抽象,第七章,-,11,1.1 Prolog,的基本元素,Prolog,程序运行,通过提问查询知识库,使用分号（,；,）查询多个解（,multiple answers,）,分号有特定的语义：表示结束当前合一，回溯查找其它可满足的解。,Prolog语言控制抽象第七章 - 111.1 Prolog,Prolog,语言控制抽象,第七章,-,12,内容,1.,Prolog,语言概述,1.1 Prolog,的基本元素,1.2 Prolog,实验环境,2.,合一,2.1,项的合一,2.2,归结,2.3,基于合一编程,3.,控制流,Prolog语言控制抽象第七章 - 12内容1.Prolog,Prolog,语言控制抽象,第七章,-,13,1.2 Prolog实验环境,SWI-Prolog,（,推荐使用,!,）,http:/www.swi-prolog.org/,安装文件（,注意顺序安装,）,（,1,）,SWI-Prolog for MS-Windows,（,version,5.10.1,）,（,2,）,SWI-Prolog-Editor,http:/lakk.bildung.hessen.de/netzwerk/faecher/informatik/swiprolog/indexe.html,Prolog语言控制抽象第七章 - 131.2 Prolog,Prolog,语言控制抽象,第七章,-,14,内容,1.Prolog,语言概述,1.1 Prolog,的基本元素,1.2 Prolog,实验环境,2.,合一,2.1,项的合一,2.2,归结,2.3,基于合一编程,3.,控制流,Prolog语言控制抽象第七章 - 14内容1.Prolog,Prolog,语言控制抽象,第七章,-,15,2.1 项的合一,合一,如果,Term1,和,Term2,是常量，那么当且仅当,Term1,和,Term2,是相同的原子或整数；,如果,Term1,是变量，,Term2,是任何类型的项，那么,Term1,实例化为,Term2,；,注：如果,Term2,也是变量，互相实例化，,共享值,。,如果,Term1,和,Term2,都是结构，两者合一，当且仅当,（,a,）两者有相同的算符（谓词）；,（,b,）两者对应的参数匹配，即能够递归地合一；,（,c,）,变量实例化必须保持一致性,；,当满足前面三种情况时，两者项合一。,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 = _G206,B = _G206;,no,?- a=a. Prolog中的相等是基于“合一”的定义内部,Prolog,语言控制抽象,第七章,-,17,2.1 项的合一,【,思考,】,Prolog,实现合一操作时是否使用标准的合一算法？,老版本的,Prolog,实现,:,Not,enough,memory,to,complete,query!,现代版本的,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(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语言控制抽象第七章 - 172.1 项的合一【思,Prolog,语言控制抽象,第七章,-,18,内容,1.Prolog,语言概述,1.1 Prolog,的基本元素,1.2 Prolog,实验环境,2.,合一,2.1,项的合一,2.2,归结,2.3,基于合一编程,3.,控制流,Prolog语言控制抽象第七章 - 18内容1.Prolog,Prolog,语言控制抽象,第七章,-,19,2.2,归结,Prolog,中的推理来自,Robison,归结原理,，,在,Prolog,中，如果,C,1,和,C,2,都是子句，且,C,1,的头部与,C,2,的体中的一个项合一，那么就可以用,C,1,的体取代,C,2,里的那个项。,例如：,Prolog语言控制抽象第七章 - 192.2 归结Prol,Prolog,语言控制抽象,第七章,-,20,内容,1.Prolog,语言概述,1.1 Prolog,的基本元素,1.2 Prolog,实验环境,2.,合一,2.1,项的合一,2.2,归结,2.3,基于合一编程,3.,控制流,Prolog语言控制抽象第七章 - 20内容1.Prolog,Prolog,语言控制抽象,第七章,-,21,2.3 基于合一编程,【,例,1】,Prolog语言控制抽象第七章 - 212.3 基于合一编程,Prolog,语言控制抽象,第七章,-,22,2.3 基于合一编程,【,例,1】,Prolog语言控制抽象第七章 - 222.3 基于合一编程,Prolog,语言控制抽象,第七章,-,23,2.3 基于合一编程,【,例,2】,匹配失败,Prolog语言控制抽象第七章 - 232.3 基于合一编程,Prolog,语言控制抽象,第七章,-,24,2.3 基于合一编程,【,例,2】,Prolog语言控制抽象第七章 - 242.3 基于合一编程,Prolog,语言控制抽象,第七章,-,25,【,例,3】,2.3 基于合一编程,Prolog语言控制抽象第七章 - 25【例3】2.3 基于,Prolog,语言控制抽象,第七章,-,26,【,例,3】,2.3 基于合一编程,DR NO/Title,Prolog语言控制抽象第七章 - 26【例3】2.3 基于,Prolog,语言控制抽象,第七章,-,27,【,例,3】,2.3 基于合一编程,DR NO/Title,匹配失败,Prolog语言控制抽象第七章 - 27【例3】2.3 基于,Prolog,语言控制抽象,第七章,-,28,【,例,3】,2.3 基于合一编程,DR NO/Title,310/Length,Prolog语言控制抽象第七章 - 28【例3】2.3 基于,Prolog,语言控制抽象,第七章,-,29,【,例,3】,2.3 基于合一编程,DR NO/Title,310/Length,Prolog语言控制抽象第七章 - 29【例3】2.3 基于,Prolog,语言控制抽象,第七章,-,30,内容,1.Prolog,语言概述,2.,合一,3.,控制流,3.1,Prolog控制流设计问题,3.2,回溯,3.3,递归,3.4,Prolog程序的顺序性,3.5 c,ut,3.6,fail,Prolog语言控制抽象第七章 - 30内容1.Prolog,Prolog,语言控制抽象,第七章,-,31,3.1 Prolog控制流设计问题,问题：（基于合一的编程实例）,采用哪种搜索策略搜索（,搜索方向,、,搜索类型,）目标？,合一失败，如何控制程序继续进行求解问题？,需要搜索更多的解（使用分号；）时，如何控制程序继续进行求解问题？,结论（控制流）：,Prolog,采用基于目标导向的深度优先搜索策略。,回溯是,Prolog,内部最基本的,自动,的控制流机制。,Prolog语言控制抽象第七章 - 313.1 Prolog,Prolog,语言控制抽象,第七章,-,32,3.1 Prolog控制流设计问题,目标导向的搜索有效地裁减了无关的搜索路径,Prolog语言控制抽象第七章 - 323.1 Prolog,Prolog,语言控制抽象,第七章,-,33,内容,1.Prolog,语言概述,2.,合一,3.,控制流,3.1,Prolog控制流设计问题,3.2,回溯,3.3,递归,3.4,Prolog程序的顺序性,3.5 c,ut,3.6,fail,Prolog语言控制抽象第七章 - 33内容1.Prolog,Prolog,语言控制抽象,第七章,-,34,3.2 回溯,【,例,1】,使用,与,/,或树,解释合一失败后回溯搜索。,C=X=_G206,seattle/_G206,失败并回溯,Prolog语言控制抽象第七章 - 343.2 回溯【例1】,Prolog,语言控制抽象,第七章,-,35,3.2 回溯,【,例,1】,使用,与,/,或树,解释合一失败后回溯搜索。,C=X=_G206,seattle/_G206,rochester/_G206,Prolog语言控制抽象第七章 - 353.2 回溯【例1】,Prolog,语言控制抽象,第七章,-,36,3.2 回溯,【,例,2】,使用,与,/,或树,解释利用回溯搜索多个解。,X=_G206, Y=_G207,a/X, c/Z,a/Y,解,1,Prolog语言控制抽象第七章 - 363.2 回溯【例2】,Prolog,语言控制抽象,第七章,-,37,3.2 回溯,【,例,2】,使用,与,/,或树,解释利用回溯搜索多个解。,X=_G206, Y=_G207,a/X, c/Z,a/Y,b/Y,解,2,解,1,Prolog语言控制抽象第七章 - 373.2 回溯【例2】,Prolog,语言控制抽象,第七章,-,38,3.2 回溯,【,例,2】,使用,与,/,或树,解释利用回溯搜索多个解。,X=_G206, Y=_G207,a/X, c/Z,a/Y,b/Y,解,2,解,1,b/X, c/Z,a/Y,解,3,Prolog语言控制抽象第七章 - 383.2 回溯【例2】,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语言控制抽象第七章 - 393.2 回溯【例2】,Prolog,语言控制抽象,第七章,-,40,3.2 回溯,【,例,3】,求解以下六个英语单词的纵横字谜问题。,abalone, abandon, anagram, connect, elegant, enhance,Prolog语言控制抽象第七章 - 403.2 回溯【例3】,Prolog,语言控制抽象,第七章,-,41,3.2 回溯,a,a,b,l,o,n,e,a,n,a,g,r,a,m,o,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语言控制抽象第七章 - 413.2 回溯aabl,Prolog,语言控制抽象,第七章,-,42,3.2 回溯,Prolog语言控制抽象第七章 - 423.2 回溯,Prolog,语言控制抽象,第七章,-,43,内容,1.Prolog,语言概述,2.,合一,3.,控制流,3.1,Prolog控制流设计问题,3.2,回溯,3.3,递归,3.4,Prolog程序的顺序性,3.5 c,ut,3.6,fail,Prolog语言控制抽象第七章 - 43内容1.Prolog,Prolog,语言控制抽象,第七章,-,44,3.3 递归,从过程的观点看,子目标,：,规则的体部含有对其它谓词的调用，这些谓词称为规则的,子目标,，子目标可能是：,事实；,其它的规则；,同一条规则（递归调用）,递归子句,基子句,递归子句,Prolog语言控制抽象第七章 - 443.3 递归从过程的,Prolog,语言控制抽象,第七章,-,45,3.3 递归,e/X, b/ Y,Prolog语言控制抽象第七章 - 453.3 递归e/X,Prolog,语言控制抽象,第七章,-,46,3.3 递归,e/X, b/ Y,e/X, b/Y,d/Z,d/Z,Prolog语言控制抽象第七章 - 463.3 递归e/X,Prolog,语言控制抽象,第七章,-,47,3.3 递归,e/X, b/ Y,e/X, b/Y,d/Z,d/Z,d/X, b/Y,c/Z,Prolog语言控制抽象第七章 - 473.3 递归e/X,Prolog,语言控制抽象,第七章,-,48,内容,1.Prolog,语言概述,2.,合一,3.,控制流,3.1,Prolog控制流设计问题,3.2,回溯,3.3,递归,3.4,Prolog程序的顺序性,3.5 c,ut,3.6,fail,Prolog语言控制抽象第七章 - 48内容1.Prolog,Prolog,语言控制抽象,第七章,-,49,3.4 Prolog程序的顺序性,Prolog,程序查询目标时按照特定的顺序,自动执行,：,基于目标反向推理,深度优先,自上而下搜索知识库中的,Horn,子句；,从左向右搜索规则体中的各个项；,使用回溯机制尝试新的搜索；,Prolog,是否是纯逻辑式编程语言？,Prolog语言控制抽象第七章 - 493.4 Prolog,Prolog,语言控制抽象,第七章,-,50,3.4 Prolog程序的顺序性,Prolog,程序控制流（,suggested by Lawrence Byrd,）,GOAL,Exception (error),CALL,FAIL,EXIT,REDO,Prolog语言控制抽象第七章 - 503.4 Prolog,Prolog,语言控制抽象,第七章,-,51,内容,1.Prolog,语言概述,2.,合一,3.,控制流,3.1,Prolog控制流设计问题,3.2,回溯,3.3,递归,3.4,Prolog程序的顺序性,3.5 c,ut,3.6,fail,Prolog语言控制抽象第七章 - 51内容1.Prolog,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 .,立即失败,Succeed,Fail,Redo,Backtrack,Prolog语言控制抽象第七章 - 523.5 cutPro,Prolog,语言控制抽象,第七章,-,53,1/X,1/X,2/X,3/X,【,例,1】,Prolog语言控制抽象第七章 - 531/X1/X2/X3,Prolog,语言控制抽象,第七章,-,54,1/X,1/X,【,例,2】,Prolog语言控制抽象第七章 - 541/X1/X【例2】,Prolog,语言控制抽象,第七章,-,55,【,例,3】,1/X,1/Y,2/Y,3/Y,0/X, 0/Y,Prolog语言控制抽象第七章 - 55【例3】1/X1/Y,Prolog,语言控制抽象,第七章,-,56,3.5 cut,【,例,4】,Prolog语言控制抽象第七章 - 563.5 cut【例4,Prolog,语言控制抽象,第七章,-,57,3.5 cut,绿色截断（,green cut,）,加入,cut,后，不改变程序的逻辑含义，效率更高。,红色截断,（,red cut,）,加入,cut,后，改变程序的逻辑含义；,应当尽量避免。,Prolog语言控制抽象第七章 - 573.5 cut绿色截,Prolog,语言控制抽象,第七章,-,58,3.5 cut,cut,谓词的几种使用：,当获得正确答案时，立即停止求解并防止回溯。,防止不必要的回溯所产生的意外。,与预定义谓词,fail,结合，使得,Prolog,对一个目标求解立即失败，并放弃对其它规则的选择。,Prolog语言控制抽象第七章 - 583.5 cutcut,Prolog,语言控制抽象,第七章,-,59,内容,1.Prolog,语言概述,2.,合一,3.,控制流,3.1,Prolog控制流设计问题,3.2,回溯,3.3,递归,3.4,Prolog程序的顺序性,3.5 c,ut,3.6,fail,Prolog语言控制抽象第七章 - 59内容1.Prolog,Prolog,语言控制抽象,第七章,-,60,3.6 fail,fail,是一个无参数的内部谓词；,当程序调用该谓词时，,立即失败并强制回溯,！,与,cut,结合，增加程序编写的灵活性；,可以在一般规则中，增加特殊性；,cut-fail combination,1,2,Prolog语言控制抽象第七章 - 603.6 failfa,Prolog,语言控制抽象,第七章,-,61,3.6 fail,标准,Prolog,对,“,cut-fail,”,的语法包装：,内部谓词：,+,Prolog语言控制抽象第七章 - 613.6 fail标准,Prolog,语言控制抽象,第七章,-,62,3.6 fail,注意：,cut-fail,的组合（失败时否定,-,negation as failure,）并不等于逻辑否定。,Prolog语言控制抽象第七章 - 623.6 fail注意,