论文摘要
逻辑程序设计语言提供了一种说明性的编程方法,与基于算法的过程性程序设计语言如Pascal、Ada和C等相比,逻辑程序设计语言具有诸多优点。首先,逻辑程序丰富的表达能力和不确定性语言机制,使其非常适合于表达人工智能和知识工程中的问题;其次,逻辑程序建立在一阶谓词逻辑的基础之上,具有严格的数学理论基础,易于进行程序的正确性证明和验证;第三,逻辑程序开发者不需要考虑程序“如何计算”,而只需要说明要“做什么”,从而有利于其将精力集中到问题的求解上,从计算模型的层面探索问题的求解。由于Prolog语言取得的成功,一直以来Prolog都是逻辑程序设计的代称。但是,Prolog基于一阶逻辑的Horn子集,作为一种无类型逻辑程序设计语言,缺乏足够的可表达性,而且,由于Prolog中引入了较多的过程性谓词如cut和retract等,使其缺乏清晰、明确的说明性语义。鉴于此,逻辑程序设计的研究者们提出了新型逻辑程序设计语言G（o|¨）del,它继承并发展了Prolog,试图解决Prolog中存在的诸多语义问题,增强其可表达性能力,缩小理想的逻辑程序与逻辑程序的具体实现之间的巨大鸿沟。据此,它引入了参数型多态多类类型系统,增加了延迟计算等新的语言成分,支持模块化程序设计和元程序设计,具有灵活的计算规则和剪枝操作,并以系统模块形式提供丰富的抽象数据类型以支持通用程序设计,对其适当扩展可支持面向对象程序设计。但是,作为一种新型的逻辑程序设计语言,G（o|¨）del语言能否真正走向成功,还取决于是否有一个高效率的编译或解释实现系统。迄今为止,就是语言的设计者们,也仅实现了一个旨在验证语言功能的原型系统。本文围绕G（o|¨）del语言的实现,提出并沿着一条全新的技术路线,初步实现了一个G（o|¨）del编译程序的实验室系统,通过了一组典型的程序实例且运行效率很高。本文重点介绍这个实验室系统中核心部分推理机的设计与实现。本文首先对推理机所要实现的G（o|¨）del语言的主要机制:类型系统、延迟计算、剪枝操作等进行了分析,讨论这些新机制对G（o|¨）del语言程序设计和SLD反驳-消解过程的影响。进一步,借鉴Warren虚拟机的设计思想,提出了将G（o|¨）del源程序通过词法、语法和语义分析把源程序翻译成带说明性语义信息的一种高度结构化的中间代码,然后在中间代码之上进行程序的推理求解的编译实现技术路线。基于该思想,我们具体讨论了G（o|¨）del语言编译系统的总体设计结构,阐述了G（o|¨）del语言推理机实现的基本原理,重点描述了中间代码结构和基于该中间代码的推理机实现。最后,通过性能分析验证了本文实现的推理机具有较高的执行效率。