Structural Subtyping as Parametric Polymorphism
Structural Subtyping as Parametric Polymorphism
复制标题
作为参数多态性的结构子类型
DOI：
10.1145/3622836
复制
发表时间：
2023
影响因子：
--
通讯作者：
Tang W
中科院分区：
文献类型：
--
作者：
Tang W
结构子类型和参数多态性为程序员提供了类似的灵活性和可重用性。例如，这两个特性都使程序员能够提供一个更宽的记录作为函数的参数，而该函数需要一个更窄的记录。然而，他们这样做的手段有很大的不同，它们之间的关系存在的确切细节，充其量，在literation.In本文中，我们系统地研究结构亚型和参数多态性的相对表达能力。我们的调查重点是建立在何种程度上的参数多态性，在行和存在多态性的形式，可以编码的变体和记录类型的结构亚型。我们的研究基于各种Church风格的λ-演算，这些演算扩展了记录和变体，不同形式的结构子类型，以及行和存在多态性。我们通过展示演算之间的组合翻译来增强表达能力。对于每个翻译，我们证明了一个类型保持和操作对应的结果。我们还证明了一些不存在的结果。通过对源类型和目标类型施加限制，我们揭示了表现力景观中的进一步微妙之处，这些限制使不可能定义的翻译成为可能。更具体地说，我们证明了完整的子类型不能通过多态性编码，但我们表明，几种限制形式的子类型可以通过特定形式的多态性编码。
Structural subtyping and parametric polymorphism provide similar flexibility and reusability to programmers. For example, both features enable the programmer to provide a wider record as an argument to a function that expects a narrower one. However, the means by which they do so differs substantially, and the precise details of the relationship between them exists, at best, as folklore in literature.In this paper, we systematically study the relative expressive power of structural subtyping and parametric polymorphism. We focus our investigation on establishing the extent to which parametric polymorphism, in the form of row and presence polymorphism, can encode structural subtyping for variant and record types. We base our study on various Church-style λ-calculi extended with records and variants, different forms of structural subtyping, and row and presence polymorphism.We characterise expressiveness by exhibiting compositional translations between calculi. For each translation we prove a type preservation and operational correspondence result. We also prove a number of non-existence results. By imposing restrictions on both source and target types, we reveal further subtleties in the expressiveness landscape, the restrictions enabling otherwise impossible translations to be defined. More specifically, we prove that full subtyping cannot be encoded via polymorphism, but we show that several restricted forms of subtyping can be encoded via particular forms of polymorphism.
登录
查看更多内容
继承作为隐式强制
影响因子：
1
作者：
V. Tannen;T. Coquand;Carl A. Gunter;A. Scedrov
通讯作者：
A. Scedrov
无需包含的可扩展记录
DOI：
--
发表时间：
1990
期刊：
影响因子：
--
作者：
R. Harper;B. Pierce
通讯作者：
B. Pierce
简单对象的完整类型推断
DOI：
--
发表时间：
1987
期刊：
Logic in Computer Science
影响因子：
--
作者：
M. Wand
通讯作者：
M. Wand
影响因子：
2
作者：
B. Liskov
通讯作者：
B. Liskov
具有范围标签的可扩展记录
DOI：
--
发表时间：
2005
期刊：
Symposium on Trends in Functional Programming
影响因子：
--
作者：
Daan Leijen
通讯作者：
Daan Leijen