KURE

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.

Basic Combinators

Simplified, the basic type is Rewrite

data Rewrite exp = ...

with methods to help order Rewrites.

-- do the first rewrite, and the second. (>+>) :: 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.

choose :: (exp -> Rewrite exp) -> Rewrite exp

Because Rewrite is abstract, we can only look at exp, can choose what to apply, not actually use the exp argument in our result.

Primitive Rewrites

There are also ways of providing primitives, promoting a monadic rewrite into an abstract Rewrite.

data RewriteM exp = ... 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.

apply :: Rewrite exp -> exp -> RewriteM exp

Searching

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.