（计算机软件与理论专业论文）Gdel语言编译系统的设计与实现.pdf

摘要 摘要 g 6 d e l 语言是继p r o l o g 语言之后出现的新型说明性通用逻辑程序设计语言。 它建立在多态多类的一阶逻辑基础之上，摒弃了p r o l o g 语言中的非逻辑成分， 集成了许多语言的有效成分和优点，引入了类型系统，增加了新的语言成分，这 使得它成为一种功能强大的高效的说明性逻辑程序设计语言。作为一种工具， g 6 d e l 语言编译系统的实现对该语言的推广、深入研究，以及人工智能的研究和 智能软件系统的开发具有重要意义。目前，只有b r i s t o l 大学的研究小组用s i c s t u s p r o l o g 通过将g 6 d e l 语言程序翻译成p r o l o g 语言的程序实现了g 6 d e l 语言的一个 编译系统。但是，由于g 6 d e l 语言程序在翻译成p r o l o g 语言程序后，其执行仍然 只能通过s i c s t u sp r o l o g 系统解释执行，其执行效率较低且只能在l i n u x 环境下 运行，而且仅仅实现了g 6 d e l 语言的一个子集。 本文提出了g 6 d e l 语言编译系统的一种实现方法：该方法编译的程序在执行 时继续沿用反驳一消解原理，但对源程序只编译到中间代码( 内部表示) ，然后与 事先设计好的具有动态推理功能的推理机连接，形成目标代码。这种中间代码具 有面向g 6 d e l 语言的特点，是在整体理解源程序过程性语义的基础上，按照推理 机执行过程对数据对象的使用要求，表达源程序的数据对象，然后作为某个特定 程序( 即作为内核程序推理机) 的输入，两者连接后生成目标代码。目标代码的 执行中借助推理机程序对中间代码的执行处理，就可完成程序的计算。这是与 b r i s t o lg 6 d e l 系统实现的技术路线完全不同的一种实现方法。基于这样的实现方 法，我们给出了编译系统的总体结构，并对编译分析系统中的词法分析、语法分 析、语义分析、中间代码生成和出错处理等各部分的实现方法和技术进行了详细 的介绍，着重讨论了一种适合于逻辑程序设计语言的优化的语义分析方法。同时， 我们将类型系统作为g 6 d e l 语言编译系统一个独立的子系统，要求它具备在程序 动态执行过程中为推理机提供各种必要的数据准备，这在逻辑程序设计语言的编 译系统实现中是一种新的技术方法。 经过三年多的探索，我们已经成功地设计、开发了一个实验室g 6 d e l 语言编 译系统，运行效率很高，并在试验运行中通过了一组典型实例。初步的测试表明： g 6 d e l 语言编译系统的设计与实现 在前人工作的基础上，我们提出的g o d e l 语言编译系统的设计思想、实现方法、 技术路线和实现技术是可行的。相信随着g 6 d e l 语言编译系统实现技术的逐步成 熟，g 6 d e l 语言将会受到更多的关注。 关键词：g 6 d e l 语言；编译系统；多态多类 a b s t r a c t a b s t r a c t g 6 d e li sad e c l a r a t i v ea n dg e n e r a l p u r p o s e l o g i cp r o g r a m m i n gl a n g u a g e s u c c e e d e dt op r o l o g i tb a s e do nm a n y s o r t e df i r s to r d e rl o g i cw i t h p a r a m e t r i c p o l y m o r p h i s m ，d i s c a r d st h ef e a t u r e so fp r o l o gw h i c ha r en o n - l o g i c a l ，i n t r o d u c e st y p e s y s t e m ，i n t e g r a t e st h em e r i to fm a n yl a n g u a g e s ，a d d ss o m en e wl a n g u a g ec o m p o n e n t s w h i c hl e ti tb eap o w e r f u ld e c l a r a t i v ep r o g r a m m i n gl a n g u a g e a sat o o l ，t h e i m p l e m e n t a t i o no ft h ec o m p i l e rf o rg 6 d e ll a n g u a g ew i l lh a v eg r e a ts i g n i f i c a n c et o i n d e p t hs t u d ya n dw i d e s p r e a du s eo fg 6 d e ll a n g u a g e ，w h i c hi sa l s oi m p o r t a n tt ot h e r e s e a r c ho fa r t i f i c i a li n t e l l i g e n c ea n dt h ed e v e l o p m e n to fi n t e l l i g e n ts o r w a r e a t p r e s e n t , o n l yh a sac o m p i l e rf o rg 6 d e ll a n g u a g ew h i c hi si m p l e m e n t e dw i t hs i c s t u s p r o l o gb yt h er e s e a r c ht e a mo fb r i s t o lu n i v e r s i t y b u ti to n l yh a si m p l e m e n t e da s u b s e to fg 6 d e ll a n g u a g e i nt h i s p a p e r , o n ei m p l e m e n t a t i o no ft h ec o m p i l e rf o rl a n g u a g eg 6 d e li s i n t r o d u c e d ：w ec o m p i l e ss o u r c ep r o g r a mt oi n t e r m e d i a t ec o d ew h i c he x p r e s s e st h e d a t ao b je c to fs o u r c ep r o g r a ma c c o r d i n gt ot h er e q u i r e m e n t so fi n f e r e n c em a c h i n e i n f e r e n c em a c h i n et a k e si n t e r m e d i a t ec o d ea si n p u tw h i c hc o n n e c t sw i t hi n f e r e n c e m a c h i n ep r o d u c e sg o a lc o d e t h es o u r c ep r o g r a mc a nb ec a l c u l a t e db yt h ee x e c u t i o n o fg o a lc o d e ，t h r o u g hw h i c hi n f e r e n c em a c h i n ed e a l sw i t ht h ei n t e r m e d i a t ec o d e t h i s i sam e t h o dw h i c hi sd i f f e r e n tf r o mt h et e c h n o l o g yr o u t eo fi m p l e m e n t a t i o no fb r i s t o l g 6 d e l b a s e do ns u c hm e t h o d ，t h eo v e r a l ls t r u c t u r eo ft h ec o m p i l e ri sg i v e n ，t h e t e c h n i q u eo fl e x i c a la n a l y s i s ，s y n t a c t i ca n a l y s i s ，s e m a n t i ca n a l y s i s ，i n t e r m e d i a t ec o d e g e n e r a t i o na n de r r o rh a n d l i n g o fc o m p i l i n ga n a l y s i s s y s t e ma r ei n t r o d u c e d ，a o p t i m i z e da l g o r i t h mo fs e m a n t i ca n a l y s i si sd i s c u s s e di nm o r ed e t a i l a l s o ，w et a k e t h et y p es y s t e ma sas e p a r a t es u b s y s t e mo fg 6 d e lc o m p i l e rs y s t e m ，a n dr e q u i r ei t p r o v i d en e c e s s a r yd a t ap r e p a r a t i o nd u r i n gt h ep e r i o do fd y n a m i ce x e c u t i o n ，w h i c hi sa n o v e lt e c h n i q u ei nt h ei m p l e m e n t a t i o no fc o m p i l e rs y s t e mo fl o g i cp r o g r a m m i n g l a n g u a g e g o d e l 语言编译系统的设计与实现 w eh a v ed e s i g n e d ，d e v e l o p e dal a b o r a t o r yc o m p i l e ro fg 6 d e ll a n g u a g ew h i c hi s e f f i c i e n ta n dc o m p i l e ss e v e r a lt y p i c a li n s t a n c e s ，d e m o n s t r a t i n gb a s i ci d e a ，t e c h n o l o g y r o u t ew ep r o p o s e da r ef e a s i b l e w eb e l i e v e dt h a t ，w i t ht h ec o m p i l e ri m p l e m e n t a t i o n t e c h n o l o g yi sg r a d u a l l ym a t u r e ，g 6 d e ll a n g u a g ew i l lb ea b l et or e c e i v em o r ea t t e n t i o n a n do b t a i nam o r ew i d e s p r e a du s e k e y w o r d s ：g 6 d e ll a n g u a g e ；c o m p i l e rs y s t e m ；p o l y m o r p h i cm a n y - s o r t e d 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明 确方式标明。本人依法享有和承担由此论文产生的权利和责任。 声明人c ：冽穆 印年6 具7 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 1 、保密( 2 、不保密( 年解密后适用本授权书。 ( 请在以上相应括号内打“4 ”) 作者繇烈孳嗍矽撕夕日 聊签谚嫌日期匆年多月7 日 第一章绪论 第一章绪论 g 6 d e l 语言作为新型逻辑程序设计语言，还不为人们所熟知。g 6 d e l 语言编 译系统的实现对该语言的推广、深入研究具有重要的意义。本文的重点就是要讨 论g 6 d e l 语言编译系统的设计与实现。本章首先对g 6 d e l 语言及其编译系统的研 究现状作简单的介绍。 1 1g 6 d e l 语言简介 g 6 d e l 语言是继p r o l o g 语言之后出现的新型说明性通用逻辑程序设计语言， 于2 0 世纪9 0 年代中期由英国b r i s t o l 大学的j w - l l o y d 和l e e d s 大学的p m h i l l 为首的研究小组设计开发。它建立在多态多类的一阶逻辑基础之上，摒弃了 p r o l o g 语言中的非逻辑成分，试图解决p r o l o g 语言中存在的语义问题与可表达性 较弱的问题。g 6 d e l 语言的主要特点是引入了参数型多态多类类型系统，增加了 延迟计算等新的语言成分，具有灵活的计算规则和剪枝操作，支持模块化程序设 计和元程序设计，并以系统模块的形式提供丰富的抽象数据类型以支持通用程序 设计，对其适当扩展可支持面向对象程序设计【l 】。 1 1 1g i j d e l 语言的类型系统 g ) d e l 语言的类型系统是一个多态多类的类型系统，它的引入增强了g t i d e l 语言的表达能力和程序描述能力，同时，提高了程序的可重用性。g 6 d e l 语言的 类型可归纳定义为2 】： 定义1 1 类型归纳定义如下： ( 1 ) 用户白定义的基类( 类型常量) 是类型； ( 2 ) 类型变量是类型； ( 3 ) 如果c 是一个i 元类型构造子，u i ( 江l ，2 9 7 , ) 为类型变量，则 c ( u l ，u 2 ，u 。) 是类型。 g 6 d e l 程序的语言说明中约定了每个常量、函数、命题以及谓词的类型，而 变量的类型则是由上下文匹配、推导得到。我们以下面的模块m 为例并对相关 1 g 6 d e l 语言编译系统的设计与实现 的类型作分析。 m o d u l e m b a s e d a y ，p e r s o n 模块说明 类型说明 c o n s t r u c t o rl is t 1 类型构造子说明 c o n s t a n t n i l ：l i s t ( a ) ：说明常量n i l 是一个空表 m o n d a y ，t u e s d a y ，w e d n e s d a y ，t h u r s d a y ，f r i d a y ，s a t u r d a y ， s u n d a y ：d a y ： f r e d ，m a r y ，j a m e s ：p e r s o n f u n c t i o n c o n s ：a , l i s t ( a ) o l i s t ( a ) 函数说明 p r e d i c a t e a p p e n d ：l i s t ( a ) * l i s t ( a ) * l i s t ( a ) 谓词说明 p 融m i c a t e p a r e n t ，m o t h e r ，f a t h e r ：p e r s o n * p e r s o n p a r e n t ( x ，y ) 卜m o t h e r ( x ，y ) vf a t h e r ( x ，y ) 语句 m o t h e r ( m a r y ，f r e d ) f a t h e r ( j a m e s ，f r e d ) a p p e n d ( n i l ，x ，x ) a p p e n d ( c o n s ( u ，x ) ，y ，c o n s ( u ，z ) ) 卜a p p e n d ( x ，y ，z ) 首先，我们讨论它的多类类型。在语言说明中基类( b a s e ) 说明和构造子 ( c o n s t r u c t o r ) 说明决定了程序中使用的类型。若仅说明基类而没有说明 构造子，则所有基类的集合就是程序中可定义的类型集合；若至少说明了一个构 造子，则由基类和构造子出发，得到的基本项( g r o u n dt e r m ) 构成了程序中构造 类型的集合。依一阶逻辑理论，该类型集合是可数无限集。例如，模块m 中说 明了基类类型d a y 和p e r s o n ，说明了一元类型构造子l i s t ，故该模块的类型集合 为： d a y ，p e r s o n ，l i s t ( d a y ) ，l i s t ( p e r s o n ) ，l i s t ( l i s t ( d a y ) ，) 。这是一个可数 无限集合，而程序中实际需要的类型只是其中一个有限子集，但这并不影响程序 的语义。 其次，讨论它的多态类型。g 6 d e l 语言的多态类型是通过引入类型变量来实 现的。显然，如果一个谓词或函数能表达和处理多种类型，将给程序员带来很大 的方便。一个含有类型变量的多态符号( 函数或谓词) 可以看成类型集合中所有 不同类型的多个符号的集合。例如，模块m 中的谓词说明a p p e n d ，它的3 个参 第一章绪论 数的类型都为l i s t ( a ) ，其中a 就是类型变量，a 可以取该模块中的任一类型，这 使得a p p e n d 可以对l i s t ( d a y ) ，l i s t ( p e r s o n ) ，l i s t ( l i s t ( d a y ) ) 等类型进行操作，体 现了多态性。 1 1 2g 6 d e l 语言的控制机制 g 6 d e l 语言的控制机制包括：计算规则和剪枝操作。下面我们依次对它们进 行介绍。 1 1 2 1 计算规则 计算规则是指在程序的执行过程中，依据反驳一消解原理，当前目标中如何 选择子公式( 子目标) 用于下一步的搜索和匹配。g 6 d e l 程序的执行和p r o l o g 程 序一样都是一个最左深度优先搜索的反驳消解的推理过程。在p r o l o g 语言中， 由于计算规则总是应用于最左的子目标，子目标的书写顺序将直接影响搜索树的 扩展，如果规则中子目标顺序安排不当则易于陷入无穷运算。也就是说，p r o l o g 语言的计算规则没有确保程序执行的安全性【3 】。为了解决这个问题，g 6 d e l 语言 改进了计算规则，允许在程序中显式地运用d e l a y 控制说明来表示延迟计算，这 一规则较无类型的p r o l o g 语言采用的最左子目标优先的计算规则更为灵活。若 目标子句由多个子目标的合取组成，那么，可选择的子目标并不限制一定是最左 子目标，而是根据d e l a y 说明中指定的条件，判断参数是否已实例化来决定子目 标需要延迟调用或是能够进行搜索和匹配。换言之，d e l a y 说明优先，若没有出 现d e l a y 说明，g 6 d e l 语言将沿用最左子目标优先的计算规则，这增强了程序的 有效性和可终止性。下面通过例子来说明d e l a y 说明是如何增强程序的有效性和 可终止性的。 采用d e l a y 机制可以使子目标( s u b f o r m u l a ) 协同执行，这样就比最左子目 标优先的计算规则更有效。我们考虑下面的模块c o r o u t i n e ，它导入了模块l i s t s 中的谓词p e r m u t a t i o n ( p e r m u t a t i o n ( x ，y ) 表示列表y 是列表x 的一个排列) 和s o r t e d ( s o r t e d ( x ) 表示x 是一个有序列表) 。 p r e d i c a t e p e r m u t a t i o n ：l i s t ( a ) * l i s t ( a ) ： g 6 d e l 语言编译系统的设计与实现 s o r t e d ：l i s t ( i n t e g e r ) d e l a yp e r m u t a ti o n ( x ，y )u n t i ln o n v a r ( x ) vn o n v a r ( y ) ： s o r t e d ( ) u n t i lt r u e ： s o r t e d “一j x ) u n t i ln o n v a r ( x ) 蛐u i 正c o r o u ti n e i m p o r tl i s t s p r e d i c a t e s l o w s o r t ：l i s t ( i n t e g e r ) ，l cl i s t ( i n t e g e r ) s l o w s o r t ( x ，y ) 卜s o r t e d ( y ) p e r m u t a t i o n ( x ，y ) 我们从p e r m u t a t i o n 和s o r t e d 的d e l a y 说明可以看出：p e r m u t a t i o n 的调用将 被延迟直到p e r m u t a t i o n 的第一个参数或第二个参数不是一个变量时为止。如果 s o r t e d 的调用参数不是 】或lx 】的一个实例，则调用延迟；如果s o r t e d 的调用 参数具有形式 st 】，其中t 为变量，那么调用延迟。 现在假设采用没有d e l a y 说明的最左子目标的计算规则，那么s l o w s o r t ( s l o w s o r t ( x ，y ) 表示对列表x 排序后得到列表y ) 的说明就要变成： s l o w s o r t ( x ，y ) 卜p e r m u t a t i o n ( x ，y ) 八s o r t e d ( y ) p e r m u t a t i o n 调用要位于s o r t e d 调用的左边，而如下所示的目标： 卜s l o w s o r t ( 6 ，l ，5 ，2 ，4 ，3 ，x ) 要执行n ! 步，其中n 为输入列表的长度。然而，如果采用了上面s o r t e d 的d e l a y 说明，那么执行这样的目标所花的时间将大大减少。s o r t e d 调用也必须位于 p e r m u t a t i o n 调用的左边，从而确保了子目标间的协同执行。首先s o r t e d 被延迟， 然后p e r m u t a t i o n 计算出列表的第一个元素( 假设列表长度大于1 ) ，然后s o r t e d 检查交换列表中的元素是否有序，并依此循环处理。 d e l a y 的另一个作用是保证计算的终止。以谓词p e r m u t a t i o n 定义中的d e l e t e 谓词的说明为例( d e l e t e ( x ，y ，z ) 表示从列表y 中删除元素x 得到列表z ) ： p r e d i c a t e d e l e t e ：a * l i s t ( a ) ，l c l i s t ( a ) d e l a y d e l e t e ( 一，y ，z ) u n t i lb o u n d ( y ) vb o u n d ( z ) d e l e t e ( x ， x i y ，y ) d e l e t e ( x ， y iz ， y 1 w ) 卜d e l e t e ( x ，z ，w ) 第一章绪论 若谓词d e l e t e 没有给出延迟声明，那么查询p e r m u t a t i o n ( x ，【l ，2 ，3 】) 将在 得到答案x = 1 ，2 ，3 之后陷入无穷循环。而有了延迟声明，在给出六种可能 的排列结果之后，p e r m u t a t i o n 将失败并终止。 1 1 2 2 剪枝操作 类似于p r o l o g 语言中的c u t 机制，g 6 d e l 语言也允许在程序中修剪搜索树。 剪枝算子一般的形式称为c o m m i t ，形式为 ) n ，其特殊形式为：一解剪枝 ( o n e s o l u t i o nc o m m i t ，或s i n g l e t o nc o m m i t ) 和条形剪枝( b a rc o m m i t ) 。 最简单的修剪方式是b a rc o m m i t ，形如i ，其作用和并行逻辑程序设计 语言中的c o m m i t 相似，b a r 的含义相当于合取关系。为了方便起见，规定如果 i 的两个参数中任意一个为t r u e ，则i 可以省略。每个子句至多仅包含 一个b a r 。b a r 的作用范围是在语句体内出现在i 左边的公式。由于没有指定语 句的计算次序，g s d e l 语言中剪枝没有p r o l o g 语言中割( c u t ) 的顺序特征。条形剪 枝只求出j 的辖域内公式的一个解，而搜索树中该谓词的其他语句所产生的分 支均被剪除。 例如，用于快速排序的p a r t i t i o n 谓词定义如下( p a r t i t i o n ( x ，w ，y ，z ) 表示 列表x 关于元素w 的一次划分得到列表y 和列表z ) ： p r e d i c a t e p a r t i t i o n ：l i s t ( i n t e g e r ) 术i n t e g e r ：i c l i s t ( i n t e g e r ) * l is t ( i n t e g e r ) d e l a y p a r t i t i o n ( ，一，一，_ ) u n t i lt r u e ： p a r t i t i o n ( u i 一 ，y ，一，一) u n t i lb o u n d ( u ) ab o u n d ( y ) p a r t i t i o n ( ，y ， ， ) 卜i p a r t i t i o n ( i x i x s ，y ， x li s ，r s ) 卜x _ k ylp a r t i t i o n ( x s ，y ，l s ，r s ) p a r t i t i o n ( i x l x s ，y ，l s ， x ir s ) 卜x yp a r t i t i o n ( x s ，y ，i s ，r s ) 谓词p a r t i t i o n 的三条定义语句中都使用了条形剪枝，使得三条语句是互斥 的，当要匹配的目标和三条定义语句中的一条匹配成功，则将不用选用其他两条 进行匹配，即使用条形剪枝可以剪掉无用的计算，大大提高了程序执行的效率。 g s d e l 还提供了s i n g l e t o nc o m m i t ， ) 之间所包括的公式只寻找一个解，其他 一5 g 6 d e l 语言编译系统的设计与实现 可能的答案将被剪除。例如，查询 p e r m u t a t i o n ( 1 ，2 ，3 ，x ) ) 只得到一个解 而不是全部六种排列结果。 d e l a y 声明还能消除由b a rc o m m i t 引起的失败，例如d e l e t e 谓词的另一种实 现方式如下： p r e d i c a t e d e l e t e ：i n t e g e r * l i s t ( i n t e g e r ) * l i s t ( i n t e g e r ) d e l a y d e l e t e ( x “ul ，一) u n t i lb o u n d ( x ) ab o u n d ( u ) d e l e t e ( x ， x i y ，y ) 卜i d e l e t e ( x ， yz ， yw ) 卜x yd e l e t e ( x ，z ，w ) 如果没有延迟d e l e t e 直至x 为约束的，那么根据d e l e t e 的第一条语句，查 询d e l e t e ( x ， 1 ，2 ，3 】，y ) 人x = 2 会先把x 约束为1 ，而后x = 2 失败，由于d e l e t e 的第二条语句中的b a r c o m m i t 禁止了对x 的其他约束的回溯，将导致整个查询失 败。 c o m m i t 是对搜索树进行剪枝的有效工具，它能影响程序的说明性语义，因 为在一定程度上正确答案可能被剪去。所以，首先应当指出：剪枝运算在编写风 格良好的g 6 d e l 程序中很少使用，代之以否定或i f - t h e n e l s e 等说明性结构，这主 要是为了保证程序具有清晰的说明性语义。尽管剪枝操作可能影响程序的说明性 语义，但合理的剪枝可以使程序执行速度和问题求解的效率大大提高，有着优越 的过程性语义，在逻辑程序设计语言中仍有重要的意义。 1 1 3g t i d e l 语言的模块系统 g 6 d e l 语言为满足开发大型复杂程序的需要，采用了开发独立的构件再组装 成更大的应用程序的方法。各个构件应尽量保持独立性从而减少名字冲突，构 件的具体执行细节是隐藏实现的，对其它构件透明。在g 6 d e l 语言中，把这些构 件统称为模块。 一个模块通常由两部分组成：一个本地部分( 用l o c a l 或m o d u l e 关键 字说明) 和一个输出部分( 用e x p o r t 关键字说明) 。一个模块可以只包含一个 本地部分或只包含一个输出部分或二者都包含。模块的本地部分和输出部分分别 开始于本地说明关键字和输出说明关键字，且都包含0 个或多个的导入说明、语 言说明和控制说明，不同之处在于本地部分还包含了程序语句，是这个模块功能 第一章绪论 实现的细节。如果一个模块只包含一个本地部分，那么使用关键字m o d u l e 来 说明就可以了。 下面我们来考察模块之间是如何连接的，以及不同模块之间符号的引用关 系。本文中的符号是指基本类型、类型构造子、常量、函数、谓词和命题。定义 1 1 、1 2 、1 3 分别给出了符号的导入、可用性以及符号的导出说明。 定义1 1 如果一个模块的一部分包含了如下的语言说明，则称该模块的此 部分导入了模块q ： i m p o r t q 如果在模块q 的输出部分说明了符号s 并且模块m 的本地部分( 或输出部 分) 导入了模块q ，则称模块m 的本地部分( 或输出部分) 通过模块ql _ 次导 入符号s 。 如果存在一个模块l ，其输出部分通过模块q ( n - 1 ) 一次导入符号s ，并且 模块m 的本地部分( 或输出部分) 导入了模块l ，则称模块m 的本地部分( 或输 出部分) 通过模块qn 次导入符号s ( 其中n 1 ) 。 定义1 2 如果一个符号在模块m 的本地部分( 或输出部分) 中要么被说明 要么被导入，则该符号在模块m 的本地部分( 或输出部分) 是可用的。 定义1 3 如果一个符号在模块m 的输出部分是可用的，则称模块m 导出 了该符号。 系统也对模块的引用提出了严格的要求，即模块不能依赖自身。为说明此条 件，我们给出依赖的定义： 定义1 4 如果模块m n 次导入( n 1 ) 了在模块q 中说明的任意符号s ， 则称模块m 的实现是依赖于模块q 的。 这个模块引用条件保证了模块结构关系( 导入链) 是一个有向无环图，具有 传递性和闭包性，可大大降低程序结构的复杂性。 在这样的一个模块系统的支持下，我们将一个任务进行抽象，封装在一个模 块中，把这个任务的实现细节隐藏在模块的本地部分。模块的本地部分对外界是 不可见的。 e x p o r tl i s t s 模块输出部分说明 g 6 d e l 语言编译系统的设计与实现 i m p o r t i n t e g e r s 导入的模块说明 c o n s t r u c t o r l i s t 1 类型构造函数说明 c o n s t a n t n i l ：l i s t ( a ) p r e d i c a t e a p p e n d ：l i s t ( a ) * l i s t ( a ) * l i s t ( a ) ：谓词说明 s o r t ：l i s t ( i n t e g e r ) * l i s t ( i n t e g e r ) 如上面的程序，l i s t s 模块的输出部分用e x p o r t 关键字来说明，相应地本 地部分是用关键字l o c a l 来说明，模块名与输出部分是一致的。i m p o r t 说明 了在l i s t s 模块中引入了另一个系统模块i n t e g e r s ，它规定了我们在l i s t s 中的谓 词s o r t 的说明里可直接使用模块i n t e g e r s 的输出部分所说明的类型i n t e g e r ，而对 于i n t e g e r 类型的细节我们是不可见的。在任何使用i m p o r t 来引入l i s t s 模块 的程序中都可以使用该模块的输出部分已说明了的类型、常量和谓词等，但它们 的实现细节同样隐藏在了模块l i s t s 的本地部分。可见这样的程序段提供了对 l i s t s 抽象数据类型中数据的掩蔽和操作的封装。 外部可使用的符号作为模块的外部接口放在模块的输出部分，对导入这个模 块的其他模块提供支持 4 】。这就很好地实现了对抽象数据类型的支持。我们将在 以后的工作中扩展语言成分，在抽象数据类型的基础上增加支持面向对象程序设 计的机制。 1 1 4g 6 d e l 语言对元程序设计的支持 元程序是一类重要的程序，其特点是将其它程序作为处理数据，如编译程序、 解释程序、调试程序等均是典型的元程序。用于实现解释程序的语言称为元语言， 被解释的语言则称为目标语言。在元语言中如何表示目标语言的程序和数据对象 是元程序设计的关键步骤，可以有两种方式【5 】：非基本表示( n o n g r o u n d r e p r e s e n t a t i o n ，目标语言的程序和数据对象被表示成元语言的非基本项) 和基本表 示( g r o u n dr e p r e s e n t a t i o n ，目标语言的程序和数据对象被表示成元语言的基本项) 。 非基本表示严重地限制了元程序，基本表示的功能更强，但过于复杂。p r o l o g 语 言通过提供了内置谓词：c l a u s e 2 、a s s e r t a ，z 1 、r e 仃a c f f l 等使用非基本表示进行 元程序设计，并补充了非逻辑性能。g o d e l 则采用基本表示的方式，在和p r o l o g 第一章绪论 相似的表达能力基础上增强了说明性语义。g r d e l 语言的三个系统模块s y n t a x ， p r o g r a m s ，t h e o r i e s 提供s y n t a x ，p r o g r a m ，t h e o r y , s c r i p t 等抽象数据类型支持元程 序设计，将目标语言表示为元语言中的基本项( g r o u n dt e r m ) 。 例如，抽象数据类型p r o g r a m 是用于刻画g o d e l 语言程序对象的项类型，用 于表示一个g r d e l 程序，包括所有语言说明、语句和模块结构。系统模块p r o g r a m s 提供了这一抽象数据类型上的大量操作，包括添加和删除程序中的语句、访问语 言说明、运行目标并写入程序等操作。 m o d u l e m 1 i m p o r t l i s t s ，p r o g r a m s p r e d i c a t e a p p e n d a ：l i s t ( a ) * l i s t ( a ) * l i s t ( a ) a p p e n d a ( x ，y ，z ) 卜a p p e n d ( x ，y ，z ) d e l e t e s t a t e m e n t ( p ，l i s t s ，e x p o r t ，a p p e n d ，p ) 对于模块m 。的程序，谓词 d e l e t e s t a t e m e n t ：p r o g r a m 木s t r i n g 母m o d u l e p a r t 木f o r m u l a 木p r o g r a m 提供了在程序的特定模块中删除特定语句的操作。目标 a p p e n d a ( 1 ，2 ， 3 ，4 ，z ) 返回结果 z = 1 ，2 ，3 ，4 同时，这个目标的执行还有一个副作用，将程序p 中的l i s t s 模块的e x p o r t 输 出接口部分的a p p e n d 语句删除，修改后的程序仍表示为p 。这样就使得模块l i s t s 的对外的用户接口中不含有谓词a p p e n d ，即别的用户无法再进行a p p e n d 调用 了。模块m 是对模块l i s t s 的一个元级控制程序，作用就是在执行了a p p e n d a 调 用后删除谓词a p p e n d 的用户接口。 这种使用基本表示来处理元程序设计的方法是说明性的，在不同抽象数据类 型上操作的谓词都可以被说明性地理解。这种抽象数据类型机制，以及相应的系 统模块所提供的大量实用的操作，都显示出g o d e l 语言系统为元程序设计提供了 一个很好的的机制。 g 6 d e l 语言编译系统的设计与实现 1 2 研究g i i d e l 语言的意义及其编译系统的研究现状 g s d e l 语言作为新型逻辑程序设计语言，既引入了现代程序设计语言的优秀 成分，又增加了新的机制。对它的研究，有助于相关领域的发展，也因为此，它 的编译系统已经有了一定的发展，但尚未取得真正的突破。 1 2 1 研究g i i d e l 语言的意义 b r i s t o l 大学的研究小组认为g 5 d e l 语言的研究对以下相关领域有较大意义： ( 1 ) 分布式人工智能程序设计。由于g s d e l 语言具有良好的数据类型、知 识表示形式与逻辑推理机制，具有一阶理论的支持，可以大大降低工作的复杂程 度； ( 2 ) 程序转换、程序分析、调试及有关元程序研究。和p r o l o g 语言相比， g o d e l 为这些任务提供了方便，具有更强的说明能力，并且提供了元程序设计的 专门支持，使得说明性调试程序等先进软件工程工具成为可能； ( 3 ) 逻辑程序设计语言的并行实现。g s d e l 语言的说明性特征使得语言的 并行实现较为容易，而p r o l o g 语言的非逻辑机制则给并行实现带来困难； ( 4 ) 逻辑程序设计教学。g s d e l 和常用语言如m o d u l a 2 一样具有类型和模 块系统，同时，g 6 d e l 摒弃了p r o l o g 中易于混淆的非逻辑谓词，代之以说明性 成分，比p r o l o g 更适合用于扩展语言并用于程序设计的教学，而且，从逻辑程 序设计语言易于过渡到数据库查询语言、形式化规格说明语言； ( 5 ) 逻辑程序设计的理论研究。逻辑程序设计理论和逻辑程序设计语言如 p r o l o g 复杂的非说明性语义之间存在着较大的鸿沟，g s d e l 语言则缩小了两者在 语义上的差距。 作为一种工具，g 6 d e l 语言编译系统的实现对该语言的推广、深入研究，以 及人工智能的研究和智能软件系统的开发具有重要的意义。 1 2 2g i i d e l 语言编译系统的研究现状 逻辑程序设计语言的重要性早已为人们所熟知，但g 6 d e l 语言作为新型逻辑 程序设计语言，它为人们所熟悉和认同需要一定的时间和实践，尤其需要合适的 第一章绪论 编译程序和开发环境支持，正如v i s u a lp r o l o g 等一系列解释程序和编译程序在 p r o l o g 语言的发展以及为人们接受的过程中所起到的重要作用一样。目前， g 6 d e l 语言的研究尚停留在实验阶段，b r i s t o l 大学的研究小组已经开发了单机上 的编译实验程序b r i s t o lg e j d e l 。该编译程序用s i c s t u sp r o l o g 实现，并将 s i c s t u sp r o l o g 作为目标语言，但它的执行效率较低且只能在l i n u x 环境下运行， 不具有通用性，而且仅仅实现了g s d e l 语言的一个子集【6 】。 1 3 本文的工作 g o d e l 语言初步的理论研究表明，g 6 d e l 语言的编译实现将大大超过解释实 现的效率，但实现方法和技术有诸多难点。为此，我们的工作主要是着眼于g s d e l 语言编译系统实现的研究，同时，为了实现编译的