History of Computers - The Lambda Calculus
The lambda calculus is a description of all computable functions. Essentially, it consists of three types of data: the expression, the function, and the application. An expression consists of a name, a function, or an application; a function consists of a name and a function, and an application consists of two functions[1].
Contents
Overview
Alonzo Church (whose students include Alan Turing, known as the "father of computing") was attempting to find the foundations of mathematics when he created the lambda calculus[2]. In essence, the lambda calculus is a system for defining functions. The name "lambda calculus" is consistent with the fact that, as arithmetic deals with changes in numbers and algebra deals with changes in variables, calculus deals with changes in functions.
Definition
The lambda calculus can be defined formally (in Backus-Naur Form) thusly[1]:
<expression> := <name> | <function> | <application> <function> := λ<name>.<expression> <application> := <function><function>
However, for the purposes of this article, most code will be written in Scheme, a dialect of Lisp centered around the lambda calculus. The syntax of Scheme is fairly simple:
(<function-name> <arg-1> ... <arg-n>)
In Scheme, the function (defun (<function-name> <arg-1> ... <arg-n>) <function-body>) is used to define a named function, and (lambda (<arg-1> ... <arg-n>) <function-body>) is used to create an anonymous function.
Numbers in the Lambda Calculus
The most common implementation of natural numbers in the lambda calculus is known as the Church numeral[1]. These are defined as such:
(defun (0 f x) x) (defun (1 f x) (f x)) (defun (2 f x) (f (f x))) ...
Currying
The definition of the lambda calculus only allows for one argument to a function. A technique to use more than one argument (known as currying, after Haskell Curry) can be defined as such[2]:
λx.λy.<function-body>
Significance
The lambda calculus was the first definition of computability, and has led to many other theories of computation[2]. In addition, the lambda calculus greatly influenced the functional programming paradigm, which states that a program should be an application of mathematical functions. However, functional programming is largely limited to academics. The lambda calculus has also influenced more practical languages such as C++ (which has a lambda construct in its new C++0x standard) and JavaScript (which has permits anonymous functions through syntax similar to the definition of a regular function). It has also influenced the popular textbook Structure and Interpretation of Computer Programs, whose cover features a lambda in a prominent position.
