ALightweight Approach To Datatype-GenericRewriting
Stc
Date: 2008-09-25
Time: 11:00
Room: BBL room 471
Speaker: Stefan Holdermans
Title: A Lightweight Approach to Datatype-Generic Rewriting
(joint work with Thomas van Noort, Alexey Rodriguez, Johan Jeuring, and Bastiaan Heeren)
Abstract
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 them. We describe a library that demonstrates how to overcome
these limitations by defining rules in terms of datatypes, and show
how to use a type-indexed datatype to automatically extend a datatype
for syntax trees with a case for metavariables. We then show how
rewrite rules can be implemented without any knowledge of how the
datatype is extended with metavariables. We use Haskell, extended with
associated type synonyms, 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.
(See
http://people.cs.uu.nl/stefan/pubs/noort08lightweight.html.)
