Under Control: Compositionally Correct Closure Conversion with Mutable State
Under Control: Compositionally Correct Closure Conversion with Mutable State
复制标题
受控：具有可变状态的组合正确的闭包转换
DOI：
10.1145/3354166.3354181
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ahmed, Amal
中科院分区：
文献类型：
--
作者：
Mates, Phillip;Perconti, Jamie;Ahmed, Amal
组合编译器验证的目的是确保组件的正确编译，而不仅仅是整个程序。Perconti和Ahmed[2014]提出了一种组合编译器正确性的方法，该方法支持与任意来源的代码链接。特别是，它们允许将编译后的组件与功能甚至不能用编译器自己的源语言表示的代码链接起来。他们的方法的本质是定义一个多语言系统，将源语言和目标语言之间的互操作性形式化，这样编译器的正确性就可以被描述为多语言中的上下文等价。他们在具有递归类型的多态语言的两遍类型保留编译器上演示了这种方法。我们将展示如何将这种多语言编译器验证方法扩展到具有ml风格可变引用的源语言。我们给出了具有可变状态的语言的类型闭包转换的第一个组合正确性证明。更重要的是，我们展示了我们可以用一级控制（call/cc）扩展我们的目标语言，从而产生一个编译器正确性定理，该定理允许从源语言（不含call/cc）编译的组件与扩展行为不能在源语言中表示的目标语言组件（含call/cc）链接。一个重要的技术贡献是设计了用于执行编译器正确性证明的多语言逻辑关系。由于两种互操作语言中参数多态性和可变状态的混合，这在语义上具有挑战性。我们用蓝色字体来排版源语言，用红色粗体来排版目标语言。这张纸如果用彩色打印的话，阅读起来会容易得多。
Compositional compiler verification aims to ensure correct compilation of components, not just whole programs. Perconti and Ahmed [2014] propose a methodology for compositional compiler correctness that supports linking with code of arbitrary provenance. In particular, they allow compiled components to be linked with code whose functionality cannot even be expressed in the compiler's own source language. The essence of their approach is to define a multi-language system that formalizes interoperability between the source and target languages so that compiler correctness can be stated as contextual equivalence in the multi-language. They illustrate this methodology on a two-pass type-preserving compiler for a polymorphic language with recursive types.We show how to extend this multi-language compiler-verification approach to a source language with ML-style mutable references. We present the first compositional correctness proof of typed closure conversion for a language with mutable state. More importantly, we show we can extend our target language with first-class control (call/cc) yielding a compiler correctness theorem that allows components compiled from the source language (without call/cc) to be linked with target-language components (with call/cc) whose extensional behavior cannot be expressed in the source. A nontrivial technical contribution is the design of the multi-language logical relation used to carry out the proof of compiler correctness. This is semantically challenging due to the mix of parametric polymorphism and mutable state in both interoperating languages.We use a blue font to typeset our source language and a bold red to typeset the target. The paper will be much easier to read if viewed/printed in color.
登录
查看更多内容
Pilsner：用于高阶命令式语言的组合验证编译器
DOI：
--
发表时间：
2015
期刊：
ACM SIGPLAN International Conference on Functional Programming
影响因子：
--
作者：
Georg Neis;C. Hur;Jan;Craig McLaughlin;Derek Dreyer;Viktor Vafeiadis
通讯作者：
Viktor Vafeiadis
PLT方案Web服务器的实现与使用
DOI：
--
发表时间：
2007
期刊：
High. Order Symb. Comput.
影响因子：
--
作者：
S. Krishnamurthi;Peter Walton Hopkins;J. McCarthy;P. Graunke;Greg Pettyjohn;M. Felleisen
通讯作者：
M. Felleisen
机器学习和线性语言出色的互操作性
DOI：
--
发表时间：
2017
期刊：
Foundations of Software Science and Computation Structure
影响因子：
--
作者：
Gabriel Scherer;Max S. New;Nick Rioux;Amal J. Ahmed
通讯作者：
Amal J. Ahmed
反转控制反转或延续与以页面为中心的编程
DOI：
--
发表时间：
2003
期刊：
SIGP
影响因子：
--
作者：
C. Queinnec
通讯作者：
C. Queinnec
类型化闭包转换保留了观察等价性
DOI：
--
发表时间：
2008
期刊：
ACM SIGPLAN International Conference on Functional Programming
影响因子：
--
作者：
Amal J. Ahmed;Matthias Blume
通讯作者：
Matthias Blume