MLstruct: principal type inference in a Boolean algebra of structural types
Open Access
- 31 October 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (OOPSLA2) , 449-478
Abstract
Intersection and union types are becoming more popular by the day, entering the mainstream in programming languages like TypeScript and Scala 3. Yet, no language so far has managed to combine these powerful types with principal polymorphic type inference. We present a solution to this problem in MLstruct, a language with subtyped records, equirecursive types, first-class unions and intersections, class-based instance matching, and ML-style principal type inference. While MLstruct is mostly structurally typed, it contains a healthy sprinkle of nominality for classes, which gives it desirable semantics, enabling the expression of a powerful form of extensible variants that does not need row variables. Technically, we define the constructs of our language using conjunction, disjunction, and negation connectives, making sure they form a Boolean algebra, and we show that the addition of a few nonstandard but sound subtyping rules gives us enough structure to derive a sound and complete type inference algorithm. With this work, we hope to foster the development of better type inference for present and future programming languages with expressive subtyping systems.Keywords
This publication has 41 references indexed in Scilit:
- Semantic subtypingJournal of the ACM, 2008
- Regular expression types for XMLACM Transactions on Programming Languages and Systems, 2005
- Type inference with non-structural subtypingFormal Aspects of Computing, 1997
- Strong Normalization and Typability with Intersection TypesNotre Dame Journal of Formal Logic, 1996
- A polymorphic record calculus and its compilationACM Transactions on Programming Languages and Systems, 1995
- Efficient inference of partial typesJournal of Computer and System Sciences, 1994
- Subtyping recursive typesACM Transactions on Programming Languages and Systems, 1993
- Type inference with subtypesTheoretical Computer Science, 1990
- A theory of type polymorphism in programmingJournal of Computer and System Sciences, 1978
- The Principal Type-Scheme of an Object in Combinatory LogicTransactions of the American Mathematical Society, 1969