Trends in Functional Programming Volume 6

Marko Van Eekelen

• Publisher: Intellect Books
• Year: 2005
• Print ISBN: 9781841501765
• eBook ISBN: 9781841509907
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Science General
• Index: Computer Science

This book presents latest research developments in the area of functional programming. The contributions in this volume cover a wide range of topics from theory, formal aspects of functional programming, transformational and generic programming to type checking and designing new classes of data types.

Not all papers in this book belong to the category of research papers. Also, the categories of project description (at the start of a project) and project evaluation (at the end of a project) papers are represented.

Particular trends in this volume are:

• software engineering techniques such as metrics and refactoring for high-level programming languages;
• generation techniques for data type elements as well as for lambda expressions; 
• analysis techniques for resource consumption with the use of high-level programming languages for embedded systems;
• widening and strengthening of the theoretical foundations.

 

Chapter 1

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

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

A.(Ident→A)→(Ident→A→A)→(A→A→A)→Term→A, to construct a catamorphism over λ-terms:

fold_λ vr lm ap (var x) = vr x

fold_λ vr lm ap (lam x m) = lm x (fold_λ vr lm ap m)

fold_λ vr lm ap (app m₀ m₁) = ap (fold_λ vr lm ap m₀) (fold_λ vr lm ap m₁)

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, and then applies f to the λ-term constructors, producing a function that transforms an input into a λ-term. It has type

A.(

B.(Ident →B) → (Ident →B →B) → (B → B →B) →A →B) →A →Term:

build_λ f = f var lam app

Cata/build fusion [GLJ93, TM95] is a simple program transformation that fuses a catamorphism with a function that produces its output using build. For λ-terms, cata/build fusion consists of the rewrite rule:

(fold_λ vr lm ap)

(build_λ f)

f vr lm ap

The fused function produces its output without constructing intermediate data structures.

1.3 THE CALL-BY-VALUE CPS TRANSFORMATION USING BUILD

The non-optimizing call-by-value CPS transformation [Plo75] is given in Figure 1.1. We assume the ability to choose fresh identifiers when needed; the identifiers k, v₀, and v₁ are chosen fresh.

Fu...

Table of contents

• Cover
• Title page
• Copyright
• Contents
• 1. Best student Paper: A New Approach to One-Pass Transformations
• 2. A Static Checker for Safe Pattern Matching in Haskell
• 3. Software Metrics: Measuring Haskell
• 4. Type-Specialized Serialization with Sharing
• 5. Logical Relations for Call-by-value Delimited Continuations
• 6. Epigram Reloaded: A Standalone Typechecker for ETT
• 7. Formalisation of Haskell Refactorings
• 8. Systematic Search for Lambda Expressions
• 9. First-Class Open and Closed Code Fragments
• 10. Comonadic Functional Attribute Evaluation
• 11. Generic Generation of the Elements of Data Types
• 12. Extensible Record with Scoped Labels
• 13. Project Start Paper: The Embounded Project
• 14. Project Evaluation Paper: Mobile Resource Guarantees