Lambda calculus: Difference between revisions
imported>Christopher J. Reiss No edit summary |
imported>Christopher J. Reiss No edit summary |
||
| Line 3: | Line 3: | ||
In mathematical logic and computer science, the lambda calculus (also λ-calculus) is a formal system designed to investigate function definition, function application and recursion. Although it was originally intended as a mathematical formalism and predates the invention of the electronic computer, it can be seen as the world's first formalized programming language. The programming language LISP was created from the λ-calculus blue-print. | In mathematical logic and computer science, the lambda calculus (also λ-calculus) is a formal system designed to investigate function definition, function application and recursion. Although it was originally intended as a mathematical formalism and predates the invention of the electronic computer, it can be seen as the world's first formalized programming language. The programming language LISP was created from the λ-calculus blue-print. | ||
It was introduced by Alonzo Church and Stephen Cole Kleene in the 1930s as part of a larger effort to base the foundation of mathematics upon functions rather than sets (in the hopes of avoiding obstacles like Russell's Paradox). | |||
The lambda calculus can be thought of as an idealized, minimalistic programming language. It is a close cousin of the Turing machine, another minimalist abstraction capable of expressing any algorithm. The difference between the two is that the lambda calculus takes a functional view of algorithms, while the original Turing machine takes an imperative view. That is, a Turing machine maintains 'state' - a 'notebook' of symbols that can change from one instruction to the next. The imperative paradigm can be seen in programming languages like C or BASIC. By contrast, the lambda calculus is stateless, it deals exclusively with functions which accept and return data (including other functions), but produce no side effects in 'state' and do not make alterations to incoming data (immutability.) The functional paradigm can be seen in modern languages like Lisp, Scheme and Haskell. | The lambda calculus can be thought of as an idealized, minimalistic programming language. It is a close cousin of the Turing machine, another minimalist abstraction capable of expressing any algorithm. The difference between the two is that the lambda calculus takes a functional view of algorithms, while the original Turing machine takes an imperative view. That is, a Turing machine maintains 'state' - a 'notebook' of symbols that can change from one instruction to the next. The imperative paradigm can be seen in programming languages like C or BASIC. By contrast, the lambda calculus is stateless, it deals exclusively with functions which accept and return data (including other functions), but produce no side effects in 'state' and do not make alterations to incoming data (immutability.) The functional paradigm can be seen in modern languages like Lisp, Scheme and Haskell. | ||
The lambda calculus - and the paradigm of functional programming - is still influential, especially within the artificial intelligence community. | The lambda calculus - and the paradigm of functional programming - is still influential, especially within the artificial intelligence community. | ||
Revision as of 14:05, 19 February 2008
Lamda Calculus
In mathematical logic and computer science, the lambda calculus (also λ-calculus) is a formal system designed to investigate function definition, function application and recursion. Although it was originally intended as a mathematical formalism and predates the invention of the electronic computer, it can be seen as the world's first formalized programming language. The programming language LISP was created from the λ-calculus blue-print.
It was introduced by Alonzo Church and Stephen Cole Kleene in the 1930s as part of a larger effort to base the foundation of mathematics upon functions rather than sets (in the hopes of avoiding obstacles like Russell's Paradox).
The lambda calculus can be thought of as an idealized, minimalistic programming language. It is a close cousin of the Turing machine, another minimalist abstraction capable of expressing any algorithm. The difference between the two is that the lambda calculus takes a functional view of algorithms, while the original Turing machine takes an imperative view. That is, a Turing machine maintains 'state' - a 'notebook' of symbols that can change from one instruction to the next. The imperative paradigm can be seen in programming languages like C or BASIC. By contrast, the lambda calculus is stateless, it deals exclusively with functions which accept and return data (including other functions), but produce no side effects in 'state' and do not make alterations to incoming data (immutability.) The functional paradigm can be seen in modern languages like Lisp, Scheme and Haskell.
The lambda calculus - and the paradigm of functional programming - is still influential, especially within the artificial intelligence community.