PatriciaJohann and
EelcoVisser.
Strategies for Fusing Logic and Control via Local, Application-Specific Transformations. Technical Report UU-CS-2003-050, Institute of Information and Computing Science, Utrecht University. (
pdf). (This is a revised and extended version of the publication below.)
Abstract
Abstract programming supports the separation of logical concerns from
issues of control in program construction. While this separation of
concerns leads to reduced code size and increased reusability of code,
its main disadvantage is the computational overhead it incurs. Fusion
techniques can be used to combine the reusability of abstract programs
with the efficiency of specialized programs.
Stratego is a language for program transformation based on the
paradigm of rewriting strategies. In Stratego, transformation rules
define basic transformation steps and user-definable strategies
control the application of rules to a program. Since the
problem-specific rules and the highly generic strategies which
apply them are kept separate, these elements can be combined in a
mix-and-match fashion to produce a variety of program transformations.
In some instances this separation of concerns leads to inefficient
implementations.
In this paper we show how such inefficiencies can be remedied using
fusion. Furthermore, we show how fusion can be implemented using
rewriting strategies by studying in detail the application of
rewriting strategies to the fusion of the generic innermost strategy
with sets of arbitrary-but-specific rewrite rules. Both the
optimization and the programs to which the optimization applies are
specified in Stratego.
The contributions of this work are twofold. In the first place, we
show how to optimize and reason about rewriting strategies, which
opens up a new area of strategy optimization. In the second place, we
demonstrate how such optimizations can be implemented effectively
using local, application-specific transformations. These techniques
are applicable to transformation of programs in languages other than
Stratego.
PatriciaJohann and
EelcoVisser.
Fusing Logic and Control with Local Transformations: An Example Optimization. In
Workshop on Reduction Strategies in Rewriting and Programming (WRS'01), volume 57 of
Electronic Notes in Theoretical Computer Science, Utrecht, The Netherlands, May 2001. Elsevier Science Publishers.
Abstract
Abstract programming supports the separation of logical concerns from issues of
control in program construction. While this separation of concerns leads to reduced
code size and increased reusability of code, its main disadvantage is the computa-
tional overhead it incurs. Fusion techniques can be used to combine the reusability
of abstract programs with the efficiency of specialized programs.
In this paper we illustrate some of the ways in which rewriting strategies can be
used to separate the de nition of program transformation rules from the strategies
under which they are applied. Doing so supports the generic de nition of program
transformation components. Fusion techniques for strategies can then be used to
specialize such generic components.
We show how the generic innermost rewriting strategy can be optimized by fusing
it with the rules to which it is applied. Both the optimization and the programs to
which the optimization applies are speci ed in the strategy language Stratego. The
optimization is based on small transformation rules that are applied locally under
the control of strategies, using special knowledge about the contexts in which the
rules are applied.
Online
CategoryPaper