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