Article contents
A lightweight approach to datatype-generic rewriting
Published online by Cambridge University Press: 27 September 2010
Abstract
Term-rewriting systems can be expressed as generic programs parameterised over the shape of the terms being rewritten. Previous implementations of generic rewriting libraries require users to either adapt the datatypes that are used to describe these terms or to specify rewrite rules as functions. These are fundamental limitations: the former implies a lot of work for the user, while the latter makes it hard if not impossible to document, test, and analyze rewrite rules. In this article, we demonstrate how to overcome these limitations by making essential use of type-indexed datatypes. Our approach is lightweight in that it is entirely expressible in Haskell with GADTs and type families and can be readily packaged for use with contemporary Haskell distributions.
- Type
- Articles
- Information
- Journal of Functional Programming , Volume 20 , Special Issue 3-4: Generic Programming , July 2010 , pp. 375 - 413
- Copyright
- Copyright © Cambridge University Press 2010
References
- 8
- Cited by
Discussions
No Discussions have been published for this article.