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

摘要 摘要 逻辑程序设计语言提供了一种说明性的编程方法，与基于算法的过程性程序 设计语言如p a s c a l 、a d a 和c 等相比，逻辑程序设计语言具有诸多优点。首先， 逻辑程序丰富的表达能力和不确定性语言机制，使其非常适合于表达人工智能和 知识工程中的问题；其次，逻辑程序建立在一阶谓词逻辑的基础之上，具有严格 的数学理论基础，易于进行程序的正确性证明和验证；第三，逻辑程序开发者不 需要考虑程序“如何计算 ，而只需要说明要“做什么 ，从而有利于其将精力集 中到问题的求解上，从计算模型的层面探索问题的求解。由于p r o l o g 语言取得 的成功，一直以来p r o l o g 都是逻辑程序设计的代称。但是，p r o l o g 基于一阶逻辑 的h o r n 子集，作为一种无类型逻辑程序设计语言，缺乏足够的可表达性，而且， 由于p r o l o g 中引入了较多的过程性谓词如c u t 和r e t r a c t 等，使其缺乏清晰、明确 的说明性语义。 鉴于此，逻辑程序设计的研究者们提出了新型逻辑程序设计语言g 6 d e l ，它 继承并发展了p r o l o g ，试图解决p r o l o g 中存在的诸多语义问题，增强其可表达性 能力，缩小理想的逻辑程序与逻辑程序的具体实现之间的巨大鸿沟。据此，它引 入了参数型多态多类类型系统，增加了延迟计算等新的语言成分，支持模块化程 序设计和元程序设计，具有灵活的计算规则和剪枝操作，并以系统模块形式提供 丰富的抽象数据类型以支持通用程序设计，对其适当扩展可支持面向对象程序设 计。但是，作为一种新型的逻辑程序设计语言，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 语言程序设计和s l d 反驳一消 解过程的影响。进一步，借鉴w a r r e n 虚拟机的设计思想，提出了将g 6 d e l 源程 序通过词法、语法和语义分析把源程序翻译成带说明性语义信息的一种高度结构 g f 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 l o g i cp r o g r a m m i n gl a n g u a g ep r o v i d e sad e c l a r a t i v ep r o g r a md e s i g n i n gm e t h o d a n dh a ss e v e r a l a d v a n t a g e sc o m p a r e d w i t ht h e a l g o r i t h m b a s e dp r o g r a m m i n g l a n g u a g es u c ha sp a s c a l ，a d aa n dc a n ds oo n f i r s t l y , l o g i cp r o g r a mi ss u i t a b l ef o r e x p r e s s i n gt h ep r o b l e m si n t h e a r e ao fa r t i f i c i a li n t e l l i g e n c ed u et o i t s a m p l e e x p r e s s i o na b i l i t ya n di n d e t e r m i n a c yn a t u r e s e c o n d l y , f o u n d e do nt h ef i r s tp r e d i c a t e l o g i c ，l o g i cp r o g r a mi sp r o v i d e dw i t has t r i c tm a t h sb a c k g r o u n d , w h i c hm a k e s i te a s y t oc o r r e c tp r o v i n ga n d v a l i d a t i n g f i n a l l y , t h el o g i cl a n g u a g ep r o g r a m m e r sh a v e n o tt o c o n s i d e r h o wt oc o m p u t e a n do n l yt os p e c i f y w h a tt od o ，h e n c et h e yc a nd e d i c a t e t h e i re n e r g yt ot h es o l u t i o no ft h ep r o b l e m sa n dq u e s tf o rt h es o l u t i o na tt h el e v e lo f c o m p u t i n gm o d e l b e c a u s eo f t h eh u g es u c c e s so fp r o l o g ，p r o l o gi sa l w a y sc o n s i d e r e d a st h ea l i a so ft h el o g i cp r o g r a ml a n g u a g e h o w e v e r ，p r o l o gb a s e so nt h eh o ms u b s e t o ff i r s tp r e d i c a t el o g i ca n di st y p e l e s s ，w h i c hm a k e si t se x p r e s s i o na b i l i t yh a r dt o s a t i s f yt h en e e do fp r a c t i c ea p p l i c a t i o n m o r e o v e r , i ti m p o r t sm a n yp r o c e s sp r e d i c a t e ， f o re x a m p l ec u ta n dr e t r a c ta n ds oo n ，w h i c hm a k e si tl a c ko fc l e a ra n dd e f i n i t i v e d e c l a r a t i o ns e m a n t i c a c c o r d i n gt oa b o v er e a s o n s ，t h er e s e a r c h e r so fl o g i cp r o g r a m m i n gl a n g u a g ea r e a p r o p o s et h eg 6 d e l w h i c hi n h e r i t sa n dd e v e l o pt h ep r o l o ga n dt r yt os o l v et h es e m a n t i c p r o b l e m so fp r o l o g ，b o o s tu pt h e i t se x p r e s s i o na b i l i t ya n ds h o r t e nt h el a r g eg a p b e t w e e nt h ei d e a la n dp r a c t i c el o g i cp r o g r a m m i n gl a n g u a g e s oi ti n t r o d u c e st h et y p e s y s t e m ，i n c r e a s et h el a n g u a g ee l e m e n t ss u c ha sd e l a yc o m p u t i n g ，a n d c a l ls u p p o r tt h e m o d u l a ra n dm e t a p r o g r a mp r o g r a m m i n g ；i th a sf l e x i b l ec o m p u t i n gr e g u l a t i o na n d c o m m i t p r u n i n go p e r a t i o na n dp r o v i d et h em e c h a n i s m t os u p p o r tt h ea b s t r a c td a t a t y p ep r o g r a m m i n gt h r o u g ht h es y s t e mm o d u l a r s h o w e v e r , a sal o g i cp r o g r a m m i n g l a n g u a g e ，w h e t h e rg 6 d e l c a na c h i e v eab i gs u c c e s si sd e t e r m i n e db yt h e i m p l e m e n t i n go fg 6 d e ls y s t e m t h i sp a p e rs h o w sai m p l e m e n t i n gs c h e m eo f g o d e l r e a l i z a t i o ns y s t e ma n dm a i n l yf o c u s e so nt h ei m p l e m e n t i n go ft h ei n f e r e n c em a c h i n e i nt h i sa r t i c l e ，w ef i r s t l yd i s c u s st h ee f f e c to ft h em a i nm e c h a n i s mo fg 6 d e ls u c h a st y p es y s t e m ，d e l a yc o m p u t i n ga n dp r u n i n go p e r a t i o na n ds oo n a n dt h e n ，w es h o w g - 6 d e l 语言编译系统中推理机的设计与实现 t h ed e s i g ni d e ao ft h eg o d e lr e a l i z a t i o ns y s t e mw h i c hi st h a tt h es y s t e mf i r s t l y t r a n s l a t e st h es o u r c ec o d eo ft h eg 6 d e lp r o g r a mt oh i g hd e g r e es t r u c t u r a li n t e r m e d i a t e c o d ea n dt h e nc a r r yt h r o u g ht h er e a s o n i n gb a s e do nt h ei n t e r m e d i a t ec o d e a c c o r d i n g t ot h i si d e aw eg i v et h ea r c h i t e c t u r eo ft h ec o m p i l e rs y s t e ma n dt h e nw eg i v et h e i n t e r m e d i a t ec o d es 缸u c t u r ea n dt h ei m p l e m e n tm e t h o do ft h ei n f e r e n c em a c h i n e f i n a l l y , t h r o u g ht h ep e r f o r m a n c ea n a l y z i n g ，w ep r o v eo u ri n f e r e n c em a c h i n eo w n i n g a g o o de f f i c i e n c y k e y w o r d s ：g 6 d e l ；i n f e r e n c em a c h i n e ；i n t e r m e d i a t ec o d e 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文而产生的权 利和责任。 声明人( 签名) ：鳓 2 0 0 7 年上月五日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留 并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 本学位论文属于 1 保密( ) ，在年解密后适用本授权书。 2 不保密吣 ( 请在以上相应括号内打“ ) 作者签名：乏笔弘亟全日期：碰年正月卫日 导师签名哆参窒鬈。日期：么班上月丑日 第一章导论 第一章导论 逻辑程序设计语言提供了一种说明性的程序设计方法，与基于算法的过程性 程序设计语言如p a s c a l 、a d a 和c 等相比，逻辑程序设计语言具有诸多优点。首 先，逻辑程序设计语言丰富的表达能力和不确定性语言机制，使其非常适合于表 达人工智能和知识工程中的问题；其次，逻辑程序设计语言建立在一阶谓词逻辑 的基础之上，具有严格的数学理论基础，易于进行程序的正确性证明和验证；第 三，逻辑程序开发者不需要考虑程序“如何计算 ，而只需要说明要“做什么 ， 从而有利于其将精力集中到问题的求解上，从计算模型的层面探索问题的求解。 这些特点使逻辑程序设计语言，如p r o l o g 除了在问题求解、启发式搜索、专家 系统等传统人工智能领域得到广泛的应用外n 均1 ，近年来其应用领域不断拓展。 例如，文献 2 3 和 4 给出了i n t e m e t 利用逻辑程序提供标准网络服务的方法， 文献 5 和 6 则描述了它在分布式多智能a g e n t 系统中的应用。作为一种基于规 则的说明性程序设计方法，逻辑程序具有过程性语言程序无法比拟的优点，它可 以用简单的规则来赋予实体推理能力并且程序设计简单。然而，p r o l o g 语言在使 用中也暴露了该语言存在的不足，如：缺乏类型和h o m 子句的语句形式限制了 语言的可表达性能力，控制机制中的非逻辑成份易于导致语义问题，开发的编译 或解释程序运行效率低，不适合大规模软件开发等。由此，g 6 d e l 语言应运而生。 可以预期，随着信息产业朝着智能化方向发展，如语义互连网、智能数据挖掘和 多智能a g e n t 技术的发展等，逻辑程序将获得更大的应用空间。显然，设计并实 现一个功能强大的逻辑程序设计语言具有重要的科学意义和实用价值。 1 1g 6 d ei 语言的主要创新 由于p r o l o g 所取得的巨大成功，一直以来p r o l o g 都是逻辑程序设计的代称。 但是，p r o l o g 基于一阶逻辑的h o r n 子集，作为一种无类型逻辑程序设计语言， 它缺乏足够的可表达性。而且，由于p r o l o g 在具体实现时，出于效率考虑，引 入了非逻辑的语言成分，如c u t 等，经常使用会使p r o l o g 程序缺乏清晰、明确的 说明性语义，导致理解、分析、转换、优化、验证、调试p r o l o g 程序都非常困 难。理想的逻辑程序设计语言应该将其理论基础从h o r n 子集扩展到一阶逻辑， 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 。g 6 d e l 试图解决p r o l o g 中存 在的诸多语义问题，增强p r o l o g 的可表达性，缩小理想逻辑程序设计语言与现 实逻辑程序设计语言的差别。 g 6 d e l 语言阳1 是继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 语言的众多变型如i c p r o l o g 、n u p r o l o g 等以及m l 语言、m o d u l a - 2 语言引入 新的语言成分，从而使其具备更强的程序设计表达能力。它建立在多态多类的一 阶逻辑基础之上，摒弃了p r o l o g 语言中的非逻辑成分，有效地解决了p r o l o g 语 言中存在的语义问题与表达性较弱的问题。g 6 d e l 语言对逻辑程序的主要创新可 以概括为：引入了参数型多态多类类型系统，增加了延迟计算等新的语言成分， 支持模块化程序设计和元程序设计；具有灵活的计算规则和剪枝操作，并以系统 模块形式提供丰富的抽象数据类型以支持通用程序设计，对其适当扩展可支持面 向对象程序设计n 们。 g 6 d e l 语言的类型系统是一个强类型系统。类型的引入便于知识表示，因为 知识的预期解释在大多数逻辑程序设计应用中是被类型化的，类型信息有利于发 现程序中的错误，提高程序的开发效率，也使得g 6 d e l 语言具有很强的可表达性 能力和实用性；g 6 d e l 语言程序设计采用模块化结构，提供了组织大规模程序的 方法，有利于信息隐藏。这些机制结合多态多类类型系统，使g 6 d e l 语言能够支 持某些现代软件工程方法n 町。g 6 d e l 语言拥有灵活的计算规则，可以通过声明延 迟计算条件，达到控制选取消解子目标次序的目的，再结合c o m m i t 剪枝，可以 极大地提高推理空间的搜索效率；采用抽象数据类型来处理元程序设计，为元程 序设计提供了一个良好的机制。 更为重要的是，g 6 d e l 语言在引入这些新的逻辑程序设计语言成分的同时， 还使该语言具有比p r o l o g 更优的程序说明性程序语义，而良好的概念化、结构 性说明性程序语义对逻辑程序至为重要。首先，它减轻了程序员的负担，使他们 第一章导论 在程序设计时只需考虑把问题及其相关的知识、逻辑关系定义好，告诉计算机系 统“要计算什么”，而不必关心“如何计算，真正向说明性程序设计方向上又迈 进了一步；其次，当前大多数实用的逻辑程序设计语言都是从p r o l o g 语言演变 而来，运用了许多非说明性语言成分和非逻辑成分，如c u t 、r e t r a c t 等，而g 6 d c l 在这一方面有了较大的进步，大大地减少了对非逻辑性成分的依赖，缩小了在逻 辑程序设计中理论与现实之间的差距，有利于逻辑程序的理论分析；最后，程序 设计语言理论研究表明，具有良好的说明性语义的程序更容易实现并行。g 6 d e l 语言的这些创新为逻辑程序设计注入了新的内容。可以预见，一旦该语言的编译 系统取得突破并得到推广，它将会成为人工智能、数据挖掘、数据库等领域进行 智能软件开发的重要的工具。 1 2g 6 d e l 语言实现系统研究现状 逻辑程序用逻辑语言来描述问题，利用归结方法来求得问题的答案。可以把 逻辑程序非形式化地概括为：a l g o r i t h m = l o g i c + c o n t r o l n 羽。其中，逻辑部分由 程序员在程序中规定，而控制部分( 推理求解过程) 则由语言对应的推理机来实 现。因此，推理机是逻辑程序中不可或缺的一部分，也是语言解释系统中的核心 程序。在过去各种版本的p r o l o g 语言的解释和编译实现中，是否拥有一个高效 率的推理机是语言实现能否走向成功的关键。如同w a m 抽象机的提出促进了各种 p r o l o g 实现版本的出现，使p r o l o g 走向实用一样，g 6 d c l 语言作为新型逻辑程序 设计语言，尤其需要合适的编译运行支撑环境和集成开发环境的支持。本文作者 所在课题组致力于g 6 d e l 语言实现系统及其集成开发环境的研究和开发，其中， 一个高效率的g 6 d c l 推理机是整个系统实现的关键之一。 g 6 d e l 语言引入了众多p r o l o g 中所没有的新机制，具有强大的功能，但同时 也造成其编译实现的困难，尤其是g 6 d e l 推理机的实现难度大大提高。目前， g 6 d c l 语言编译系统的开发尚停留在实验室研究阶段，只有b r i s t o l 大学的研究小 组在单机上开发了旨在验证g 6 d e l 语言功能的实验程序叫r i s t o lg 6 d c l u 引。在 用s i c s t u sp r o l o g 实现的b r i s t o lg 6 d c l 系统中，g 6 d c 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 的解释系统解释执行。因此，实际上该系 统并不是一个真正的编译系统，许多新的语言成分也并没有实现，故仅是一个快 速原型系统，没有实用的价值。作为一个快速原形系统，其执行效率较低且只能 g 6 d e l 语言编译系统中推理机的设计与实现 在l i n u x 环境下运行，这在一定程度上影响了g 6 d e l 语言的研究和推广。然而， 如何实现g 6 d e l 语言，一直以来是一个没有解决的问题。问题的困难之处在于， 与传统的面向过程的程序设计语言不同，逻辑程序设计的特点和运行机制决定了 推理机必须作为目标程序的一部分，而多态多类类型系统的引入和逻辑程序中不 确定性的增加导致现有的编译方法在生成目标代码时遇到困难；新的语言成分和 计算规则的引入也需要发展新的实现技术。于是，为了获得一个具有较高执行效 率的g 6 d e l 编译系统，实现过程中必须另辟蹊径，探索新的技术路线。 1 3 本文的主要工作及篇章结构 本文对g 6 d e l 程序设计模型进行了讨论，分析了类型系统、延迟计算和剪枝 操作等引入后，如何设计一个语义清晰并易于获得较高推理求解速度的g 6 d e l 程序的编译方法和技术路线。围绕推理机主要任务本文还重点介绍了中间代码结 构，阐述了g 6 d e l 推理机设计的主要思想和技术路线，并讨论了基于中问代码的 推理机的软件实现技术。 本文共分为五章。第一章对逻辑程序的历史地位和g 6 d e l 语言的主要创新作 了简要介绍，阐述了目前该语言推理机的研究现状；第二章介绍了g 6 d e l 语言程 序设计模型，重点分析了g 6 d e l 所引入的新机制为逻辑程序设计带来的新变化； 第三章讨论了g 6 d e l 编译的设计思想，阐述了系统的总体结构；第四章是本文的 重点，给出了推理机的实现方法和技术；第五章对本文进行了总结和讨论，提出 了下一步工作的设想。 第二章g s d e l 语言程序设计模型 第二章g i ；d e l 语言程序设计模型 在逻辑程序设计中，一个程序是一个逻辑公式的集合，g 6 d e l 语言也不例 外。程序设计的过程就是根据各种已知条件和问题求解方法中内在要素的相互 关系( 层次关系和逻辑关系) ，编辑撰写逻辑公式，而实际计算则交由事先设计 的推理机系统来完成。它以这个逻辑公式集合为前提，通过逻辑演绎推理，获 得计算的结果。因此，推理机成为逻辑程序设计语言编译程序或解释程序不可 或缺的一个组成部分。程序的语义有说明性语义和过程性语义之分。说明性语 义蕴涵在逻辑公式集合中，其过程性语义体现在推理机的执行过程之中。与 p r o l o g 相比，g 6 d e l 语言以多态多类一阶逻辑作为其理论基础，具有更强的语言 可表达性能力；通过引入延迟计算和剪枝机制使程序具有更为灵活的计算规则 和更清晰的说明性语义；模块化系统的引入则为g o d e l 语言提供了组织大规模 程序的方法。 2 1 逻辑程序基本理论 逻辑程序设计语言中最基本的语言实体单元是项。项可以是常量、变量和 复合项，复合项具有形式：( ，9 o 9 乙) ，其中是函数符，而参数是项。 项的形式是多种多样的，例如函数a d d ( k , 1 ) 就是一个项，它返回k + l 的值，同 时作为一个复合项，该项中又包含两个项即变量项k 和常量项l 。 在项的基础上可完成谓词的构造，在形式上它与复合项类似，但它不表示 复合项结构，而是一个逻辑断言。两者之间通过保留字或说明区分。一个程序 子句可以是事实( 单个谓词) ，也可以是一条规则。规则具有如下形式： 尺卜弓a 鼻 a e ，其中月和只是谓词；该规则的含义是：所有的层为 真蕴涵曰为真。一个逻辑程序由一系列的子句构成。关于逻辑程序的具体例子 我们将在2 2 6 目集中阐述，读者可参看。 程序的执行从一组子句( 公理) 出发，运用s l d 反驳一消解法，由推理机 推导出用户要求证明的目标子句( 新的定理) 的真假，或在推导的过程中，通 过目标所含变量、数据的参数传递，获得用户想要的某些满足程序逻辑语义模 g & t e l 语言编译系统中推理机的设计与实现 型的变量数据值。在s l d 反驳一消解过程中，完成推理最核心的基本运算是变 量置换与合一操作，通过这些操作，当用户目标被证明为真时，目标中的变量 也被约束到某些特定的值上，使用户可获得所求变量的值，以此达到用户的编 程目的，或在归结失败时，输出用户求证目标的逻辑否定值。目前所有的逻辑 程序，虽各不相同，但基本上以上述计算模型为基础，g 6 d e l 语言程序也不例 外。 s l d 反驳一消解法是一般消解法的特殊形式，即对给定子句的带选择函数 的线性消解法，它是一种适合于逻辑程序设计的消解法。一般消解法则是综合 变量置换、肯定前件的假言推理和各种三段论法综合形成的一般推理法则，而 s l d 反驳一消解法本质上是一种反证法，其消解过程如下文定义n 钔。 定义2 1 置换p 是形如 x l ，乙x ) 的有限集，其中是互不相同的变 量，是不等于而的项，符号t 表示变量t 被约束nt , ，例如3 z 表示z 此 时被约束到3 即其值为3 。 定义2 2 令p = 五，乙吒) 为置换，e 为表达式( 项、原子公式及 其析取式称为表达式) ，e 经置换p 所得到的新的表达式为e o ，它由把在居中 出现的气同时、分别替换为f f 而得到。 定义2 3 令s = 互”，e ) 为简单表达式( 不含析取式的表达式) 的非空 有限集，我们把 巨p ，e o o ) 记为e o 。若e p 是单元素集合，即蜀0 = = e o ， 则称d 为s 的一个通代，也称s 为可合一的。若对s 的任一通代仃，存在一个 置换y ，使仃= o r ，则p 称为s 的一个最广通代，记为m g u 。 定义2 4 计算规则月是从目标子旬到其中一个原子的映射，即从目标子 句中挑选子目标的规则。 定义2 5 令g 为目标子句：卜4a a 以a a4 ( 七1 ) ，c 为子句： 彳卜墨a a 吃( q 0 ) ，r 为一个计算规则，0 为一个置换。若r ( g ) = 厶， p 是 4 ，a ) 的一个m g u ，则下面的新目标子句g 。： 卜( 4a a4 ，一la 尽a a 色a 以+ la a4 ) p 第二章g s d e l 语言程序设计模型 称为g 和c 的一个消解式，也称g 由g 和c 经规则曰用1 9 l 导出。 定义2 5 逻辑程序p 和g ( 目标的非) 构成的理论p u g ，的一个经月的 s l d 的推导由下面三个序列组成： 目标子句序列：o o = g ，g l ，g 2 ， 尸中子旬系列：g ，c 2 ， 置换序列： q ，0 2 ， 其中，g ：f + l 是由g j 和c ： + l 经月用q + l 导出( 扛o ，l ，2 ，) 。若对某整数刀，经s l d 推导后，有q = 口( 空子句，代表一对矛盾) ，则称该推导为成功的推导，或称 该推导为尸u g 的一个反驳，此时有g 的非为真，即目标为真。 所谓s l d 反驳一消解法就是寻找一个反驳过程。关于s l d 反驳一消解法的 正确性和完备性证明请参考文献n 们。关于上文定义的s l d 反驳一消解过程中涉及 的诸多概念的具体例子，请参看2 2 6 目。 显然，s l d 反驳一消解过程根据计算规则曰的不同而不同。p r o l o g 采用的是 计算规则是最左文字优先( 即每次选取目标中的最右子目标) ，g o d e l 语言的设 计者们为了让程序的实现者具有更大的自由度，没有规定程序的s l d 反驳一消 解过程中的计算规则，我们将在下文规定本文所的g 6 d e l 语言实现系统中所采 用的s l d 反驳一消解规则。 2 2g s d e i 语言程序设计 g 6 d e l 程序语言成分较多，本节我们主要从程序结构和子句结构两方面进行 介绍，更详细的介绍请参考文献嘲。 2 2 1 程序结构 与p r o l o g 相比，在程序结构方面，g 6 d e l 语言引入了模块系统，提供了组织 大规模程序的方法，能避免程序的不同部分之间的名字冲突，并且提供隐藏数 据和执行细节的方法。模块化程序设计思想可上溯至2 0 世纪6 0 年代初期，在 命令式语言中已有充分的体现。g 6 d e l 模块系统同样基于这一思想，程序可以 g 6 d e l 语言编译系统中推理机的设计与实现 由模块集 够) ：o ( 刀0 ) 组成，其中至少包含一个主模块m o 。子集 m ：。中 的模块由坛直接或间接导入。每个模块内部包含声明部分和子句定义部分， 声明部分由以下可选语言成分组成： m o d u l e i m p o r t b a s e c o n s t r u c t o r c o n s w a n t 嗍1 0 n p r e d i c a t e d e l a y 它们是对子句定义部分的补充，主要是说明子句中的谓词名称、参数个数及其 类型以及是否进行延迟计算等。 2 2 2 程序子句结构 在程序的子句层面，g 6 d e l 语言对p r o l o g 语言进行了诸多改进。p r o l o g 语 言基于一阶逻辑的h o r n 子集，其程序子句可以用下式表示： 公式2 1 么卜蜀a aea b 。( 1 f 刀) ， 其中，a 和e 是原子公式且b 。可以为空，a 和e 中所包含的项没有类型。g 6 d e l 语言的程序子句经过编译处理后仍可用公式2 1 来表述，所不同的是此时a 和 置是多态多类谓词，并且g 6 d e l 语言是强类型语言，a 和e 中的所有成分都必 须先声明( 说明) 后使用。g o d e l 语言对置引入了延迟计算机制：尽只有在满 足延迟计算条件的时候，才能被选取为反驳一消解子目标。这样做有利于程序员 控制子目标的消解顺序。此外，g o d e l 语言完全屏弃了p r o l o g 子句中具有较多 争议的c u t 操作，代之以c o m m i t 剪枝，因此，e 还可能是具有 c ) 形式的剪 枝声明公式( 如果源程序中存在一解剪枝或条形剪枝必须进行转换) 。其中，多 态多类谓词c 是剪枝条件，即当公式c 为真时，剪除程序中所有其他可与公式 a 匹配且含有剪枝标签l 的程序子旬。下面我们对g 6 d e l 程序子句中的这几项 重要机制及其作用进行分析，这些机制在推理机中的实现将是本文的重点。 第二章c , & l e l 语言程序设计模型 2 2 3 类型系统 在程序的子旬层面，g 6 d e l 语言对p r o l o g 语言进行了诸多改进。p r o l o g 语 言近年来在研究中不断得到改进，为增强逻辑程序的可表达性，研究者们提出 了多态多类逻辑n 司陆1 ，并被g 6 d e l 语言在设计中所采纳。p r o l o g 语言的逻辑基础 是无类型的h o r n 子句逻辑，而g 6 d e l 语言则建立在多态多类的一阶逻辑基础之 上，具有更强的可表达性能力，更容易进行程序开发。这是因为：首先，类型 有助于知识的表示，知识的预期解释在大多数逻辑程序设计中一般是被类型化 的，引入类型有利于直接获取应用中的相关知识；其次，有了类型信息，能够 进行程序的静态类型检查从而发现程序中存在的错误，提高程序开发的效率； 第三，项带上类型信息后，在进行匹配搜索时，只需查找相应类型的搜索域， 从而改善了p r o l o g 那种因采用字符匹配的盲目搜索算法( 在整个搜索空间上进 行搜索) 所造成的低效率。 作为具有多种类型的语言，一个g 6 d e l 语言程序的类型集合由语言声明中 的基类( b a s e ) 声明和构造子( c o n s t i c t o r ) 声明决定。其中，构造子 是一个类型生成函数，用于构造新的类型，它以类型变量作为其参数，类型变 量的值域为基本类型和构造子生成的所有其它类型。一个程序的类型集合，可 定义如下： 定义2 6g 6 d e l 语言程序的类型集合由以下规则递归定义构成： ( 1 ) 参量是类型； ( 2 ) 用户定义的基本类型是类型； ( 3 ) 如果c 是一个具有n 个参量t 。，e ee pt 。的构造子，那么c ( t 。，e e e l lt 。) 是类型。 由上述定义，可以看出，如果程序中只定义了基类，即只有用户自定义类型， 而没有定义构造子函数，那么，程序的类型集合为所有用户自定义类型；否则， 由基类和构造子出发，得到的所有基本项( g r o u n dt e r m ) ，构成了程序的类型集 合。很明显，该集合是一个可数无穷集。 g 6 d e l 语言是强类型语言，它要求程序中的所有常量、谓词、函数等都要 事先声明才能使用，对谓词中的项和函数中的参数必须在声明时给出其类型， 而变量的类型则可以通过已有的声明推导得到。换言之，g o d e l 语言程序中的 g o d e l 语言编译系统中推理机的设计与实现 项必须携带类型信息，定义2 6 给出了程序所有可用的类型，据此g 6 d e l 语言 程序中的项可定义如下： 定义2 7g 6 d e l 语言程序中项递归定义如下： ( 1 ) 一个类型t 的变量是类型t 的项； ( 2 ) 一个类型t 的常量是类型t 的项； ( 3 ) 如果，是一个n 元函数，t 。( i = 1 ，n ) 是类型r ；的变量，tt 为， 的参数类型，并有类型运算：t 。t 。专t 则，( tl ，”，t 。) 是 类型c 的项；其中类型运算主要用于声明函数。 上面的两个定义给出了g 6 d c l 语言多类系统的原理，下面我们通过一个例子来 获得更为直观的认识。程序模块m l 定义如图1 所示，该程序给出了追加谓词 a p p e n d 的g 6 d e l 语言版本。 在模块m 1 中，基类声明( b a s e ) 给出了两个用户自定义类型d a y 和p e r s o n ： 构造子声明( c o n s t i m c t o r ) 给出了构造子函数l i s t ，构造子函数后的l 表 图2 1 程序模块m 1 示该构造子是一元构造子即只有一个类型变量作为参数，程序中的7a 即 为类型变量，所以由定义1 可以得到模块m 1 的类型集合i 为 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 语言程序设计模型 ( 兀烈c t i o n ) 谓词声明( p r e d i c a t e ) 为程序中的项附上类型信息。函数声 明中声明了函数c o n s 的参数类型和值类型，c o n s 具有两个参数其类型为7a 和 l i s t ( a ) ，运算结果的类型为l i s t ( a ) ，其中a l ；谓词声明中规定了 a p p e n d 谓词中的三个项的类型为l i s t ( a ) ，所以a p p e n d ( n i l ，x ，x ) 语句中的 变量x 的类型就可以推导出来了。很明显，其类型是l i s t ( a ) 。常量声明 ( c o n s t a n t ) 给出了程序中可以使用的常量及其类型，如我们可以使用常量 m o n d a y ，它的类型为d a y 。 在多类的基础上，g 6 d e l 语言还可以支持多态类型，极大地提高了程序设 计的灵活性。类似面向对象程序设计语言中的多态函数，g 6 d e l 语言中的谓词 或函数可以处理多种不同类型的输入，可以方便的把已定义的多态谓词、函数 和数据结构重用于任何需要的类型实例。g 6 d e l 语言的多态称为参数型多态， 通过引入类型变量，使谓词或函数中的参数类型为一个类型集合，从而使得该 谓词或函数可以处理不同的类型。例如，在模块m 1 中，通过构造子l i s t 和类型 变量a 使程序不仅能够处理d a y 型链表的追加操作( 此时a 类型为d a y ) ， 也能处理p e r s o n 型链表的追加操作( 此时7a 类型为p e r s o n ) ，这在p r o l o g 语言 中这需要多个程序才能实现。多态多类系统的引入使逻辑程序设计语言 g 6 d e l 语言，具有了过程性语言的一些显著特点，极大地提高了逻辑程序设计 语言的设计能力和灵活性。 2 2 4 延迟计算 在程序子旬层面，g 6 d e l 语言对p r o l o g 语言进行了诸多改进。g 6 d e l 语言具 有灵活的计算规则，不再是p r o l o g 中一成不变的最左文字优先。对如何选取子 目标，g 6 d e l 语言只是给出了一些原则，这些原则包括： ( 1 ) 可以选择任何系统实现者觉得方便的顺序来扩展子目标； ( 2 ) 当多个子目标的延迟计算条件满足时，选择唤醒哪一个被挂起的子目标进 行扩展也由系统实现者自己定义； ( 3 ) 如果所有的子目标都被延迟，则当前目标无法计算。 上述原则中一个重要的概念是延迟，程序员通过显式的延迟( d e l a y ) 声明能 部分地控制计算规则。g 6 d e l 语言引入了延迟计算，通过在程序中进行延迟声 g 6 d e l 语言编译系统中推理机的设计与实现 明( d e l a y ) ，明确地给出谓词( 子目标) 被扩展执行的条件。d e l a y 控制说明 的语法e b n f ( 扩展的b n f ) 为： d e i a ya t o mu n t i lc o n d c o n d _ c o n d llc o n d l & c o n d l ) ic o n d l vc o n d l ) c o n dl - - n o n v a r ( v a r i a b l e ) ig r o u n d ( v a r i a b l e ) lt r u ei ( c o n d ) 其中，a t o m 为原子谓词或逻辑表达式，原子谓词必须由谓词声明( p r e d i c a t e ) 定义。c o n d 是c o n d i t i o n 的缩写，表示a t o m 被调用执行的条件，条件可以是多 个子条件的析取或合取组合。子条件由c o n d l 定义，分为三类：其一为a t o m 中某变量( 由v a r i a b l e 给出) 被实例化( n o n w 浓) ，即该变量已经被约束到具 体的值，不再是一个变量；其二为a t o m 中某项( 由v a r i a b l e 给出) 是基项 ( g r o u n d ) ，其中不再含有变量；其三为无条件为真，即当a t o m 以某种形式 出现时可以立即被执行。延迟计算作为g s d e l 语言程序执行过程中重要的控制 机制，具有多方面的作用。 首先，延迟( d e l a y ) 语句类似于过程性语言中的w h e n 语句，是w h e n 语 句在逻辑程序中的变形，它的引入有利于程序的正常终止。例如在模块m 1 中， 如果我们有如下目标： a p p e n d ( x ，y