Abstract

This is a presentation of the paper by Matthias Blume, Umut Acar, and Wonseok Chae. Their abstract is as follows:

We present language mechanisms for polymorphic, extensible records and
their exact dual, polymorphic sums with extensible first-class cases.
These features make it possible to easily extend existing code with
new cases. In fact, such extensions do not require any changes to code
that adheres to a particular programming style. Using that style,
individual extensions can be written independently and later be
composed to form larger components. These language mechanisms provide
a solution to the expression problem.

We study the proposed mechanisms in the context of an implicitly
typed, purely functional language PolyR. We give a type system for the
language and provide rules for a 2-phase transformation: first into an
explicitly typed λ-calculus with record polymorphism, and finally to
efficient index-passing code. The first phase eliminates sums and
cases by taking advantage of the duality with records.

We implement a version of PolyR extended with imperative features and
pattern matching - we call this language MLPolyR. Programs in MLPolyR
require no type annotations - the implementation employs a
reconstruction algorithm to infer all types. The compiler generates
machine code (currently for PowerPC) and optimizes the representation
of sums by eliminating closures generated by the dual construction.