Dictionary-free Overloading by Partial Evaluation

Mark P. Jones, ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, Orlando, Florida, June 1994.

Abstract:

One of the most novel features in the functional programming language Haskell is the system of type classes used to support a combination of overloading and polymorphism. Current implementations of type class overloading are based on the use of dictionary values, passed as extra parameters to overloaded functions. Unfortunately, this can have a significant effect on run-time performance, for example, by reducing the effectiveness of important program analyses and optimizations.

This paper describes how a simple partial evaluator can be used to avoid the need for dictionary values at run-time by generating specialized versions of overloaded functions. This eliminates the run-time costs of overloading. Furthermore, and somewhat surprisingly given the presence of multiple versions of some functions, for all of the examples that we have tried so far, specialization actually leads to a reduction in the size of compiled programs.

(Supported in part by a grant from ARPA, contract number N00014-91-J-4043.)

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

An earlier version of this paper appeared as a Yale technical report; it includes some additional material about the use of specialization to eliminate polymorphism, and to support the use of type-specific representations. It also describes problems related to separate compilation. Unfortunately, I had to leave it out of later versions of the paper because of lack of space ... which is a pity, because I thought the ideas were quite interesting. You can get a copy now by http in pdf, PostScript, or gzipped dvi.