A Polymorphic Type System for Extensible Records and Variants

A Polymorphic Type System for Extensible Records and Variants

Benedict R. Gaster and Mark P. Jones,
Technical Report NOTTCS-TR-96-3,
Functional Programming Research Group,
Department of Computer Science,
University of Nottingham,
Nottingham NG7 2RD, UK.


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.

Available by http in pdf, gzipped PostScript, or gzipped dvi.