Dictionary Passing for Polytypic Polymorphism
Report ID: TR-635-01Author: Chen, Juan / Appel, Andrew W.
Date: 2001-03-00
Pages: 15
Download Formats: |PDF| |Postscript|
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.