Research group

Programming Languages and Tools Lab

MLscript: Principal Type Inference in a Boolean Algebra of Structural Types

May 16

What would TypeScript look like if it had been designed with type inference and soundness in mind? We provide one possible answer in MLscript, a programming language with records, generic classes, first-class unions and intersections, instance matching, and ML-style principal type inference. While MLscript is mostly structurally typed, it contains a healthy sprinkle of nominality for classes, which gives it desirable semantics, enabling the expression of extensible variants. Technically, we define the constructs of our language using union, intersection, and complement (or 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 aim to disprove a long-held belief that principal type inference is not feasible for programming languages with expressive subtyping systems, and we hope to encourage and help the implementation of better type inference for present and future programming languages.


Speaker: Lionel Parreaux

Google Meet: