Compiling Laziness Using Projection Types

Clem Baker-Finch. University of Canberra Research Report, 1999, R 99/113, School of Computing.

Abstract

Strictness analysis is accepted as an important tool for the efficient implementation of lazy functional languages. However, the analyses are usually first-order and the optimisations that follow may be ad hoc. Using projections to represent static properties of programs is appealing because they naturally describe component-wise demand on data structures and can handle latent demands such as head-strictness. However their extension to higher-order functions is problematic.

This paper introduces projection types, a notation for expressing static information about higher-order functions that combines the dual aspects of demand on arguments and behaviour of functional arguments. A strictness analysis using projection types is presented and later extended to an optimisation scheme that translates expressions into a language with explicit closure construction and evaluation operations. An important advantage of this approach is that the optimisations are verified correctness-preserving transformations. This paper extends and complements the results of Ross Paterson, ``Compiling Laziness with Projections'' presented at the 3rd Static Analysis Symposium, 1996.

BibTeX, PostScript, gzipped PostScript