Lambda Calculus

The Lambda Calculus

Origin

The Lambda Calculus has been created by the American logician Alonzo Church in the 1930's and is documented in his works published in 1941 under the title `The Calculi of Lambda Conversion'.

Alonzo Church wanted to formulate a mathematical logical system and had no intent to create a programming language. The intrinsic relationship of his system to programming was discovered much later in a time in which programming of computers became an issue.

Definition

Definition of Lambda Calculus

Syntax of Lambda Expressions

The syntax of lambda expressions is defined as follows:
Syntax of a Lambda Expression
The Lambda Calculus therefore includes three diffenrent types of lambda expressions:
  • variables (referencing lambda expressions)
  • lambda abstractions (defining functions)
  • applications (invoking functions, performing a synthesis of two lambda expressions)

Remark: The parentheses in the syntax of an application are not mandatory. This results from the law of associativity for applications introduced below.

More Details

For a detailed introduction to the Calculi of Lambda Conversion see Appendix B of the online version of the A++ book. For the reader's convenience a PDF-Version of this article is also available at this address.

Literature

As a mathematical logical system the Lambda Calculus is covered in detail in [Bar81] and less comprehensively but in a more readable form in [Sto81]. A clear account of the historical origins and basic properties of the lambda calculus is presented by Curry and Fey in their book [CF58]. This view is taken from [Jon87] page 23.

From the programmer's point of view the Lambda Calculus is adressed in [Jon87], [Kam90], [Cha96].



Home | ARS Based Programming | A++ Introduction | Online Documentation | Publication | Interpreter | Download
| Contact | Links
© 1999-2005 Georg P. Loczewski. All Rights Reserved.

The documentation of this site is released under the terms of the GNU Free Documentation License. More details on the copyright license are given here.

domain access counterGeorg P. Loczewski 2004-12-15