|
Metamorphic Programming Extension to Haskell
|
Metamorphic programming is an approach to extend the structured recursive
programming discipline, which favors the use of fold operations over general
recursion, to abstract data types. The key idea is to represent an ADT
by two parts, a constructorand a destructor,which are essentially
functions to/from a common representation. Then a fold can work on an
ADT by applying parameter functions to values that are delivered by the
ADT's own destructor. Fold operations that use as a parameter the constructor
of another ADT, called ADT transformers,play an important role and
offer a concise programming style. Several laws for ADT folds and transformers
exist that can be used for program optimization and verification.
rdup = via list set list 
To experiment with metamorphic programming:
- download meta.tar.gz
- gunzip and untar the archive
- start hugs
(I have tested the programs with Hugs 1.4, Version of June 1998)
- enter :load ADTprog
The idea of metamorphic programming is explained and motivated in the paper
That paper uses Haskell notation and presents most of the examples contained
in the distribution.
I am collecting laws/equations here.
The category theory background is given in the papers
Metamorphic programming offers many opportunities for program optimization.
One aspect is to introduce state monads to improve the efficiency of data
structures. In programs that are expressed as ADT transformers, we can
observe restricted usage patterns for ADTs, and this can be exploited to
derive (i) partial data structurescorrectly implementing the ADTs
and (ii) imperative realizations of these partial data structures. With
a library of ADTs together with (some of) their imperative implementations,
efficient versions of functional programs can be obtained without being
concerned or even knowing about state monads. This is described in the
paper below. One example is the optimization of a graph ADT resulting in
an optimal imperative implementation of depth-first search.
Please send any comments and bug reports to:
erwig@cs.orst.edu