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:

- What are lambda calculi?
- What is alpha-, beta-, eta- conversion?
- What are Church numerals and pairs?
- What are fixed points and recursion?
- How to interpret and compile Scheme?
- How to interpret and compile lambda calculus?
- How to represent abstractions efficiently?

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.