Implementing Functional Generic Programming Ulf Norell

Abstract Functional generic programming extends functional programming with the ability to parameterize functions on the structure of a datatype. This allows a programmer to implement certain algorithms once and for all, instead of re-implementing them for each datatype they apply to. Examples of such algorithms include simple traversals and pretty printing as well as more complex XML processing tools. The topic of this dissertation is the implementation of functional generic programming. More precisely we address two particular questions: how can we reduce the amount of work required to implement generic programming languages, and how can we embed generic programming in an existing functional language. To answer the first question we show how meta-programming can be used to quickly prototype generic programming languages. In particular we describe prototype implementations of two generic programming languages: PolyP [15] and Generic Haskell [4]. The prototypes are extremely light-weight while still retaining most of the functionality of the original languages. One thing that is missing, though, is a way of adding type systems to the prototypes. In answer to the second question we show how generic programming can be embedded in Haskell by exploiting the class system. We describe a new version of PolyP (version 2) together with a compiler that compiles PolyP 2 code into Haskell. By compiling the polytypic library, PolyLib [16], with our compiler we get a library of generic functions for Haskell. Acknowledgments First of all I would like to thank my supervisor Patrik Jansson without whom I would never had started working on generic programming in the first place. He has been a constant source of good ideas and helpful suggestions guiding me through the writing of this dissertation and the work that lies behind it