Revisiting Row Polymorphism for Set-Theoretic Types
Open Access
- 1 October 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA2) , 1632-1658
Abstract
Set-theoretic types support expressive record types through unions, intersections, and negations, but they lack the row polymorphism needed to type operations that propagate unknown fields across records. Prior work addresses this by allowing Boolean combinations of rows in type substitutions, which complicates the formalism and prevents the tallying algorithm from being complete. We propose an alternative: instead of enriching substitutions, we allow Boolean combinations of row variables directly within record type constructors, where the tail of a record has the same shape as any field. This design keeps substitutions simple---a row variable maps to a single row---and yields a natural extension of the subtyping and tallying algorithms. Tallying is complete for all solutions whose rows are constant over labels not mentioned in the constraints. We implement our approach in the set-theoretic type library SSTT and the type checker MLsem, providing the first implementation of a type system that combines semantic subtyping with row polymorphism. We demonstrate the expressiveness of the system by encoding several data structures from the R programming language: heterogeneous lists, variadic function arguments, and class-based dispatch.Keywords
Funding Information
- Czech Ministry of Education, Youth and Sports (LL2325)
- Czech Science Foundation (23-07580X)
This publication has 16 references indexed in Scilit:
- Typing Records, Maps, and StructsProceedings of the ACM on Programming Languages, 2023
- Set-theoretic Types for Erlang2022
- Designing types for R, empiricallyProceedings of the ACM on Programming Languages, 2020
- Abstracting extensible data types: or, rows by any other nameProceedings of the ACM on Programming Languages, 2019
- Polymorphism, subtyping, and type inference in MLsub2017
- A Logical Approach to Deciding Semantic SubtypingACM Transactions on Programming Languages and Systems, 2015
- Polymorphic Functions with Set-Theoretic Types2015
- Polymorphic functions with set-theoretic types2014
- Set-theoretic foundation of parametric polymorphism and subtyping2011
- A gentle introduction to semantic subtyping2005