没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记347(2019)203-222www.elsevier.com/locate/entcs从整体到局部状态,共代数和合成吉姆·莱尔德英国巴斯大学摘要我们描述了一种类型理论或元语言,用于构造和推理具有全局和局部状态的高阶程序这提供了一个封装原语,用于抽象全局状态并使其成为对象的本地状态,以便仅在其调用之间传递我们的演算和它的语义扩展的解释,在一个笛卡尔封闭的范畴与monoidal行动一类的评估上下文-sequoid-这是双重的功能类型的行动的条件。这给出了一个新的类型构造函数的解释,它允许全局状态的表示-通过这提供了我们的微积分方程理论与共归纳规则证明与局部状态的对象之间的等价我们表明,这一理论是健全的和完整的范畴语义,通过构建一个长期的模型,我们表明,它是一致的,通过给出一个具体的例子的基础上一类的游戏和策略,以前用来解释一般参考。1引言本文描述了一种构造高阶有状态程序的方法- 特别是,通过使状态局部于函数或对象,并在它们之间建立等价性。 通过限制状态的变化在哪里以及如何发生,局部性简化了有状态程序的模块化构造和验证-例如,不再需要跟踪不断增加的全局变量集合以避免不希望的状态变化。然而,关于局部状态的推理可能是微妙的,因为状态的变化隐含在交互中因为它有一个正式的、分类的模型,我们使状态局部化的操作伴随着一个健全而完整的程序等价理论。它是基于一个强大的和完善的原则,用于从计算系统中抽象状态,该计算系统可以表示为函子的余代数,通过将唯一映射带入其最终余代数[20]。例如,如果我们有一个(确定性)系统,它在每一步都从集合S中获取一个输入状态s,输 出 状态sJ∈S,并产生一个可观测值v∈V,这可能是https://doi.org/10.1016/j.entcs.2019.09.0111571-0661/© 2019作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。204J. Laird/Electronic Notes in Theoretical Computer Science 347(2019)203表示为函数f:S → V × S-即集合范畴上函子V×的余代数这个函子的最终余代数是由V中的无穷序列(流)的集合和取这样的流v1v2v3.的函数给出的。到(v1,v2,v3. . ).来自f的唯一余代数态射是取初始状态s并返回相应的可观测值流π1f(s)π1f(π2f(s))π1f(π2f(π2f(s)))的函数。. .这准确地描述了系统的可观察行为,同时隐藏了状态从一个步骤到下一个步骤的内部传递它还带有基于生成无限流的余代数来推理无限流的余归纳原理[21]。共代数原则已经被用来描述有状态编程语言的语义,如Java[6]。我们的方法的新颖性和技术挑战我们的有状态对象,允许它们组合。为了捕获这种共享访问,需要一种新的全局状态的共代数表示,在集合类中是不可用的:我们的模型是有动机的,游戏语义学它是从对局部状态的博弈语义的研究中发展起来的,特别是高阶文献[2]。这个开创性的模型优雅地将有状态行为提炼成局部变量声明的解释,作为一种策略,作为一个引用单元格,因此与此单元格的组合产生一个游戏的整个历史可以作为一种内部状态的一类策略。 细胞的组合定义-以及它生成的程序的表示-与抽象的状态概念缺乏直接关系;在[10,5]中,它可以用余代数来解释,使用最终余代数来表示一种新的函子,序列式。这里报告的工作抽象这些技术从技术设置的游戏语义到一个通用的元语言推理状态。具体地说,我们描述了简单类型λ-演算到类型系统的保守扩展,该类型系统具有用于输出状态的新构造函数(对于该构造函数,具有全局状态的对象可以表示为余代数)和对应于到其最终余代数的唯一映射的封装运算符。后者的唯一性性质为我们提供了一个新的共归纳原理,用于证明具有局部状态的程序之间的等价性,基于它们的局部约简。这是我们的元语言的一个健全而完整的等式理论的一部分,它可以作为新的编程语言的基础,或者通过翻译来分析现有的语言。1.1概述及相关工作我们首先介绍我们的微积分的一部分,其中我们可以表示具有全局状态的对象。这是基于将变量的显式定义添加到λ演算中,如显式替换的λσ演算[1]。一个关键特性是变量可以在其定义的词法范围之外被调用。因此,我们引入了两个进一步的绑定操作:以π演算[14]的风格进行的具有范围挤出的变量隐藏,以及抽象我们模型中定义变量的能力的操作(类似于能力的σ-抽象的概念)。J. Laird/Electronic Notes in Theoretical Computer Science 347(2019)203205写入[ 4 ]中描述的全局引用),该引用使用新的构造函数来类型化。在第3节中,我们描述了λ演算(Cartesian闭范畴)模型上的附加结构CCC. 这是基于解释的基本操作添加一个变量的定义,通过其monoidal行动的一个类别的线性态射对应的评估上下文的一个术语。Møgelberg和Staton[15]探索了使用monoidal action来描述状态传递风格的语义,他们还证明了与延续传递风格的精确对应关系,这与我们模型的另一个属性有关:序列和CCC的内部hom之间的对偶性。这导致了一种形式的跟踪算子[9],用它来解释变量π演算的模型,如[7])。我们关于我们的演算的方程理论的可靠性和完备性结果通过构造一个项模型来证明,表明它是序列CCC的内部语言,扩展了(例如)简单类型λ-演算的原始结果[11]。序列CCC的例子来自CCC和紧致闭范畴之间的任何(前)么半群的附加-例如集合和函数的范畴,以及集合和关系的范畴。然而,有些情况并非如此。我们给出了一个基于Hyland-Ong风格游戏的例子,用于给出高阶引用的指称语义[2]。在[10]中介绍了序列CCC的另一个例子:这是从直觉线性逻辑模型构建的,其中指数!A是序列函子A的最终余代数。正如在[5]中讨论的,这给出了一个定义策略的方法,通过对一个余代数σ:S→A→S(正如我们已经注意到的,它对应于一个在S中具有全局状态的对象)进行变形,导致从S到的余代数态射!A.国家是隐藏的。 朗利提出了类似的操作[13]。 目前的工作的一个贡献在第4节中,我们扩展了我们的演算与相应的语法编译操作,它绑定一个变量到一个术语,其中全局可见的状态(例如,通过状态传递样式解释导出)已经通过使用隐藏变量在变量的连续调用之间共享它这是[17]的抽象操作的特征,其中引入了反框架在这里,我们描述了一个共归纳规则,用于证明具有封装状态的对象的定义之间的等价性,并将其应用于一些简单的例子,包括参考细胞。在第5节中,我们通过发展一个新的余代数范畴和sequoidal范畴上的“sequoidal自然变换”,将我们的范畴模型及其方程理论的可靠性和206J. Laird/Electronic Notes in Theoretical Computer Science 347(2019)203第2章全局状态在这一节中,我们将以一种新的类型理论的形式描述我们表示高阶态的基础,在这种类型理论中,项可以包含变量(作为项)的明确定义,并且可以抽象出做出这种定义的能力它是(按名称调用)简单类型λ-演算的有限乘积的直接扩展-尽管这并不直接反映典型的“现实生活”有状态高阶编程语言的语义,原始术语由以下语法生成:t:= x |λx.t |TT |t{x:= t} |vx.t |λx.t |t x|不行我|第1,..., t n−1- 也就是说,通过以下操作扩展λ演算:• 定义-s{x :=t}将变量x的定义作为t添加到s。• 声明(隐藏)-v x.t将变量x隐藏在t中。• 共同抽象-λx.t 抽象定义变量x的能力-和• 共同应用-t y赋予y在t中抽象的定义。类型由语法给出:S,T:= B|阿<仁寺|S→T|ST-即从一组基类型B通过简单类型λ-演算的有限积和函数类型构造器扩展为“输出类型”S T的概念,它通过共同抽象引入并通过共同应用消除:当提供T类型的变量时,S T类型的项定义它并返回类型s的结果。我们假设子项可以在必要的地方用它们的类型进行注释,但是通常省略这些注释。打字判断的规则见表1。它们生成形式为Γt:T; Δ的上下文中的项,其中Γ和Δ是类型化变量的集合(非重复序列,被认为是置换)。Γ(输入上下文)包含t可以调用的自由变量,Δ(输出上下文)包含它定义的自由变量。如果一个名字出现在Γ中,它可能出现在Δ中,也可能不出现在Δ中,反之亦然。• 定义可以是递归的: 例如我们可以定义定点组合子YT:(T→T)→T=dfλf.νx.x{x:=fx}.• 非线性地处理输入,而线性地处理输出(变量只定义一次,但可以根据需要多次调用)。这些约束条件意味着术语表示顺序的和确定性的程序,尽管它们可以被放松。• 虽然应用和共同应用不是对称的,因为一个项可以只共同应用于一个变量,但可以应用于任何项,我们可以通过将应用ts替换为νx.t x{x:=s}来恢复这些操作之间的对称性。为了简明地给出一个等式理论,我们引入了中心语上下文,它具有J. Laird/Electronic Notes in Theoretical Computer Science 347(2019)203207Γ,x:T<$x:T;Γ,x:St:T;Δ,x:ST;Δrs:S;Δrt:T;rs{x:=t}:SΔ,x:TΓ,x:St:T;Δx/∈ΔΓt:T;Δ,x:Sx/∈Γti:Ti;Δi
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 基于单片机的瓦斯监控系统硬件设计.doc
- 基于单片机的流量检测系统的设计_机电一体化毕业设计.doc
- 基于单片机的继电器设计.doc
- 基于单片机的湿度计设计.doc
- 基于单片机的流量控制系统设计.doc
- 基于单片机的火灾自动报警系统毕业设计.docx
- 基于单片机的铁路道口报警系统设计毕业设计.doc
- 基于单片机的铁路道口报警研究与设计.doc
- 基于单片机的流水灯设计.doc
- 基于单片机的时钟系统设计.doc
- 基于单片机的录音器的设计.doc
- 基于单片机的万能铣床设计设计.doc
- 基于单片机的简易安防声光报警器设计.doc
- 基于单片机的脉搏测量器设计.doc
- 基于单片机的家用防盗报警系统设计.doc
- 基于单片机的简易电子钟设计.doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功