智能程序设计语言课件

16.1 综综 述述 16.1.1 16.1.1 函数型语言函数型语言 LISP是一种函数型程序设计语言。LISP程序由一组函数组成,程序的执行过程就是一系列的函数调用和求值过程。但 LISP还不是纯函数型语言,准确地讲,它是基于函数的语言。除LISP外,20世纪70年代J.Backus还提出了一种称为FP的所谓纯函数型程序设计语言。但该语言现在还限于理论研究,实现上还存在一定困难。16.1.2 16.1.2 逻辑型语言逻辑型语言逻辑型程序设计语言起源于PROLOG(PROgramming in LOGic)。PROLOG语言首先由法国马塞大学的Colmerauer和它的研究小组于1972年研制成功,后来在欧洲得到进一步发展。特别是1981年日本宣布要以PROLOG作为他们正在研制的新一代计算机智能计算机的核心语言,更使PROLOG举世瞩目,迅速风靡世界。现在PROLOG几乎在人工智能的所有领域都获得了应用,成为与LISP并驾齐驱的甚至更加流行的智能程序设计语言。由于PROLOG语言是一种逻辑型程序设计语言,因此用它编写的程序也就是逻辑程序,即在PROLOG程序中一般不需告诉计算机“怎么做”,而只需告诉它“做什么”。因此,PROLOG亦属陈述性语言。与通常的过程性程序设计语言相比,PROLOG是更高级的语言。PROLOG语言是以Horn子句逻辑为基础的程序设计语言,它是目前最具代表性的一种逻辑程序设计语言。早期PROLOG版本都是解释型的,1986 年美国的Borland公司推出了编译型PROLOG-Turbo PROLOG,并很快成为PC机上流行的PROLOG。现在还有运行在Windows环境下的可视化编程语言Visual PROLOG。但这些PROLOG语言版本属顺序逻辑程序设计语言。为了进一步提高运行效率和推理速度,从20世纪80年代初起,人们开始研制并行逻辑程序设计语言。目前已开发出了不少并行逻辑语言,其中比较著名和成熟的有PARLOG(PARallel LOGical programming language)、ConcurrentPROLOG、GHC(Guarded Horn Clauses)等。16.1.3 16.1.3 面向对象语言面向对象语言20 世 纪 80 年 代 以 来,面 向 对 象 程 序 设 计(ObjectOriented Programming,OOP)异军突起,发展迅速,如今已日渐成熟,并越来越流行起来。面向对象程序以其信息隐蔽、封装、继承、多态、消息传递等一系列优良机制,大大改善了软件的复杂性、模块性、重用性和可维护性,有望从根本上解决软件的生产效率问题。另一方面,由于面向对象程序设计的类、对象、继承等概念,与人工智能特别是知识表示和知识库产生了天然的联系。因而,现在面向对象程序设计语言也成为一种人工智能程序设计语言,面向对象程序设计也被广泛引入人工智能程序设计,特别是知识工程、专家系统程序设计。面向对象程序设计语言也种类繁多,已发展成为一个大家族。其中最纯正、最具面向对象风格的语言当推Smalltalk,而最流行的OOP语言是C+,Java则是适于网络(Internet)环境的一种面向对象语言。16.1.4 16.1.4 混合型语言混合型语言 1.1.函数型与逻辑型相结合的语言函数型与逻辑型相结合的语言 函数型与逻辑型语言的结合方式有耦合型和统一型两类。统一型又可分为具有归结语义的函数型语言和集成式语言两个子类。耦合型语言意为将具有归约语义的函数型语言和具有归结语义的逻辑型语言组合在一起,并在二者之间提供一个接口而形成的一种混合型语言。其典型代表有：(1)LOGLISP。该语言在LISP的基础上增加了表达合一、回溯等机制的系统函数,从而在保持LISP特色的同时又有了逻辑程序设计能力。(2)FUNLOG。该语言在 PROLOG 之外又增加了函数定义机制,系统以归结语义执行PROLOG程序,以归约语义求解函数。(3)POPLOG。这是POP-11、PROLOG和LISP的混合型语言,三种成分各有一个增量式编译器。具有归结语义的函数型语言又可分为N-语言、F-语言和R语言。2.2.函数型与面向对象相结合的语言函数型与面向对象相结合的语言 在LISP语言的基础上再扩充面向对象机制而产生的语言,称为函数型的面向对象程序设计语言(亦称为面向对象的LISP)。这种语言现已成为一个家族,其中比较著名的有：(1)Flavors 由 MIT 的 Lisp Machine 小组于 1979 年研制而成,它的基语言是Symbolics Common LISP。(2)LOOPS(Lisp-Object-OrientedProgramming System)。它是在InterLisp-D环境上实现的基于LISP的OOP语言,由Xerox公司于1983年推出。(3)CommonLoops。它是基于CommonLisp的函数型OOP语言,由Xerox公司于1985 年推出。(4)CLOS(CommonLisp Objetc System)。它是Xerox公司于1986 年推出的一个CommonLoops与New Flavors的后继产品。(5)CommonObjects。它 是 由 HP公 司 于 19831985年 实 现 的 又 一 个 基 于CommonLisp 的OOP语言。(6)OBJ2 也是一种面向对象的函数型语言。3.3.逻辑型与面向对象相结合的语言逻辑型与面向对象相结合的语言 这类语言著名的有:(1)SPOOL。该语言是日本IBM分部于1985年推出的以面向对象思想扩充的PROLOG语言。(2)Orient 84K。该 语 言 是 Keio大 学 于 1984年 发 表 的 基 于 PROLOG和Smalltalk 的并行执行语言。(3)Vulan。该语言是一种面向对象的逻辑型语言。16.2 函数型程序设计语言函数型程序设计语言LISP LISP语言的主要特点是：(1)LISP程序由一组函数组成,程序的执行过程是函数的调用过程。(2)程序和数据在形式上是相同的,即都是符号表达式,简称为S-表达式。(3)递归是LISP语言的主要控制结构。(4)程序以交互方式运行。16.2.1 LISP16.2.1 LISP的程序结构与运行机制的程序结构与运行机制LISP的程序一般由函数的定义和函数的调用两部分组成。其一般格式为：(DEFUN(函数名(形参表)函数体)(函数名(形参表)函数体)(函数名(形参表)函数体)(函数名 实参表)(函数名 实参表)(函数名 实参表)其中的“DEFUN”是定义函数的关键字,“函数名”可以是系统的内部函数(名),也可以是用户用DEFUN定义的函数(名)。例如下面就是一个LISP程序。(DEFUN HANOI(a b c n)(COND(=n 1)(MOVE-DISK a c)(T(HANOI a c b(-n 1)(MOVE-DISK a c)(HANOI b a c(-n 1)(DEFUN MOVE-DISK(from to)(TERPRI)(PRINC Move Disk From)(PRINC from)(PRINC To)(PRINC to)(HANOI abc 3)可以看出,这个程序的函数定义部分定义了名为HANOI和MOVE-DISK两个函数,其中前者调用后者；函数调用部分只有一个函数调用,即最后一行。这个程序运行时,就从对函数HANOI关于实参(abc 3)的调用、求值开始,依函数体内各子函数的逻辑顺序,又依次对各函数进行调用、求值,直到最后一个或最后一次函数调用和求值完成后,整个程序运行结束。所以,LISP程序的运行过程,就是一个不断地进行函数调用和求值的过程。16.2.2 S-16.2.2 S-表达式表达式 从语法上看,LISP程序的基本单位是S-表达式。S-表达式又可分为原子和表两大类。原子(atom)是由字母和数字组成的字符串,是S-表达式的最简单情况。原子又可分为文字原子、串原子和数字原子三种。文字原子又称符号(symbol),是以字母开头的字母数字串,用来表示常量、变量和函数的名字等。例如：ABC、X1等。串原子是由双引号括起来的一串字符。如LISP Program。数字原子由数字串组成。在其前面可以有符号“-”或“+”,中间可出现“.”,用来表示整数和实数。例如：256、-66、3.141 59等。S-表达式可以递归定义如下：(1)原子是S-表达式。(2)若S1和S2是S-表达式,则(S1S2)也是S-表达式。由定义,下面的式子都是S-表达式：X2 123 (AB)(A(BC)表(list)是LISP语言中最常用的数据类型,也是主要的处理对象。表是由圆括号括起来的由空格分开的若干个元素的集合。表的一般形式为：(S-表达式S-表达式 S-表达式)例如：(X Y Z),(+1 2),(A(B C)左括号后面的第一个元素称为表头,其余的元素组成的表称为表尾。例如,对于表(+1 2)的头为+,尾为(1 2)。特别地,元素个数为零的表为空表,记为()或NIL。表是一种特殊的S-表达式,每一个表都对应着一个S-表达式。二者的关系由下面的例子说明。表S表达式(A)(A NIL)(A B)(A (B NIL)(A B C)(A (B (C NIL)(A B)C D)(A(B NIL)(C (D NIL)可以看出,表的 S-表达式的结构实际是一棵二叉树。16.2.3 16.2.3 基本函数基本函数LISP的函数都以表的形式出现,并一律使用前缀表示方式,即表头为函数名,并且每个函数都有一个返回值。LISP的函数可分为语言自身提供的内部函数(称为基本函数或系统函数)和用户自定义函数两类。基本函数的种类有十多个,下面仅给出其中主要的几类。1.1.表处理函数表处理函数 表处理是LISP的主要特色,表处理的函数也很多,下面仅给出最常用的几个。1)CAR函数 格式 (CAR 表)其中CAR为函数名,它是一个保留字(下同)。功能 取出表中的表头。例如：(CAR(LISP Language Program)返回值为：LISP 2)CDR函数 格式(CDR 表)功能 取出表中的表尾。例如：(CDR(LISP Language Program)返回值为：(Language Program)3)CONS函数 格式 (CONS S-表达式 表)功能 将S-表达式作为一个元素加到表中去,并作为所构成新表中的第一个元素。例如：(CONS My(LISP Language Program)返回值为：(My LISP Language Program)4)APPEND函数 格式(APPEND 表1 表2 表n)功能 将n个表中的元素合并成一个新表。例如：(APPEND(TIGER LION)(DOG CAT)返回值为：(TIGER LION DOG CAT)5)LIST函数 格式(LIST S-表达式1S-表达式2 S-表达式n)功能 把n个S-表达式作为元素括在一起构成一张新表。例如：(LIST YELLOW RED BLUE)返回值为：(YELLOW RED BLUE)2.2.算术函数算术函数 LISP的算术表达式也是用函数表示的,称为算术函数。下面我们仅举例说明。(+2 5)表示2+5,返回值为7。(-(*4 8)(/10 5)表示48-10/5,返回值为30。3.3.求值与赋值函数求值与赋值函数 在上面的函数中多次出现撇号,它的意思是禁止求值。为什么要禁止求值呢？原来,LISP总是试图对一切S-表达式求值。表的值是通过函数运算而得到的,原子的值则是通过赋值函数实现的。撇号也是一个函数,它实际是禁止求值函数QUOTE的简写形式。赋值函数有多个,其中SET函数是一个最基本的赋值函数。格式 (SET 变量 S-表达式)功能 把S-表达式赋给变量。例如：(SET X 8);X得到值8 (SET Y(a b c);Y得到值(a b c)(SET Z(CDR Y);Z得到值(b c)另外,赋值函数还有SETQ、SETF(COMMON LISP),其功能是类似的。4.4.谓词函数谓词函数 返回值为逻辑值真或假的函数称为谓词函数,简称谓词。LISP中真和假分别用T和NIL表示,当函数的返回值为非NIL时,也表示为真。另外,NIL也表示空表。1)原子谓词ATOM 格式(ATOM 参数)功能 检测其参数是否为原子,是则返回T,否则返回NIL。例如：(ATOM a);返回T (ATOM(a b);返回NIL 2)相等谓词EQUAL 格式(EQUAL 参数 参数)功能 判断两个参数是否逻辑相等。例如：(EQUAL a a);返回T (EQUAL(a b)(a c);返回NIL (EQUAL(a b)(CONS a(b);返回T 还有一种相等谓词,其格式为：(EQ ),但它只是用来判断两个原子是否相等。例如：(EQ a a),则返回T 3)判空表函数NULL 格式(NULL 参数)功能 判断参数是否为空表,是则返回T,否则返回NIL。5.5.条件函数条件函数 条件函数也称分支函数,类似于其他语言中的分支语句,其作用是控制程序的流程。最常用到的条件函数是COND函数。格式 (COND(P1 e1)(P2 e2)(Pn en)其中Pi(i=1,n)为谓词,ei(i=1,n)为一个或多个S-表达式。功能如果P1为真，则COND函数的值为e1(当e1为多个S表达式时，取最后一个S表达式的值，下同)。否则，判断P2，直到某个Pi真为止，然后将对应的ei作为函数值。若没有一个Pi的值为非NIL，则COND的返回值为NIL。特别地，Pi也可以为逻辑常量T，这时则对其对应的各表达式求值，并把最后一个表达式的值作为COND的返回值。例如：(COND(NULL x)0)(ATOM x)1)(LISTP x)(LENGTH x)其语义是，若x的值为NIL，则COND的返回值为0;若x为原子，则COND的返回值为1;若x的值为表，则COND的返回值为表的长度。16.2.4 自定义函数自定义函数 基本函数是LISP提供的基本处理功能，要用LISP编程解决实际问题，仅有基本函数还是不够的，用户还必须根据问题的需要，利用基本函数自定义所需的函数。自定义函数的格式为：(DEFUN()其中函数体，又可能是用户自定义的函数或LISP基本函数的某种组合。所以，一般来讲，LISP自定义函数就是由其基本函数组合而成的。常用的组合方法有复和、分支、递归、迭代等。其中最具特色的构造方法是递归。例16.1 定义求N!的LISP函数。阶乘的公式是 n!n(n-1)!1!1 0!1 由此我们给出其LISP函数如下：(DEFUNN!(n)(COND(=n 0)1)(=n 1)1)(T(*n(N!(-n 1)可以看出，该函数的最后一行中又调用了它自己。所以，这个函数N!是递归定义的。需说明的是，一个函数是否能递归定义，要取决于以下两条：(1)函数的求值存在最简的情形，在这种情形下函数值是显然的或已知的；(2)该函数对于其参数的求值，可以归结为对另一些参数的求值，而且后者比前者更容易求值，即使问题朝最简情形逼近了一步。16.2.5 程序举例程序举例 例例16.2 符号微分程序。这里是指数学上的一元函数求导。我们用D(ex)表示数学上的de/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)其中D-RULE是一个获取给定操作符的微分规则的LISP函数。微分规则的存放，是通过为相应操作符建立d特性的方法完成的。D-RULE的定义为 (DEFUN D-RULE(operator)(GET operatord)其中操作符d的特性值需事先用SETF函数建立好。例如对于操作符加和乘，在数学上有 d(uv)/dxdu/dxdv/dx d(uv)/dxvdu/dxudv/dx用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)有了这些函数，我们就可以用机器求符号微分了。例如，给出如下的函数调用(D(+(*2x)(*x x)x);即求一元函数2x+x2关于x的导函数则得到返回值为 (+(+(*0 x)(*1 2)(+(*1 x)(*1 x)即2+2x，结果正确。16.3 Visual Prolog语言简介语言简介 Visual Prolog 是一种可视化逻辑程序设计语言。它是美国的Prolog开发中心(PDC)推出的新一代Prolog语言,其语言特性符合相应的国际标准ISO/IEC 13211-1:1995,并自带可视化集成开发环境。Visual Prolog与Turbo Prolog及PDC Prolog的最显著区别就是支持图形用户界面程序设计。Visual Prolog及其Visual Prolog程序不仅能够运行于Windows系列操作系统环境,而且也可以运行于Linux,SCOUNIX和OS/2等操作系统环境。Visual Prolog不仅可以用于逻辑程序设计,而且它还支持模块化和面向对象程序设计。它几乎是一个融逻辑、函数、过程和面向对象等程序设计范型为一体的综合型程序设计语言。Visual Prolog几乎包含了各种应用程序和系统程序所需要的所有特性和功能。例如,它不仅具有诸如模式匹配、递归、回溯、动态数据库、谓词库、文件操作、图形开发、字符串处理、位级运算、算术与逻辑运算、与其他语言的接口、编译器、连接器和调试器等传统功能,而且还具有对象机制、动态链接库DLL、多线程、异常处理、支持基于网络的应用开发、支持与C/C+的直接链接、对Win32API函数的直接访问以及数据库、多媒体等等。而且随着版本的升级,这些特性和功能还在不断扩充和提高。从结构来看,Visual Prolog包含一个大型库,捆绑了大量的API函数,包括Windows GUI函数族、ODBC/OCI数据库函数族和因特网函数族(socket,FTP,HTTP,CGI等)。其开发环境包含对话框、菜单、工具栏等若干编码专家和图形编辑器。正因为有如此强大的功能和优势,所以Visual Prolog已是当今智能化应用开发的有力工具。据悉,在美国、加拿大、西欧、澳大利亚、新西兰、日本、韩国、新加坡等国家和地区,Visual Prolog广为流行。习习 题十题十 六六 1.综述智能程序设计语言分类和发展概况。2.简述LISP语言的主要特点、程序结构和运行机理。3.上网登录PDC网站,进一步了解Visual Prolog语言的原理和应用。