 |
|
|
Lambda calculus - Lambda calculus and programming languages | A Wisdom Archive on Lambda calculus - Lambda calculus and programming languages | | Lambda calculus - Lambda calculus and programming languages A selection of articles related to Lambda calculus - Lambda calculus and programming languages | |
|
|
More material related to Lambda Calculus can be found here:
|
|
|
| | |
Lambda calculus, Lambda calculus - Arithmetic in lambda calculus, Lambda calculus - Computable functions and lambda calculus, Lambda calculus - Formal definition, Lambda calculus - History, Lambda calculus - Informal description, Lambda calculus - Lambda calculus and programming languages, Lambda calculus - Logic and predicates, Lambda calculus - Recursion, Lambda calculus - Undecidability of equivalence, Lambda calculus - α-conversion, Lambda calculus - β-reduction, Lambda calculus - η-conversion, SKI combinator calculus, H.P. Barendregt's Lambda cube, Jean-Yves Girard's System F, Thierry Coquand's calculus of constructions, Typed lambda calculus, Curry-Howard isomorphism, Anonymous recursion, Unlambda
| | |
|
ARTICLES RELATED TO Lambda calculus - Lambda calculus and programming languages | | | |  Lambda calculus - Lambda calculus and programming languages: Encyclopedia II - Lambda calculus - Lambda calculus and programming languagesMost programming languages are equivalent to the lambda calculus extended with some additional programming language constructs. The classical work where this viewpoint was put forward was Peter Landin's "A Correspondence between ALGOL 60 and Church's Lambda-notation", published in CACM in 1965. The key point is that the lambda calculus expresses the kind of procedural abstraction and application useful for any programming language. Prominently, functional programming languages are basically the lambda calculus with some constants and datatyp ...
See also:Lambda calculus, Lambda calculus - History, Lambda calculus - Informal description, Lambda calculus - Formal definition, Lambda calculus - α-conversion, Lambda calculus - β-reduction, Lambda calculus - η-conversion, Lambda calculus - Arithmetic in lambda calculus, Lambda calculus - Logic and predicates, Lambda calculus - Recursion, Lambda calculus - Computable functions and lambda calculus, Lambda calculus - Undecidability of equivalence, Lambda calculus - Lambda calculus and programming languages Read more here: » Lambda calculus: Encyclopedia II - Lambda calculus - Lambda calculus and programming languages |
| |
|
| | | | Lambda calculus - Lambda calculus and programming languages: Encyclopedia II - Lambda calculus - Formal definition Formally, we start with a countably infinite set of identifiers, say {a, b, c, ..., x, y, z, x1, x2, ...}. The set of all lambda expressions can then be described by the following context-free grammar in BNF:
<expr> ::= <identifier>
<expr> ::= (λ <identifier>. <expr>)
<expr ...
See also:Lambda calculus, Lambda calculus - History, Lambda calculus - Informal description, Lambda calculus - Formal definition, Lambda calculus - α-conversion, Lambda calculus - β-reduction, Lambda calculus - η-conversion, Lambda calculus - Arithmetic in lambda calculus, Lambda calculus - Logic and predicates, Lambda calculus - Recursion, Lambda calculus - Computable functions and lambda calculus, Lambda calculus - Undecidability of equivalence, Lambda calculus - Lambda calculus and programming languages Read more here: » Lambda calculus: Encyclopedia II - Lambda calculus - Formal definition |
| |
|
| | | | Lambda calculus - Lambda calculus and programming languages: Encyclopedia II - Lambda calculus - Undecidability of equivalence There is no algorithm which takes as input two lambda expressions and outputs TRUE or FALSE depending on whether or not the two expressions are equivalent. This was historically the first problem for which the unsolvability could be proven. Of course, in order to do so, the notion of algorithm has to be cleanly defined; Church used a definition via recursive functions, which is now known to ...
See also:Lambda calculus, Lambda calculus - History, Lambda calculus - Informal description, Lambda calculus - Formal definition, Lambda calculus - α-conversion, Lambda calculus - β-reduction, Lambda calculus - η-conversion, Lambda calculus - Arithmetic in lambda calculus, Lambda calculus - Logic and predicates, Lambda calculus - Recursion, Lambda calculus - Computable functions and lambda calculus, Lambda calculus - Undecidability of equivalence, Lambda calculus - Lambda calculus and programming languages Read more here: » Lambda calculus: Encyclopedia II - Lambda calculus - Undecidability of equivalence |
| |
|
| | | | Lambda calculus - Lambda calculus and programming languages: Encyclopedia II - Lambda calculus - Recursion Recursion is the definition of a function using the function itself; on the face of it, lambda calculus does not allow this. However, this impression is misleading. Consider for instance the factorial function f(n) recursively defined by
f(n) = 1, if n = 0; and n·f(n-1), if n>0.
In lambda calculus, one cannot define a function which includes itself. To get around this, one may start by defining a function, here called g< ...
See also:Lambda calculus, Lambda calculus - History, Lambda calculus - Informal description, Lambda calculus - Formal definition, Lambda calculus - α-conversion, Lambda calculus - β-reduction, Lambda calculus - η-conversion, Lambda calculus - Arithmetic in lambda calculus, Lambda calculus - Logic and predicates, Lambda calculus - Recursion, Lambda calculus - Computable functions and lambda calculus, Lambda calculus - Undecidability of equivalence, Lambda calculus - Lambda calculus and programming languages Read more here: » Lambda calculus: Encyclopedia II - Lambda calculus - Recursion |
| |
|
| | | | Lambda calculus - Lambda calculus and programming languages: Encyclopedia II - Lambda calculus - Logic and predicates By convention, the following two definitions (known as Church booleans) are used for the boolean values TRUE and FALSE:
TRUE := λ x y. x
FALSE := λ x y. y
(Note that FALSE is equivalent to the Church numeral zero defined above)
Then, with these two λ-terms, we can define some logic operators:
AND := λ p q. p q FALSE
OR := ...
See also:Lambda calculus, Lambda calculus - History, Lambda calculus - Informal description, Lambda calculus - Formal definition, Lambda calculus - α-conversion, Lambda calculus - β-reduction, Lambda calculus - η-conversion, Lambda calculus - Arithmetic in lambda calculus, Lambda calculus - Logic and predicates, Lambda calculus - Recursion, Lambda calculus - Computable functions and lambda calculus, Lambda calculus - Undecidability of equivalence, Lambda calculus - Lambda calculus and programming languages Read more here: » Lambda calculus: Encyclopedia II - Lambda calculus - Logic and predicates |
| |
|
| | | | Lambda calculus - Lambda calculus and programming languages: Encyclopedia II - Lambda calculus - Arithmetic in lambda calculus There are several possible ways to define the natural numbers in lambda calculus, but by far the most common are the Church numerals, which can be defined as follows:
0 := λ f x. x
1 := λ f x. f x
2 := λ f x. f (f x)
3 := λ f< ...
See also:Lambda calculus, Lambda calculus - History, Lambda calculus - Informal description, Lambda calculus - Formal definition, Lambda calculus - α-conversion, Lambda calculus - β-reduction, Lambda calculus - η-conversion, Lambda calculus - Arithmetic in lambda calculus, Lambda calculus - Logic and predicates, Lambda calculus - Recursion, Lambda calculus - Computable functions and lambda calculus, Lambda calculus - Undecidability of equivalence, Lambda calculus - Lambda calculus and programming languages Read more here: » Lambda calculus: Encyclopedia II - Lambda calculus - Arithmetic in lambda calculus |
| |
|
| | | | Lambda calculus - Lambda calculus and programming languages: Encyclopedia II - Lambda calculus - Informal description In lambda calculus, every expression stands for a function with a single argument; the argument of the function is in turn a function with a single argument, and the value of the function is another function with a single argument. A function is anonymously defined by a lambda expression which expresses the function's action on its argument. For instance, the "add-two" function f such that f(x) = x + 2 would be expressed in lambda calculus as λ x. x + 2 (or ...
See also:Lambda calculus, Lambda calculus - History, Lambda calculus - Informal description, Lambda calculus - Formal definition, Lambda calculus - α-conversion, Lambda calculus - β-reduction, Lambda calculus - η-conversion, Lambda calculus - Arithmetic in lambda calculus, Lambda calculus - Logic and predicates, Lambda calculus - Recursion, Lambda calculus - Computable functions and lambda calculus, Lambda calculus - Undecidability of equivalence, Lambda calculus - Lambda calculus and programming languages Read more here: » Lambda calculus: Encyclopedia II - Lambda calculus - Informal description |
| |
|
| |
|
|
|
|
More material related to Lambda Calculus can be found here:
|
|
|
|
| |
