Terms and Conditions:
Simon Peyton Jones wrote:My 1987 book is now out of print, but it is now available online in its entirety.
This book is about implementing functional programming languages using lazy graph reduction
, and it divides into three parts.
The first part describes how to translate a high-level functional language into an intermediate language, called the lambda calculus
, including detailed coverage of pattern-matching and type-checking. The second part begins with a simple implementation of the lambda calculus, based on graph reduction, and then develops a number of refinements and alternatives, such as supercombinators, full laziness and SK combinators. Finally, the third part describes the G-machine, a sophisticated implementation of graph reduction, which provides a dramatic increase in performance over the implementations described earlier.
One of the agreed advantages of functional languages is their semantic simplicity. This simplicity has considerable payoffs in the book. This book repeatedly able to make semi-formal arguments for the correctness of the compilation algorithms, and the whole book has a distinctly mathematical flavor - an unusual feature in a book about implementations.
Most of the material to be presented has appeared in the published literature in some form (though some has not), but mainly in the form of conference proceedings and isolated papers. References to this work appear at the end of each chapter.
This book is about implementations, not languages, it will make no attempt to extol the virtues of functional languages or the functional programming style. Instead this book will assume that the reader is familiar with functional programming; those without this familiarity may find it heavy going.