人工智能程序设计语言150

第2章人工智能程序设计语言第2章人工智能程序设计语言2.1综述2.2函数型程序设计语言LISP2.3逻辑型程序设计语言PROLOG2.4TurboPROLOG程序设计第2章人工智能程序设计语言2.1综述2.1.1函数型语言LISP是一种函数型程序设计语言。LISP程序由一组函数组成，程序的执行过程就是一系列的函数调用和求值过程。但LISP还不是纯函数型语言，准确地讲，它是基于λ--函数的语言。除LISP外，20世纪70年代J.Backus还提出了一种称为FP的所谓纯函数型程序设计语言。但该语言现在还限于理论研究，实现上还存在一定困难。第2章人工智能程序设计语言2.1.2逻辑型语言逻辑型程序设计语言起源于PROLOG(PROgramminginLOGic的缩写)。PROLOG语言首先由法国马塞大学的Colmerauer和它的研究小组于1972年研制成功，后来在欧洲得到进一步发展。特别是1981年日本宣布要以PROLOG作为他们正在研制的新一代计算机——智能计算机的核心语言，更使PROLOG举世瞩目，迅速风靡世界。第2章人工智能程序设计语言PROLOG语言是以Horn子句逻辑为基础的程序设计语言，它是目前最具代表性的一种逻辑程序设计语言。早期PROLOG版本都是解释型的，1986年美国的Borland公司推出了编译型PROLOG-TurboPROLOG，并很快成为PC机上流行的PROLOG。现在运行在Windows环境下的可视化编程语言VisualPROLOG也已面世。但这些PROLOG语言版本属顺序逻辑程序设计语言。第2章人工智能程序设计语言2.1.3面向对象语言20世纪80年代以来，面向对象程序设计(ObjectOrientedProgramming，简称OOP)异军突起，发展迅速，如今已日渐成熟，并越来越流行起来。面向对象程序以其信息隐蔽、封装、继承、多态、消息传递等一系列优良机制，大大改善了软件的复杂性、模块性、重用性和可维护性，有望从根本上解决软件的生产效率问题。另一方面，由于面向对象程序设计的类、对象、继承等概念，与人工智能特别是知识表示和知识库产生了天然的联系。第2章人工智能程序设计语言因而，现在面向对象程序设计语言也成为一种人工智能程序设计语言，面向对象程序设计也被广泛引入人工智能程序设计，特别是知识工程、专家系统程序设计。面向对象程序设计语言也种类繁多，已发展成为一个大家族。其中最纯正、最具面向对象风格的语言当推Smalltalk，而最流行的OOP语言是C++，Java则是适于网络(Internet)环境的一种面向对象语言。第2章人工智能程序设计语言2.1.4混合型语言以上三种语言都各有所长，但也都有其不足之处。为了扬长避短，于是便出现了基于这三种语言的混合型语言。1.函数型与逻辑型相结合的语言函数型与逻辑型语言的结合方式有耦合型和统一型两类。统一型又可分为具有归结语义的函数型语言和集成式语言两个子类。第2章人工智能程序设计语言2.函数型与面向对象相结合的语言在LISP语言的基础上再扩充面向对象机制而产生的语言，称为函数型的面向对象程序设计语言(亦称为面向对象的LISP)。3.逻辑型与面向对象相结合的语言第2章人工智能程序设计语言2.2函数型程序设计语言LISPLISP语言的主要特点是：(1)LISP程序由一组函数组成，程序的执行过程是函数的调用过程。(2)程序和数据在形式上是相同的，即都是符号表达式，简称为S─表达式。(3)递归是LISP语言的主要控制结构。(4)程序以交互方式运行。第2章人工智能程序设计语言2.2.1LISP的程序结构与运行机制LISP的程序一般由函数的定义和函数的调用两部分组成。其一般格式为：(DEFUN(函数名(形参表)函数体)(函数名(〖WB〗形参表)函数体)…(函数名(形参表)函数体))(函数名实参表)(函数名实参表)…(函数名实参表)第2章人工智能程序设计语言其中的“DEFUN”是定义函数的关键字，“函数名”可以是系统的内部函数(名)，也可以是用户用DEFUN定义的函数(名)。例如下面就是一个LISP程序。(DEFUNHANOI(abcn)(COND((=n1)(MOVE-DISKac))(T(HANOIacb(-n1))(MOVE-DISKac)(HANOIbac(-n1))))第2章人工智能程序设计语言(DEFUNMOVE-DISK(fromto)(TERPRI)(PRINC″MoveDiskFrom″)(PRINCfrom)(PRINCTo)(PRINCto))(HANOI′a′b′c3)第2章人工智能程序设计语言2.2.2S─表达式从语法上看，LISP程序的基本单位是S─表达式。S─表达式又可分为原子和表两大类。原子(atom)是由字母和数字组成的字符串，是S─表达式的最简单情况。原子又可分为文字原子、串原子和数字原子三种。文字原子又称符号（symbol），是以字母开头的字母数字串，用来表示常量、变量和函数的名字等。例如：ABC、X1等。第2章人工智能程序设计语言串原子是由双引号括起来的一串字符。如LISPProgram。数字原子由数字串组成。在其前面可以有符号“-”或“+”，中间可出现“.”，用来表示整数和实数。例如：256、-66、3.14159等。第2章人工智能程序设计语言S─表达式可以递归定义如下：(1)原子是S─表达式。(2)若S1和S2是S─表达式，则(S1·S2)也是S─表达式。由定义，下面的式子都是S─表达式：X2123(A·B)(A·(B·C))第2章人工智能程序设计语言表(list)是LISP语言中最常用的数据类型，也是主要的处理对象。表是由圆括号括起来的由空格分开的若干个元素的集合。表的一般形式为：(S─表达式S─表达式…S─表达式)第2章人工智能程序设计语言例如：(XYZ),(+12),(A(BC))左括号后面的第一个元素称为表头，其余的元素组成的表称为表尾。例如，对于表(+12)的头为+，尾为(12)。特别地，元素个数为零的表为空表，记为()或NIL。表是一种特殊的S─表达式，每一个表都对应着一个S─表达式。二者的关系由下面的例子说明。第2章人工智能程序设计语言表←————————————→S-表达式(A)(A·NIL)(AB)(A·(B·NIL))(ABC)(A·(B·(C·NIL)))((AB)CD)((A·(B·NIL))·(C·(D·NIL)))可以看出，表的S─表达式的结构实际是一棵二叉树。第2章人工智能程序设计语言2.2.3基本函数LISP的函数都以表的形式出现，并一律使用前缀表示方式，即表头为函数名，并且每个函数都有一个返回值。LISP的函数可分为语言自身提供的内部函数(称为基本函数或系统函数)和用户自定义函数两类。基本函数的种类有十多个，下面仅给出其中主要的几类。1.表处理函数表处理是LISP的主要特色，表处理的函数也很多，下面仅给出最常用的几个。第2章人工智能程序设计语言1)CAR函数格式(CAR表)其中CAR为函数名，它是一个保留字（下同）。功能取出表中的表头。例如：(CAR′(LISPLanguageProgram))返回值为：LISP第2章人工智能程序设计语言2)CDR函数格式(CDR表)功能取出表中的表尾。例如：(CDR′(LISPLanguageProgram))返回值为：(LanguageProgram)3)CONS函数格式(CONSS─表达式表)功能将S─表达式作为一个元素加到表中去，并作为所构成新表中的第一个元素。例如：(CONS′My′(LISPLanguageProgram))返回值为：(MyLISPLanguageProgram)第2章人工智能程序设计语言4)APPEND函数格式(APPEND表1表2…表n)功能将n个表中的元素合并成一个新表。例如：(APPEND′(TIGERLION)′(DOGCAT))返回值为：(TIGERLIONDOGCAT)第2章人工智能程序设计语言5)LIST函数格式(LISTS─表达式1S─表达式2…S表达式n)功能把n个S─表达式作为元素括在一起构成一张新表。例如：(LIST′YELLOW′RED′BLUE)返回值为：(YELLOWREDBLUE)第2章人工智能程序设计语言2.算术函数LISP的算术表达式也是用函数表示的，称为算术函数。下面我们仅举例说明。(+25)表示2+5，返回值为7。(-(*48)(/105))表示4×8-10/5，返回值为30。第2章人工智能程序设计语言3.求值与赋值函数在上面的函数中多次出现撇号′，它的意思是禁止求值。为什么要禁止求值呢？原来，LISP总是试图对一切S─表达式求值。表的值是通过函数运算而得到的，原子的值则是通过赋值函数实现的。撇号′也是一个函数，它实际是禁止求值函数QUOTE的简写形式。赋值函数有多个，其中SET函数是一个最基本的赋值函数。第2章人工智能程序设计语言格式(SET变量S─表达式)功能把S─表达式赋给变量。例如：(SET′X′8);X得到值8(SET′Y′(abc));Y得到值(abc)(SET′Z(CDRY);Z得到值(bc)另外，赋值函数还有SETQ、SETF(COMMONLISP)，其功能是类似的。第2章人工智能程序设计语言4.谓词函数返回值为逻辑值真或假的函数称为谓词函数，简称谓词。LISP中真和假分别用T和NIL表示，当函数的返回值为非NIL时，也表示为真。另外，NIL也表示空表。谓词函数也有多个，下面我们仅给出常用的几个。第2章人工智能程序设计语言(1)原子谓词ATOM格式(ATOM参数)功能检测其参数是否为原子，是则返回T，否则返回NIL。例如：(ATOM′a);返回T(ATOM′(ab));返回NIL第2章人工智能程序设计语言(2)相等谓词EQUAL格式(EQUAL参数参数)功能判断两个参数是否逻辑相等。例如：(EQUAL′a′a);返回T(EQUAL′(ab)′(ac));返回NIL(EQUAL′(ab)(CONS′a′(b)));返回T还有一种相等谓词，其格式为：(EQ参数参数)，但它只是用来判断两个原子是否相等。例如：(EQ′a′a)，则返回T第2章人工智能程序设计语言(3)判空表函数NULL格式(NULL参数)功能判断参数是否为空表，是则返回T，否则返回NIL。第2章人工智能程序设计语言5.条件函数条件函数也称分支函数，类似于其他语言中的分支语句，其作用是控制程序的流程。格式(COND(P1e1)(P2e2)…(Pnen))其中Pi(i=1,...,n)为谓词，ei(i=1,...,n)为一个或多个S─表达式。第2章人工智能程序设计语言功能如果P1为真，则COND函数的值为e1(当e1为多个S─表达式时，取最后一个S─表达式的值，下同)。否则，判断P2，……直到某个Pi真为止，然后将对应的ei作为函数值。若没有一个Pi的值为非NIL，则COND的返回值为NIL。特别地，Pi也可以为逻辑常量T，这时则对其对应的各表达式求值，并把最后一个表达式的值作为COND的返回值。第2章人工智能程序设计语言例如：(COND((NULLx)0)((ATOMx)1)((LISTPx)(LENGTHx)))其语义是，若x的值为NIL，则COND的返回值为0;若x为原子，则COND的返回值为1;若x的值为表，则COND的返回值为表的长度。第2章人工智能程序设计语言2.2.4自定义函数基本函数是LISP提供的基本处理功能，要用LISP编程解决实际问题，仅有基本函数还是不够的，用户还必须根据问题的需要，利用基本函数自定义所需的函数。自定义函数的格式为：(DEFUN函数名(形参表)函数体)第2章人工智能程序设计语言其中函数体，又可能是用户自定义的函数或LISP基本函数的某种组合。所以，一般来讲，LISP自定义函数就是由其基本函数组合而成的。常用的组合方法有复和、