Dictionary Passing for Polytypic Polymorphism

Abstract:

Polytypic functions are defined by induction on the structure of types.
These functions are not parametrically polymorphic in the
conventional sense, but they are not entirely ad hoc either.
An example is the ``polymorphic'' equality function of Standard ML.
Current implementations of polytypic polymorphism either inhibit
efficient data representations, need the programmer to supply
specialized functions for concrete types, or don't generalize to
the ML module system or quantified type systems.
We implement polytypic polymorphism by dictionary passing. In our
approach the compiler generates and passes dictionaries automatically;
the kind of a type decides the shape of its dictionary. The type
theory and dictionary transformations are not new, but we show that
among the current tag-free approaches that implement polytypic
polymorphism dictionary passing has the best integration with an
existing production compiler. We show the type theory, describe an
implementation, and explain how the transformation interacts with the compiler.