（计算机应用技术专业论文）Gdel语言程序设计环境的设计与实现.pdf

摘要 摘要 g i ；d e l 语言是继p r o l o g 语言之后出现的一种通用、高效、表达性较强的说 明性逻辑程序设计语言，它摒弃了p r o l o g 语言中的非逻辑成分，试图解决p r o l o g 语言中存在的语义问题。在多年来逻辑程序设计研究和原有p r o l o g 语言的基础 上，g g d e l 语言引入了类型系统和模块系统，增加了延迟计算和剪枝操作等控制 机制，支持抽象数据类型( a d t ) 和元程序设计，使它具有较强的可表达性能力。 逻辑程序设计语言的重要性早已为人们所熟知，但g i ，d e l 语言作为新型逻辑 程序设计语言，它为人们所熟悉和认同需要一定的时间和实践，尤其需要合适的 编译程序和开发环境支持。本文承接项目组开发的一个g g d e i 语言编译程序，设 计和初步实现了一个g g d e l 语言程序设计环境g p d e ( g 5 d e lp r o g r a m m i n g d e v e l o p m e n te n v i r o n m e n t ) ，它是一个在w i n d o w s 环境下开发的集程序设计、文 件编辑、程序编译、连接装配、运行调试和程序执行等多种功能于一体的具有良 好人机交互界面的可视化程序设计环境，为g g d e l 语言程序设计与开发提供了良 好的支持。我们依据现代系统软件开发原理和风范，在给出用户需求分析和系统 基本功能分析的基础上，设计并提出了实现g g d e l 语言程序设计环境g p d e 的体 系结构模型，阐述了该体系结构模型的工作原理及其各功能模块的设计思想，分 析了它与编译程序和推理机程序的关系，并着重阐述了g p d e 中多文档机制的源 程序编辑程序、项目资源管理和可视化计算技术等部件的实现方法和技术。 模块系统是g g d e l 语言的重要成分和机制，它支持抽象数据类型( a d t ) 程序 设计。g 6 d e l 语言本身拥有一个丰富的系统模块库，可为用户提供几乎满足各种 应用需要的抽象数据类型。模块系统在g p d e 中的组织和实现为g g d e l 语言的编 译系统提供了一种模块独立编译的实现机制。本文详细介绍了分块编译和类型安 全链接机制，对模块系统在g p d e 中的组织方法和实现进行了详细的分析和设计， 给出了模块系统实现的功能结构，并对其中的编译预处理、模块存储器和独立编 译生成中间文件等主要的功能模块及其实现做了详细的阐述，同时，对g 甜e l 语言系统模块的实现和动态调用做了详细的介绍，并给出了系统模块的实现实 例。 g 6 d e i 语言程序设计环境的设计与实现 我们设计和实现的这个g s d e l 语言程序设计环境g p d e 基本上拥有当前高级 语言程序设计环境的功能组成，它将为g b d e l 语言的推广、深入研究起到一定的 基础作用。相信随着g 6 d e l 语言编译系统实现技术的逐步成熟，以及其程序设计 环境的不断完善，g 6 d e l 语言将会受到更多的关注。 关键词：g s d e l 语言；程序开发环境；模块系统 a b s t r a o t g 刮l e li sad e c l a r a t i v e ，g e n e r a l - p u r p o s e ，h i g he f f i c i e n c yl o g i cp r o g r a m m i n g l a n g u a g es u c c e e dt ol a n g u a g ep r o l o g g o d e ld i s c a r & t h eu n l o g i ci n g r e d i e n ta n dt r i e s t os o l v et h es e m a n t i cp r o b l e mi nl a n g u a g ep r o l o g b a s e do nt h eo r i g i n a l p r o l o g l a n g u a g ea n dt h ey e a r s r e s e a r c ho i ll o g i cp r o g r a m m i n g , g o d e li n t r o d u c e st ot y p e s y s t e m , m o d u l e s ，d e l a ya n dc o m m i tc o n t r o lr o l e si nl a n g u a g e i ta l s op r o v i d e s 、历t 1 1 t h ef a c i l i t yo fa b s t r a c td a t at y p e ( a d t ) a n dm e t a - p r o g r a m m i n g , a l lo ft h e s e i n g r e d i e n t sm a k et h en e wl a n g u a g em o r ee x p r e s s i v e t h ei m p o r t a n c eo ft h el o g i cp r o g r a m m i n gh a sb e e nf a m i l i a rt op r o g r a m m e ry e a r s b e f o r e b u tt ob ean e wl o g i cp r o g r a m m i n gl a n g u a g e ，g o d e ln e e d ss o m et i m ea n d p r a c t i c e st om a k ei t s e l ft ob ea c c e p t e da n dp o p u l a r , w h i c he s p e c i a l l yr e q u i r e st h e s u p p o r to ft h ea p p r o p r i a t ec o m p i l e ra n dd e v e l o p m e n te n v i r o n m e n to ft h i sl a n g u a g e i n t h i s p a p e r , w ed e s i g na n dp r i m a r i l yi m p l e m e n tap r o g r a m m i n gd e v e l o p m e n t e n v i r o n m e n tf o rg 6 d e l ( g p d e ) s u c c e e dt ot h ed e v e l o p m e n to ft h eg 6 d e lc o m p i l e r w h i c hd e s i g n e da n d i m p l e m e n t e db yo t h e r sm e m b e ri np r o j e c tt e a m g p d ei sav i s u a l p r o g r a m m i n gd e v e l o p m e n te n v i r o n m e n tr u n n i n gu n d e rw i n d o w se n v i r o n m e n t rh a s m a n yt h ef u n c t i o n ss u c ha sp r o g r a m m i n g , f i l ee d i t ，p r o g r a mc o m p i l i n g , l o a d i n ga n d l i n k i n g , r u n n i n ga n dd e b u g g i n g , a n dp r o g r a mr u n n i n g s oi tc a np r o v i d ew e l ls u p p o r t f o rg 6 d e lp r o g r a m m i n g a c c o r d i n ga st h ed e v e l o p m e n tp r i n c i p l ea n ds t y l eo fm o d e r ns y s t e ms o r w a r e ，i n t h i sp a p e r , w ed e s i g na n dg i v et h es y s t e mf r a m e w o r km o d e lo fg p d eb a s e do n r e q u i r e m e n ta n a l y s i sa n df u n c t i o na n a l y s i s w ed i s c u s st h ew o r kp r i n c i p l eo ft h e m o d u l ea n dt h ed e s i g ni d e a so ft h em a i nf u n c t i o nm o d u l e t h e nw eg i v et h e c o n n e c t i o no ft h ec o m p i l e ra n di n f e r e n c em a c h i n e 、) i ，i 也g p d e , a n de m p h a s i z et h e i m p l e m e n t a t i o nm e t h o da n dt e c h n i q u eo ft h em u l t i d o c u m e n t - i n t e r f a c ec m d i ) s o u r p c o d ee d i t o r , p r o j e c tm a n a g e ra n dt h ev i s u a lc o m p u t a t i o n t e c h n o l o g y m o d u l es y s t e mi so n eo ft h em a i ni n g r e d i e n ta n df a c i l i t yo fg 6 d e l ，i ts u p p o r tt h e g 玷d el 语言程序设计环境的设计与实现 p r o g r a m m i n go fa b s t r a c td a m 孵( a d t ) g 6 d e ll a n g u a g ei t s e l fh a sar i c hs y s t e m m o d u l e sl i b r a r y , i tp r o v i d e sw i t ha b s t r a c td a t at y p ew h i c hh a r d l ys a t i s f i e sa l lt h e a p p l i c a t i o nf o ru s e r s t h eo r g a n i z a t i o na n di m p l e m e n t a t i o nf o rt h em o d u l es y s t e mi ng p d ew i l l p r o v i d ew i t has e p a r a t ec o m p i l i n gi m p l e m e n t a t i o nf a c i l i t yf o rg t d e ll a n g u a g e s c o m p i l i n gs y s t e m t h em o d u l es y s t e mw eh a v ei m p l e m e n t e dp r o v i d e sac o m p i l e - l i n k m o d u l ew h i c hs u p p o r t ss e p a r a t e dc o m p i l i n ga n dt y p e s a f el i n k i n gf a c i l i t y i nt h i s p a p e r , w eg i v ead e t a i ld e s i g na n da n a l y s i sf o rt h eo r g a n i z a t i o na n di m p l e m e n t a t i o no f t h em o d u l es y s t e mi ng p d e ，f i r s t l y , w eg i v et h ef u n c t i o nf l a m e w o r k ，s e c o n d l y , w e g i v et h ed e t a i ld e s i g na n di m p l e m e n t a t i o nf o rt h ep r e - c o m p i l i n gp r o c e s s o r , m o d u l e s t o r a g ea n dt h ei n t e r m e d i a t ef i l ew h i c hg e n e r a t e db ys e p a r a t e dc o m p i l i n g a tl a s tw e g i v et h ei m p l e m e n t a t i o ne x a m p l e so ft h es y s t e mm o d u l e o nt h ew h o l e ，t h eg 6 d e lp r o g r a m m i n ge n v i r o n m e n tg p d ew h i c hw ed e s i g na n d i m p l e m e mh a st h eb a s i cf u n c t i o nc o m p o n e n to fm o d e ma d v a n c e dp r o g r a m m i n g e n v i r o n m e n t g p d ew i l lb a s i c a l l yh e l pw i t ht h ep o p u l a ra n dd e e ps t u d yo fl a n g u a g e g 6 d e l w eb e l i e v e dt h a tg 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 na n d o b t a i nam o r ew i d e s p r e a du s ew i t ht h em a t u r eo fg 6 d e lp r o g r a m m i n ge n v i r o n m e n t k e yw o r d ：l a n g u a g eg 6 d e l ；p r o g r a m m i n gd e v e l o p m e n te n v i r o n m e n t ；m o d u l e s y s t e m 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：女芥娜 州年6 月6 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ( 请在以上相应括号内打“4 ) 作者签名：1 灰半词产 导师签名易叁徘 二 日期：为。 年月占日 b 期：矽7 年多其7e l 第一章绪论 第一章绪论 g & l e l 语言作为新型逻辑程序设计语言，还不为人们所熟知。g & t e l 语言编 译系统及其程序设计环境的实现对该语言的推广、深入研究具有重要的意义。本 文的重点就是要讨论g & t e l 语言程序设计环境的设计与实现。本章首先对g & t e l 语言及其编译系统的研究现状作简单的介绍，并给出本文的主要工作概要说明。 1 1g 6 d el 语言的主要特点及其对程序设计环境的影响 g 6 d e l 语言是继逻辑程序设计语言p r o l o g 之后出现的一种通用、高效、表 达性较强的说明性逻辑程序设计语言【，它建立在多态多类的一阶逻辑基础之 上，摒弃了早期p r o l o g 语言中的非逻辑成分，试图解决p r o l o g 语言中存在的语 义问题。g 6 d e l 语言的主要特点是增加了参数型多态多类类型系统，引入了延迟 计算等新的语言成分，支持模块化程序设计和元程序设计，具有灵活的计算规则 和剪枝操作，并以系统模块形式提供丰富的抽象数据类型支持通用程序设计。这 里，我们将概要介绍g s d e l 语言的主要特征及其对程序设计环境的影响。 1 1 1g s d e l 语言的类型系统 在逻辑程序设计语言中引入类型的主要目的是为了提高知识可表达性能力 和程序描述能力。早期p r o l o g 语言的逻辑基础是无类型( u n s o r t e d ) 的一阶逻辑 的h o r n 子集，而g 6 d e l 语言的逻辑基础则是多态多类( p o l y m o r p h i s m m a n y - s o r t e d ) 的一阶逻辑。正是不同的逻辑基础使得g s d e l 语言具有更强的可表 达性能力。g 6 d e l 语言是一种强类型语言，在程序的说明部分规定了每个常量、 函数、命题以及谓词的类型，而变量的类型可根据上下文进行推断得到这意味 着每个表达式、谓词、函数等定义，都能在编译时检查它们是否符合语言的类型 说明规则，强类型系统接受表达式的定义能确保计算时不发生类型错误。 下面，我们以模块m 1 为例，对g 6 d e l 语言的多态多类类型系统进行简单的 讨论。模块m l 的定义如图1 1 所示。 6 8 d el 语言程序设计环境的设计与实现 m o d u l e m i 模块说明 b a s e d a y ，p e r s o n 基类类型说明 0 0 瞒t 砥j c t 衄l i s t 1 类型构造子说明 c 0 嘲瓢n t n i l ：l i s t ( a ) ：常量说明 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 ，b a r n e y 。w il m a ，b e t t y ：p e r s o m f 唧c t i 嘶c o n s ：a 宰l i s t ( a ) _ 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 r e d i c a t e a p p e n d 3 ：l i s t ( a ) 枣l i s t ( a ) 幸l i s t ( a ) 牛l i s t ( a ) p r e d i c a t ep 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 ， a p p e n d 3 ( x ，y ，z ，u ) 卜a p p e n d ( x ，y ，旬a p p e n d h ， 规则语句 事实语句 z ) z ，u ) 图1 1 一个模块m 1 的定义 首先，我们讨论它的多类类型。在程序的说明中基类( 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 1 中说明了基 类类型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 s d e l 语言的多态类型是通过引入类型变量来实 2 ) ) ) ) ) ) ) ) ) 0 l n 心 “ 伯 仃 n n ) ) ) ) ) ) 地 n m 垢 坞 ，l，l 第一章绪论 现的。显然，如果一个谓词或函数能表达和处理多种类型，将给程序员带来很大 的方便。一个含有类型变量的多态符号( 函数或谓词) 可以看成类型集合中所有 不同类型的多个符号的集合。例如，模块m 1 中的谓词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 ) 等类型进行 操作，体现了类型的多态性。 可见，g s d e l 语言相对于早期的p r o l o g 语言，最大的优势之一是引进了强类型 机制。类型声明可以使编译程序在g s d e l 语言程序开发的早期阶段指出创建的类 型错误和较严重的逻辑错误。更进一步，这些类型声明将有助于编译程序生成更 有效的程序，在执行期间节省更多的存储空间。 因此，基于g s d e l 语言的强类型机制，在其程序设计环境中应提供相关的功能 模块来支持类型的检测。具体包括以下两个方面： ( 1 ) 提供智能化的编辑器，在编辑程序的同时，能为程序员指出定义的类型 错误。在当前流行的许多语言的集成开发环境，如b o r l a n d 公司开发的集成开发 工具c + + b u il d e r 就能在程序编辑过程中指出定义的类型错误； ( 2 ) 提供良好的用户交互界面，能即时、准确地显示类型检查的错误报告并 根据报告准确定位错误所在的位置。 1 1 28 i j d e i 语言的模块化程序结构 在g s d e l 语言中，程序是由模块的集合 m ；) n i = o ( n 0 ) 组成，其中至少包含一个 主模块m d ，子集 m ；) “。中的模块由 i o 直接或间接导入。g s d e l 语言的一个模块通 常由两部分组成：一个本地部分( 用l o c a l 或m o d u l e 关键字说明) 和一个输出 部分( 用e x p o r t 关键字说明) 【l 】。一个模块的输出部分包括导入模块说明、语 言说明、控制说明。语言说明中声明的符号可用于此模块的任何地方和其它导入 这个模块的模块中的任何地方；控制说明和导入模块说明中给出一些来自其它模 块的符号，这些符号同样可用于本模块的任何地方和其它导入本模块的模块中的 任意地方。一个模块的本地部分同样包括语言说明、控制说明和导入模块说明， 本地模块的语言说明中声明的符号只在本地模块可用；导入模块说明给出来自其 它模块可以在本地模块使用的符号；控制说明以及那些命题和谓词的定义由本地 6 8 d e l 语言程序设计环境的设计与实现 模块中的语言说明来具体定义。模块的本地部分和输出部分分别开始于本地说明 关键字和输出说明关键字，且都包含0 个或多个的导入模块说明、语言说明和控 制说明，不同之处在于本地部分还包含了程序语句，是这个模块功能实现的细节。 g s d e l 语言的一个模块可以只包含一个本地部分或只包含一个输出部分或二者都 包含，如果一个模块只包含一个本地部分，用关键字m o d u l e 说明。 同时，g s d e l 语言还提供了一个丰富的系统模块集共包含2 0 个系统模块【l 】， 这些模块中有用来处理数字( n u m b e r s ) 、列表( l i s t s ) 、字符串( s t r i n g s ) 、集 合( s e t s ) 等的模块，还有提供输入输出的模块和提供元一程序设计机制的模块。 g s d e l 系统模块提供了大量重要的抽象数据类型( a d t ) ，包括u n i t ( 单元类型， 类似项结构) ，f l o c k ( 有序单元集合的类型) ，p r o g r a m ( 表示g s d e l 程序的项类 型) 和t h e o r y ( 表示多态多类一阶理论的项类型) 。对于每一种模块提供了该类 型上的操作集合，模块系统隐藏了这些操作的执行细节。同时，g s d e l 语言系统 模块提供的类型可以是部分抽象的，也即用户还可以在模块中自定义类型。不过， g s d e l 已经提供了许多完备的抽象数据类型，用户在对g s d e l 语言充分了解的基 础上，可以熟练地使用g s d e l 语言已经定义好的抽象数据类型，不必自己重新定 义。总之，g s d e l 语言本质上提供了几乎可以满足各种应用需要的抽象数据类型， 同时也为用户提供了自己定义抽象数据类型的机制。 由此我们可以看出，g s d e l 语言充分利用了抽象数据类型的思想，它是通过 使用模块和类型系统来实现的，一个抽象数据类型由一个类型和该类型上的操作 集组成，类型表示方法的细节和操作的执行细节是不可见的，实现了数据隐藏与 操作封装。 模块系统在软件工程中的应用是众所周知的，它同样也很好地应用在了 g s d e l 语言中。在g s d e l 语言中模块化机制提供了组织大规模复杂程序的方法， 能避免程序的不同部分之间的名字冲突，并且提供隐藏程序执行细节的方法。因 此，在g s d e l 语言程序设计环境中应提供组织多文件结构的大型程序项目的具体 功能，包括以下三点： ( 1 ) 将每个功能相关模块放在一个单独的文件中，并以模块名来命名文件 名，支持以模块文件( 一个模块对应于一个源程序文件) 为单位进行独立的编译 和程序调试。 4 第一章绪论 ( 2 ) 提供项目资源管理功能，为用户创建的项目添加不同功能的模块文件： ( 3 ) 提供项目文件目录树管理，用户能够通过目录树，可以查看相关功能 模块所在的源文件。同时，应提供菜单项文件列表，在列表中显示当前所有打开 的文件。 对模块系统做适当变动可以支持面向对象程序设计，我们将在第五章详细阐 述g s d e l 语言的模块系统机制及其对面向对象程序设计的支持。 1 1 3g 6 d e l 语言的控制机制 g 6 d e l 语言的控制机制包括：计算规则和剪枝操作。下面我们依次对它们进 行介绍。 1 计算规则 计算规则是指在程序的执行过程中，依据反驳消解原理，当前目标中如何 选择子公式( 子目标) 用于下一步的搜索和匹配。g 6 d e l 程序的执行和p r o l o g 程 序一样都是一个最左深度优先搜索的反驳消解的推理过程。在p r o l o g 语言中， 由于计算规则总是应用于最左的子目标，子目标的书写顺序将直接影响搜索树的 扩展，如果规则中子目标顺序安排不当则易于陷入无穷运算。也就是说，p r o l o g 语言的计算规则没有确保程序执行的安全性网为了解决这个问题，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 ya t o mu n t i lc o n d ( 2 ) c o n d 专c o n d lic o n d l & c o n d l lc o n d l vc o n d l ) ( 3 ) c o n d l 一唧腿( v a r i a b l e ) ig r o 咖( y a r i a b l e ) i 侧ei ( c o n d 图1 2d e l a y 控制说明的语法形式 5 6 6 d el 语言程序设计环境的设计与实现 其中，a t o m 为原子，c o n d 对原子中出现的变量延迟调用条件进行说明， v a r i a b l e 是出现在a t o m 中的变量，关键字n o n v a r 表示延迟条件中指称的对象 是变量时延迟执行该原子公式的计算，直到该对象不再是变量时为止。类似地， 关键字g r o u n d 可视为一个断言，表示变量为基本项。 ( 1 ) p r e d i c a t e f i b ：i n t e g e r 宰i n t e g e r 谓词说明 ( 2 ) b e l a yf i b ( x ，y ) u n t i ln o n v a r ( x ) vn o n v a r ( y ) 控制说明 图1 3 谓词f i b 的语言说明 如图1 3 谓词f i b 的语言成分说明中使用了d e l a y 控制，它表示当谓词f i b 的两个参数至少有一个不是变量时才进行计算，当两个参数都是变量时，计算 f i b 将失败，这使得程序不会进入循环的搜索、匹配中，保证了程序的正确性、 有效性和可终止性。 2 g s d e l 语言剪枝机制 g s d e l 语言包含剪枝规则，它可以用来对一棵搜索树进行剪枝操作，进而影 响搜索过程的完整性。剪枝算子一般的形式称为c o m m i t ，形式为 ) j 。g s d e l 语言为程序员提供了两种不同的剪枝处理，分别为一解剪枝( o n es o l u t i o n ，或 s i n g l e t o nc o n n n i t ) 和条形( b a rc o n n n i t ) 剪枝。一解剪枝是当找到了一个解时就 立即返回，相当于剪除剩下的全部分枝，不再进行求解计算。条形剪枝是在剪枝 条件满足时，删除程序中满足定义里剪枝条件的剪枝标记所标示的所有其它语句 的分支。 ( 1 ) f i b ( 0 ，0 ) 卜 t r u e 一1 语句 ( 2 ) f i b ( 1 ，1 ) 4 - - t r u e 一1 ( 3 ) f i b ( k ，n ) 4 - - k 1 ) 一1 f i b i t ( k - 2 ，1 ，1 ，n ) 图1 4 谓词f i b 的剪枝规则程序语句 同样地，如图1 4 中在求f i b 的规则中加入了剪枝规则，3 条f i b 规则是互 斥的，若当前匹配项与其中一条匹配时，则将具有和当前规则相同剪枝号的规则 剪掉，省去了无用的计算。 6 第一章绪论 剪枝规则是对搜索树进行剪枝的有效工具。由于程序的执行存在不确定性， 如果发生正确答案所在分支被剪去的情况，它将影响程序的说明性语义。显然， 剪枝的不恰当应用有可能偏离了g s d e l 语言设计的基本目标使程序尽可能 有更好的说明性语义。所以，剪枝在g s d e l 程序里较少使用，因为它可用诸如否 定或i f - t h e n - e l s e 等的说明性控制结构来替换。g s d e l 提供的另一个控制机制 是i f - t h e n - e l s e 结构，这个结构具有说明性语义而且提供了重要的控制信息。 i f - t h e n - e l s e 结构经常出现在g s d e l 的程序中，这是g 6 d e l 程序设计风格之一。 g 6 d e l 语言的这些控制机制是g s d e l 语言独特的重要程序机制，它能够改变 程序的执行顺序，提高程序的执行效率。因此在g s d e l 语言的程序设计环境中应 提供可视化计算的功能机制，提供一个交互式图形用户界面，直观地显示程序的 执行轨迹。并且为程序员提供一个可视化的程序结构和执行效率的监控工具。 1 1 4g 6 d e l 语言对元程序的支持机制 元程序是一类重要的程序，其特点是将其它程序作为处理数据，如编译程 序、解释程序、调试程序等均是典型的元程序。用于实现解释程序的语言称为元 语言，被解释的语言则称为目标语言。在元语言中如何表示目标语言的程序和数 据对象是元程序设计的关键步骤，可以有两种方式闭：非基本表示( 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 l 、r c t r a c f f l 等使用非基本表示进行 元程序设计，并补充了非逻辑性能。g 6 d e l 则采用基本表示的方式，在和p r o l o g 相似的表达能力基础上增强了说明性语义。g 6 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 6 d e l 语言程序对象的项类型，用 于表示一个g 6 d e l 程序，包括所有语言说明、语句和模块结构。系统模块p r o g r a m s 提供了这一抽象数据类型上的大量操作，包括添加和删除程序中的语句、访闯语 言说明、运行目标并写入程序等操作。 7 d ei 语言程序设计环境的设计与实现 坂l d 眦 m 。 i m p 0 9 r 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 ) ad 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 c 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 6 d e l 语言系统为元程序设计提供了 一个很好的的机制。 1 2g 6 d ei 语言的研究背景及科学意义 1 2 1 研究背景 逻辑程序设计语言从1 9 7 2 年k o w a l s k i 和c o l m e r a u e r 提出逻辑可以作为程 序设计语言的基本思想诞生以来，已经历了3 0 多年的发展历程。逻辑程序设计 语言的设计环境，也随着语言理论的发展而不断的完善和改进。其中围绕p r o l o g 语言的开发环境从最初的解释系统下的命令行开发环境，到后来为了提高程序的 执行效率出现的并行p r o l o g 开发环境，以及近年来出现的v i s u a lp r o l o g 的集 第一章绪论 成开发环境。v i s u a lp r o l o g 是p r o l o g 开发中心( p d c ) 最新推出的基于w i n d o w s 环境的智能化开发工具，它是在原有p r o l o g 语言的基础上，集当代高级程序设 计语言的优点和逻辑程序语言的优点于一身的可视化逻辑程序设计语言集成开 发环境，已经在美国、加拿大、西欧等发达国家和地区得到广泛的使用。 但是现有的逻辑程序设计语言编译系统及其开发环境基本上都是基于 p r o l o g 语言的，最初的p r o l o g 语言存在一些语义上的问题，后来随着逻辑程序 语言理论的发展，一些问题得到了解决，但是同时为了提高其程序的开发效率， 在其语言成分中集成了一些非逻辑的成分，这使得逻辑程序设计语言在一定的程 度上降低了它语言应有的优势，如高说明性和强表达性，从而也降低了语言的可 靠性、代码的可读性以及运行结果的正确性【。 g 5 d e l 语言的出现正是希望改变这种现状，它是在9 0 年代中期由以英国 b r i s t o l 大学的j w l l o y d 和l e e d 大学的p m h il l 为代表的研究小组设计 开发。设计者以2 0 世纪著名的逻辑学家k u r tg 5 d e l 为该语言命名，并指出g 5 d e l 恰好也是g o d so w nd e c l a r a t i v el a n g u a g e 字首的缩写。但g s d e l 语言作为新 型的逻辑程序设计语言，它为人们所熟悉和认同需要一定的时间和实践，尤其需 要合适的编译系统和开发环境支持，正如v is u a lp r o l o g 等一系列解释器和编译 器在p r o l o g 语言的发展和为人们接受的过程中起到重要的作用一样。目前， g s d e l 语言尚停留在实验阶段，b r i s t o l 大学的研究小组已经开发了单机上的编 译实验程序- b r is t o lg s d e l ，该编译器用s i c s t u sp r o l o g 实现，并将s i c s t u s p r o l o g 作为目标语言【3 1 。该实验系统允许用户从网上免费下载【4 】，提供了s p a r c 工作站环境下的系统，但它的执行效率较低且只能在l i n u x 环境下运行，不具有 通用性，而且仅仅实现了g s d e l 的一个子集。遗憾的是，目前尚未开发m s d o s 或m i c r o s o f tw i n d o w s 环境下的编译器，如果要在p c 机上试运行g s d e l ，则必 须在l i n u x 环境下。 1 2 2 研究的科学意义 b r i s t o l 大学的研究小组认为g s d e l 语言的研究对以下相关领域有较大意义： ( 1 ) 分布式人工智能程序设计。由于g 6 d e l 语言具有良好的数据类型、知识 表示形式与逻辑推理机制，具有一阶理论的支持，可以大大降低工作的复杂程度； 9 a o d el 语言程序设计环境的设计与实现 ( 2 ) 程序转换、程序分析、调试及有关元程序研究。和p r o l o g 语言相比， g 6 d e l 为这些任务提供了方便，具有更强的说明能力，并且提供了元程序设计的 专门支持，使得说明性调试程序等先进软件工程工具成为可能； ( 3 ) 逻辑程序设计语言的并行实现。g 6 d e l 语言的说明性特征使得语言的并 行实现较为容易，而p