COMPILING LAMBDA CALCULUS

Lulu Press, 2016 - 167 pages - 12 figures - 6" x 9" format - CC0 code

Order a PDF copy at Lulu.com
Order a paperback copy at Lulu.com
Get the source code from the book
Read a few pages (PDF)
Errata (PDF)

This book introduces the theory and interpretation of lambda calculus.

Some questions answered in this book:

The text starts by describing lambda calculus as a formal term rewriting system and outlining some simple applications, like Church numerals, propositional functions, ordered pairs, and recursion via the fixed point combinator.

The focus is then shifted toward interpretation of lambda calculus by a computer. This part of the book defines and implements a tiny subset of the Scheme programming language and then extends it iteratively until it can be used as the basis for a real-world implementation.

This part covers two models of interpretation as well as the transformation of lambda calculus to abstract machine code and portable C code.

The final part of the book explores a language that resembles lambda calculus more closely, by supporting partial function application. Even here, a full compiler for the language is provided.

The compilers and languages introduced in the book are implemented in Scheme, with runtime support in C. All code in the book is provided under the Creative Commons Zero license (a.k.a. Public Domain).

Intended audience: implementors of Scheme, LISP, and other functional languages, everyone interested in the theoretical background of LISPy languages.


contact