函数式程序语言与传值进程演算的关系研究

来源 :上海交通大学 | 被引量 : 0次 | 上传用户:lcyR87777
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
基于进程演算的程序语言设计与实现能够将并发理论的语法和语义理论研究真正应用于实践,并从根本上用高效的并发计算去替代传统的顺序计算,这是研究进程演算的一个关键问题。本文从经典的顺序函数式类型程序语言出发,层层深入地考虑现有成熟的程序语言与传值进程演算之间的关系。首先,本文把PCF(编程可计算函数式语言)作为最初的切入点,去讨论程序语言之间的表达能力关系,如果有了一个语法类型系统更简单而且表达能力足够强的语言,那么就便于去研究与进程演算之间的关系;进一步的,在PCF的基础上,本文讨论并发高性能的函数式语言,研究其与进程演算之间的表达能力关系,这对于进程演算的应用价值将会有更深的体现,对进程演算中的理论研究结果也将有更直观的认识。  进程演算中现有应用于程序语言的工作,主要是集中在π演算上,该传名进程演算对于通信相对抽象。在程序语言的实现中也存在语法和等价关系的问题,现在基于π演算的程序语言性能上还有很大的不足,都需要更多的工作来找合适的进程演算模型和等价关系,以促进进程演算在程序语言中的应用。  本文工作的主要贡献主要分为三个方面:  1.通过在按值归约PCF引入完备和可判定的一阶理论Presburger算术,本文提出了一个类型系统更简单的语言PCFLC。从递归函数定义和程序语言表达能力两方面来研究了PCFLC和按值归约PCF的关系:递归函数定义方面,本文提出一个了PCF的极小化模型,给出了函数阶的概念,并且证明了任意函数阶的项都可以在PCFLC中定义出来;程序语言表达能力方面,定义了类型程序语言中的值应用互模拟等价关系,给出了一个从按值归约PCF到PCFLC的编码,这个编码对于值应用互模拟是完全抽象的,这部分工作表明了PCFLC和按值归约PCF在操作语义上有相同的表达能力,而其语法简单可以做为一个中间模型来比较程序语言的表达能力。  2.进程演算中实际应用最多的模型是π演算,但现有π演算中的等价关系大多不适用于类型函数式语言的验证,并且对于无限值的编码也缺乏效率。传值进程演算虽然抽象性低于π演算,但有很好的方法来解决这些问题。因此本文提出了一个传值进程演算的变种VPCΣ,并且引入了很多内置的函数来使其对于实际程序的验证和分析更加有效,然后给出了其的符号操作语义,并研究了VPCΣ的表达能力。  3.提出了一个VPCΣ中的通用解释程序语言解释框架。在此框架下,对并发函数式语言Erlang的核心语义进行了解释,并给出正确性的证明,主要包括:参照Erlang及其核心部分core Erlang的手册归规范形式化了该语言的操作语义;对于core Erlang语言,给出了一个VPCΣ中结构化的解释;证明了形式化操作语义和本文解释之间在迟符号互模拟关系下满足操作一致性,这对Erlang形式化工作一个非常好的性质。而前人的工作中因为π演算中存在的问题大多没有办法给出这方面的结果,本文用一个并行通信的实例进行了说明。  总的来说,本文主要研究了如下问题:函数式语言中等价关系、表达能力关系;传值进程演算的表达能力;传值进程演算对并发函数式程序语言的通用解释和正确性证明,这些工作保证了程序分析的可靠性。本文的工作对于进程演算有很好的指导意义,即便不具有π演算的传名能力,传值进程演算仍然可以作为一个抽象层面稍低的演算,并利用其中的语法和语义结果来指导并发函数式语言的实现,本文可以对传值进程演算和传名进程演算的解释能力进一步的进行研究,以便对基于进程演算的程序语言设计有更深入的了解。
其他文献
将服务作为向用户所提供的基本单位,通过匹配用户需求与服务本身的功能,对服务资源池中合适的服务进行重用、组合和验证,构成“按需服务”的松耦合网络应用,是面向服务的体系结构
随着嵌入式系统硬件性能的提高和相关软件技术的发展,嵌入式POS 的使用越来越广泛,更多的企业和组织已加入到POS 应用和服务的领域中。为了可以使POS 设备增加新的功能而不必
智能交通系统是未来交通的发展方向,车型识别作为智能交通的重要组成部分及关键技术基础,在交通监控和调度,路桥收费管理等领域一直有着重要的应用。而随着计算机视觉的发展,如何
随着信息技术的飞速发展,手机的功能也越来越复杂,从普通手机逐渐过度到多功能手机,现在又出现了结合掌上电脑功能和手机功能的智能手机。手机里面的软件也随之更新,传统手机里的
个人身份识别的准确性以及个人隐私信息的安全性,在身份识别中已发展成了亟待解决的重要社会问题。由于传统的身份识别方法暴露出了很多弊端,已经不能适应科技的发展和社会进步
最近几年,城市车辆的保有量逐年递增,给公众交通带来了巨大的负担,很多研究正在尝试构建智能交通系统来缓解城市公众交通的压力,车载自组织网络作为智能交通领域的一个重要组成
作为一类重要的复杂类型数据,时间序列已成为数据挖掘领域的热点研究对象之一。针对时间序列的数据挖掘在智能交通控制中有着十分重要的作用,其通常首先需要将时间序列分段并转
随着高性能计算机、宽带网络、多媒体、视频压缩和存储等技术的发展,视频数据得到了越来越广泛的应用,如视频点播系统(VOD)、数字化图书馆(DL)、媒体资产管理(MAM)等。近年来,基
配色系统是配色领域与计算机技术结合的产物,属于CAD/CAM研究领域,它目前已广泛用于染料颜料制造业、印染业、塑料着色加工业、涂料业及油墨等着色相关行业,可帮助生产人员进行
本文对基于G.723.1压缩编码算法的纸介质声音存储系统进行了研究。文章对二维条码技术作了阐述,在对已有的码图结构和编码规则进行分析与研究的基础上,提出了针对本系统的应用