The notion of records, which are used to organize closely related
groups of data so the group can be treated as a unit, and also provide
access to the data within by name, is almost universally supported in
programming languages. However, in virtually all cases, the
operations permitted on records in statically typed languages are
extremely limited. Providing greater flexibility in dealing with
records, while simultaneously retaining the benefits of static type
checking is a desirable goal.
This problem has generated considerable interest, and a number of type systems dealing with records have appeared in the literature. In this work, we present the first polymorphic type system that is expressive enough to type a number of complex operations on records, including three forms of concatenation and natural join. In addition, the precise types of the records involved are inferred, to eliminate the burden of explicit type declarations. Another aspect of this problem is an efficient implementation of records and their associated operations. We also present a compilation method which accomplishes this goal.