（计算机系统结构专业论文）godel语言编译系统中实现计算可视化.pdf

摘要 摘要 g o 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 语言成为具有较强功能而且比较实用的一种说明 性逻辑程序设计语言。 逻辑程序设计语言与过程性程序设计语言如p a s c a l 、c 等相比，最大的区别 是逻辑程序设计语言提供了一种说明性的编程方法。这使得逻辑程序开发人员在 程序设计中不需要考虑“如何解决问题 ，而只需要说明程序“要做什么，从而 可以使开发人员将精力放在问题的描述上面，从计算模型的层次上探索问题的求 解。它简单统一的语法和语句，类型的合一匹配及回溯操作使程序设计与传统的 面向过程的程序设计语言相比更加简洁、明确。但是，这些特点使得对于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 语 言推理过程跟踪显示器首先要调用推理过程中产生的调试信息( s l d t r e e x m l ) ， 通过装载调试信息在推理过程跟踪显示器内部将调试信息转换为c s h o w 类对 象，然后通过操作控制命令控制推理过程的显示。这样，程序编译后执行时，在 推理过程显示区我们可以动态地实时观察推理机推理的整个过程。基于这样的一 种应用需求，结合g 6 d e l 语言编译程序的实现方法，我们给出了g 6 d e l 语言计算 可视化的总体结构，并对基于g 6 d e l 语言计算可视化的编译系统的设计和计算可 视化显示等两个部分的实现方法和技术进行了详细的介绍，着重讨论了编译系统 中调试信息生成时所采用的方法和技术。g 6 d e l 语言推理过程跟踪显示器是一个 独立的应用程序，该程序可以直接从操作系统上运行，也可以从g p d e ( g 6 d e l g o 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 ) 上运行。此时，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 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 s d 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 ep 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 gi nt h ef a m i l yo fl o g i cp r o g r a m m i n gl a n g u a g e s c o m p a r e d w i t ht h ea l g o r i t h m b a s e dp r o g r a m m i n gl a n g u a g es u c ha sp a s c a l 。ca n ds o o n ，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 g m e t h o d s ot h el o g i cl a n g u a g ep r o g r a m m e r sf o c u so nd e s c r i p t i o nt h ep r o b l e m a n dq u e s tf o rt h es o l u t i o na tt h el e v e lo fc o m p u t i n gm o d e l i t ss i m p l e ， u n i f o r ms y n t a xa n ds e n t e n c e s ，p o w e r f u li n b u ii tf e a t u r e so fu n i f i c a t i o n a n db a c k t r a c k i n go f t e n a l l o wa l g o r i t h m st ob ee n c o d e dm o r ee l e g a n t l yt h a n i no t h e r ， m o r ec o n v e n t i o n a ll a n g u a g e s u n f o r t u n a t e l y ，t h e s ee x c e l l e n t f e a t u r e sb r i n ga b o u td i f f i c u l t i e st on o v i c e sa tg s d e l o u rm a i np u r p o s ei st od e s i g nav i s u a ls y s t e m ( g s d e lr e f e r e n c et r a c e t 0 0 1 ) w h i c hm o n i t o r sa n dt r a c e st h ei n f e r e n c es t e p so fg s d e ll a n g u a g ea n d i m p l e m e n tt h i ss y s t e mb yc + + t h e s ed i s s e r t a t i o n sf o c u so nt h ev i s u a l c o m p u t i n go fg s d e ll a n g u a g e ，t h ed e s c r i p t i o no ft r a c i n gg s d e ll a n g u a g e i n f e r e n c ep r o c e s sa n di m p l e m e n t a t i o no fs y s t e m t h i sc h a p t e r ，w eb e g i n t os t u d yt h es t a t u sq u ol a n g u a g eg s d e lg i v eab r i e fa c c o u n t g s d e lr e f e r e n c et r a c et o o ln o to n l yp l a y sa ni m p o r t a n tr o l ei nt h e p r o c e s so ft r a c k i n gd i s p l a y sd e b u g g i n gp r o c e d u r e ，a n di tc a na l s ob eu s e d a saa s s i s t a n tt o o l i nt h eg s d e lp r o g r a m m i n g g s d e lr e f e r e n c et r a c et o o l f i r s tc a l l st h er e f e r e n c ep r o c e s so fd e b u g g i n gi n f o r m a t i o n ( s l d t r e e x m l ) ， t h r o u g hl o a d i n gd e b u gi n f o r m a t i o ni nt h er e a s o n i n gp r o c e s so ft r a c k i n g m o n i t o r si n t e r n a ld e b u g g i n gi n f o r m a t i o nw i i ib ec o n v e r t e dt oc s h o wc l a s s ， a n dt h e nt h r o u g ht h ep r o c e s sc o n t r o lb u t t o n sc o n t r o lt h ed i s p l a y i nt h i s w a y ，a f t e rt h ei m p l e m e n t a t i o no fp r o c e d u r e sf o rc o m p i l i n g ，i nt h ep r o c e s s o fr e a s o n i n gw ec a nd i s p l a yad y n a m i cr e a l t i m eo b s e r v a t i o no ft h ew h o l e r e a s o n i n gp r o c e s so fr e a s o n i n g b a s e do ns u c ha na p p l i c a t i o nn e e d s ，w i t h g 6 d e l 语言编译系统中实现计算可视化 t h em e t h o do fg a d e ll a n g u a g ec o m p ile rs y s t e mw eg iv eg a d e lc o m p u ti n g v i s u a l i z a t i o no ft h eo v e r a l ls t r u c t u r e ，a n db a s e do nt h ev i s u a l i z a t i o n o fg s d e ll a n g u a g ec o m p i l e rs y s t e md e s i g na n dv i s u a ld i s p l a yo fp a r to f t h er e a li z a t i o no ft h et w om e t h o d sa n dt e c h n i q u e si nd e t a il ，f o c u s e do n c o m p il e rs y s t e md e b u g g i n gi n f o r m a t i o ng e n e r a t e db yt h eu s eo fm e t h o d sa n d t e c h n i q u e s g s d e lr e f e r e n c et r a c et o o lt r a c k i n gd i s p l a yi sa ni n d e p e n d e n t a p p li c a ti o np r o c e d u r e s ，t h ep r o c e d u r e s c a nb er u nd i r e c t l yf r o mt h e o p e r a ti n gs y s t e m ，a n dc a na l s or u no ng p d e ，w h e ng s d e lv e r b a lr e a s o n i n g p r o c e s st r a c k i n gm o n it o r sa sp a r to ft h ed e v e l o p m e n te n v i r o n m e n t 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 i1i a rt op e o p l e y e a r sb e f o r e b u tt ob en e wl o g i cp r o g r a m m i n gl a n g u a g e ，g s d e ln e e d ss o m e t i m ea n dp r a c t i c et om a k e i 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 h e s p e c i a l l yr e q u i r e st h es 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 d d 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 o u rd e s i g ng s d e li n f e r e n c e t r a c et o o lh a sd e b u gf u n c t i o n t h em o t i v a t i o nf o rd e v e l o p i n gt h i sn e wt o o l n o to n lyin c r e a s e st h ep r o d u c tiv it yo fe x p e r ie n c e dp r o g r a m m e r sb u ta ls o t om a k et h et e a c h i n go fg s d e lm o r ee f f e c t i v e g s d e li n f e r e n c et r a c et o o l w i l1 h e l pg s d e ll a n g u a g e ss t u d ya n db ep o p u l a r w eb e li e v et h a tg 5 d e l l a n g u a g ew i l l b ea b l et or e c e i v em o r ea t t e n t i o na n do b t a i na m o r e w i d e s p r e a du s ew i t ht h em a t u r eo fg s 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 ：o o d e ll a n g u a g e ；c o m p i l e rs y s t e m ；v i s u a lc o m p u t i n g ； 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：胁 跏磅年多月t - 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( v ) ( 请在以上相应括号内打“”) 作者签名：名勺余 日期：础年多月午日 导师签睦讯日期谢年多月门 第一章绪论 第一章绪论 g 6 d e l 语言是继p r o l o g 语言之后出现的新型说明性通用逻辑程序设计语言， 目前还不为人们所广泛熟知。g 6 d e l 语言程序执行过程的计算可视化实现对该语 言的推广、深入研究具有重要的意义。本文重点讨论g 6 d e l 语言程序计算可视化 问题，详细介绍了g 6 d e l 语言程序计算可视化的设计与实现。本章，我们首先对 g 6 d e l 语言研究现状作简单的介绍。 1 1g i d e l 语言简介 g 6 d e l 语言是一种新型通用逻辑程序设计语言【l j ，它充分吸收了逻辑程序设 计研究领域的最新成果，对p r o l o g 语言存在的缺陷作了诸多改进。首先，它借 鉴、继承了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 语言中存在的不足并试图解决其中颇有争议的语义问题。 其次，在表达能力上，g 6 d e l 语言与p r o l o g 语言相比也有了很大的提高，其理论 基础不再限于一阶逻辑的h o r n 子集，而是引入多态多类类型系统【2 j 【3 】，将语言建 立在多态多类的一阶逻辑基础之上，使语言具备了更强的描述能力，更易于进行 程序开发，且改善了p r o l o g 语言那种基于字符匹配的盲目搜索算法所造成的低 效率。第三，在控制策略上，g 6 d e l 语言引入了延迟和剪枝机制。延迟机制的引 入改变了p r o l o g 语言中最左文字优先的计算规则，使语言具有更为灵活的计算 规则，提高了语言的执行效率。剪枝操作改进了p r o l o g 语言中的c u t 操作，它建 立在并发语言的c o m m i t 机制之上，具有更好的说明性语义1 4 1 ，可用来对搜索树 进行剪枝从而影响搜索的完全性，进而提高问题求解效率。剪枝操作有效解决了 p r o l o g 语言中c u t 带来的一些语义问题，如：程序的基本逻辑部分界定的不确定 性；在存在否定的情况下，c u t 的使用是不可靠的，即从程序逻辑部分的完整性 来考虑，可能存在不确定的计算结果【l 】【副。此外，g 6 d e l 语言的设计融入了一些 程序设计方法和技术。例如，通过对抽象数据类型程序设计的支持可实现面向对 象程序设计思想【6 】，进一步发展并支持模块化程序设计，能够方便地进行大规模 g o d e l 语言编译系统中实现计算可视化 程序开发，发展p r o l o g 语言中元程序的思想，以便在智能程序设计中更有效地 支持元级程序设计。 1 2g i i d e l 语言的主要机制 g 6 d e l 语言主要包括类型系统、模块系统、控制机制等。为了让人们对g f d e l 语言的语法和语义有所认识，下面将结合g 6 d e l 源程序实例对各主要机制的特性 分别进行介绍。 1 2 1g i i d e l 语言的类型系统 长期以来，逻辑程序设计研究者一直在不断地改进逻辑程序设计语言，在增 强逻辑程序的可表达性方面提出了引入多态多类逻辑的构想，并体现在g 6 d e l 语言的设计之中。 p r o l o g 语言的逻辑基础是一阶逻辑的h o r n 子集，语言设计中没有考虑引入 数据表示的类型系统，因而其表达能力十分有限。而g 6 d e l 语言的逻辑基础则是 建立在多态多类( p o l y m o r p h i s mm a n y s o r t e d ) 的一阶逻辑基础之上，使语言具备了 更强的描述能力，更易于程序开发和编译实现中的错误检测。引入类型系统主要 有以下优点。首先，有了类型系统便于知识的表示。由于知识的预期解释在大多 数逻辑程序设计应用中一般是被模型化的，引入类型有助于直接获取应用中的相 关知识；其次，有了类型信息，能够进行程序的类型检查从而减少程序错误，提 高程序员的程序开发效率；第三，项带上类型信息后，在进行匹配搜索时，只需 在对应类型的搜索域中进行查找，可以改善p r o l o g 语言基于字符匹配的机械的 搜索算法所造成的低效率。 g 6 d e l 语言程序的类型集合是由语言声明中基类( b a s e ) 声明和构造子 ( c o n s t r u c t o r ) 声明来决定的。若仅定义基类而没有构造子，则所有基类 的集合就是语言的类型集合：若至少说明了一个构造子，则由基类b a s e 和构造 子c o n s t r u c t o r 出发，得到的基本项( g r o u n dt e r m ) 构成语言的类型集合，该 类型集合是可数无限集。 例1 1 模块m 定义如下： m o d u l em 本地模块说明 第一章绪论 i m p o r t i n t e g e r s 导入模块说明 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 id a y ，s a t u r d a y ， s u n d a y ：d a y f r e d ，b i1 1 ，m a r y ：p e r s o n f u n c t l 0 nc o n s ：a 木l i s t ( a ) 一l i s t ( a ) 函数说明 p r e d i c a t em e m b e r ：a * l i s t ( a ) 谓词说明 d e l a y m e m b e r ( x ，z ) u n t i ln o n v a r ( x ) vn o n v a r ( z ) 延迟说明 m e m b e r ( u ，c o n s ( u ，x ) 一 t r u e - 1 语句 m e m b e r ( x ，c o n s ( u ，z ) ) 一m e m b e r ( x ，z ) * - m e m b e r ( m o n d a y ， m o n d a y ，t h u r s d a y ，s u n d a y ) 模块m 中声明基类类型d a y 和p e r s o n ，类型构造子l i s t 之后的整数1 表示 一元构造子，程序中出现的a 代表类型变元，该模块的类型集合t m 为( 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 ) ) 。) ，即： d a y e t m ，p e r s o n e t m ，x t m l i s t ( x ) e t m 当然，程序中实际所需要的类型并不是可数无限的，而是其中一个有限子集，但 这并不影响程序的语义。 此外，g 6 d e l 语言还支持多态类型，引入类型变元带来了参数型多态，可进 一步提高程序设计的灵活性。一个含有类型变元的多态符号( 常量、函数或谓词) 可以看成类型集合中所有不同类型的多个符号的集合。例如，模块m 2 中的常量 声明n i i 可以代表类型为l i s t ( d a y ) 的常量n i l d a y ，类型为l i s t ( p e r s o n ) 的常量 n i l p e 噶o n ，类型为l i s t ( l i s t ( d a y ) ) 的常量n i l l i s t ( d a y ) ，等等。 多态类型的一个重要优点是谓词、函数和数据结构能重用于任何需要的类型 实例，同样的定义能用于表示或计算不同的类型，若语言不支持多态类型则需要 在程序中给出不同的定义分别进行处理。但是，多态类型语言的类型检查比传统 的单念类型语言更为困难，特别，当涉及到类型变量匹配中类型相同的情况时是 很难判断的，并且需要合一的支持操作。 g o d e l 语言编译系统中实现计算可视化 1 2 2g i j d e i 语言的模块系统 g 6 d e l 语言的模块系统不仅为语言提供了组织大规模复杂程序的方法，而且 通过引入类型系统实现了支持抽象数据类型程序设计，从而为支持面向对象程序 设计奠定了基础。 模块化提供了组织大规模复杂程序的方法，能避免程序的不同部分之间的名 字冲突，并且提供隐藏执行细节的方法。模块化程序设计思想可上溯至1 9 6 0 年 代初期，在命令式语言中已有充分的体现。g 6 d e l 模块系统同样基于这一思想， 程序可以由模块集 m i ) n i = o ( 佗o ) 组成，其中，至少包含一个主模块m o ，子集 m i ) “i ：1 中的模块由m o 直接或间接导入。每个模块可分为输出部分( e x p o r tp a r t ) 和本地部 分( 1 0 c a lp a n ) 。模块的输出部分为程序的说明部分包括语言说明、控制说明和模 块说明。语言说明中声明一些符号，这些符号可用于此模块的任何地方和其他导 入这个模块的模块中的任何地方；控制说明和模块说明中给出一些来自其他模块 的符号，这些符号同样可用于本模块的任何地方和其他导入本模块的任何地方。 模块的本地部分主要用于给出输出部分定义谓词的实现细节，同样包括语言说 明、控制说明和模块说明，其语言说明声明的符号只在本地模块可用；模块说明 给出来自其他模块的可以用以本地模块的符号：控制说明以及那些命题和谓词的 定义由本地模块中的语言说明来具体定义。 g 6 d e l 语言可选语言说明由以下部分组成： 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 t a n t f u n c t i o n p r e d i c a t e d e l a y p r o p o s i t i o n 下面通过具体的例子来说明g 6 d e l 语言模块化的思想。 第一章绪论 例1 2 定义模块m 1 和模块m 2 如下： e x p o r l 。m 1 i m p o r tl i s t s b a s e d a y , p e r s o n c o n s t a n t 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 p r e d l c a t e a p p e n d 2 ：l i s t ( a ) ，i cl is t ( a ) 半l i s t ( a ) 木l is t ( a ) l o c a lm 1 a p p e n d 2 ( x ，y ，z ，u ) 一a p p e n d ( x ，y ，、) 八a p p e n d ( w , z ，u ) m o d u l em 2 i m p o r tm 1 p r e d i c a t em e m b e r ：a ，i ca 木l i s t ( a ) m e m b e r ( x ，y ，z ) 一a p p e n d 3 ( 一， xi 一 ， yi 一 ，z ) 这里我们定义两个模块m 1 和m 2 。模块m 1 包含输出部分( e x p o r t ) 和 本地部分( l o c a l ) 。m 1 的输出部分说明它所声明或是导入的符号都可以被其 它导入这个模块的模块所引用。 例如模块m 1 声明的类型d a y ，p e r s o n ；常量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 和谓词a p p e n d 2 都可以被模块m 2 所使用。 在模块m 1 输出部分声明的导入模块l i s t s ，使l i s t s 模块的输出部分所声明的所 有符号对于模块m 1 是可用的。并且任何引入模块m i 的模块都可以应用模块 m 1 的输出部分声明的符号和模块l i s t s 输出部分声明的符号，而不需在i m p o r t 部分声明引入l i s t s 模块。模块m 1 的本地部分定义声明部分所声明的谓词 a p p e n d 2 ，此谓词用到的谓词a p p e n d 已经在模块l i s t s 中有定义，因而直接引用 它就可以。 通过模块m 1 和模块m 2 的对比，我们可以知道模块m 2 只是声明了本地部 分。因此它声明时关键字要用m o d u l e 而非l o c a l 。模块m 2 通过i m p o r t 声明引入了所有m i 声明的符号，其中包括谓词a p p e n d 2 和所有由模块l i s t s 输 出部分声明的符号。模块m 2 包含谓词m e m b e r 2 的定义。m e m b e r 2 表明当且仅 g 6 d e l 语言编译系统中实现计算可视化 当表z 中包含表x 和表y 的所有元素，并且x 中的所有元素都在y 前面时为真。 g 6 d e l 语言提供了一个丰富的系统模块集共包含2 0 个系统模块，这些模块 有用来处理数值( n u m b e r s ) 的、列表( 1 i s t s ) 的、字符争( s t r i n g s ) 的、集合( s e t s ) 的等， 并提供了u n i t ，f l o c k ，p r o g r a m ，t h e o r y 等支持元程序设计的模块。类型系统和模 块化相结合还带来了数据掩蔽与操作封装的优势。用户可以在模块中自定义类 型，将类型定义和与之相关的操作放在某个模块中，通过模块的导入和导出进行 数据掩蔽与操作封装以实现内容隐藏。 1 2 3g i j d e l 语言的控制机制 g 6 d e l 语言的控制机制可以从两个方面分别进行讨论：计算规则和剪枝操作。 1 2 3 1 计算规则 g 6 d e l 语言沿袭了p r o l o g 的计算规则，并有所发展，形成了自身特有的、灵 活的计算规则。与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 语言程序中显式地运用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 语言将沿用“最左文字”计算规则。而在p r o l o g 语言中，由 于计算规则总是应用于最左的子目标，子目标的书写顺序将直接影响搜索树的扩 展进而影响计算结果。如果规则中子公式顺序安排不当则易于陷入无穷运算或死 循环。也就是说，p r o l o g 语言的计算规则没有确保程序执行的安全性【_ 7 1 。g 6 d e l 语言为避免这一问题，引入d e l a y 说明以增强程序的有效性和可终止性。此外， 通过延迟可使子目标得到协同执行，从而使其具有比最左文字优先更高的效率。 引入d e l a y 延迟计算有利于提高逻辑程序的执行效率但不破坏程序的说明性和 可读性。 第一章绪论 d e l a y 控制说明的语法形式为： d e l a ya t o mu n t i lc o n d c o n d ：= c o n d lc o n d l c o n d l ic o n d l vc o n d l ) 1 c o n d l ：= 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 ) t r u ef ( c o n d ) 其中，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 表示变量为基本项。关键字t r u e 表示无条件，即当a t o m 以 某种形式出现时可以立即被执行。延迟语句( d e l a y ) 类似于过程性语言中的w h e n 语句，是w h e n 语句在逻辑程序中的变形，它的引入有利于程序的正常终止。 下面通过例子来说明d e l a y 说明是如何增强程序的有效性和可终止性的。 例1 3 把给定序列由小到大排序的g o d e l 源程序。 m o d u l es o r t i m p o r tl is t s 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 cl i s t ( a ) s o r t e d ：l i s t ( i n t e g e r ) s l o w 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 ) d e l a y p e r m u t a t i 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 r t e d ( ) u n t i lt r u e s o r t e d ( - ) u n t i lt r u e s o r t e d ( x ， yl u n t i ln o n v a r ( x ) 八n o n v a r ( y ) p e r m u t a t i o n ( 口， ) p e r m u t a t i o n ( x | y ， u iv ) * - - d e l e t e ( u ， x i y ，z ) 八p e r m u t a t i o n ( z ，v ) s o r t e d ( ) s o r t e d ( l ) s o r t e d ( x ，yz ) 一x = y 八s o r t e d ( ylz ) 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 ) - - s l o w s o r t ( a ，b ) 表示列表a 经排序产生列表b 定义谓词p e r m u t a t i o n ( a ，b ) 表示列表a 是列表b 的一个排列，其中，调用 x 表示x 的0 次或多次 f j 现。 g 6 d e l 语言编译系统中实现计算可视化 的谓词d e l e t e ( a ，b ，c ) 表示从列表b 删除元素a 得到列表c 。程序中谓词 p e r m u t a t i o n 的d e u 声明表示当谓词p e r m u t a t i o n 中的参数确定时才进行计 算。若谓词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 谓词的作用是判断一个列表是否有序。 程序中谓词s l o w s o r t 有两个项，y 。当x 和y 至少有一个已约束时，s l o w s o r t 才能计算。若y 为约束的，则s o r t e d 无须延迟。若s o r t e d 成功，则当x 为约束 的变量时，p e r m u t a t i o n 验证x 是否为y 的一个排列；若x 为非约束的变量时， 则x 为y 的所有可能的排列。若y 为非约束的而x 为约束的时候，则s o r t e d 将 被延迟，p e r m u t a t i o n 将y 实例化为x 的一个排列。整个排列过程不要求在s o r t e d 继续之前完成，只要求得到排列的前两个元素。若前两个元素已表明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 将回溯到另一排列。d e u 的另一个作用是保证计算的终止。若没 有给出延迟声明，那么查询p e r m u t a t i o n ( x “1 ，2 ，3 】) 将在得到答案x = 【1 ，2 ， 3 】之后陷入无穷循环。在定义了延迟声明，给出六种可能的排列结果之后， p e r m u t a t i o n 失败并终止。 1 2 3 2 剪枝操作 类似于p r o l o g 中的c u t 机制，g 6 d e l 语言也提供了对s l d 树进行不完全搜 索的方法，即剪枝操作。g 6 d e l 语言的剪枝( c o m m i t ) 机制是p r o l o g 中c u t 机制 的改进，它建立在并发语言的c o m m i t 机制之上，具有更好的语义说咧4 1 ，用来 对搜索树进行剪枝进而影响搜索的完全性，提高问题求解效率。它有效地解决了 p r o l o g 中因c u t 带来的诸如程序的逻辑部分界定的不确定性、存在否定时c u t 造 成求解结果的不可靠性等问题。与c u t 机制最本质的区别在于，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 r c o m m i t ) 。 第一章绪论 一解剪枝操作记为 ) ，它的作用范围为花括号之间的公式，当花括号内的 公式求得一个解时就立即返回，相当于剪除其他可能正确的所有答案。例如，我 们对模块s o r t 中的p e r m u t a t i o n 谓词做如下询问： - - p e r m u t a t i o n ( 1 ，2 ，3 ，x ) 将产生结果： x = 1 ，2 ，3 x = 1 ，3 ，2 x - - 3 ，2 ，1 程序将给出所有的排列，但如果我们进行如下询问： 一 p e r m u t a t i o n ( 1 ，2 ，3 ，x ) ) 则程序给出一种正确排列后便结束。 条形剪枝操作记为i ，每条g 6 d e l 程序语句最多只能含有一个i ，i 的作用 范围就是在语句体内出现在i 左边的那个公式。如果一个程序中某语句含有i ， 那么该程序将求出i 辖域中公式的一个解后，剪除由同一谓词定义的语句中包含 i 的语句所产生的搜索树中的所有其它语句的分支。 例如，用于快速排序的p a r t i t i o n 谓词定义如下( p a r t i t i o n ( a ，b ，c ，d ) 表示 列表a 关于元素b 的一次划分得到列表b 和列表c ) ： p r e d i c a t ep 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 木l i s t ( i n t e g e r ) ，i c l i s t ( i n t e g e r ) d e l a y p a r t i t i o n ( ，一，j 一) 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 ) b 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 ( x | x s ，y ， x li s ，r s ) 一x = ylp a r t i t i o n ( x s ，y ，i s ，r s