Optimizing Outermost Rewrite Sequences

Jon Pospischil

Abstract programming supports the separation of logic from control in program construction. By separating control from logic, control can be specified in a generic manner. This makes it possible to use the same control mechanism to apply any computational logic to a program, as well as to apply the same computational logic to a program using any control mechanism. The resulting mixing and matching of logic and control has many benefits, most notably reduced code size, and increased modularity and reusability of code. Unfortunately, the construction and traversal of intermediate terms required to ``glue" together separate program components means that this mixing usually comes at the cost of efficiency as well. But, fortunately, it is often possible to automatically ``fuse" the separate logic and control components of a modular program to produce a more efficient, monolithic equivalent in which the generic control structures appearing in the program have been specialized to the specified logic.

Strategy-based programming languages are designed for the specification of program transformations and are built on the ideas of abstract programming. In such languages, first-order terms representing programs are transformed using logic defined by rewrite rules according to control information encoded by strategies for applying them. One strategy of particular interest is an outermost reduction strategy, which performs rewriting in a ``top-down" or ``outside-in" manner. In this paper we lay the theoretical foundation for fusing --- and thus optimizing --- an outermost control strategy with the logic defined by any term rewriting system.