preface.src

% $Date: 91/09/10 14:48:31 $
% $Revision: 1.5 $
% (c) 1991 Simon Peyton Jones & David Lester.
\chapter*{Preface}
\addcontentsline{toc}{chapter}{Preface}

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 {\em
executed} as well as {\em 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.

\section*{Overview of the book}

The principal content of the book is a series of implementations of
a small functional language called the {\em 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~\ref{sect:language}, in which we also develop a parser
and pretty-printer for the Core language.

Appendix~\ref{sect:core-progs}
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.
\begin{itemize}
\item
Chapter~\ref{sect:template} describes the most direct implementation, based
on {\em template instantiation}.

\item
Chapter~\ref{sect:g-machine} introduces the {\em G-machine}, and
shows how to compile the program to
sequences of instructions (G-code) which can be further translated
to machine code.

\item
Chapter~\ref{sect:tim} repeats the same exercise for a different abstract
machine, the {\em 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~\ref{sect:tim} therefore
contains a rather more detailed development of the TIM's evaluation
model than that given for the G-machine.

\item
Finally, Chapter~\ref{sect:par-g-machine} adds a new dimension by showing how
to compile functional programs for a {\em parallel G-machine}.
\end{itemize}

For each of these implementations we discuss two main parts, the {\em compiler}
and the {\em 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 {\em state transition system} so that
there is a very clear connection between the machine interpreter and
a `real' implementation.
Figure~\ref{fig:overview} summarises the structure of our implementations.
\begin{figure*}
\input{overview.tex}
\caption{Overview of the implementations}
\label{fig:overview}
\end{figure*}

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 {\em 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~\ref{sect:lambda-lift} we develop
a suitable lambda lifter.
This chapter is more than just a re-presentation of standard material.
{\em Full laziness} is a property of functional programs which had previously
been seen as inseparable from lambda lifting.  In Chapter~\ref{sect:lambda-lift}
we show that they are in fact quite distinct, and show how to implement
full laziness in a separate pass from lambda lifting.

Throughout the book we use a number of utility functions and data types
which are defined in Appendix~\ref{sect:utils}.

Some sections and exercises
are a little more advanced, and can be omitted without
major loss.  They are identified with a dagger, thus: \advanced.

\section*{The prototyping language}

The question arises of what language to use for writing our implementations.
We have chosen to use an existing functional language,
Miranda%
\footnote{Miranda is a trade mark of Research Software Ltd.}.
One of the major uses of functional languages is for rapid
prototyping, because they allow us to express the fundamental aspects of
the prototype without getting bogged down in administrative detail.
We hope that this book can serve as a large example to substantiate
this claim.  In addition, working through this book should provide
useful experience of writing substantial functional programs.

This book is not an introduction to functional programming.
We assume that you have done some programming in a functional language
already.
(Suitable introductions to functional programming include \cite{BirdWadler}
and \cite{Hoyler}.)
Nevertheless, the programs developed in this book are quite substantial,
and we hope they will serve as a role model, to
stretch and develop your ability to write clear,
modular functional programs.

Miranda code is written in typewriter fount
using the `inverse comment convention'.
For example, here is a definition of a function which takes the length of
a list:

> length [] = 0
> length (x:xs) = 1 + length xs

The @>@ mark in the left margin indicates that this is a line of
executable Miranda code.
Not only does this distinguish Miranda code from Core-language programs
(which are also written in typewriter fount), but Miranda itself recognises
this convention, so the text of each chapter of
this book {\em is} executable Miranda code!
Indeed, it has all been executed.
(Actually, a small amount of pre-processing is required before feeding the
text to Miranda, because we
sometimes write several versions of the same function, as we refine
the implementation, and Miranda objects to such multiple definitions.
The pre-processing is simply a selection process to pick the particular
version we are interested in.)

The text contains {\em all} the code required for the initial version of
each implementation.
Occasionally, this becomes rather tiresome, because we have to present
chunks of code which are not very interesting.  Such chunks could have been
omitted from the printed text (though not from the executable version), but
we have chosen to include them, so that you can always find a definition for
every function. (The index contains an entry for every
Miranda function definition.)

Like most functional languages, Miranda comes with a collection of
pre-declared functions, which are automatically in scope.
We make use of these throughout the text, referring to them as
{\em standard functions}.
You can find details of all the standard functions
in Miranda's online manual.

\subsection*{What this book does not cover}

We focus exclusively in this book on the `back end' of functional-language
compilers.  We make no attempt to discuss how to translate programs written
in a fully fledged functional language, such as Miranda, into the Core language,
or how to type-check such programs.

The development throughout is informal.  It would be nice to give a formal
proof of the equivalence between the meaning of a Core program and
its implementation, but this is quite a hard task.  Indeed, the only
full proof of such an equivalence which we know of is \cite{Lester88}.

\subsection*{Relationship to {\it The implementation of functional
programming languages}}

An earlier book by one of us, \cite{PJBook}, covers similar material to this
one, but in a less practically oriented style.
Our intention is that a student should be able to follow a course
on functional-language implementations using the present book alone, without
reference to the other.

The scope of this book is somewhat more modest, corresponding to
Parts 2 and 3 of \cite{PJBook}.  Part 1 of the latter,
which discusses how a high-level
functional language can be translated into a core language, is not
covered here at all.

\subsection*{Getting the machine-readable sources}
\input{getting.tex}

\subsection*{Errors}

We would greatly appreciate your help in eliminating mistakes in the
text.  If you uncover any errors, please contact one of us at the addresses
given below.

\theendnotes


\chapter*{Acknowledgements}

We would like to thank Professor Rajaraman from the Indian Institute
of Science in Bangalore for the invitation to give the course on which
this book is based, and the British Council for sponsoring the visit.

A number of people have made helpful comments on drafts of this
material.  We thank them very much, especially Guy Argo, Cordelia Hall,
Denis Howe, John Keane, Nick North, David Wakeling and an anonymous reviewer.

\begin{flushleft}
\begin{tabular*}{\textwidth}{@@{}l@@{\extracolsep{\fill}}l@@{}}
Simon L. Peyton Jones           & David R. Lester \\
Department of Computing Science & Department of Computer Science \\
University of Glasgow G12 8QQ   & University of Manchester M13 9PL \\
email: \mbox{\tt simonpj@@dcs.glasgow.ac.uk}
			& email: \mbox{\tt dlester@@cs.manchester.ac.uk}
\end{tabular*}
\end{flushleft}