Warm Fusion In Stratego
Stratego -- Strategies for Program Transformation
Warm Fusion in Stratego. A Case Study in the Generation of Program Transformation Systems
by PattyJohann? and EelcoVisser
To appear in Annals of Mathematics and Artificial Intelligence.
The technical report version of the paper contains the complete Stratego specification of the implementation
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