Lambda Calculus

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 the fundamental operations. All other programming constructs differ in the way their evaluation strategies are implemented. Furthermore, its syntax can be further extended and simplified.

Contents

  1. Basic Definitions
  2. Lambda Reduction
  3. Building Blocks
This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.