Implementing functional languages: a tutorial

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.

• Chapter 2 describes the most direct implementation, based on template instantiation.
• Chapter 3 introduces the G-machine, and shows how to compile the program to sequences of instructions (G-code) which can be further translated to machine code.
• Chapter 4 repeats the same exercise for a different abstract machine, the Three Instruction Machine (TIM), whose evaluation model is very different from that of the G-machine. The TIM was developed more recently than the G-machine, so there is much less other literature about it. Chapter 4 therefore contains a rather more detailed development of the TIM’s evaluation model than that given for the G-machine.
• Finally, Chapter 5 adds a new dimension by showing how to compile functional programs for a parallel G-machine.

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).

• Page 128, second to last paragraph of section 3.7, first sentence. “addis” should be “is a”.
• Page 134, the code for i’. The “n” under the big brace symbol should say “n pairs”.
• Page 135. Equation 3.36 should have “NConstr”, not “Constr”.
• Page 230, second paragraph. “There one final gloss…” should be “There is one final gloss…”.
• Page 278, the definition of nfib. Replace “n==0” by “n<=1”.

Now, alas, out of print. However the full text of the book is available above. You can order a nicely-bound copy from http://www.cafepress.com/haskell_books. Thanks to John Meacham for setting this up.

There is also a tutor’s guide available.