Compilation by transformation for non-strict functional languages

In this thesis we present and analyse a set of automatic source-to-source program transformations that are suitable for incorporation in optimising compilers for lazy functional languages.  These transformations improve the quality of code in many different respects, such as execution time and memory usage.

The transformations presented are divided into two sets: global transformations, which are performed once (or perhaps twice) during compilation; and a set of local transformations with are performed before and after each of the global transformations, so that they can simplify the code before applying the global transformations, and take advantage of them afterwards.

Many of the local transformations are simple, well known, and do not have major effects on their own.  They become important as they interact with each other and with global transformations, sometimes in non-obvious ways.  We present how and why they improve the code, and perform extensive experiments with real application programs.

We describe four global transformations, two of which have not been used in any lazy functional compiler we know of: the static argument transformations and let-floating transformations.  The other two are well known for lazy functional languages, but no major studies of their effects have been performed: full laziness and lambda lifting.  We also study and measure the effects of different inlining strategies.

We also present a Cost Semantics as a way to reason about the effects of program transformations in lazy functional languages.

[I have listed myself as an author only so that this thesis appears on my home page; it is Andre’s thesis!]