模块化PROLOG语言的设计与实现

PROLOG语言是基于一阶谓词逻辑的子集——HORN子句逻辑的程序设计语言,以其易于理解和易于书写,在当前正越来越受到重视。本文在分析基本PROLOG语言的基础上,参考有关的工作,设计了一种模块化的PROLOG语言M-PROLOG,并且实现了由Kowalski提出的证明性谓词demo,从而提供了元级推理与目标级推理的接口。最后,本文简单介绍了MPROLOG在Altos-986微机上实现解释系统A-SYSTEM的一些体会。     

PROLOG的指称语义和操作语义

PROLOG程序的语义通常是根据一阶逻辑的模型论给出的。但是,这并不足以刻划PROLOG程序的计算特性。PROLOG的实现主要采用了以程序中子句和字面的正文出现次序为基础的顺序计算策略,并用到诸如“Cut”之类的非逻辑成份。在本文中提出了一种指称语义,它能刻划PROLOG的计算特性。我们给出了不含“Cut”的PROLOG的语义,然后,将其推广到含“Cut”的pROLOG。在两这情况下,我们分别证明了该语义与标准操作式解释程序的等价性。作为这一指称语义的应用,还证明了有关PROLOG程序变换的一些标准的“常用”定理的正确性。     

PROLOG的指称语义和操作语义（续）

4.含CUT的PROLOG语义 4.1 语言成份“cut”前面所讨论的PROLOG解释程序简单控制策略的问题之一是在子树中进行大量的回溯搜索有可能没有解(在极端情况下,对无限树形结构进行的穷尽搜索会使逻辑上正确的程序永不终止)。语言成份cut为用户提供了控制这类回溯的手段。     

目标独立的Prolog程序路径依赖分析语义

在Prolog程序分析中,考虑程序的执行路径和非逻辑的cut操作可提高程序分析的精度.当前用于Prolog程序路径依赖分析的语义因依赖于程序执行的目标而不适合目标独立的程序分析.为此,本文采用了一种携带路径信息并允许cut操作的Prolog抽象语法,在此基础上给出了Prolog的操作语义和一种目标独立的标号树(LT)语文,并证明了LT语义相对于操作语义的正确性.LT语义可作为目标独立的Prolog程序路径依赖分析的基础.     

一类受限PROLOG程序的抽象解释及其应用

本文提出一类受限的PROLOG程序——例化良好程序的抽象解释的理论模型,证明抽象解释的结果精确地反应了此类程序在实际运行时的模式信息,即各个谓词调用点处变元例化的状况.这一模式信息可应用于PROLOG的各种实现系统之中,使PROLOG程序的运行速度提高一至两个数量级.作为例子,本文给出适用于变量分离型程序的简化合一算法.本文最后还讨论了向全Horn子集推广的问题.     

谓词模态逻辑到对应物理论的翻译

对应物理论(counterpart theory)是一阶逻辑的一种理论.Lewis利用谓词模态逻辑到对应物理论的翻译来研究谓词模态逻辑的性质,但是Lewis的翻译存在把不可满足的公式翻译为可满足公式的情况针对这个问题,提出了一种扩展语义的谓词模态逻辑,建立了扩展语义后谓词模态逻辑模型与对应物理论模型的一一对应关系,并在此基础上建立了谓词模态逻辑到对应物理论的语义忠实语义满翻译(faithful and full translation),其可确保将谓词模态逻辑的可满足公式和不可满足公式分别翻译为对应物理论的可满足公式和不可满足公式.由对应物理论是可靠的、完备的一阶逻辑的理论且语义忠实语义满翻译保持可靠性和完备性,进一步证明了扩展语义的谓词模态逻辑也是可靠和完备的.     

移动界程模型检测

首次将嵌套谓词等式系应用到带递归的谓词界程逻辑模型检测中,提出了第1个时间复杂性与逻辑公式的交错嵌套深度呈指数关系的局部模型检测算法,这也是目前已知的第2个带递归的谓词界程逻辑模型检测算法.所做的工作有:①讨论了谓词界程逻辑公式与嵌套谓词等式系间语义的等价性,给出了谓词界程逻辑公式转换成嵌套谓词等式系的方法;②讨论了谓词界程逻辑模型检测问题,给出了具体算法,并分析了算法的复杂性.     

基于逻辑一致性判定的广义不透明谓词检测方法

不透明谓词是一类轻量级的代码混淆方法,能以单向的执行复杂度对抗程序的逆向分析。广义不透明谓词扩展狭义不透明谓词的值恒定属性至逻辑恒定属性,已经应用于部分恶意代码中以提升抗查杀能力。为消除不透明谓词对程序恶意性判定的影响,以广义不透明谓词后趋依赖的属性为依据,结合逻辑恒定判定,提出了基于逻辑一致性的广义不透明谓词检测方法。通过静态分析提取谓词前置条件约束、后趋逻辑约束和谓词判定表达式,以相交基本块搜寻初筛谓词,并依据约束求解方法判定广义不透明谓词。构造原型系统并进行测试,结果表明该方法能精准高效地检测出恶意代码中的不透明谓词。     

PROLOG语言及其实现

PROLOG语言是一种逻辑式程序设计语言,其名字就来源于PROgram和LOGic。PROLOG语言改变了人们所熟悉的程序设计语言中一些基本概念,引入了新的思想。PROLOG的程序并不说明运算的过程,它所描述的是事物间的逻辑关系,因而也被归类为非过程式程序设计语言。 本文将通过以下三个部分,介绍笔者于一九八四年实现并通过技术鉴定的一个PROLOG语言系统。它是一个可以在IBM-PC、IBM-PC/XT、IBM-PC/AT和IBM-PC兼容机,以及WANG-PC机上运行的 PROLOG语言系统。1.PROLOG语言的程序结构;2.PROLOG语言系统的核心算法;3.PROLOG语言系统的实现。