The Glasgow Haskell compiler: a technical overview

Simon L Peyton Jones Cordy Hall Kevin Hammond Will Partain

Phil Wadler

Department of Computing Science, University of Glasgow, G12 8QQ.

email: [email protected]

December 22, 1992

This paper appears in the Proceedings of the UK Joint Framework for Information Technology (JFIT) Technical Conference, Keele, 1993.

Abstract

We give an overview of the Glasgow Haskell compiler, focusing especially on way in which we have been able to exploit the rich theory of functional languages to give very practical improvements in the compiler.

The compiler is portable, modular, generates good code, and is freely available.

1 Introduction

Computer Science is both a scientific and an engineering discipline. As a scientific discipline, it seeks to establish generic principles and theories that can be used to explain or underpin a variety of particular applications. As an engineering discipline, it constructs substantial artefacts of software and hardware, sees where they fail and where they work, and develops new theory to underpin areas that are inadequately supported. (Milner [1991] eloquently argues for this dual approach in Computer Science.)

Functional programming is a research area that offers an unusually close interplay between these two aspects (Peyton Jones [1992b]). Theory often has immediate practical application, and practice often leads directly to new demands on theory. This paper describes our experience of building a substantial new compiler for the purely functional language Haskell. We discuss our motivations, major design decisions and achievements, paying particular attention to the interaction of theory and practice.

Scaling prototypes up into large real" systems appears to be less valued in the academic community than small systems that demonstrate concepts, being sometimes being dismissed as just development work". Nevertheless, we believe that many research problems can only be exposed during the act of constructing large and complex

systems. We hope that this paper serves to substantiate this point.

The compiler work described in this paper is one of the two strands of the SERC-funded GRASP project. The other concerns parallel functional programming on the GRIP multiprocessor, but space precludes coverage of both.

2 Goals

Haskell is a purely functional, non-strict language designed by an international group of researchers (Hudak et al. [1992]). It has now become a de facto standard for the non-strict (or lazy) functional programming community, with at least three compilers available.

Our goals in writing a new compiler were these:

ffl To make freely available a robust and portable compiler for Haskell that generates good quality code. This goal is more easily stated than achieved. Haskell is a rather large language, incorporating: a rich syntax; a new type system that supports systematic overloading using so-called type classes (Wadler & Blott [1989]); a wide variety of built-in data types including arbitrary-precision integers, rationals, and arrays; a module system; and an input/output system.

ffl To provide a modular foundation that other researchers can extend and develop. In our experience, researchers are often unable to evaluate their ideas because the sheer effort of building the framework required is too great. We have tried very hard to build our compiler in a well-documented and modular way, so that others will find it (relatively) easy to modify.

ffl To learn what real programs do. The intuition of an implementor is a notoriously poor basis for taking critical design decisions. The RISC revolution in computer architecture was based partly on the simple idea of measuring what real programs actually do most often, and implementing those operations very