Implementing functional languages: a tutorial
~
SL Peyton Jones and DR Lester
In the Spring of 1992 Prentice Hall will publish the above book, as
part of their International Series in Computer Science (ed Hoare).
The book gives a practical approach to understanding implementations
of non-strict functional languages using lazy graph reduction.
The main unusual feature of the book is that the text of each chapter
is itself a directly-executable Miranda(TM) program, constituting a
minimal but complete compiler and interpreter for a particular
abstract machine. The complete source code for the book, and a
Tutor's Guide containing solutions to the exercises, is available in
machine-readable form by network file transfer (FTP). [Details below.]
A second feature is a substantial chapter on the Three Instruction
Machine (TIM). Most functional language implementors know something
of TIM, and there have been quite a few research papers about variants
of it, but I believe this is the first published unified treatment,
covering arithmetic, data structures, let(rec) expressions and so on,
in a single framework.
Written to allow the reader to modify, extend and experiment with the
implementations provided in the text, we hope that this book will help
to make a course on functional-langauge implementation "come alive".
The main topics covered are:
* A "core" language, including a parser and pretty printer.
* A template-instantiation implementation
* The G-machine
* The three instruction machine (TIM)
* A parallel G-machine
* Lambda lifting and full laziness
This book is *not* a second edition of Simon's earlier book "The
implementation of functional programming langauges" (Prentice Hall
1987), though it is in the same series. The new book differs in the
following ways:
* it is intended as a course text;
* it has executable examples of everything discussed (including
a pointer-reversing garbage collector...);
* it has a substantial chapter on TIM, which was not covered
at all in the earlier book;
* the treatment of full laziness is new, based on
the ideas in our paper in Software P&E (May 1991)
Getting the sources
~~~
You can get all the source code for this book, by network file
transfer (FTP) from the several sites.
These sources contain the complete source text for the book, both
executable and typesettable, so you can print yourself a copy (about
300 pages). Needless to say, we'd won't get any of those lovely
royalties if everyone uses their laser-printer rather than their
bookshop; so please buy a copy too when it is in print! And of
course, please don't reproduce lots of copies. Meanwhile, we're happy
for you to print individual copies.
You need only get the single file
pjlester-n.m.tar.Z
where n.m is the current version number of the book. There is always
only one such file, but the n.m may vary as we correct errors and
otherwise improve the material. [The current release is 1.2]
Once you have got the file, run the command
zcat pjlester-n.m.tar.Z | tar xf -
and then read or print the README file, and the DVI file installation.dvi.
If you don't have zcat, do the following instead:
uncompress pjlester-n.m.tar.Z
cat pjlester-n.m.tar | tar xf -
The sites where the sources are held are as follows:
Site Host name Host address Directory
~~~
Glasgow ftp.dcs.glasgow.ac.uk@ 130.209.240.50 pub/pj-lester-book
Yale nebula.cs.yale.edu@ 128.36.13.1pub/pj-lester-book
Chalmers animal.cs.chalmers.se@ 129.16.2.27pub/pj-lester-book
Log in as "anonymous", and use your email address as password.
Here is a sample Internet FTP session:
% ftp nebula.cs.yale.edu
Connected to NEBULA.SYSTEMSZ.CS.YALE.EDU.
220 nebula FTP server (SunOS 4.0) ready.
Name (nebula.cs.yale.edu:guestftp): anonymous
331 Guest login ok, send ident as password.
Password: [EMAIL PROTECTED]
230 Guest login ok, access restrictions apply.
ftp> type binary
200 Type set to I.
ftp> cd pub/funlit
250 CWD command successful.
ftp> get pjlester-1.2.tar.Z
ftp> bye
Within the UK, you may get the above file by anonymous UK NIFTP from
@uk.ac.glasgow.dcs@ (binary mode; user: @guest@; password: your e-mail address);
request:
/pj-lester-book/filename
A typical command you might use on at least some Unix machines is:
cpf -b '[EMAIL PROTECTED]'
pjlester-1.2.tar.Z
(TM) Miranda is a trade mark of Research Software Ltd
