Implementing functional languages: a tutorial

Simon Peyton Jones and David Lester. Published by Prentice Hall, 1992.

Now, alas, out of print. However the full text of the book is available here:

Abstract

This book gives a practical approach to understanding implementations of non-strict functional languages using lazy graph reduction. The book is intended to be a source of practical labwork material, to help make functional-language implementations `come alive', by helping the reader to develop, modify and experiment with some non-trivial compilers.

The unusual aspect of the book is that it is meant to be executed as well as read. Rather than merely presenting an abstract description of each implementation technique, we present the code for a complete working prototype of each major method, and then work through a series of improvements to it. All of the code is available in machine-readable form.

Overview of the book

The principal content of the book is a series of implementations of a small functional language called the Core language. The Core language is designed to be as small as possible, so that it is easy to implement, but still rich enough to allow modern non-strict functional languages to be translated into it without losing efficiency. It is described in detail in Chapter 1, in which we also develop a parser and pretty-printer for the Core language.

Appendix B contains a selection of Core-language programs for use as test programs thoughout the book.

The main body of the book consists of four distinct implementations of the Core language.

For each of these implementations we discuss two main parts, the compiler and the machine interpreter. The compiler takes a Core-language program and translates it into a form suitable for execution by the machine interpreter.

The machine interpreter simulates the execution of the compiled program. In each case the interpreter is modelled as a state transition system so that there is a very clear connection between the machine interpreter and a `real' implementation.

One important way in which the Core language is restrictive is in its lack of local function definitions. There is a well-known transformation, called lambda lifting, which turns local function definitions into global ones, thus enabling local function definitions to be written freely and transformed out later. In Chapter 6 we develop a suitable lambda lifter. This chapter is more than just a re-presentation of standard material. Full laziness is a property of functional programs which had previously been seen as inseparable from lambda lifting. In Chapter 6 we show that they are in fact quite distinct, and show how to implement full laziness in a separate pass from lambda lifting.

Typographical errors

Here are some typographical errors, spotted by various readers. Page numbers refer to the online versions (which differ from the printed version).
Simon Peyton Jones, simonpj@microsoft.com