面向对象程序设计中的类型理论

一、什么是类型理论?类型理论是研究类型的定义、模型和推导规律的形式化理论,它和逻辑、代数、计算机程序设计语言、软件开发都有着密切的联系。类型理论起源于对数学悖论的研究,脱胎于带类型的λ-演算及其与逻辑的对应关系的探讨,在计算机科学中找到了其广阔应用领域。如果从研究对象和侧重点上来划分,类型理论可粗略地分为两类:代数类型理论和逻辑类型理论。代数类型理论主要研究类型的代数结构和模型,所使用的工具主要是多类代数、范畴论,Topoes 理论等。程序设     

γω演算——一种高级合成逻辑

本文创建了γω演算,它在语言层次方面远高于curry合成逻辑(简称C逻辑),但在理论上依然奠基在C逻辑之上.这是一种高级的合成逻辑,它不失C逻辑的简洁性,更重要的,它可直接地用作编程语言,或者间接地用作各种各样“带糖衣”的函数编程语言、作用式编程语言和归约编程语言的语义理论基础.文中论述了γω演算的理论及其与C逻辑的内在联系.     

线性逻辑导论

1.从古典逻辑到线性逻辑1986年,法国巴黎第七大学 J。Y.Gi-rard 教授在研究二阶λ-演算的指称语义时发现古典逻辑中的隐含连接词 A(?)B 可以分解成更基本的线性运算!A(?)B,在此基础上,一个与证明论及计算机科学密切相关的新型逻辑系统——线性逻辑(LL)诞生了。由于古典逻辑缺乏切实的方式把证明看成算法,因此是不可构造的,除了不存在任何非平凡的指称语义外,矢列演算中 Cut 的消去也不满足 CR 性质。为了避免这些缺点,     

基于中文陈述句灵活语序的Lambek演算

目前,自然语言处理已从句法、词法层面走向轻量级语义层面。针对中文陈述句的自然语言处理,传统Lambek演算无法解决中文陈述句灵活语序的问题,而现有的方法加入模态词、新连接词等后,又进一步增加了已经是NP-hard的Lambek演算的复杂性,因此并不适合计算机的相关处理。基于此,采用加标动词匹配的Lambek演算对中文陈述句灵活语序进行处理。加标动词匹配算法的时间复杂度低,使得计算机及其程序能有效地对中文陈述句灵活语序进行处理,并能通过Curry-Howard对应理论与λ-演算引入轻量级语义处理。     

ELNF演算的解释技术

ＥＬＮＦ演算是我们在ＬＮＦ演算的基础上扩充逻辑程序设计能力而得到的一种函数／逻辑演算系统，它构成了作者设计的函数／逻辑语言ＲＦＵＮＬＯＧ的基础．本文介绍ＥＬＮＦ演算的解释实现技术，包括数据结构、系统结构以及各个模块的设计思想．最后给出了在此解释系统下，几个典型程序的运行时间．     

抽象算法C—T—ABS和ABSTRACT的理论推导与等价性证明

ＡＢＳＴＲＡＣＴ，Ｃ－Ｔ－ＡＢＳ是把λ表达式转换成ＳＫＩ表达式的抽象算法，是函数式语言实现的理论基础。本文从λ演算，ＳＫＩ演算的基本理论出发，对这两个算法进行了理论推导及功能的等价证明。展示了对一输入，Ｃ－Ｔ－ＡＢＳ能生成较优化的代码，并对它们生成代码的长度及归约效率进行了比较。     

中介命题逻辑一种新的无穷值语义模型及意义

中介逻辑ML（Medium Logic）,自建立了它的三值语义模型后,ML就被许多学者认定为三值逻辑。对于中介逻辑核心理论的中介命题逻辑系统,潘给出了一种无穷值语义模型,并证明了中介命题逻辑在此模型下具有可靠性与完备性。在此基础上,给出一种真值域为[0,λ)∪(λ,1](λ∈(0.5,1))的无穷值语义模型,研究了它的性质,证明了中介命题逻辑在该模型下也具有可靠性与完备性。新模型的存在进一步表明,认定中介逻辑是一种三值逻辑的理由是不充分的。新模型不仅反映了中介逻辑的基本思想,而且为中介逻辑在其他领域的应用提供了基础。     

布尔逻辑的代数表示及其应用研究

目前布尔逻辑已成为计算机科学的重要理论基础之一,是研究人类思维规律的重要工具.文章提出了一种系统化的布尔逻辑的代数表示方法,其基本思想是把布尔集合用一组多项式来表示,在此基础上定义完备的逻辑运算符集.文章对该方法在可满足性问题(SAT)求解和测试模式自动生成(ATPG)中的应用进行了讨论.     

时态查询语言的并发Lambek演算及范畴语法

时态逻辑不可递归公理化的性质,造成它的公理化系统和证明论方法不适于时态查询语言的建模．这使得时态逻辑无法利用公理化系统的良好性质及相关证明论方法对时态数据库的推理和查询做更为严谨和细致地刻画．因此寻找时态逻辑的替代者,以公理化的方式对时态查询语言做句法和语义的分析是必要的．考虑的2个主要工具是作为句法分析工具的以Lambek演算为核心的范畴语法系统,和作为语义分析工具的类型演算λ－演算．这主要是基于类型论的演算特点、SQL语句与陈述句的相似性、Lambek演算和λ－演算的公理化与证明论方法,及它们作为句法和语义分析工具之间的密切联系与对应性决定的．据此从Lambek演算出发,结合时态的处理,构建了并发的Lambek演算（LCTQ）及相应的范畴语法,对以公理化系统为基础的时态查询语言的句法分析做相关研究,并从证明论性质上保障了计算性资源,使得系统更为严谨和完善．     

基于Game理论的μ-演算公理化

随着软硬件系统复杂性的不断提高,各种验证技术被越来越广泛的使用.模型检验技术是一种保证软硬件设计、实现正确性的有效技术.在针对软硬件的模型验证技术中,一般采用时序逻辑作为规约语言.模态μ-演算是模态和时序逻辑中应用较为广泛的一种,它具有语法成分简洁、表达能力强等特点.扩展了Lange和Stirling基于Focus Game的LTL和CTL的公理化方法.提出了一种基于Game理论的μ-演算公式的可满足性的测试方法,该种方法能够将模态μ-演算公式的可满足性问题转化为Focus Game的求解问题.进一步,基于这套Game规则,给出了一个新的关于μ-演算可靠完备的推理系统.同已有的μ-演算公理系统相比,该推理系统相对直观、简洁.