164 智能系统学报 第4卷 的可读性，便于程序员设计程序与开展合作交流；而 个构造子被说明了，则类型的集合将把基类视为 且编译器也可根据类型系统说明的信息产生效率更 “常量”，把构造子视为“函数”来构造获得函数类 高的代码，同时有助于捕获程序设计中的错误，大大 型，这样就可以构造诸如List(Day)、 增加了程序设计的正确性四 List(List(Day))等可数无限的类型的集合 Pobg以Hom子句逻辑为基础，是一种无类型 例中，a是一个类型变量，允许反映Godeli语言 程序设计语言.这种特点虽然简化了它的语言、编译 的参数多态性，它可以替换任意一个可以构造的类 和执行过程，但却大大降低了可表达性能力，使程序 型.一个类型是一个项，它可以如下构造：将基类视 员设计的程序不易阅读和理解.在Godeli语言中，由 为常量”，类型参数（选取子）视为变量”，构造子 于引入了类型，通常语言说明以关键字BASE、CON- 视为“函数”例如，对上述说明来说，所有类型的集 STRUCTOR,CONSTANT、FUNCTON、PROPOSITDN 合将是Day,Person、List(Day)、List(List(Day)、a、 等开头，这些说明定义了程序中出现的各种数据类 List(a)等等.基于参数多态性，这里的谓词Append 型和符号，有助于程序的阅读和理解 能够对任何类型列表进行追加 例1 Godeli语言的类型说明示例 Godeli语言的类型系统是一个强类型系统，程 BASE Day,Person %基类说明 序中的每个项和它的类型必须进行语言说明.尽管 CONSIRUCIR List/1 %类型构造算子 变量的类型说明不做强制要求，但为了保证其类型 CONSTANT Nit List(a）. %常量说明 可由上下文推测出来，约定程序中有足够的信息可 Monday,Tuesday:Day 被编译程序和推理机用于判定类型并保证程序的安 Fred,Bilt Person 全执行，而不需要显式地给出变量的类型说明) FNCTON Cons a*List(a）-List(a）. %函数说明 Godeli语言在引入类型后，显然大大提高了语 PRED CATE Append:L(a）·Lis(a）·List(a).%谓词说明 言的可表达性能力，使其程序拥有更好的说明性语 如例1所示，程序中的语言说明可以由以下几 义.并且类型系统的引入给Godel语言的编译带来 部分组成： 了方便，提高了执行效率，也更容易实现程序的并行 1)以关键字BASE开头的语言说明给出了多态 执行) 多类语言程序的基本类型，称为基类 2控制机制的区别 2)CONSTRUCTOR说明了用户命名的含有n元 类型参数的结构类型称为构造子).可以从一些类 控制机制主要针对语言的过程性语义.在Po 型构造产生新的类型 bg语言中，针对其Hom子句，采用9D反驳一消解 3)CONSTANT说明定义了常量 法来推导出最后的结果.这种方法无论从实际的操 4)FUNCTON和PRED CATE分别说明了函数 作过程还是从理论的推导上都是严谨正确的，它也 和谓词类型，对应Godel语言中的项和原子.Godel 是PDbg语言说明性语义和过程性语义的桥梁。 语言的函数和谓词都是基于类型的，函数和谓词的 例2设有Pobg程序片段 每一个参数都需要进行类型说明 1)Reverse([]]) 在上面的示例中，Day和Person是基类，CON- 2)Reverse ([HI T/,Rev)+Reverse T. STANT说明Nil是List(a)类型的一个常量，Mon- TR)AAppend(TR.[HJ.Rev). day Tuesday分别是Day类型的常量，Fred、Bil分别 这里，Append(X,y,Z)谓词将列表X和按顺 是Person类型的常量.UNCTDN说明了Cons是一 序合并成新表Z.如该程序目标子句为Append([l, 个二元函数，它把二元组（第1个参数是a类型，第 2],【3,41,Z),则Z的输出结果为[1,2,3,41Re 2个参数是List(a)类型)映射到一个List(a)类 verse(X,)谓词是将X列表逆转得到新表Y.如果 型的元素.PRED CATE说明了Append是一个三元 目标子句为Reverse([2,4,3],),容易得到Y= 谓词，每个参数都是List(ad类型 [3,4,21但对于目标子句Reverse(y,[2,4,3]), 一元构造子Lst本身不是一个类型，但程序中 系统会因为回溯的无法停止而陷入无限循环 出现的所有基类和构造子都必须说明.没有构造子， Poog引入了附加的控制语句cut(I)以及重新 则所有类型的集合只是所有基类的集合.如果有一 调整定义子句和子目标的次序等方法来试图解决此 1994-2009 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net的可读性 ,便于程序员设计程序与开展合作交流 ;而 且编译器也可根据类型系统说明的信息产生效率更 高的代码 ,同时有助于捕获程序设计中的错误 ,大大 增加了程序设计的正确性 [ 2 ] . Prolog以 Horn子句逻辑为基础 ,是一种无类型 程序设计语言. 这种特点虽然简化了它的语言、编译 和执行过程 ,但却大大降低了可表达性能力 ,使程序 员设计的程序不易阅读和理解. 在 Go¨del语言中 ,由 于引入了类型 ,通常语言说明以关键字 BASE、CON2 STRUCTOR、CONSTANT、FUNCTION、PROPOSITION 等开头 ,这些说明定义了程序中出现的各种数据类 型和符号 ,有助于程序的阅读和理解. 例 1 Go¨del语言的类型说明示例 BASE Day, Person. % 基类说明 CONSTRUCTOR L ist/1. % 类型构造算子 CONSTANT N il: L ist( a ). Monday, Tuesday: Day. Fred,B ill: Person. % 常量说明 FUNCTION Cons: a 3 L ist( a ) →L ist( a ). % 函数说明 PRED ICATE Append: List( a ) 3 List( a ) 3 List( a ). % 谓词说明 如例 1所示 ,程序中的语言说明可以由以下几 部分组成 : 1)以关键字 BASE开头的语言说明给出了多态 多类语言程序的基本类型 ,称为基类. 2) CONSTRUCTOR说明了用户命名的含有 n元 类型参数的结构类型 (称为构造子 ) ,可以从一些类 型构造产生新的类型. 3) CONSTANT说明定义了常量. 4) FUNCTION和 PRED ICATE分别说明了函数 和谓词类型 ,对应 Go¨del语言中的项和原子. Go¨del 语言的函数和谓词都是基于类型的 ,函数和谓词的 每一个参数都需要进行类型说明. 在上面的示例中 , Day和 Person是基类 , CON2 STANT说明 N il是 L ist( a )类型的一个常量 ,Mon2 day、Tuesday分别是 Day类型的常量 , Fred、B ill分别 是 Person类型的常量. FUNCTION说明了 Cons是一 个二元函数 ,它把二元组 (第 1个参数是 a类型 ,第 2个参数是 L ist( a )类型 )映射到一个 List ( a )类 型的元素. PRED ICATE说明了 Append是一个三元 谓词 ,每个参数都是 List ( a) 类型. 一元构造子 L ist本身不是一个类型 ,但程序中 出现的所有基类和构造子都必须说明. 没有构造子 , 则所有类型的集合只是所有基类的集合. 如果有一 个构造子被说明了 ,则类型的集合将把基类视为 “常量 ”,把构造子视为“函数 ”来构造获得函数类 型 , 这 样 就 可 以 构 造 诸 如 List ( Day )、 List(L ist(Day) )等可数无限的类型的集合. 例中 , a是一个类型变量 ,允许反映 Go¨del语言 的参数多态性 ,它可以替换任意一个可以构造的类 型. 一个类型是一个项 ,它可以如下构造 :将基类视 为“常量 ”,类型参数 (选取子 )视为“变量 ”,构造子 视为“函数 ”. 例如 ,对上述说明来说 ,所有类型的集 合将是 Day、Person、List(Day)、List(L ist(Day) )、a 、 List( a )等等. 基于参数多态性 ,这里的谓词 Append 能够对任何类型列表进行追加. Go¨del语言的类型系统是一个强类型系统 ,程 序中的每个项和它的类型必须进行语言说明. 尽管 变量的类型说明不做强制要求 ,但为了保证其类型 可由上下文推测出来 ,约定程序中有足够的信息可 被编译程序和推理机用于判定类型并保证程序的安 全执行 ,而不需要显式地给出变量的类型说明 [ 2 ] . Go¨del语言在引入类型后 ,显然大大提高了语 言的可表达性能力 ,使其程序拥有更好的说明性语 义. 并且类型系统的引入给 Go¨del语言的编译带来 了方便 ,提高了执行效率 ,也更容易实现程序的并行 执行 [ 3 ] . 2 控制机制的区别 控制机制主要针对语言的过程性语义. 在 Pro2 log语言中 ,针对其 Horn子句 ,采用 SLD反驳 —消解 法来推导出最后的结果. 这种方法无论从实际的操 作过程还是从理论的推导上都是严谨正确的 ,它也 是 Prolog语言说明性语义和过程性语义的桥梁. 例 2 设有 Prolog程序片段 1) Reverse ( [ ], [ ]). 2) Reverse ( [ H | T ] , Rev) ← Reverse ( T, TR ) ∧Append ( TR, [H ], Rev). 这里 ,Append ( X, Y, Z ) 谓词将列表 X和 Y按顺 序合并成新表 Z . 如该程序目标子句为 Append ( [ 1, 2 ], [ 3, 4 ], Z ) ,则 Z 的输出结果为 [ 1, 2, 3, 4 ]. Re2 verse ( X, Y) 谓词是将 X列表逆转得到新表 Y. 如果 目标子句为 Reverse ( [ 2, 4, 3 ], Y) , 容易得到 Y = [ 3, 4, 2 ]. 但对于目标子句 Reverse ( Y , [ 2, 4, 3 ]) , 系统会因为回溯的无法停止而陷入无限循环. Prolog引入了附加的控制语句 cut(! )以及重新 调整定义子句和子目标的次序等方法来试图解决此 ·164· 智 能 系 统 学 报 第 4卷