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

-- AlexeyRodriguez - 30 Jun 2008