人工智能程序设计语言.doc

人工智能程序设计语言-Prolog1概述1970年由法国马赛大学Alain Colmerauer等开发，作为逻辑程序设计的工具。很多著名的专家系统外壳都用Prolog编写，如ESP/Advisor, APE, X1等。程序特点：陈述式语言。只要给出必要的事实和规则，Prolog就可以用演绎推理自动求解问题。而过程式语言必须告之求解过程才行。实例与基本概念：一个Prolog的实例程序如下：domains /*领域声明段*/person,activity=symbol /*域person和activity的声明，symbol为标准域*/predicates /*谓词格式说明段*/likes(person,activity) /*likes为谓词名，表示某人person喜欢activity活动*/clauses /*子句段*/likes(ellen,tennis). /*事实：ellen喜欢tennis*/likes(john,football).likes(tom,baseball).likes(eric,swimming).likes(mark,tennis).likes(bill,X):-likes(tom,X). /*规则：tom喜欢的，bill也喜欢*/goal /*目标段*/likes(bill,football). /*考察bill是否喜欢football*/变量：以大写字母开头，后跟若干数字、下划线、字母组成的符号名称。是在满足目标时，其值未知的量。例如：likes(X_Persons,tennis).中的X。对象与关系：谓词表示一个或多个对象之间的某种关系。例如：likes(mark,tennis).中的likes谓词表示某人喜欢某类活动。其中，mark和和tennis分别是关系likes中的对象。又如：owns(susan,horse).eats(jill,meat).valuable(gold). /*黄金是值钱的*/注：对象名和关系名都必须以小写字母开头。领域与谓词：谓词是用语描述事实和关系的。但与此相关的谓词之涉及对象的领域范围必须明确。因此，在Prolog中，需要对关系中的对象的域进行声明。例如：likes(person,activity).表明，谓词likes中第一个参数为person域，第二个为activuty域。如果目标中输入likes(12,x)，系统将给出一个领域类型错的信息。因为，第一个参数不属于person域，此处即symbol域。复合目标：由多个子目标构成的问题目标描述。例如：likes(tom,X) and likes(erric,X)。无名变量：即谓词参数中以下划线表示时，该变量称为无名变量。表示此时该变量的值无关紧要。例如：likes(_,baseball) and likes(ellen,tennis).表示只要有人喜欢baseball，ellen就喜欢tennis。car(_,_,Age,_,Cost) and Cost27000.表示查找价格在27000$以下的车，并给出其使用年限和价格。无名变量用于事实时，表示任意或全部都成立。例如：owns(_,shirt).表示人人都有一件衬衣。washface(_).表示人人都洗脸。回溯：当子目标匹配或搜索失败时，回到最近的成功点继续进行余下的事实或规则的匹配的过程。以如下程序为例：domainschild=symbolage=integerpredicatespupil(child,age)clausespupil(peter,9).pupil(chris,9).pupil(paul,10).pupil(susan,9).问题：安排一次班级上9岁同学的乒乓球比赛，每对运动员赛两场。则目标子句可描述pupil(P1,9) and pupil(P2,9) and P1P2.的执行过程如下：子目标1子目标2子目标3结果说明peterpeterpeterpeter失败回溯到第二子目标chrispeterchris成功回溯到第二子目标继续寻找下一组解susanpetersusan成功子目标2已搜索完毕，回溯到子目标1chrispeterchrispeter成功回溯到第二子目标继续寻找下一组解chrischirschris失败回溯到第二子目标susanchrissusan成功子目标2已搜索完毕，回溯到子目标1susanpetersusanpeter成功回溯到第二子目标继续寻找下一组解chrissusanchris成功回溯到第二子目标继续寻找下一组解susansusansusan失败全部搜索完毕not的用法：表示谓词或规则的否定。例如：likes(X,baseball) and not(likes(X,tennis).表示喜欢baseball但不喜欢tennis的人。注释问题：Prolog中的注释用/*/方法。其它符号约定： “if” “:-”； “,” “and”； “;” “or”2 Visual Prolog简介2-1 程序的整体结构2-1-1 编译器导向(置于程序文本的开头)bgidriver-(BGI-Borland Graphics Interface)。如果程序需要BGI图形模式，则可加此导向语句。(只对DOS版用！)用法：bgidriver _CGA_driver_farbgifont-与bgidriver类似。用法：bgifont _gothic_font_farnowarnings-不再显示警告信息。nobreak-程序执行时不能中断，只有启动机器才能终止执行。（其它见help）2-1-2 常量声明段用于声明和使用一些在程序中将使用到的符号常量。其关键词是CONSTANTS，后跟对符号常量的声明。其符号常量的声明语法格式如下：=例如：CONSTANTSzero= 0one= 1two= 2hundred= (10*(10-1)+10)pi= 3.141592653ega= 3slash_fill= 4red= 4注：在编译程序之前，Visual Prolog将用符号常量全部替换程序中对应的符号串（与C语言中的宏替换相似！）对符号常量使用过程中的约束如下：1) 符号常量声明时，系统并不区分符号常量的大小写。因此，在CLAUSES部分，为了和变量名区分开来，符号常量名的首字符必须小写。例如：CONSTANTStwo = 2GOALA=two, write(A).2) 符号常量定义中不能自己定义自己例如：my_number = 2*my_number3) 程序中可以有多个CONSTANTS区，但必须遵循先声明，后使用原则4) 常量的有效范围从声明处开始，直到源文件的末尾，包含程序文件的包含情形在内。5) 常量标识符只能声明一次2-1-3 变量、约束变量与自由变量变量：其值在程序执行过程中可以发生改变的量。变量的表示：大写字母开头的符号串。变量的两种状态：值不定时为自由变量，值已知时为约束变量。例如：DOMAINSperson,hobby=symbolPREDICATESlikes(person,hobby)CLAUSESlikes(ellen,reading).likes(john,computers).likes(john,badminton).likes(leonard,badminton).likes(eric,swimming).likes(eric,reading).GOALlikes(X,reading) and likes(X,swimming).分析：目标有两个子目标。Prolog试图从左到右逐一满足。在搜索过程中，likes(X,reading)没有被满足之前，其X的值没有确定，此时称X为自由变量。当用likes(ellen,reading)匹配第一子目标后，X被约束为ellen值，此时称X为约束变量。此后，对第二子目标likes(X,swimming)进行匹配时，X是约束变量。2-1-4 事实数据库段Visual prolog程序是事实和规则的集合。在程序运行期间，对程序操纵的事实的更新、改变、移动及增加、减少等，因此，属于动态库(dynamic database)或内部库(internal database)。Visual prolog包含了一个专门用来说明属于动态库的事实的部分，即FACTS部分。FACTS的一般声明格式如下：GLOBAL FACTS | DATABASE - databasenamenocopynondeterm|determ|single fact_1(ArgsList_1).nocopysingle|determ|nondeterm fact_N(ArgsList_N).其中，“”表示多选一，且必选一，“”表示可有可无，“*”表示任意多次重复（包含0次）。GLOBAL-表明事实部分是否是全局的。nocopy-事实匹配时不进行复制。nondeterm-默认情形是事实fact_N的任意多个实例可以存在(即不确定的)。determ-任何时候，一个fact_N的实例不超过1个。single-任何时候，事实fact_N的实例有且只能有一个。fact_N-事实或谓词。argsList_N-事实或谓词中的参数表。其形式为： Domain_1 Name_1 , Domain_2 Name_2 * 例如：FACTSperson(STRING Name, STRING Address, INTEGER Age)determ counter(integer CounterValue)single singleFact(STRING)single my_font(font_list)2-1-5 域段用于声明任何Visual Prolog标准域以外的域。类似于C语言中的数据类型定义typedef的功能。2-1-5-1符号约定及说明dom-领域名。reference表示允许有非约束变量作为输入参数。其声明的方法是在域声明右边加一关键字reference。例如：DOMAINSreflist = reference refint*refint = reference integerterm = reference int(refint); symb(refsymb)refsymb = reference symbol当一个复合域被声明为一个reference域时，其所有的子域自动成为reference的。然而，应该在域段中明确指出要成为reference域的域。如果子域是标准域，如integer，string，则整个程序中的标准域都将成为reference域。注：不应该将标准域作为reference域。在纯粹的Prolog中，这将显著地增加系统的负担。在含C调用的工程中，还将导致不正确的参数传递甚至保护性错误。例如：用reference域进行排序的实例。DOMAINStree = reference t(val, tree, tree) /*tree是一个reference域*/val = integerlist = integer*PREDICATESinsert(integer,tree)instree(list,tree)nondeterm treemembers(integer,tree)sort(list,list)CLAUSESinsert(Val,t(Val,_,_):-!.insert(Val,t(Val1,Tree,_):-ValVal1,!,insert(Val,Tree).insert(Val,t(_,_,Tree):-insert(Val,Tree).instree(,_).instree(H|T,Tree):-insert(H,Tree),instree(T,Tree).treemembers(_,T):-free(T),!,fail.treemembers(X,t(_,L,_):-treemembers(X,L).treemembers(X,t(Refstr,_,_):-X = Refstr.treemembers(X,t(_,_,R):-treemembers(X,R).sort(L,L1):-instree(L,Tree),findall(X,treemembers(X,Tree),L1).GOALsort(3,6,1,4,5,L),write(L=,L),nl.align byte|word|dword内存分配与使用方法指定。对标准Prolog内存的处理是自动进行的。(详细情形及例子见Help)declaration_1 ;declaration_2* 可选择的复合对象声明部分。其格式为：functor(sub_1 , sub_2* )。2-1-5-2用标准领域进行声明标准领域类型：integer, char, real, string, symbol, word, byte, short, unsigned, long, ulong, ushort, binary等。其定义如下：integer：-3276832767之间的整数。char：单引号引起来的单个字符，如a。其中，n, t, b等为转义字符。real：+/-1.0e-307之间的实数。string：双引号引起来的任意多个字符构成。可以是空串。symbol：有两种格式，一是以小写字母开头，后跟若干字母、数字和下划线组成的符号串，一是由双引号引起来的一串字符。后者主要用于含空格字符或起始字符不是小写的时候。byte, word, short, ushort, signed, unsigned, long, ulong, binary：表示不同的数据类型。注1：符号和串可以交替使用，但在机器内部的处理过程是不同的。对符号串，内部是用表存放的，能加速匹配过程。其缺点是占用专门的存储空间，且搜索需要花费一定时间。注2：如果程序中谓词说明都用标准领域，则领域段可以省略。基本域的说明格式：dom , dom1 = reference 例如：DOMAINS brand, color = symbolage, price = integermileage = realPREDICATEScar(brand, mileage, age, color, price)CLAUSEScar(chrysler,130000,3,red,12000).car(ford,90000,4,gray,25000).car(datsun,8000,1,red,30000).GOALScar(Make,Odometer,Years_on_road,Body,25000); /查找价格为25000车car(Make,Odometer,Years_on_road,Body,Cost) and Cost25000. /或查找25000以下的车特殊域的说明格式：dom ,dom1 = reference signed | unsigned byte | word | dword2-1-5-3复合对象及其领域的声明复合对象：对象中含对象时，该对象称为复合对象。例如：复合对象实例。owns(john,book(“From Here to Eternity”, “James Jones”).和owns(john,horse(blacky).分别表示John拥有James Jones写的从现在到未来的书，以及John拥有一匹黑马的事实。而用owns(john,“From Here to Eternity”).和owns(john,blacky).是不能表达以上两个事实的。复合对象的构成：由函数子及属于此函数子的子对象构成，即functor(obj1,obj2,objN)。没有子对象的函数子表示为functor()或functor，用于区分不同的对象，如前面的book和horse。复合对象的领域说明：其完整格式如下：GLOBAL DOMAINSdom ,dom_1 = reference align byte|word|dword declaration_1 ;declaration_2*例如：复合对象域的声明实例。DOMAINStitle,author,name = symbolarticles = book(title,author);horse(name) /*各选择域之间用分号分隔*/符合对象的层次结构表示特征：书作者书名姓名复合对象域的树结构示意图DOMAINS articles = book(title,author);author = author(firstname,surname)title, firstname, surname = symbol注：一个领域语句一次仅能描述一层树结构，而不能描述整棵树。例如：articles=book(title,author(name,surname)作为领域说明是不行的。必须分别如上例所示进行描述。没有函数子的复合对象(单选择的复合对象)：一般格式：dom , dom_1 = struct align byte | word | dword obj_declaration例如：BOOKS = struct book(SYMBOL Author_Name, SYMBOL Title)注：域的右边不能再有其它可选择域！2-1-5-4列表及其领域的声明表是Prolog程序中的基本数据结构，与Pascal和C等面向过程程序设计语言的数组结构相当。列表域声明的一般格式：mylist , mylist1= reference elementDom*注1：其中的星号表示可有0个或多个元素。注2：表中元素必须具有相同领域，如果不为标准领域范围，则必须有一个关于对象的声明。注3：表中元素可以是任何对象类型，也包含表类型本身。其一般定义格式如下：DOMAINSobjectlist=objects*objects=例如：DOMAINSintegerlist=integer*namelist=name*name=symbol表的表示方法：以扩住的，其间由多个元素构成，元素和元素之间由逗号分隔。例如：1,2,3 dog, cat, canary “valerie”, “jonathan”, “Michael”等。表的基本结构与操作：Prolog将表分成表头(head)和表尾(tail)两部分。表头是表中的第一个元素，表尾是除去表头元素后剩下的部分。表头和表尾可用竖线(“|”)分隔。(其表示与基本操作可以参见数据结构中广义表结构的讨论)注：空表的表头和表尾均无定义。 例如：表及其表头、表尾实例。a,b,c的表头为a，表尾为b,c。可以表示为a|b,c。1的表头为1，表尾为。可以表示为a|。的表头无定义，表尾也无定义。1,2,3,2,3,4,的表头为1,2,3，表尾为2,3,4,。可以表示为1,2,3|2,3,4,。例如：表头表尾的匹配实例。X,Y,Z与egbert, eats, icecream匹配结果为：X= egbert,Y= eats,Z= icecream。7与X|Y匹配的结果为：X=7,Y=。1,2,3,4与X,Y|Z的匹配结果为：X=1,Y=2,Z=3,4。1,2与3|X匹配失败。例如：有关表头、表尾操作的程序实例。DOMAINSnamelist=name*name=symbolPREDICATESmember(name,namelist).CLAUSESmember(Name,Name|_). /*下划线表示子句匹配时不感兴趣*/member(Name,_|Tail) if member(Name,Tail). /*判定Name是否表中成员*/write_a_list(). /*表空时停止(此时匹配成功)*/write_a_list(Head|Tail):-write(Head),nl,write_a_list(Tail).(3) 特殊的预定义对象(略)(4) 谓词域的声明(略)(5) 对象谓词域的声明(略)(6) 引用域的声明(略)(7) 目标域的声明(略)2-1-6 谓词段用于声明谓词、函数或谓词之值的地方。谓词、函数的声明形式：GLOBAL PREDICATESPredicateMode ReturnDomain predicateName(arglist)- flowpatterns language namespecGLOBAL-表示该谓词定义为全局的。PredicateMode-谓词模式，定义为procedure | determ | nondeterm | failure | erroneous | multi。用于定义谓词的执行方式，因为 ，Visual Prolog是强制类型执行系统，它强迫程序员指定谓词的两种行为的确定：一是谓词的调用是否要失败，一个谓词可以产生的解答个数。其中：multi-定义非确定性谓词，可以回溯产生多解。这种谓词总是成功的，因此，至少有一个解。(never fail!)procedure-定义被称之为过程的谓词。过程总是成功的，但不回溯。过程有且仅有一个解。运行时可能有错误产生！编译器将总是检查并给出过程中的非确定性子句的警告。如果不能保证一个过程不绝失败的话，编译器将给出595或596错误。erroneous-不应产生一个解，且永远不失败。(相当于一个运行时错误，可以用于设置陷阱的处理)failure-不产生一个解，但可以失败。用于强迫程序回溯到最近的回溯点，或者与运行时错误一样，起中断程序执行的作用。例如内建谓词fail。编译器总是检查并对含不确定子句的谓词进行警告。determ-定义确定性谓词。该类谓词可以成功，也可以失败，但绝不回溯。即该类谓词不会多于一个解。编译器总是检查并对谓词中含不确定性子句的进行警告。注：determ也用于事实的声明中。nondeterm-定义能够进行回溯并产生多解的非确定性谓词。可以失败，此时，不产生任何解。注：determ也用于事实的声明中。ReturnDomain-声明一个函数时的返回域。返回值从函数子句的最后一个参数获得，但该参数在谓词声明时不必出现。例如：PREDICATESINTEGER /*Return*/ cube(INTEGER In) /*代入一整型参数，返回一整型结果*/CLAUSEScube(In,Return):- Return = In*In*In. /*函数cub()的子句表示！*/predicateName-谓词名(或函数名)由字母开头(最好小写)，后跟字母、数字、下画线的符号串组成，最长不超过250个。名字中间不能出现减号、空格、星号等字符。- flowpatterns -形如( flow , flow * )。其中，flow即 i | o | functor flowpattern | listflow ，flowpattern指明每一个参数如何使用：i表示输入流，o表示输出流，functor and flowpattern是指一个复合项的输入流和输出流情形。例如：输入流、输出流的控制流分析实例。diagnostics %should be placed before the start of the program text PREDICATESnondeterm plus(integer, integer, integer)nondeterm num(integer)CLAUSESplus(X,Y,Z):- /*X+Y=?-X加Y的结果是什么*/bound(X),bound(Y),!,Z=X+Y. /* (i,i,o) */plus(X,Y,Z):- /*?+Y=Z-什么加Y等于Z*/bound(Y),bound(Z),!,X=Z-Y. /* (o,i,i) */plus(X,Y,Z):- /*X+?=Z-X加什么等于Z*/bound(X),bound(Z),!,Y=Z-X. /* (i,o,i) */plus(X,Y,Z):- /*?+?=Z-加起来的结果为Z的有哪些*/free(X),free(Y),bound(Z),num(X),Y=Z-X. /* (o,o,i) */plus(X,Y,Z):- /*?+Y=?-加数为Y的有哪些*/free(X),free(Z),bound(Y),num(X),Z=X+Y. /* (o,i,o) */plus(X,Y,Z):- /*X+?=?-被加数为X的有哪些*/free(Y),free(Z),bound(X),num(Y),Z=X+Y. /* (i,o,o) */plus(X,Y,Z):- /*?+?=?-加法有哪些*/free(X),free(Y),free(Z),num(X),num(Y),Z=X+Y. /* (o,o,o) */% Generator of numbers starting from 0num(0).num(X):-num(A),X = A+1.为方便，一般可以在谓词声明时，为其指定输入输出流的可能使用情形。尤其是谓词流模式不是所有模式都有效时，可以帮助Prolog的流分析器分析子句所属流。例如：指定谓词流模式的实例。PREDICATESprocedure plus(integer, integer, integer) - (i,i,o),(i,o,i),(o,i,i)此例中，流模式的指定告诉系统，谓词必须有两个输入值，一个输出值。由此可以避免其它模式的分析与匹配。language-用于指定转换用的编译器，当声明的域要被传送到其它语言子程序时用，默认的是Prolog。language asm | c | pascal | prolog | stdcall | syscall 。namespec-用于指定目标代码的扩展名字。(主要用于与其它语言接口时)注1：对全局谓词，必须说明其输入、输出流模式。否则，Prolog将把所有参数都作为默认的流处理，即输入流。例如：GLOBAL PREDICATES my_converter(STRING, INTEGER)等价于my_converter(STRING, INTEGER)- (i,i)注2：每个谓词的流模式可以有多个。注3：对每一种流模式，都可以分别指定一个谓词模式。例如：PREDICATESprocedure append(ILIST,ILIST,ILIST) - (i,i,o)determ(i,i,i)nondeterm(o,o,i)注4：谓词允许有多重说明。要求对同一谓词的重复说明必须一个接一个连续给出，且要求谓词的参数个数必须一致，但领域可以不同。例如：要定义一个实数加法和整数加法时，谓词声明如下：add(integer,integer,integer)add(real,real,real)谓词值的声明形式：GLOBAL PREDICATESpredicateName : predicateDomain namespec例如：(略)函数与返回值：例如：PREDICATESUNSIGNED /*Return*/ triple(UNSIGNED In)CLAUSEStriple(In, Return):- Return = In * 3.GOALReturnTripleVal = triple(6),write(ReturnTripleVal).无参函数的声明与调用：如果函数无任何参数，其声明的谓词名后的括号对不能省略，否则，程序出错，或不能当函数使用。例如：PREDICATESunsigned hour()CLAUSEShour(H):- time(H,_,_,_).其调用形式为：Hour = hour()，不能为Hour = hour。函数与尾递归(tail recursion)：当一个谓词被声明为一个有返回值的函数时，不能按常规谓词的调用方法调用之（即在参数表的最后给出输出参数的方法），而是要用函数的方法进行调用。原因在于函数将返回值存到了寄存器中去了，即编译之前和函数调用之后的代码与常规的谓词谓词调用是不同的。因此，调用其自身的函数不是尾递归的。例如：DOMAINSilist = integer*PREDICATESilist neg(ilist)CLAUSESneg(,).neg(Head|Tail,NHead|NTail):-NHead = -Head,NTail = neg(Tail). /*不是尾递归的！*/GOALX=neg(1,2,3,4). /*neg(1,2,3,4,X)调用时，系统将告之参数个数不对*/以下代码是尾递归的：DOMAINSilist = integer*PREDICATESneg(ilist,ilist)CLAUSESneg(,).neg(Head|Tail,NHead|NTail):-NHead = -Head,neg(Tail,NTail). /*此子句形式是尾递归的！*/GOALneg(1,2,3,4,X). /* Y=neg(1,2,3,4,X).要出错，即目标类型错*/2-1-7 问题目标段是程序的内建目标段，一个Prolog程序必须有一个目标段，且只有一个目标段。跟规则体一样，由一个或多个子目标构成。但与规则体之区别在于：目标后面不跟“：-”。程序启动后，将自动执行目标。复合目标：由两个以上的子目标构成的目标。子目标：复合目标中的任一目标。两个子目标之间是联合关系时，用逗号分隔。Prolog尽量满足目标中体，一旦所有子目标都成功，程序成功结束。否则，失败。两个子目标之间是“或”关系时，用分号分隔。执行时依次满足子目标，一旦子目标被满足，则成功结束，否则，将满足下一子目标。直到所有子目标都不满足时，失败退出。例如：car(Make,Odometer,Years_on_road,Body,Cost)，Cost25000./小于25000的车car(ford,Odometer,Years_on_road,Body,Cost) ；Cost25000./ford车或小于25000的车外部目标与内部目标：在文本模式下的Prolog对话窗口中给定测试目标时，称为外部目标（Visual Prolog中已经没有了）。在程序中给定目标称为内部目标。注：在Visual Prolog中实施以前外部目标的调试功能，可以借助于系统提供的测试目标功能(Test Goal)。2-1-8 子句部分Prolog是基于谓词逻辑形式系统的一个子集，即Horn子句。一个Prolog程序由两种子句构成：事实和规则。一个程序可以有多个子句段，每个子句段都由CLAUSES开头。事实：已知为真的关系或性质。如：likes(bill, cindy).规则：相互依赖的关系。允许Prolog从一类信息推出另外的信息。如果给定的条件为真，则规则为真。规则由两部分构成：一是规则头，一是规则体。规则头和规则体之间用“：-”分隔。规则头又称结论(conclusion)或依赖关系(dependent relation)。规则体是一些必须为真的条件或事实，它们将由Prolog去证明。注1：“:-”可用“if”代替。注2：一个谓词的子句应该放在一起。注3：定义一个谓词的子句序列被成为过程(procedure)。注4：规则体中的事实或条件之间有连接词“and”/“or”或“，”/“；”分隔。注5：每一子句以点“.”结束。注6：Prolog试图满足一个目标时，按子句出现的先后顺序进行。例如：如前述各例及后面所有相关例子所示。2-2 Prolog内建函数(Built-in functions)简介2-2-1 算术函数与谓词X mode Y X div Y abs(X) exp(X) ln(X) log(X) sqrt(X)round(X) trunc(X) val(domain,X) cos(X) sin(X) tan(X) arctan(X) random(X)-之间的随机实数。random(X,Y)-之间的随机整数。randominit(X)-初始化随机数产生器。2-2-2 控制谓词bound(Variable)-测试变量是否被约束。free(Variable)-测试变量是否自由变量。fail()-强迫失败，以引起回溯。not(Atom)-对子目标结果的否定。true()-总是成功。可以作为陷阱函数的参数使用。findall(X, predicateName(_,_,X,_,_), VarList)-汇集非确定性谓词调用的所有求解结果到值域表中去。其中，要求谓词具有nond