Unboxed values as first class citizens in a non-strict functional

language?

Simon L Peyton Jones and John Launchbury
Department of Computing Science, University of Glasgow G12 8QQ
fsimonpj, [email protected]

July 26, 1991

Abstract

The code compiled from a non-strict functional program usually manipulates heapallocated boxed numbers. Compilers for such languages often go to considerable trouble to optimise operations on boxed numbers into simpler operations on their unboxed forms. These optimisations are usually handled in an ad hoc manner in the code generator, because earlier phases of the compiler have no way to talk about unboxed values.

We present a new approach, which makes unboxed values into (nearly) first-class citizens. The language, including its type system, is extended to handle unboxed values. The optimisation of boxing and unboxing operations can now be reinterpreted as a set of correctness-preserving program transformations. Indeed the particular transformations required are ones which a compiler would want to implement anyway. The compiler becomes both simpler and more modular.

Two other benefits accrue. Firstly, the results of strictness analysis can be exploited within the same uniform transformational framework. Secondly, new algebraic data types with unboxed components can be declared. Values of these types can be manipulated much more efficiently than the corresponding boxed versions.
Both a static and a dynamic semantics are given for the augmented language. The denotational dynamic semantics is notable for its use of unpointed domains.

1 Introduction

Most compilers have a phase during which they attempt to optimise the program by applying correctness-preserving transformations to it. Constant folding is a particular example of this sort of transformation; procedure inlining is another.

Functional languages are especially amenable to such transformation because of their simple semantics. Non-strict functional languages are nicest of all, because -reduction (sometimes called unfolding in a transformational context) is always valid; in a strict language it is only valid if the body of the function being unfolded is guaranteed to evaluate the argument.

?This paper appears in the Proceedings of the 1991 Conference on Functional Programming Languages and Computer Architecture, Cambridge, Sept 1991.