Lambda Calculus

From Wikibooks, open books for an open world
Jump to: navigation, search

Lambda Calculus is a formal language which facilitates the definition of the notion of a computable function. The calculus was first developed by Alonzo Church in 1936 and is closely related to Alan Turing's reflections on the nature of computing. In general the class of functions definable by the calculus is equivalent to those computable by a Turing machine. The calculus has been influential in computer science and linguistics as well as in mathematics.

As well as the theoretical interest of the calculus, various attempts have been made to implement it as a practical computing system - each more or less directly. Among these languages Lisp, Scheme and Haskell are all in some way related to lambda calculus.

The two central language constructs of the calculus are abstraction and application, which are its fundamental operations. All other programming constructs are derived from these basic notions.

Contents[edit]

  1. Basic Definitions
  2. Lambda Reduction
  3. Building Blocks