### Abstract

Many algorithms have to be implemented over and over again for
different datatypes, either because datatypes change during the
development of programs, or because the same algorithm is used for
several datatypes. Examples of such algorithms are equality tests,
pretty printers, and pattern matchers, and polytypic programming is
a paradigm for expressing such algorithms. This dissertation
introduces polytypic programming for functional programming
languages, shows how to construct and prove properties of polytypic
algorithms, presents the language extension PolyP for implementing
polytypic algorithms in a type safe way, and presents a number of
applications of polytypic programming. The applications include a
library of basic polytypic building blocks, PolyLib, and two larger
applications of polytypic programming: rewriting and data
conversion.
PolyP extends a functional language (a subset of Haskell) with a
construct for defining polytypic functions by induction on the
structure of user-defined datatypes. Programs in the extended
language are translated to Haskell.

PolyLib contains powerful structured recursion operators like
catamorphisms, maps and traversals, as well as polytypic versions of
a number of standard functions from functional programming: sum,
length, zip, (==), (<=), etc. Both the specification of the library
and a PolyP implementation are presented.

The first larger application is a framework for polytypic
programming on terms. We show that an interface of four functions
is sufficient to express polytypic functions for pattern matching,
unification and term rewriting. Using this framework, a term
rewriting function is specified and transformed into an efficient
and correct implementation.

In the second application, a number of functions for polytypic data
conversion are implemented and proved correct. The conversions
considered include pretty printing, parsing, packing and unpacking
of structured data. The conversion functions are expressed in an
embedded domain specific language for data conversion (a hierarchy
of Haskell's constructor classes).

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

AMS 1991 subject classification 68N15, 68N20

## Defence

The public thesis defence is at 10.15 on June 9, 2000 in Hörsalen,
Matematiskt Centrum, Eklandagatan 86, Göteborg.
Opponent is Associate Professor
Mark Jones,
Oregon Graduate Institute, USA.
## Bibliographic details

@PhdThesis{jansson-phdthesis,
author = {Jansson, Patrik},
title = {Functional Polytypic Programming},
school = {Computing Science, Chalmers University of Technology
and Göteborg University, Sweden},
month = may,
isbn = {91-7197-895-X},
year = 2000
}

Last modified: Wed May 24 16:07:16 MET DST 2000
by
Patrik Jansson /
NOpatrikjSP@AMchalmers.se