Compiling Lambda Calculus

Compiling Lambda CalculusThis book introduces the reader to the theory and interpretation of lambda calculus. It first describes lambda calculus as a formal term rewriting system and outlines some simple applications, like Church numerals, the Y combinator, etc. The next 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

This book introduces the reader to the theory and interpretation of lambda calculus.

It first describes lambda calculus as a formal term rewriting system and outlines some simple applications, like Church numerals, the Y combinator, etc.

The next 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.

The compilers and languages introduced in the book are implemented in Scheme and provided under the Creative Commons Zero license (a.k.a. Public Domain).

Intended audience: compiler writers and everyone interested in the theoretical background of LISPy languages.