ALightweight Approach To Datatype-GenericRewriting
Thomas van Noort, Alexey Rodriguez, Stefan Holdermans, Johan Jeuring, Bastiaan Heeren. A Lightweight Approach to Datatype-Generic Rewriting. Submitted to the Workshop on Generic Programming 2008.
Previous implementations of generic rewriting libraries
have a number of limitations: they require the user to either adapt the
datatype on which rewriting is applied, or the rewriting rules are
specified as functions, which makes it hard or impossible to document,
test, and analyse rules.
We describe a library that demonstrates how to overcome these limitations
by defining rules as datatypes, and how to use a type-indexed datatype to
automatically extend a datatype with a case for meta-variables.
We then show how to implement rules without knowledge of how the
datatype is extended with meta-variables.
We use Haskell extended with associated types to implement both
type-indexed datatypes and generic functions.
We analyse the performance of our library and compare it with other
approaches to generic rewriting.
Paper (To appear in the proceedings of the Workshop on Generic Programming 2008): pdf
- 30 Jun 2008