Theorems for free for free: parametricity, with and without types
Theorems for free for free: parametricity, with and without types
复制标题
免费定理：参数化，有类型和没有类型
DOI：
10.1145/3110283
复制
发表时间：
2017
影响因子：
--
通讯作者：
Ahmed A
中科院分区：
文献类型：
--
作者：
Ahmed A
多态归咎演算集成了静态类型，包括通用类型，与动态类型。这种集成的主要挑战是保持参数性：即使是动态类型的代码，一旦转换为通用类型，也应该满足参数性。Ahmed et al.（2011）在多态归咎演算中使用运行时类型生成来保持参数性，但它这样做的证明一直难以捉摸。马修斯和艾哈迈德（2008）给出了一个结合ML和Scheme的密切相关系统的参数性证明，但后来发现他们的证明中有一个缺陷。在本文中，我们提出了一个改进版本的多态归咎演算，我们证明了它满足关系参数。证明依赖于一个步骤索引的Kripke逻辑关系。在动态类型的情况下，需要步进索引来使逻辑关系定义良好。可能世界包括生成的类型名到它们的类型的映射以及类型名到关系的映射。我们证明了这种逻辑关系的基本属性，它是健全的上下文等价。为了证明多态责备演算中参数性的效用，我们推导出两个自由定理。
The polymorphic blame calculus integrates static typing, including universal types, with dynamic typing. The primary challenge with this integration is preserving parametricity: even dynamically-typed code should satisfy it once it has been cast to a universal type. Ahmed et al. (2011) employ runtime type generation in the polymorphic blame calculus to preserve parametricity, but a proof that it does so has been elusive. Matthews and Ahmed (2008) gave a proof of parametricity for a closely related system that combines ML and Scheme, but later found a flaw in their proof. In this paper we present an improved version of the polymorphic blame calculus and we prove that it satisfies relational parametricity. The proof relies on a step-indexed Kripke logical relation. The step-indexing is required to make the logical relation well-defined in the case for the dynamic type. The possible worlds include the mapping of generated type names to their types and the mapping of type names to relations. We prove the Fundamental Property of this logical relation and that it is sound with respect to contextual equivalence. To demonstrate the utility of parametricity in the polymorphic blame calculus, we derive two free theorems.
登录
查看更多内容
抽象类型的生成性和动态不透明度
DOI：
--
发表时间：
2003
期刊：
ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming
影响因子：
--
作者：
Andreas Rossberg
通讯作者：
Andreas Rossberg
DOI：
--
发表时间：
2007
期刊：
Dynamic Languages Symposium
影响因子：
--
作者：
Arjun Guha;Jacob Matthews;R. Findler;S. Krishnamurthi
通讯作者：
S. Krishnamurthi
DOI：
--
发表时间：
2016
期刊：
ACM-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
M. Cimini;Jeremy G. Siek
通讯作者：
Jeremy G. Siek
DOI：
10.1007/978-3-540-73589-2_2
发表时间：
2007-07
期刊：
--
影响因子：
--
作者：
Jeremy G. Siek;Walid Taha
通讯作者：
Jeremy G. Siek;Walid Taha
一流课程的逐步打字
影响因子：
--
作者：
Asumu Takikawa;T. Strickland;Christos Dimoulas;Sam Tobin;Matthias Felleisen
通讯作者：
Matthias Felleisen