The full document is available as
PDF (841k) and as
.ps.gz (334k).
[En sammanfattning finns även på svenska.]
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
@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
}