Zipping strategies and attribute grammars

Abstract

Strategic term rewriting and attribute grammars are two powerful programming techniques widely used in language engineering. The former relies on strategies (recursion schemes) to apply term rewrite rules in defining transformations, while the latter is suitable for expressing context-dependent language processing algorithms. Each of these techniques, however, is usually implemented by its own powerful and large processor system. As a result, it makes such systems harder to extend and to combine. We present the embedding of both strategic tree rewriting and attribute grammars in a zipper-based, purely functional setting. The embedding of the two techniques in the same setting has several advantages: First, we easily combine/zip attribute grammars and strategies, thus providing language engineers the best of the two worlds. Second, the combined embedding is easier to maintain and extend since it is written in a concise and uniform setting. We show the expressive power of our library in optimizing Haskell let expressions, expressing several Haskell refactorings and solving several language processing tasks for an Oberon-0 compiler.