A modular fully-lazy lambda lifter in Haskell

Simon L Peyton Jones
Department of Computing Science, University of Glasgow, G12 8QQ

David Lester
Department of Computer Science, University of Manchester, M13 9PL

June 15, 1995

Abstract

An important step in many compilers for functional languages is lambda lifting. In his thesis, Hughes showed that by doing lambda lifting in a particular way, a useful property called full laziness can be preserved (Hughes [1983]). Full laziness has been seen as intertwined with lambda lifting ever since.

We show that, on the contrary, full laziness can be regarded as a completely separate process to lambda lifting, thus making it easy to use different lambda lifters following a full-laziness transformation, or to use the full-laziness transformation in compilers which do not require lambda lifting.
On the way, we present the complete code for our modular fully-lazy lambda lifter, written in the Haskell functional programming language.
This paper appears in Software Practice and Experience 21(5), May 1991.

1 Introduction

Lambda lifting and full laziness are part of the folk lore of functional programming, yet the few published descriptions of fully-lazy lambda lifting have been either informal or hard to understand, with the notable exception of Bird (Bird [1987]). Our treatment differs from earlier work in the following ways:

ffl The main technical contribution is to show how full laziness can be separated from lambda lifting, so that the two transformations can be carried out independently. This makes each transformation easier to understand and improves the modularity of the compiler.

ffl Our treatment deals with a language including let- and letrec-expressions. Not only is this essential for efficient compilation in the later stages of most compilers, but we also show that eliminating let(rec) expressions, by translating them into lambda abstractions, loses full laziness. To our knowledge, this has not previously been realised.

ffl We show how to decompose each of the transformations further into a composition of simple steps, each of which is very easy to program, thus further improving modularity.