第2章人工智能程序设计语言课件

《第2章人工智能程序设计语言课件》由会员分享，可在线阅读，更多相关《第2章人工智能程序设计语言课件（150页珍藏版）》请在装配图网上搜索。

1、,第二级,第三级,第四级,第五级,,*,页,*,第2章 人工智能程序设计语言,第2章 人工智能程序设计语言,,2.1 综述,2.2 函数型程序设计语言LISP,2.3 逻辑型程序设计语言PROLOG,2.4 Turbo PROLOG程序设计,,,1,页,第2章 人工智能程序设计语言 2.1 综述1页,1,2.1 综述,2.1.1 函数型语言,LISP是一种函数型程序设计语言。LISP程序由一组函数组成，程序的执行过程就是一系列的函数调用和求值过程。但LISP还不是纯函数型语言，准确地讲，它是基于λ--函数的语言。除LISP外，20世纪70年代J.Backus还提

2、出了一种称为FP的所谓纯函数型程序设计语言。但该语言现在还限于理论研究，实现上还存在一定困难。,,,2,页,2.1 综述 2.1.1 函数型语言2页,2,2.1.2 逻辑型语言,逻辑型程序设计语言起源于PROLOG(PROgramminginLOGic的缩写)。PROLOG语言首先由法国马塞大学的Colmerauer和它的研究小组于1972年研制成功，后来在欧洲得到进一步发展。特别是1981年日本宣布要以PROLOG作为他们正在研制的新一代计算机——智能计算机的核心语言，更使PROLOG举世瞩目，迅速风靡世界。,,3,页,2.1.2 逻辑型语言3页,3,PROLOG语言是以

3、Horn子句逻辑为基础的程序设计语言，它是目前最具代表性的一种逻辑程序设计语言。早期PROLOG版本都是解释型的，1986年美国的Borland公司推出了编译型PROLOG-TurboPROLOG，并很快成为PC机上流行的PROLOG。现在运行在Windows环境下的可视化编程语言VisualPROLOG也已面世。但这些PROLOG语言版本属顺序逻辑程序设计语言。,,4,页,PROLOG语言是以Horn子句逻,4,2.1.3 面向对象语言,20世纪80年代以来，面向对象程序设计(ObjectOrientedProgramming，简称OOP)异军突起，发展迅速，如今已日渐成熟，并越来越流行

4、起来。面向对象程序以其信息隐蔽、封装、继承、多态、消息传递等一系列优良机制，大大改善了软件的复杂性、模块性、重用性和可维护性，有望从根本上解决软件的生产效率问题。另一方面，由于面向对象程序设计的类、对象、继承等概念，与人工智能特别是知识表示和知识库产生了天然的联系。,,5,页,2.1.3 面向对象语言5页,5,因而，现在面向对象程序设计语言也成为一种人工智能程序设计语言，面向对象程序设计也被广泛引入人工智能程序设计，特别是知识工程、专家系统程序设计。面向对象程序设计语言也种类繁多，已发展成为一个大家族。其中最纯正、最具面向对象风格的语言当推Smalltalk，而最流行的OOP语言是C++，J

5、ava则是适于网络(Internet)环境的一种面向对象语言。,,,6,页,因而，现在面向对象程序设计语言也成为,6,2.1.4 混合型语言,以上三种语言都各有所长，但也都有其不足之处。为了扬长避短，于是便出现了基于这三种语言的混合型语言。,1. 函数型与逻辑型相结合的语言,函数型与逻辑型语言的结合方式有耦合型和统一型两类。统一型又可分为具有归结语义的函数型语言和集成式语言两个子类。,,,7,页,2.1.4 混合型语言7页,7,2. 函数型与面向对象相结合的语言,在LISP语言的基础上再扩充面向对象机制而产生的语言，称为函数型的面向对象程序设计语言(亦称为面向对象的LISP)。,3. 逻辑

6、型与面向对象相结合的语言,,,8,页,2. 函数型与面向对象相结合的语言8,8,2.2 函数型程序设计语言LISP,LISP语言的主要特点是：,(1) LISP程序由一组函数组成，程序的执行过程是函数的调用过程。,(2) 程序和数据在形式上是相同的，即都是符号表达式，简称为S─表达式。,(3) 递归是LISP语言的主要控制结构。,(4) 程序以交互方式运行。,,,9,页,2.2 函数型程序设计语言LISP,9,2.2.1 LISP的程序结构与运行机制,LISP的程序一般由函数的定义和函数的调用两部分组成。其一般格式为：,(DEFUN(()),((〖WB〗)),…,(())),(),(),

7、…,(),,,10,页,2.2.1 LISP的程序结构与运行机制 10页,10,其中的“DEFUN”是定义函数的关键字，“函数名”可以是系统的内部函数(名)，也可以是用户用DEFUN定义的函数(名)。例如下面就是一个LISP程序。,(DEFUNHANOI(a b c n),(COND((=n1)(MOVE-DISK a c)),(T(HANOI a c b(-n1)),(MOVE-DISK a c),(HANOI b a c(-n1)))),,,,11,页,其中的“DEFUN”是定义函数的关键,11,(DEFUNMOVE-DISK(from to),(TERPRI),(PRINC″Move

8、 Disk From″),(PRINC from),(PRINC"To"),(PRINC to)),,(HANOI′a′b′c3),,,12,页,(DEFUNMOVE-DISK(from to)12页,12,2.2.2 S─表达式,从语法上看，LISP程序的基本单位是S─表达式。S─表达式又可分为原子和表两大类。,原子(atom)是由字母和数字组成的字符串，是S─表达式的最简单情况。原子又可分为文字原子、串原子和数字原子三种。,文字原子又称符号（symbol），是以字母开头的字母数字串，用来表示常量、变量和函数的名字等。例如：ABC、X1等。,,,13,页,2.2.2 S─表达式13页,1

9、3,串原子是由双引号括起来的一串字符。如"LISP Program"。,数字原子由数字串组成。在其前面可以有符号“-”或“+”，中间可出现“.”，用来表示整数和实数。例如：256、-66、3.14159等。,,14,页,串原子是由双引号括起来的一串字符。如,14,S─表达式可以递归定义如下：,(1) 原子是S─表达式。,(2) 若S1和S2是S─表达式，则(S1·S2)也是S─表达式。由定义，下面的式子都是S─表达式：,X2,123,(A·B),(A·(B·C)),,,15,页,S─表达式可以递归定义如下：15页,15,表(list)是LISP语言中最常用的数据类型，也是主要的处理对象。表是由

10、圆括号括起来的由空格分开的若干个元素的集合。,表的一般形式为：,(…),,16,页,表(list)是LISP语言中最常用,16,例如：,(X Y Z),(+12),(A (B C)),左括号后面的第一个元素称为表头，其余的元素组成的表称为表尾。例如，对于表,(+12)的头为+，尾为(12)。,特别地，元素个数为零的表为空表，记为()或NIL。,表是一种特殊的S─表达式，每一个表都对应着一个S─表达式。二者的关系由下面的例子说明。,,,17,页,例如：17页,17,表←————————————→S -表达式,(A) (A·NIL

11、),(AB) (A·(B·NIL)),(ABC) (A·(B·(C·NIL))),((AB)CD) ((A·(B·NIL))·(C·(D·NIL))),可以看出，表的S─表达式的结构实际是一棵二叉树。,,18,页,表←————————————→S -表达,18,2.2.3 基本函数,LISP的函数都以表的形式出现，并一律使用前缀表示方式，即表头为函数名，并且每个函数都有一个返回值。LISP的函数可分为语言自身提供的内部函数(称为基本函

12、数或系统函数)和用户自定义函数两类。基本函数的种类有十多个，下面仅给出其中主要的几类。,1. 表处理函数,表处理是LISP的主要特色，表处理的函数也很多，下面仅给出最常用的几个。,,,,19,页,2.2.3 基本函数19页,19,1) CAR函数,格式(CAR),其中CAR为函数名，它是一个保留字（下同）。,功能取出表中的表头。,例如：(CAR′(LISP Language Program)),返回值为：LISP,,,20,页,1) CAR函数20页,20,2) CDR函数,格式(CDR),功能取出表中的表尾。,例如：(CDR′(LISP Language Program)),返回值为：(

13、Language Program),3) CONS函数,格式(CONS),功能将S─表达式作为一个元素加到表中去，并作为所构成新表中的第一个元素。,例如：(CONS′My′(LISP Language Program)),返回值为：(My LISP Language Program),,21,页,2) CDR函数21页,21,4) APPEND函数,格式 (APPEND<表,1,><表,2,>…<表,n,>),功能 将n个表中的元素合并成一个新表。,例如：(APPEND′(TIGER LION)′(DOG CAT)),返回值为：(TIGER LION DOG CAT),,,22,页,4) A

14、PPEND函数22页,22,5) LIST函数,格式(LIST…),功能把n个S─表达式作为元素括在一起构成一张新表。,例如：(LIST′YELLOW′RED′BLUE),返回值为：(YELLOW RED BLUE),,23,页,5) LIST函数23页,23,2.算术函数,LISP的算术表达式也是用函数表示的，称为算术函数。下面我们仅举例说明。,(+25),表示2+5，返回值为7。,(-(*48)(/105))表示4×8-10/5，返回值为30。,,,24,页,2.算术函数24页,24,3. 求值与赋值函数,在上面的函数中多次出现撇号′，它的意思是禁止求值。为什么要禁止求值呢？原来，L

15、ISP总是试图对一切S─表达式求值。表的值是通过函数运算而得到的，原子的值则是通过赋值函数实现的。撇号′也是一个函数，它实际是禁止求值函数QUOTE的简写形式。,赋值函数有多个，其中SET函数是一个最基本的赋值函数。,,,25,页,3. 求值与赋值函数25页,25,格式(SET),功能把S─表达式赋给变量。,例如：,(SET′X′8); X 得到值8,(SET′Y′(a b c)); Y 得到值(a b c),(SET′Z(CDRY); Z 得到值(b c),另外，赋值函数还有SETQ、SETF

16、(COMMON LISP)，其功能是类似的。,,26,页,格式(SET),26,4. 谓词函数,返回值为逻辑值真或假的函数称为谓词函数，简称谓词。LISP中真和假分别用T和NIL表示，当函数的返回值为非NIL时，也表示为真。另外，NIL也表示空表。谓词函数也有多个，下面我们仅给出常用的几个。,,,,27,页,4. 谓词函数27页,27,(1) 原子谓词ATOM,格式 (ATOM),功能检测其参数是否为原子，是则返回T，否则返回NIL。,例如：,(ATOM′a);返回T,(ATOM′(a b));返回NIL,,,28,页,(1) 原子谓词ATOM28页,28,(2) 相等谓词EQUAL,格式(E

17、QUAL),功能判断两个参数是否逻辑相等。,例如：,(EQUAL′a′a); 返回T,(EQUAL′(a b)′(ac)); 返回NIL,(EQUAL′(a b)(CONS′a′(b))); 返回T,还有一种相等谓词，其格式为：(EQ)，但它只是用来判断两个原子是否相等。例如：(EQ′a′a)，则返回T,,29,页,(2) 相等谓词EQUAL29页,29,(3)判空表函数NULL,格式(NULL),功能判断参数是否为空表，是则返回T，否则返回NIL。,,30,页,(3)判空表函数NULL3

18、0页,30,5.条件函数,条件函数也称分支函数，类似于其他语言中的分支语句，其作用是控制程序的流程。,格式 (COND(P,1,e,1,),(P,2,e,2,), …,(P,n,e,n,)),其中P,i,(i=1,...,n)为谓词，e,i,(i=1,...,n)为一个或多个S─表达式。,,,31,页,5.条件函数31页,31,功能如果P,1,为真，则COND函数的值为e,1,(当e,1,为多个S─表达式时，取最后一个S─表达式的值，下同)。否则，判断P,2,，……直到某个P,i,真为止，然后将对应的e,i,作为函数值。若没有一个P,i,的值为非NIL，则COND的返回

19、值为NIL。特别地，P,i,也可以为逻辑常量T，这时则对其对应的各表达式求值，并把最后一个表达式的值作为COND的返回值。,,,32,页,功能如果P1为真，则COND函数的,32,例如：,(COND((NULL x)0),((ATOM x)1),((LISTP x)(LENGTH x))),其语义是，若x的值为NIL，则COND的返回值为0;若x为原子，则COND的返回值为1;若x的值为表，则COND的返回值为表的长度。,,33,页,例如：33页,33,2.2.4 自定义函数,基本函数是LISP提供的基本处理功能，要用LISP编程解决实际问题，仅有基本函数还是不够的，用户还必须根据问题的需

20、要，利用基本函数自定义所需的函数。,自定义函数的格式为：,(DEFUN(),),,,34,页,2.2.4 自定义函数34页,34,其中函数体，又可能是用户自定义的函数或LISP基本函数的某种组合。所以，一般来讲，LISP自定义函数就是由其基本函数组合而成的。常用的组合方法有复和、分支、递归、迭代等。其中最具特色的构造方法是递归。,,,35,页,其中函数体，又可能是用户自定义的函数,35,例2.1 定义求N!的LISP函数。,阶乘的公式是,n!＝n×(n-1)!,1!＝1,0!＝1,由此我们给出其LISP函数如下：,(DEFUNN!(n),(COND((=n 0)1),((=n 1)1),

21、(T(* n(N!(- n 1)))))),,,36,页,例2.1 定义求N!的LISP函数。36页,36,可以看出，该函数的最后一行中又调用了它自己。所以，这个函数N!是递归定义的。,需说明的是，一个函数是否能递归定义，要取决于以下两条：,(1)函数的求值存在最简的情形，在这种情形下函数值是显然的或已知的；,(2)该函数对于其参数的求值，可以归结为对另一些参数的求值，而且后者比前者更容易求值，即使问题朝最简情形逼近了一步。,,37,页,可以看出，该函数的最后一行中又调用了,37,2.2.5 程序举例,例2.2 符号微分程序。,这里是指数学上的一元函数求导。我们用D(ex)表示数学上的de

22、/dx,这里e为需求导的函数表达式，x为自变量。程序如下：,(DEFUND(ex),(COND((ATOM e)(IF(Eq e x)1 0)),(T(APPLY(D-RULE(CAR e)),(APPEND(CDR e)),(LIST x))))),,,38,页,2.2.5 程序举例38页,38,其中D-RULE是一个获取给定操作符的微分规则的LISP函数。微分规则的存放，是通过为相应操作符建立d特性的方法完成的。D-RULE的定义为,(DEFUN D-RULE(operator),(GET operator′d)),其中操作符d的特性值需事先用SETF函数建立好。例如对于操作符加＋和乘

23、·，在数学上有,d(u＋v)/dx＝du/dx＋dv/dx,d(u·v)/dx＝v·du/dx＋u·dv/dx ,,39,页,其中D-RULE是一个获取给定操作符,39,用LISP表示就是,(SETF(GET′+′D)′(LAMBDA(u v,x)′(+,(Dux),(D v x)))),(SETF(GET′*′D)′(LAMBDA(u v,x)′(+(*,(Dux),v)(*,(D v x),u))))),,,40,页,用LISP表示就是40页,40,有了这些函数，我们就可以用机器求符号微分了。例如，给出如下的函数调用(D′(+(*2x)(*x x))′x);即求一元函数2x+x2关于

24、x的导函数则得到返回值为,(+(+(* 0 x)(* 1 2))(+(* 1 x)(*1 x))),即2+2x，结果正确。,,,41,页,有了这些函数，我们就可以用机器求符号,41,由于篇幅所限，上面我们对LISP语言仅做了简要介绍。需进一步学习的读者，可参阅有关专门著作。实际上，以此为入门和基础，读者就可以参照某一具体的LISP语言资料，进行LISP程序设计了。经过30多年的发展，LISP的方言和版本也很多。目前比较流行的有INTERLISP、MACLISP、COMMONLISP。其中COMMONLISP将成为一种标准，以统一各种LISP方言。,,42,页,由于篇幅所限，上面我们对LISP

25、语言,42,2.3 逻辑型程序设计语言PROLOG,,2.3.1 PROLOG的语句,PROLOG语言只有三种语句，分别称为事实、规则和问题。,1.事实(fact),格式().,其中谓词名是以小写英文字母打头的字母、数字、下划线等组成的字符串，项表是以逗号隔开的项序列。,,43,页,2.3 逻辑型程序设计语言PROLOG 2.3.,43,,PROLOG中的项包括由常量或变量表示的简单对象以及函数、结构和表等,即事实的形式是一个原子谓词公式。,,例如：,student(john).,like( mary ,music).,就是PROLOG中的两个合法事实。,,,44,页,PRO

26、LOG中的项包括由常量或变量表示的简单对象以及,44,功能 一般表示对象的性质或关系。,例如上面的两个事实就分别表示“约翰是学生”和“玛丽喜欢音乐”。,作为特殊情形，一个事实也可以只有谓词名而无参量。,例如：,abc.,repeat.,等也是允许的。,,45,页,功能 一般表示对象的性质或关系。,45,2. 规则(rule),格式():-(){,()}.,其中“:-”号表示“if”（也可以直接写为if），其左部的谓词是规则的结论（亦称为头），右部的谓词是规则的前提（亦称为体），{}表示零次或多次重复，逗号表示and(逻辑与),即规则的形式是一个逻辑蕴含式。,,,46,页,2. 规则(ru

27、le)46页,46,例如：,bird(X):-animal(X),has(X,feather).,grandfather(X,Y):-father(X,Z),father(Z,Y).,就是PROLOG的合法规则。,,47,页,例如：47页,47,功能一般表示对象间的因果关系、蕴含关系或对应关系。,例如，上面的第一条规则就表示“如果X是动物，并且X有羽毛，则X是鸟”；第二条规则就表示“X是Y的祖父，如果存在Z，X是Z的父亲并且Z又是Y的父亲”。作为特殊情形，规则中的谓词也可以只有谓词名而无参量。,例如：,run:-start,step1(X),step2(X),end.,也是一个合法规则。,

28、,48,页,功能一般表示对象间的因果关系、蕴含关,48,3.问题(question),格式?-(){,()}.,例如：,?-student(john).,?-like(mary,X).,就是两个合法的问题。,功能 问题表示用户的询问，它就是程序运行的目标。,,,49,页,3.问题(question)49页,49,,2.3.2 PROLOG程序,PROLOG程序一般由一组事实、规则和问题组成。问题是程序执行的起点，称为程序的目标。,例如下面就是一个PROLOG程序。,likes(bell,sports).,likes(mary,music).,likes(mary,sports).,like

29、s(jane ,smith).,friend(john,X):-likes(X,reading),likes(X,music).,friend(john,X):-likes(X,sports),likes(X,music).,?-friend(john,Y).,,50,页,2.3.2 PROLOG程序50页,50,可以看出，这个程序中有四条事实、两条规则和一个问题。其中事实、规则和问题都分行书写。规则和事实可连续排列在一起，其顺序可随意安排，但同一谓词名的事实或规则必须集中排列在一起。问题不能与规则及事实排在一起，它作为程序的目标要么单独列出，要么在程序运行时临时给出。,,51,页,可以看出，

30、这个程序中有四条事实、两条,51,这个程序的事实描述了一些对象（包括人和事物）间的关系；而规则则描述了john交朋友的条件，即如果一个人喜欢读书并且喜欢音乐（或者喜欢运动和喜欢音乐），则这个人就是john的朋友（当然，这个规则也可看作是john朋友的定义）；程序中的问题是“约翰的朋友是谁？”,当然，PROLOG程序中的目标可以变化，也可以含有多个语句(上例中只有一个)。如果有多个语句，则这些语句称为子目标。例如对上面的程序，其问题也可以是,,,52,页,这个程序的事实描述了一些对象（包括人,52,?-likes(mary,X).,或,?-likes(mary,music).,或,?-fri

31、end(X,Y).,或,?-likes(bell,sports),,likes(mary,music),,friend(john,X).,等等。当然，对于不同的问题，程序运行的结果一般是不一样的。,,53,页,?-likes(mary,X).53,53,2.3.3 PROLOG程序的运行机理,既然PROLOG程序是基于Horn子句的逻辑程序，那么其运行机理自然就是基于归结原理的演绎推理（归结原理将在第3章介绍）。下面我们就来看PROLOG程序是怎样运行的。,PROLOG程序的运行是从目标出发，并不断进行匹配、合一、归结，有时还要回溯，直到目标被完全满足或不能满足时为止。那么，什么是匹配

32、、合一和回溯呢？下面我们就先介绍这几个概念。,,,54,页,2.3.3 PROLOG程序的运行机理54页,54,1. 自由变量与约束变量,PROLOG中称无值的变量为自由变量，有值的变量为约束变量。一个变量取了某值就说该变量约束于某值，或者说该变量被某值所约束，或者说该变量被某值实例化了。,,,55,页,1. 自由变量与约束变量55页,55,2. 匹配合一,两个谓词可匹配合一，是指两个谓词的名相同，参量项的个数相同，参量类型对应相同，并且对应参量项还满足下列条件之一：,(1)如果两个都是常量，则必须完全相同。,(2)如果两个都是约束变量，则两个约束值必须相同。,(3)如果其中一个是常量，一个

33、是约束变量，则约束值与常量必须相同。,(4)至少有一个是自由变量。,,,56,页,2. 匹配合一56页,56,例如：下面的两个谓词,pre1("ob1","ob2",Z),pre1("ob1",X,Y),只有当变量X被约束为"ob2"，且Y、Z的约束值相同或者至少有一个是自由变量时，它们才是匹配合一的。,,57,页,例如：下面的两个谓词57页,57,3. 回溯,所谓回溯，就是在程序运行期间，当某一个子目标不能满足（即谓词匹配失败）时，控制就返回到前一个已经满足的子目标（如果存在的话），并撤消其有关变量的约束值，然后再使其重新满足。成功后，再继续满足原子目标。如果失败的子目标前再无子目标，则控

34、制就返回到该子目标的上一级目标（即该子目标谓词所在规则的头部）使它重新匹配。回溯也是PROLOG的一个重要机制。,,,58,页,3. 回溯58页,58,下面，我们介绍PROLOG程序的运行过程。我们仍以上面的程序为例。设所给的询问是,?-friend(john,Y).(john和谁是朋友?),则求解目标为,friend(john,Y).,这时，系统对程序进行扫描，寻找能与目标谓词匹配合一的事实或规则头部。显然，程序中前面的四条事实均不能与目标匹配，而第五个语句的左端即规则,,,59,页,下面，我们介绍PROLOG程序的运行,59,friend(john,X):-likes(X,readin

35、g),likes(X,music).,的头部可与目标谓词匹配合一。但由于这个语句又是一个规则，所以其结论要成立则必须其前提全部成立。于是，对原目标的求解就转化为对新目标,likes(X,reading),likes(X,music).,的求解。这实际是经归结，规则头部被消去，而目标子句变为,?-likes(X,reading),likes(X,music).,现在依次对子目标,likes(X,reading)和likes(X,music),求解。,,60,页,friend(john,X):-like,60,子目标的求解过程与主目标完全一样，也是从头对程序进行扫描，不断进行测试和匹配合一

36、等，直到匹配成功或扫描完整个程序为止。可以看出，对第一个子目标like(X,reading)的求解因无可匹配的事实和规则而立即失败，进而导致规则,friend(john,X):-likes(X,reading),likes(X,music).,的整体失败。于是，刚才的子目标,likes(X,reading)和likes(X,music),,61,页,子目标的求解过程与主目标完全一样，,61,被撤消，系统又回溯到原目标friend(john,X)。这时，系统从该目标刚才的匹配语句处（即第五句）向下继续扫描程序中的子句，试图重新使原目标匹配，结果发现第六条语句的左部，即规则,friend(jo

37、hn,X):-likes(X,sports),likes(X,music).,的头部可与目标为谓词匹配。但由于这个语句又是一个规则，于是，这时对原目标的求解，就又转化为依次对子目标,likes(X,sports)和likes(X,music),,,62,页,被撤消，系统又回溯到原目标frien,62,的求解。这次子目标likes(X,sports)与程序中的事实立即匹配成功，且变量X被约束为bell。于是，系统便接着求解第二个子目标。由于变量X已被约束，所以这时第二个子目标实际上已变成了,likes(bell,music).,由于程序中不存在事实likes(bell,music)，所以该

38、目标的求解失败。于是，系统就放弃这个子目标，并使变量X恢复为自由变量，然后回溯到第一个子目标，重新对它进行求解。由于系统已经记住了刚才已同第一子目标谓词匹配过的事实的位置，所以重新求解时，便从下一个事实开始测试。,,63,页,的求解。这次子目标likes(X,sports)与,63,易见，当测试到程序中第三个事实时，第一个子目标便求解成功，且变量X被约束为mary。这样，第二个子目标也就变成了,likes(mary,music).,再对它进行求解。这次很快成功。,由于两个子目标都求解成功，所以，原目标friend(john,Y)也成功，且变量Y被约束为mary(由Y与X的合一关系)。于是，系

39、统回答： Y=mary,程序运行结束。,上面只给出了问题的一个解。如果需要和可能的话，系统还可把john的所有朋友都找出来。我们把上述程序的运行过程再用示意图（图2─1）描述如下：,,,64,页,易见，当测试到程序中第三个事实时，第,64,图2─1 PROLOG程序运行机理示例,,65,页,图2─1 PROLOG程序运行机理示例 65页,65,上述程序的运行是一个通过推理实现的求值过程。我们也可以使它变为证明过程。,例如，把上述程序中的询问改为,friend(john,mary),则系统会回答:yes,若将询问改为：,friend(john,smith),则系统会回答:no,

40、,,66,页,上述程序的运行是一个通过推理实现的求值,66,从上述程序的运行过程可以看出，PROLOG程序的执行过程是一个（归结）演绎推理过程。其特点是：推理方式为反向推理，控制策略是深度优先，且有回溯机制。其具体实现方法是：匹配子句的顺序是自上而下；子目标选择顺序是从左向右；（归结后）产生的新子目标总是插入被消去的目标处（即目标队列的左部）。PROLOG的这种归结演绎方法被称为SLD(LinearresolutionwithSelectionfunctionforDefiniteclause)归结，或SLD反驳-消解法。SLD归结就是PROLOG程序的运行机理，它也就是所谓的PROLOG语言

41、的过程性语义。,,,67,页,从上述程序的运行过程可以看出，PRO,67,2.4 Turbo PROLOG程序设计,2.4.1 Turbo PROLOG的程序结构,一个完整的Turbo PROLOG(2.0版)程序一般包括常量段、领域段、数据库段、谓词段、目标段和子句段等六个部分。各段以其相应的关键字constants、domains、database、predicates、goal和clauses开头加以标识。：,,68,页,2.4 Turbo PROLOG程序设计 2.,68,另外，在程序的首部还可以设置指示编译程序执行特定任务的编译指令；在程序的任何位置都可设置

42、注解。总之，一个完整的TurboPROLOG(2.0版)程序的结构如下,/**/,,constants,,domains,,database,,,69,页,另外，在程序的首部还可以设置指示编译,69,,predicates,,goal,,clauses,,,,70,页,70页,70,当然，一个程序不一定要包括上述所有段，但一个程序至少要有一个predicates段、clauses段和goal段。在大多数情形中，还需要一个domains段，以说明表、复合结构及用户自定义的域名。如若省略goal段，则可在程序运行时临时给出，但这仅当在开发环境中运行程序时方可给出。若要生成一个独立的可执行文件，则在

43、程序中必须包含goal段。另一方面，一个程序也只能有一个goal段。,,,71,页,当然，一个程序不一定要包括上述所有段,71,,例2.3 如果把上节中的程序要作为TurboPROLOG程序，则应改写为：,/*例子程序-1*/,DOMAINS,name=symbol,PREDICATES,likes(name,name).,friend(name,name),GOAL,friend(john,Y),write(″Y=″,Y).,,,72,页,例2.3 如果把上节中的程序要作,72,CLAUSES,likes(bell,sports).,likes(mary,music).,likes(ma

44、ry,sports).,likes(jane,smith).,friend(john,X):-likes(X,sports),likes(X,music).,friend(john,X):-likes(X,reading),likes(X,music).,,73,页,CLAUSES73页,73,结合上例，我们再对上述程序结构中的几个主要段的内容和作用加以说明(其余段在后面用到时再作说明)：,领域段该段说明程序谓词中所有参量项所属的领域。领域的说明可能会出现多层说明，直到最终说明到Turbo PROLOG的标准领域为止(如上例所示)。Turbo PROLOG的标准领域即标准数据类型，包括整数、实

45、数、符号、串和符号等，其具体说明如表2.1所示。,,,74,页,结合上例，我们再对上述程序结构中的几,74,表2.1 Turbo PROLOG的标准领域,,75,页,表2.1 Turbo PROLOG的标准领域 75页,75,谓词段该段说明程序中用到的谓词的名和参量项的名(但Turbo PROLOG的内部谓词无须说明)。,子句段该段是Turbo PROLOG程序的核心，程序中的所有事实和规则就放在这里，系统在试图满足程序的目标时就对它们进行操作。,,,76,页,谓词段该段说明程序中用到的谓词的名和,76,,目标段,该段是放置程序目标的地方。目标段可以只有一个目标谓词，例如上面的例子中就只有一个

46、目标谓词；也可以含有多个目标谓词，如：,goal,readint(X),Y=X+3,write("Y=",Y).,就有三个目标谓词。这种目标称为复合目标。,另外，一般称程序目标段中的目标为内部目标，而称在程序运行时临时给出的目标为外部目标。,,77,页,目标段 该段是放置程序目标的地方。目,77,2.4.2 Turbo PROLOG的数据与表达式,1.领域,1)标准领域,Turbo PROLOG中不定义变量的类型，只说明谓词中各个项的取值域。,2)结构,结构也称复合对象，它是TurboPROLOG谓词中的一种特殊的参量项（类似于谓词逻辑中的函数）。,,78,页,2.4.2 Turbo P

47、ROLOG的数据与表达式78,78,结构的一般形式为,(),其中函子及参量的标识符与谓词相同。注意，这意味着结构中还可包含结构。所以，复合对象可表达树形数据结构。例如下面的谓词,likes(Tom,sports(football,basketball,table-tennis)).,中的,sports(football,basketball,table-tennis),就是一个结构,即复合对象。,,79,页,结构的一般形式为79页,79,又如：,person("张华",student("西安石油学院"),address("中国","陕西","西安")).,reading("王宏",boo

48、k("人工智能技术基础教程","西安电子科技大学出版社")).,friend(father("Li"),father("Zhao")).,这几个谓词中都有复合对象。,,80,页,又如：80页,80,复合对象在程序中的说明，需分层进行。例如，对于上面的谓词,likes(Tom,sports(football,basketball,table-tennis)).,在程序中可说明如下：,domains,name=symbol,sy=symbol,sp=sports(sy,sy,sy),predicates,likes(name,sp),,,81,页,复合对象在程序中的说明，需分层进行。,81,3

49、) 表,表的一般形式是,［x,1,,x,2,,…,x,n,］,其中x,i,(i=1,2,…,n)为PROLOG的项，一般要求同一个表的元素必须属于同一领域。,不含任何元素的表称为空表，记为［］。例如下面就是一些合法的表。,,82,页,3) 表82页,82,［1,2,3］,［apple,orange,banana,grape,cane］,［"PROLOG","MAENS","PROGRAMMING","in logic"］,［［a,b］,［c,d］,［e］］,［］,表的最大特点是其元素个数可在程序运行期间动态变化。表的元素也可以是结构或表，且这时其元素可以属于不同领域。,,83,页,［1,2

50、,3］83页,83,例如：,［name("Li Ming"),age(20),sex(male),address(xi an)］,［［1,2］,［3,4,5］,［6,7］］,都是合法的表。后一个例子说明，表也可以嵌套。,实际上，表是一种特殊的结构。它是递归结构的另一种表达形式。这个结构的函数名取决于具体的PROLOG版本。这里我们就用一个圆点来表示。,,84,页,例如：84页,84,下面就是一些这样的结构,及它们的表表示形式：,结构形式 表形式,·(a,［］) ［a］,·(a,·(b,［］))

51、 ［a,b］,·(a,·(b,·(c,［］))) ［a,b,c］,,,85,页,下面就是一些这样的结构85页,85,表的说明方法是在其组成元素的说明符后加一个星号*。如：,domains,lists=string*,predicates,pl(lists),就说明谓词pl中的项lists是一个由串string组成的表。,,86,页,表的说明方法是在其组成元素的说明符后,86,对于由结构组成的表，至少得分三步说明。例如对于下面谓词p中的表,p(［name("Liming"),age(20)］),则需这样说明:,domains,rec=seg*,s

52、eg=name(string);age(integer),predicates,p(rec),,,87,页,对于由结构组成的表，至少得分三步说明,87,2. 常量与变量,由上面的领域可知，Turbo PROLOG的常量有整数、实数、字符、串、符号、结构、表和文件这八种数据类型。同理，Turbo PROLOG的变量也就有这八种取值。另外，变量名要求必须是以大写字母或下划线开头的字母、数字和下划线序列，或者只有一个下划线。这后一种变量称为无名变量。,,,88,页,2. 常量与变量88页,88,3. 算术表达式,Turbo PROLOG提供了五种最基本的算术运算：加、减、乘、除和取模，相应运算符号为

53、+、-、*、/、mod。这五种运算的顺序为：*、/、mod优先于+、-。同级从左到右按顺序运算，括号优先。算术表达式的形式与数学中的形式基本一样。例如：,数学中的算术表达式 PROLOG中的算术表达式,x+y z X+Y*Z,ab-c/d A*B-C/D,u mod v U mod V(表示求U除,以V所得的余数),

54、,,89,页,3. 算术表达式89页,89,即是说，Turbo PROLOG中算术表达式采用通常数学中使用的中缀形式。这种算术表达式为PROLOG的一种异体结构，若以PROLOG的结构形式来表示，则它们应为,+(X,*(Y,Z)),-(*(A,B),/(C,D)),mod(U,V),所以，运算符+、-、*、/和mod实际也就是PROLOG内部定义好了的函数符。,,,90,页,即是说，Turbo PROLOG中,90,在Turbo PROLOG程序中，如果一个算术表达式中的变元全部被实例化（即被约束）的话，则这个算术表达式的值就会被求出。求出的值可用来实例化某变量，也可用来同其他数量进行比较，

55、用一个算术表达式的值实例化一个变量的方法是用谓词“is”或“=”来实现。例如：,Y is X+5,或,Y=X+5 (*),,91,页,在Turbo PROLOG程序中，,91,就使变量Y实例化为X+5的值(当然X也必须经已被某值实例化)，可以看出，这里对变量Y的实例化方法类似于其他高级程序语言中的“赋值”，但又不同于赋值。例如，在PROLOG中下面的式子是错误的:,X=X+1,,,92,页,就使变量Y实例化为X+5的值(当然X,92,4. 关系表达式,Turbo PROLOG提供了六种常用的关系运算，即小于、小于或等于、等于、大于、大于或等于和不等于，其运算符依次为,,

56、>=,,Turbo PROLOG的关系表达式的形式和数学中的也基本一样，例如：,数学中的关系式 Turbo PROLOG中的关系式,X+1≥Y X+1>=Y,X≠Y XY,,,93,页,4. 关系表达式93页,93,即是说，Turbo PROLOG中的关系式也用中缀形式。当然，这种关系式为Turbo PROLOG中的异体原子。若按Turbo PROLOG中的原子形式来表示，则上面的两个例子为,>=(X+1,Y)和(

57、X,Y),所以上述六种关系运算符，实际上也就是Turbo PROLOG内部定义好了的六个谓词。这六个关系运算符可用来比较两个算术表达式的大小。,,94,页,即是说，Turbo PROLOG中的,94,所以上述六种关系运算符，实际上也就是Turbo PROLOG内部定义好了的六个谓词。这六个关系运算符可用来比较两个算术表达式的大小。例如：,brother(Name1,Name2):-person(Name1,man,Age1),,person(Name2,man,Age2),,mother(Z,Name1),mother(Z,Name2),,Age1>Age2.,需要说明的是，“=”的用法比较特

58、殊，它既可以表示比较，也可以表示约束值，即使在同一个规则中的同一个“=”也是如此。,,95,页,所以上述六种关系运算符，实际上也就是,95,例如：,p(X,Y,Z):-Z=X+Y.,当变量X、Y、Z全部被实例化时，“=”就是比较符。如：对于问题,Goal:p(3,5,8).,机器回答：yes。而对于,Goal:p(3,5,7).,机器回答：no。,即这时机器把X+Y的值，与Z的值进行比较。,,96,页,例如：96页,96,但当X,Y被实例化，为Z未被实例化时，“=”,号就是约束符。如：,Goal:p(3,5,Z).,机器回答：Z=8,这时，机器使Z实例化为X+Y的结果。,,,97,页,

59、但当X,Y被实例化，为Z未被实例化时，“=”97页,97,2.4.3 输入与输出,虽然PROLOG能自动输出目标子句中的变量的值，但这种输出功能必定有限，往往不能满足实际需要；另一方面，对通常大多数的程序来说，运行时从键盘上输入有关数据或信息也是必不可少的。为此每种具体PROLOG一般都提供专门的输入和输出谓词，供用户直接调用。例如，下面就是TorboPROLOG的几种输入输出谓词：,,98,页,2.4.3 输入与输出98页,98,(1) readln (X)。,这个谓词的功能是从键盘上读取一个字符串，然后约束给变量X。,(2) readint (X)。,这个谓词的功能是从键盘上读取一个整

60、数，然后约束给变量X，如果键盘上打入的不是整数则该谓词失败。,(3) readreal (X)。,这个谓词的功能是从键盘上读取一个实数，然后约束给变量X，如果键盘上打入的不是实数则该谓词失败。,,,,99,页,(1) readln (X)。99页,99,(4) readchar(X)。,这个谓词的功能是从键盘上读取一个字符，然后约束给变量X，如果键盘上打入的不是单个字符，则该谓词失败。,(5) write(X,1,,X,2,,…　X,n,)。,这个谓词的功能是把项X,i,(i=1,2,…n)的值显示在屏幕上或者打印在纸上，当有某个X,i,未实例化时，该谓词失败，其中的X,i,可以是变量，也可以

61、是字符串或数字。,,100,页,(4) readchar(X)。10,100,(6) nl换行谓词。它使后面的输出(如果有的话)另起一行。另外，利用write的输出项"\n"也同样可起换行作用。例如：,write("name"), n l ,write("age"),与,write("name","\n","age"),的效果完全一样。,,,101,页,(6) nl换行谓词。它使后面的输出(,101,例2.4用上面的输入输出谓词编写一个简单的学生成绩数据库查询程序。,PREDICATES,student(integer,string,real),grade,GOAL,grade.,CLAU

62、SES,,,102,页,例2.4用上面的输入输出谓词编写一个,102,student(1,"张三",90.2).,student(2,"李四",95.5).,student(3,"王五",96.4).,grade:-write("请输入姓名:"),readln(Name),,student(-,Name,Score),,nl,write(Name,"的成绩是",Score).,grade:-write(“对不起，找不到这个学生!”).,grade:-write("对不起，找不到这个学生!").,下面是程序运行时的屏幕显示:,请输入姓名： 王五,王五的成绩是96.4。,,103,页,stud

63、ent(1,"张三",90.2).103页,103,2.4.4 分支与循环,PROLOG中并无专门的分支和循环语句，但PROLOG也可实现分支和循环程序结构。,1.分支,对于通常的IF-THEN-ELSE分支结构，PROLOG可用两条同头的并列规则实现。例如，将,IF x>0THENx:=1,ELSE x:=0,,,104,页,2.4.4 分支与循环104页,104,用PROLOG实现则是,Br :-x>0,x=1.,Br :-x=0.,类似地，对于多分支，可以用多条规则实现。例如：,Br :-x>0,x=1.,Br :-x=0,x=0.,Br :-x<0,x=-1.,,,105,页,用

64、PROLOG实现则是105页,105,2.循环,PROLOG可以实现计循环次数的FOR循环，也可以实现不计循环次数的DO循环。,例如下面的程序段就实现了循环，它使得write语句重复执行了三次，而打印输出了三个学生的记录。,student(1,"张三",90.2).,student(2,"李四",95.5).,student(3,"王五",96.4).,print:-student(Number,Name,Score),,write(Number,Name,Score),n l ,,Number=3.,,,106,页,2.循环106页,106,这个例子可以看作是计数循环。当然，也可以通过设置计

65、数器而实现真正的计数循环。下面的程序段实现的则是不计数的DO循环。,student(1,"张三",90.2).,student(2,"李四",95.5).,student(3,"王五",96.4).,print:-student(Number,Name,Score),,write(Number,Name,Score),nl,,fail.,print:-.,,107,页,这个例子可以看作是计数循环。当然，也,107,这个程序段中的fail是一个内部谓词，它的语义是恒失败。这个程序段与上面的程序段的差别仅在于把原来用计数器（或标记数）循环控制语句变成了恒失败谓词fail，另外再增加了一个print

66、语句。增加这个语句的目的是为程序设置一个出口。因为fail是恒失败，下面若无出口的话，将引起print本身的失败。进而又会导致程序中的连锁失败。,,108,页,这个程序段中的fail是一个内部谓词,108,2.4.5 动态数据库,动态数据库就是在内存中实现的动态数据结构。它由事实组成，程序可以对它操作，所以在程序运行期间它可以动态变化。Turbo PROLOG提供了三个动态数据库操作谓词:,asserta ().,assertz ().,retract ().,,109,页,2.4.5 动态数据库109页,109,其中fact表示事实。这三个谓词的功能是：,asserta ().把fact插入当前动态数据库中的同名谓词的事实之前；,assertz ().把fact插入当前动态数据库中的同名谓词的事实之后；,retract().把fact从当前动态数据库中删除。,,110,页,其中fact表示事实。这三个谓词的功能,110,例如语句,asserta(student(20,"李明",90.5)).,将在内存的谓词名为student的事实前插入一个新事实：,student(20,"李明