Revision as of 05:03, 3 November 2008
Kansas University Rewrite Engine (KURE, pronounced cure) is a DSL for writing rewrite systems over grammars with scope. It was used (along with Template Haskell) to provide the basic rewrite abilities inside HERA. It has been recently rewritten and will be published on hackage shortly. KURE provides combinators for ordering the application of an abstract type, Rewrite, combinators for building primitive rewrites, and combinators performing rewrite searches. KURE will be used to power the next version of HERA.
1 Basic Combinators
Simplified, the basic type is Rewrite
with methods to help order Rewrites.
(>+>) :: Rewrite exp -> Rewrite exp -> Rewrite exp
-- do the first rewrite, then second iff the first changed something.
(>&>) :: Rewrite exp -> Rewrite exp -> Rewrite exp
-- do the first rewrite, then second iff the first did not change anything.
(>|>) :: Rewrite exp -> Rewrite exp -> Rewrite exp
-- id rewrite, does not change anything.
nullRewrite :: Rewrite exp
-- repeat the application of rewrites until no more are possible.
many :: Rewrite exp -> Rewrite exp
None of these methods can actually choose based on the internals of the expression, so we have a combinator that can choose.
Because Rewrite is abstract, we can only look at exp, can choose what to apply, not actually use the exp argument in our result.
2 Primitive Rewrites
There are also ways of providing primitives, promoting a monadic rewrite into an abstract Rewrite.
rewrite :: (exp -> RewriteM exp) -> Rewrite exp
and a method for promoting a Rewrite into a RewriteM rewrite, allowing the authorship of abstraction breaking primitives in terms of other abstract rewrites, if required.
The library also provides ways of searching for places to applying rewrite rules inside syntax trees, allowing KURE to be used as a nanopass engine for compilation or optimization. Rewrites (or combinations of rewrites) can be applied in a prefix or postfix order.