Lune

OOPSLA2023Top-tier venue

Structural Subtyping as Parametric Polymorphism

Wenhao Tang, Daniel Hillerström, James McKinna, Michel Steuwer, Ornela Dardha, Rongxiao Fu, Sam Lindley

Abstract

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Polymorphic Records for Dynamic Languages cites MLstruct: principal type inference in a Boolean algebra of structural types
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Polymorphic Records for Dynamic LanguagesGiuseppe Castagna, Loïc PeyrotOOPSLA 2025 · 2 citations

Builds on3

  1. MLstruct: principal type inference in a Boolean algebra of structural typesLionel Parreaux, Chun Yin ChauOOPSLA 2022 · 31 citations
  2. FreezeML: complete and easy type inference for first-class polymorphismFrank Emrich, Sam Lindley, Jan Stolarek, James Cheney et al.PLDI 2020 · 13 citations
  3. Making a Type Difference: Subtraction on Intersection Types as Generalized Record OperationsHan Xu, Xuejing Huang, Bruno C. d. S. OliveiraPOPL 2023 · 7 citations

Related papers

  1. Parametric Subtyping for Structural Parametric PolymorphismHenry DeYoung, Andreia Mordido, Frank Pfenning, Ankush DasPOPL 2024 · 3 citations
  2. Revisiting Row Polymorphism for Set-Theoretic TypesMickaël Laurent, Pierre Donat-Bouillud, Filip Křikava, Jan VitekOOPSLA 2026
  3. The Simple Essence of MonomorphizationMatthew Lutze, Philipp Schuster, Jonathan Immanuel BrachthäuserOOPSLA 2025 · 2 citations
  4. Extensible Data Types with Ad-Hoc PolymorphismMatthew Toohey, Yanning Chen, Ara Jamalzadeh, Ningning XiePOPL 2026 · 1 citation
  5. Space-Efficient Polymorphic Gradual Typing, Mostly ParametricAtsushi Igarashi, Shota Ozaki, Taro Sekiyama, Yudai TanabePLDI 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines