Implementing Functional Generic Programming

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.</p> 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.</p> 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 and Generic Haskell. 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. </p> 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, with our compiler we get a library of generic functions for Haskell