Warm Fusion In Stratego

PatriciaJohann and EelcoVisser. Warm fusion in Stratego: A case study in the generation of program transformation systems. Annals of Mathematics and Artificial Intelligence, 29(1--4):1--34, 2000.

The technical report version of the paper contains the complete Stratego specification of the implementation

• http://www.cs.uu.nl/~visser/ftp/JV2000-TR.ps.gz
• http://www.cs.uu.nl/~visser/ftp/JV2000-TR.ps.zip

Abstract

Stratego is a domain-specific language for the specification of program transformation systems. The design of Stratego is based on the paradigm of rewriting strategies: user-definable programs in a little language of strategy operators determine where and in what order transformation rules are (automatically) applied to a program. The separation of rules and strategies supports modularity of specifications. Stratego also provides generic features for specification of program traversals.

In this paper we present a case study of Stratego as applied to a non-trivial problem in program transformation. We demonstrate the use of Stratego in eliminating intermediate data structures from (also known as 'deforesting') functional programs via the 'warm fusion' algorithm of Launchbury and Sheard. This algorithm has been specified in Stratego and embedded in a fully automatic transformation system for kernel Haskell. The entire system consists of about 2600 lines of specification code, which breaks down into 1850 lines for a general framework for Haskell transformation and 750 lines devoted to a highly modular, easily extensible specification of the warm fusion transformer itself. Its successful design and construction provides further evidence that programs generated from Stratego specifications are suitable for integration into real systems, and that rewriting strategies are a good paradigm for the implementation of such systems.

See Also

• WarmFusionTransformation
• HSX: a Haskell Transformation Framework

---

CategoryPaper | StrategoPublications