Best Student Paper: A New Approach to One-Pass Transformations

Kevin Millikin

Abstract: We show how to construct a one-pass optimizing transformation by fusing a non-optimizing transformation with an optimization pass. We state the transformation in build form and the optimization pass in cata form, i.e., as a catamorphism; and we use cata/build fusion to combine them. We illustrate the method by fusing Plotkin's call-by-value and call-by-name CPS transformations with a reduction-free normalization function for the λ-calculus, thus obtaining two new one-pass CPS transformations.

1.1 INTRODUCTION

Compiler writers often face a choice between implementing a simple, non-optimizing transformation pass that generates poor code which will require subsequent optimization, and implementing a complex, optimizing transformation pass that avoids generating poor code in the first place. A two-pass strategy is compelling because it is simpler to implement correctly, but its disadvantage is that the intermediate data structures can be large and traversing them unnecessarily can be costly. In a system performing just-in-time compilation or run-time code generation, the costs associated with a two-pass compilation strategy can render it impractical. A one-pass optimizing transformation is compelling because it avoids generating intermediate data structures requiring further optimization, but its disadvantage is that the transformation is more difficult to implement.

The specification of a one-pass transformation is that it is extensionally equal to the composition of a non-optimizing transformation and an optimization pass. A one-pass transformation is not usually constructed this way, however, but is instead constructed as a separate artifact which must then be demonstrated to match its specification. Our approach is to construct one-pass transformations directly, as the fusion of passes via shortcut deforestation [GLJ93, TM95], thus maintaining the explicit connection to both the non-optimizing transformation and the optimization pass.

Shortcut deforestation relies on a simple but powerful program transformation rule known as cata/build fusion. This rule requires both the transformation and optimization passes to be expressed in a stylized form. The first pass, the transformation, must be written as a build, abstracted over the constructors of its input. The second pass, the optimization, must be a catamorphism, defined by compositional recursive descent over its input.

The non-optimizing CPS transformation generates terms that contain administrative redexes which can be optimized away by β-reduction. A one-pass CPS transformation [DF90, DF92] generates terms that do not contain administrative redexes, in a single pass, by contracting these redexes at transformation time. Thus β-reduction is the notion of optimization for the CPS transformation. The normalization function we will use for reduction of CPS terms, however, contracts all β-redexes, not just administrative redexes. In Section 1.6 we describe how to contract only the administrative redexes.

When using a metalanguage to express normalization in the object language, as we do here, the evaluation order of the metalanguage is usually important. However, because CPS terms are insensitive to evaluation order [Plo75], evaluation order is not a concern.

This work. We present a systematic method to construct a one-pass transformation, based on the fusion of a non-optimizing transformation with an optimization pass. We demonstrate the method by constructing new one-pass CPS transformations as the fusion of non-optimizing CPS transformations with a catamorphic normalization function.

The rest of the paper is organized as follows. First, we briefly review cata-morphisms, builds, and cata/build fusion in Section 1.2. Then, in Section 1.3 we restate Plotkin's call-by-value CPS transformation [Plo75] with build, and in Section 1.4 we restate a reduction-free normalization function for the untyped λ-calculus to use a catamorphism. We then present a new one-pass CPS transformation obtained by fusion, in Section 1.5. In Section 1.6 we describe how to modify the transformation to contract only the administrative redexes. We compare our new CPS transformation to the one-pass transformation of Danvy and Filinski [DF92] in Section 1.7. In Section 1.8 we repeat the method for Plotkin's call-by-name CPS transformation. We present related work and conclude in Section 1.9.

Prerequisites. The reader should be familiar with reduction in the λ-calculus, and the CPS transformation [Plo75]. Knowledge of functional programming, particularly catamorphisms (i.e., the higher-order function fold) [MFP91] is expected. We use a functional pseudocode that is similar to Haskell.

1.2 CATA/BUILD FUSION FOR λ-TERMS

The familiar datatype of λ-terms is defined by the following context-free grammar (assuming the metavariable x ranges over a set Ident of identifiers):

Term [contains as member] m :: = var x | lam x m | app m m

A catamorphism [GLJ93, MFP91, TM95] (or fold) over λ-terms captures a common pattern of recursion. It recurs on all subterms and replaces each of the constructors var, lam, and app in a λ-term with functions of the appropriate type. We use the combinator foldλ, with type [for all]A. (Ident->A)->(Ident ->A->A)->(A ->A->A)->Term->A, to construct a catamorphism over λ-terms:

[MATHEMATICAL EXPRESSION OMITTED]

We use the combinator buildλ to systematically construct λ-terms. It takes a polymorphic function f which uses arbitrary functions (of the appropriate types) instead of the λ-term constructors to transform an input into an output,...