Transforming Lazy Functions using Comportment Properties

Ross Paterson. In PLILP, Southampton, UK, September 1997, LNCS vol. 1292, pages 111-125.

Abstract

This paper develops a source-to-source transformation that seeks to delay the creation of thunks as much as possible, often eliminating them altogether. The generated programs make use of simpler representations, including types in which all expressions terminate. The transformation is guided by an abstract interpretation, with the abstract values of basic comportment analysis concretized as representation types related by injections.

The transformation of functions is polyvariant, with functions mapped to natural transformations. This leads to a clean treatment of higher order functions.

Formats

gzipped PostScript, gzipped DVI, BibTeX.

Background

• Parametricity and Unboxing with Unpointed Types, John Launchbury and Ross Paterson. In European Symposium on Programming, Linköping, Sweden, April 1996, LNCS vol. 1058, pages 204-218.

  Introduces the source language used in this paper. Lifting (corresponding to unboxed values) is explicit in the language, and thus amenable to a source-to-source transformation.

• Higher-order Abstract Interpretation (and Application to Comportment Analysis Generalizing Strictness, Termination, Projection and PER Analysis of Functional Languages), Patrick Cousotand Radhia Cousot. Invited paper, in International Conference on Computer Languages. Toulouse, France, pages 95-112.