Functional Polytypic Programming
Use and Implementation

Patrik Jansson

A dissertation for the Licentiate Degree in Computing Science
at Chalmers University of Technology

The full document is available as ps, ps.gz, dvi and dvi.gz files , all references as a bib file. Slides from the presentation are also available.


Many functions have to be written over and over again for different datatypes, either because datatypes change during the development of programs, or because functions with similar functionality are needed on different datatypes. Examples of such functions are pretty printers, pattern matchers, equality functions, unifiers, rewriting functions, etc. Such functions are called polytypic functions.

A polytypic function is a function that is defined by induction on the structure of user-defined datatypes. This thesis introduces polytypic functions, shows how to construct and reason about polytypic functions and describes the implementation of the polytypic programming system PolyP.

PolyP extends a functional language (a subset of Haskell) with a construct for writing polytypic functions. The extended language type checks definitions of polytypic functions, and infers the types of all other expressions. Programs in the extended language are translated to Haskell.

Keywords: Programming languages, Functional programming, Algebraic datatypes, Polytypic programming, Generic programming

AMS 1991 subject classification 68N15, 68N20

The thesis is presented at a seminar on May 28 1997.

Last modified: Wed Oct 7 18:19:00 MET DST 1998 by
Patrik Jansson /