A Polymorphic Type System for Extensible Records and Variants

Benedict R. Gaster  and Mark P. Jones

Nottingham University; 1 edition (July 25, 2011)
Technical report NOTTCS-TR-96-3. November 1996.


Records and variants provide flexible ways to construct datatypes, but the restrictions imposed by practical type systems can prevent them from being used in flexible
ways. These limitations are often the result of concerns about efficiency or type inference, or of the difficulty in providing accurate types for key operations.

This paper describes a new type system that remedies these problems: it supports extensible records and variants, with a full complement of polymorphic operations
on each; and it offers an effective type inference algorithm and a simple compilation method. It is a practical system that can be understood and implemented
as a natural extension of languages like Standard ML and Haskell. In an area that has already received a great deal of attention from the research community,
the type system described here is the first to combine all of these features in a practical framework.

One important aspect of this work is the emphasis that it places on the use of rows in the construction of record and variant types. As a result, with only small extensions of the core type system, we are able to introduce new, powerful operations on records using features
such as row polymorphism and first-class labels.