Specializing Type-Indexed Values by Partial Evaluation

The Generic Haskell programming language allows functions to be defined by induction on the structure of data types. This gives rise to generic functions which can be applied to values of any conceivable data type. Compiling a Generic Haskell program amounts to generating a Haskell program in which all generic functions have been translated to ordinary Haskell functions. Since the Haskell language only allows functions to be defined on the values of a data type, translating generic functions defined on the structure of data types is not straightforward. The application of a generic function to a value involves specializing the function to the type of its parameter. For every distinct specialization of a generic function in a Generic Haskell program, an ordinary Haskell function is generated in the compilation process. Hence, the compilation of a generic function will typically yield several ordinary functions. The current method that is used to translate specializations is rather unsophisticated. At run-time, values are frequently converted back and forth to a structural representation which simplifies the code generation process considerably. This approach is often extremely detrimental to the space and time efficiency of the generated functions. In this thesis an optimization method is described which attempts to dialnate all structural conversions from the generated functions by applying partial evaluation in combination with a number of program transformations. This approach essentially evaluates all conversions in the representation of values at compile-time. The functions of the resulting optimized program approach the efficiency of hand-written Haskell functions in terms of space and time usage. An implementation of the described method is included as an optimizer in the final phase of the Generic Haskell compiler.