Graduality and parametricity: together again for the first time
Graduality and parametricity: together again for the first time
复制标题
渐进性和参数化：首次再次结合在一起
DOI：
10.1145/3371114
复制
发表时间：
2020
影响因子：
--
通讯作者：
Ahmed, Amal
中科院分区：
文献类型：
--
作者：
New, Max S.;Jamner, Dustin;Ahmed, Amal
参数多态性和渐进类型化已经被证明是一个困难的组合，还没有语言能够满足每一个的基本定理：参数性和渐进性。值得注意的是，Toro，Labrada和Tanter（POPL 2019）推测，对于使用动态类型生成的系统F的任何渐进扩展，渐进性和参数性是“简单地不兼容”的。然而，我们认为，这不是渐进性和参数本身是不兼容的，而是在以前的工作中，将系统F的语法与动态类型生成相结合，需要类型导向的计算，我们表明，这是一个共同的来源渐进性和参数违反在以前的工作。然后，我们表明，通过修改通用和存在类型的语法，使类型名生成显式，我们去除了对类型定向计算的需要，并且得到了一种同时满足渐进性和参数性定理的语言。该语言具有简单的运行时语义，可以通过转换为静态类型语言来解释，其中动态类型被解释为动态可扩展的sum类型。远离冲突，我们表明，参数性定理如下作为一个直接的推论的关系解释的渐进性财产。
Parametric polymorphism and gradual typing have proven to be a difficult combination, with no language yet produced that satisfies the fundamental theorems of each: parametricity and graduality. Notably, Toro, Labrada, and Tanter (POPL 2019) conjecture that for any gradual extension of System F that uses dynamic type generation, graduality and parametricity are ``simply incompatible''. However, we argue that it is not graduality and parametricity that are incompatible per se, but instead that combining the syntax of System F with dynamic type generation as in previous work necessitates type-directed computation, which we show has been a common source of graduality and parametricity violations in previous work.We then show that by modifying the syntax of universal and existential types to make the type name generation explicit, we remove the need for type-directed computation, and get a language that satisfies both graduality and parametricity theorems. The language has a simple runtime semantics, which can be explained by translation to a statically typed language where the dynamic type is interpreted as a dynamically extensible sum type. Far from being in conflict, we show that the parametricity theorem follows as a direct corollary of a relational interpretation of the graduality property.
登录
查看更多内容
带参考的渐进安全打字
DOI：
--
发表时间：
2013
期刊：
IEEE Computer Security Foundations Symposium
影响因子：
--
作者：
L. Fennell;Peter Thiemann
通讯作者：
Peter Thiemann
DOI：
10.1007/978-3-540-73589-2_2
发表时间：
2007-07
期刊：
--
影响因子：
--
作者：
Jeremy G. Siek;Walid Taha
通讯作者：
Jeremy G. Siek;Walid Taha
DOI：
10.1145/3009837.3009856
发表时间：
2017-01
期刊：
Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages
影响因子：
--
作者：
Nico Lehmann;É. Tanter
通讯作者：
Nico Lehmann;É. Tanter
抽象渐进式打字
DOI：
--
发表时间：
2016
期刊：
ACM-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
Ronald Garcia;Alison M. Clark;É. Tanter
通讯作者：
É. Tanter
一流课程的逐步打字
影响因子：
--
作者：
Asumu Takikawa;T. Strickland;Christos Dimoulas;Sam Tobin;Matthias Felleisen
通讯作者：
Matthias Felleisen