First-Class Constrained Types: Elaboration, Type Inference, Approximation, and a Characterization of Termination
This program is tentative and subject to change.
We study a first-class treatment of constrained types, which were previously confined mostly to ML-style polymorphism. We define System FCCT, an extension of System F with polymorphic subtyping and constraint abstraction in types. A value of type 𝑐 ⇒ 𝜏 can be used at type 𝜏 in any context where the subtyping constraint 𝑐 can be discharged. We show that FCCT exhibits interesting properties. First, all well-typed FCCT terms terminate under call-by-name evaluation (CBN), which can be shown by elaboration into System F. Second, all CBN-terminating terms are well-typed in FCCT. Together, these two properties mean that typability in System FCCT characterizes call-by-name termination. Third, FCCT admits a principal type inference semi-algorithm, called FCCTI, which makes no approximations and can thus be seen as an idealized “ground truth” of type inference. We show that FCCTI indirectly simulates term reduction, shedding some light on the difficulty of bounded polymorphic type inference. Finally, we extend FCCTI to track abstracted call contexts and perform approximation by sharing polymorphic instantiations, ensuring termination on all input terms while preserving soundness. In addition to making the connection between polymorphic subtype constraint solving and term reduction, this paper also establishes a connection between constrained types and existing intersection type systems, which are also known to characterize various normalization properties.
This program is tentative and subject to change.
Tue 25 AugDisplayed time zone: Eastern Time (US & Canada) change
10:30 - 12:00 | Types, Testing, and Data StructuresICFP Papers at IP126 Auditorium Chair(s): Steve Zdancewic University of Pennsylvania | ||
10:30 18mTalk | Inlining as a space optimization: a simple time- and space-invariant implementation of the weak lambda-calculusRemote ICFP Papers Thibaut Balabonski LMF, CNRS, Université Paris-Saclay | ||
10:48 18mTalk | First-Class Constrained Types: Elaboration, Type Inference, Approximation, and a Characterization of Termination ICFP Papers Chun Kit Lam The Hong Kong University of Science and Technology (HKUST), Florent Ferrari-Dominguez ENS de Lyon, Lionel Parreaux HKUST (The Hong Kong University of Science and Technology) | ||
11:06 18mTalk | Programmable Property-Based Testing ICFP Papers Alperen Keles University of Maryland at College Park, Justine Frank University of Maryland, College Park, Ceren Mert University of Maryland, College Park, Harrison Goldstein University at Buffalo, SUNY, Leonidas Lampropoulos University of Maryland at College Park | ||
11:24 18mTalk | A Catenable, Splittable, Transient Sequence Data Structure ICFP Papers | ||