Compiling Laziness using Projections

Ross Paterson. In Static Analysis Symposium, Aachen, Germany, September 1996, LNCS vol. 1145, pages 255-269.

Abstract

Projection-based strictness analysis is a powerful technique, able to cope with non-flat domains and latent demand. By analysing the projections as embedding-projection pairs, we develop an algorithm to translate lazy functions into a strict functional language with explicit closures. The translated functions typically operate on simpler types than the originals, in particular types containing fewer liftings, which correspond to the operational notion of closures. Like the analysis on which it is based, our algorithm is restricted to first-order functions.

Formats

gzipped PostScript, gzipped DVI, BibTeX.

Correction

In the bottom line of equation (19), `v' should be replaced by `let y = x in v'.

Background

• Projections for Strictness Analysis, Philip Wadler and John Hughes. In 3rd International Conference on Functional Programming Languages and Computer Architecture, Portland, Oregon, September 1987, pages 385-407.

  The paper that introduced projection-based strictness analysis, and still the best introduction.

• Implementing Projection-based Strictness Analysis, Ryszard Kubiak, John Hughes and John Launchbury. In 1991 Glasgow Workshop on Functional Programming, Springer Workshops in Computing, pages 207-224,

  A report on a prototype implementation of the analysis, addressing a number of important issues rarely discussed elsewhere.