Mathematical logic is a subfield of mathematics and logic with close connections to computer science and philosophical logic. The field includes the mathematical study of logic and the applications of formal logic to other areas of mathematics.... and computer science
Computer science
Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.... , lambda calculus, also written as ?-calculus, is a formal system
Formal system
In logic, a formal system consists of a formal language together with a deductive system which consists of a set of inference rules and/or axioms.... designed to investigate function
Function (mathematics)
The mathematical concept of a function expresses dependence between two quantities, one of which is known and the other which is produced. A function associates a single output to each input element drawn from a fixed Set , such as the real numbers , although different inputs may have the same output.... definition, function application and recursion
Recursion
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... . It was introduced by Alonzo Church
Alonzo Church
Alonzo Church was an United States mathematician and list of logicians who made major contributions to mathematical logic and the foundations of theoretical computer science.... and Stephen Cole Kleene
Stephen Cole Kleene
Stephen Cole Kleene was an United States mathematician who helped lay the foundations for theoretical computer science. One of many distinguished students of Alonzo Church, Kleene, along with Alan Turing, Emil Post, and others, is best known as a founder of the branch of mathematical logic known as recursion theory.... in the 1930s as part of an investigation into the foundations of mathematics
Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory.... , but has emerged as a useful tool in the investigation of problems in computability or recursion theory
Recursion theory
Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees.... , and forms the basis of a paradigm of computer programming called functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of function s and avoids program state and immutable object data.... .
The key concept of lambda calculus is that of a lambda expression - a reification
Reification (computer science)
Reification is a process through which a computable/addressable object - a resource - is created in a system, as a proxy for a non computable/addressable object.... of the concept of a procedure without side effects
Side Effects
Side Effects is an anthology of 17 comical short stories written by Woody Allen between 1975 and 1980, all but one of which were previously published in, variously, The New Republic, The New York Times, The New Yorker, and The Kenyon Review.... .
Mathematical logic is a subfield of mathematics and logic with close connections to computer science and philosophical logic. The field includes the mathematical study of logic and the applications of formal logic to other areas of mathematics.... and computer science
Computer science
Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.... , lambda calculus, also written as ?-calculus, is a formal system
Formal system
In logic, a formal system consists of a formal language together with a deductive system which consists of a set of inference rules and/or axioms.... designed to investigate function
Function (mathematics)
The mathematical concept of a function expresses dependence between two quantities, one of which is known and the other which is produced. A function associates a single output to each input element drawn from a fixed Set , such as the real numbers , although different inputs may have the same output.... definition, function application and recursion
Recursion
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... . It was introduced by Alonzo Church
Alonzo Church
Alonzo Church was an United States mathematician and list of logicians who made major contributions to mathematical logic and the foundations of theoretical computer science.... and Stephen Cole Kleene
Stephen Cole Kleene
Stephen Cole Kleene was an United States mathematician who helped lay the foundations for theoretical computer science. One of many distinguished students of Alonzo Church, Kleene, along with Alan Turing, Emil Post, and others, is best known as a founder of the branch of mathematical logic known as recursion theory.... in the 1930s as part of an investigation into the foundations of mathematics
Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory.... , but has emerged as a useful tool in the investigation of problems in computability or recursion theory
Recursion theory
Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees.... , and forms the basis of a paradigm of computer programming called functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of function s and avoids program state and immutable object data.... .
The key concept of lambda calculus is that of a lambda expression - a reification
Reification (computer science)
Reification is a process through which a computable/addressable object - a resource - is created in a system, as a proxy for a non computable/addressable object.... of the concept of a procedure without side effects
Side Effects
Side Effects is an anthology of 17 comical short stories written by Woody Allen between 1975 and 1980, all but one of which were previously published in, variously, The New Republic, The New York Times, The New Yorker, and The Kenyon Review.... . The lambda calculus can be thought of as an idealized, minimalistic programming language. It is capable of expressing any algorithm
Algorithm
In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing.... , and it is this fact that makes the model of functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of function s and avoids program state and immutable object data.... an important one. Functional programs are stateless and deal exclusively with functions that accept and return data (including other functions), but they produce no side effects
Side effect (computer science)
In computer science, a subroutine or expression is said to produce a side effect if it modifies some state_ in addition to returning a value. For example, a function might modify a global or a static variable, modify one of its arguments, write data to a display or file, or read some data from other side-effecting functions.... in 'state' and thus make no alterations to incoming data. Modern functional languages, building on the lambda calculus, include Erlang, Haskell
Haskell (programming language)
Haskell is a standardized, purely functional programming language with non-strict programming language, named after logician Haskell Curry. The goals of the language are described as:... , Lisp, ML, and Scheme, as well as more recent languages like Clojure
Clojure
Clojure is a modern dialect of the Lisp programming language. It is a general-purpose language sporting interactive development, and it encourages a functional programming style that enables simplified Thread programming.... , F#, Nemerle
Nemerle
Nemerle is a high level language static typing programming language for the Microsoft .NET platform. It offers functional programming, object-oriented and imperative programming features.... , and Scala.
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory.... , through the Curry-Howard correspondence. However, as a naïve foundation for mathematics, the untyped lambda calculus is unable to avoid set-theoretic paradoxes (see the Kleene-Rosser paradox
Kleene-Rosser paradox
In mathematics, the Kleene-Rosser paradox is a paradox that shows Alonzo Church's original lambda calculus is inconsistent. It is similar to Russell's paradox, in that it is a statement that asserts its own falsehood if and only if it is true; that is, it is a negation.... ).
This article deals with the "untyped lambda calculus" as originally conceived by Church. Most modern applications concern typed lambda calculi
Typed lambda calculus
A typed lambda calculus is a typed formalism that uses the lambda-symbol to denote anonymous function abstraction. Typed lambda calculi are foundational programming languages and are the base of typed functional programming languages such as ML programming language and Haskell and, more indirectly, typed imperative programming.... .
Informal description
The key concept of lambda-calculus is a lambda expression. A lambda expression represents an anonymous function and defines the transformation that the function performs to its argument. For instance, a numeric "add-two" function, which adds 2 to its argument, can be expressed in lambda calculus as ? x. x + 2 . The variable x is specific to this lambda expression, which means that we could have equivalently expressed the same function as ? y. y + 2; the name of the argument is immaterial (see -conversion). In a more conventional mathematical notation this function can be expressed as f such that f(x) = x + 2 .
In lambda-calculus the application of this function to a number "3" can be written as (? x. x + 2) 3. Note that part of what makes this description "informal" is that the expression x + 2 (or even the number 2) is not part of core lambda calculus; instead, numbers and arithmetic can be fully defined in lambda calculus, see below. In a more conventional mathematical notation, the application of function with the name "f" to a number "3" is expressed as f(3).
In lambda-calculus all functions are anonymous. The lambda expression reifies
Reification (computer science)
Reification is a process through which a computable/addressable object - a resource - is created in a system, as a proxy for a non computable/addressable object.... the concept of a function definition: a lambda expression can be used as any other expression, such as a number. In particular, a lambda expression can be returned as the result of some function, or can be used as an argument to another function.
A unary function is a function that takes one Parameter . In computer science, a unary operator is a subset of unary function.Many of the elementary functions are unary functions, in particular the trigonometric functions and hyperbolic function are unary.... , i.e. a function with only one input (known as its argument). When an expression is applied to another expression (which corresponds to a function 'call' with the other expression as its argument), it returns a single value (known as its result). Function application is left associative: fxy = (fx) y. Consider the function which takes a function as an argument and applies it to the number 3 as follows: ? f. f 3. This latter function could be applied to our earlier "add-two" function as follows: (? f. f 3) (? x. x + 2). The three expressions:
(? f. f 3) (? x. x + 2)
(? x. x + 2) 3
3 + 2
are equivalent.
A function of two variables is expressed in lambda calculus as a function of one argument which returns a function of one argument (see currying
Currying
In computer science, currying, invented by Moses Sch?nfinkel and Gottlob Frege, and independently by Haskell Curry, is the technique of transforming a function that takes multiple parameter in such a way that it can be called as a chain of functions each with a single argument.... ). For instance, the function f(x, y) = x - y would be written as ? x. ? y. x - y. A common convention is to abbreviate curried functions as, in this example, ? xy. x - y. While it is not part of the formal definition of the language,
? x1x2 … xn. expression
is used as an abbreviation for
? x1. ? x2. … ? xn. expression
The following expression in the lambda calculus is particularly notable:
(? x. xx) (? x. xx)
This expression is an application of a lambda expression (? x. xx) (first sub-expression) to an argument (? x. xx) (second sub-expression). The sub-expression x x is also an application. It means that a function (represented by a variable x ) is applied to its argument (also represented by the variable x).
When the above application is evaluated (the sub-expression (? x. xx) is substituted for the argument x in the lambda expression) it reproduces itself:
(? x. xx) (? x. xx)
So, the process of evaluation the above expression never terminates.
A similar situation arises with:
(? x. xxx) (? x. xxx)
(? x. xx) is also known as the ? combinator;
((? x. xx) (? x. xx))
is known as O,
((? x. xxx) (? x. xxx))
as O2, etc.
Lambda calculus expressions may contain free variables, i.e. variables not bound by any ?. For example, the variable y is free in the expression (? x. y) , representing a function which always produces the result y. Occasionally, this necessitates the renaming of formal arguments. For example, in the formula below, the letter y is used first as a formal parameter, then as a free variable:
(? xy. yx) (? x. y).
To reduce the expression, we rename the first identifier z so that the reduction does not mix up the names:
(? xz. zx) (? x. y)
the reduction is then
? z. z (? x. y).
If one only formalizes the notion of function application and replaces the use of lambda expressions by the use of combinators, one obtains combinatory logic
Combinatory logic
Combinatory logic is a notation introduced by Moses Sch?nfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages.... .
Formal definition
Definition
Lambda expressions are composed of
variables v1, v2, . . . vn
the abstraction symbols ? and .
parentheses
The set of lambda expressions, ?, can be defined recursively
Recursion
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... :
If x is a variable, then x ? ?
If x is a variable and M ? ?, then ( ? x . M ) ? ?
If M, N ? ?, then ( M N ) ? ?
Instances of 2 are known as abstractions and instances of 3, applications.
Notation
To keep the notation of lambda expressions uncluttered, the following conventions are usually applied.
Outermost parentheses are dropped: M N instead of (M N).
Applications are assumed to be left associative: M N P means (M N) P.
The body of an abstraction extends as far right as possible: ? x . M N means ? x . (M N) and not (? x . M) N
A sequence of abstractions are contracted: ? x . ? y . ? z . N is abbreviated as ? x y z . N
Free and bound variables
The abstraction operator, ?, is said to bind its variable wherever it occurs in the body of the abstraction. Variables that fall within the scope of a lambda are said to be bound. All other variables are called free. For example in the following expression y is a bound variable and x is free:
? y . x x y
Also note that a variable binds to its "nearest" lambda. In the following expression one single occurrence of x is bound by the second lambda:
? x . y (? x . z x)
The set of free variables of a lambda expression, M, is denoted as FV(M) and is defined by recursion on the structure of the terms, as follows:
FV( x ) = , where x is a variable
FV ( ? x . M ) = FV ( M ) -
FV ( M N ) = FV ( M ) FV ( N )
An expression which contains no free variables is said to be closed. Closed lambda expressions are also known as combinators and are equivalent to terms in combinatory logic
Combinatory logic
Combinatory logic is a notation introduced by Moses Sch?nfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages.... .
Reduction
Reduction is the process of evaluating an expression. Reduction rules are the axiom
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evidence, or subject to necessary decision.... s of the lambda calculus that define axiomatic semantics
Axiomatic semantics
Axiomatic semantics is an approach based on mathematical logic to proving the correctness of computer programs. It is closely related to Hoare logic.... of the lambda calculus. Each operator must have an evaluation rule but the interesting case is the application of functions.
ß-reduction
Beta-reduction defines an axiom related to the idea of function application. The beta-reduction of ((? V. E) E′) is E[V := E′] .
where E[V := E′] denotes the substitution of the formal parameter V with the argument E′ throughout the expression E.
For example,
((? n. n*2+3) 7
--> (n*2+3)[n:= 7]
--> 7*2+3
--> 14+3
--> 17
Substitution
Substitution, written E[V := E′], corresponds to the replacement of a variable V by expression E′ every place it is free within E (assuming that variable names are unique).
Substitution on terms of the ?-calculus is defined by recursion on the structure of terms, as follows.
x[x := N] ≡ N
y[x := N] ≡ y, if x ? y
(M1 M2)[x := N] ≡ (M1[x := N]) (M2[x := N])
(? y. M)[x := N] ≡ ? y. (M[x := N]), if x ? y and y?fv(N)
If an expression does not have unique variable name, the so-called a-conversion has to be performed. For example, it is not correct for (? x.y)[y := x] to result in (? x.x), because the substituted x was supposed to be free but ended up being bound. The correct substitution in this case is (? z.x), up-to a-equivalence. Notice that substitution is defined uniquely up-to a-equivalence.
a-conversion
Alpha-conversion allows bound variable names to be changed. For example, an alpha-conversion of ?x.x would be ?y.y. Frequently in uses of lambda calculus, terms that differ only by alpha-conversion are considered to be equivalent.
The precise rules for alpha-conversion are not completely trivial. First, when alpha-converting an abstraction, the only variable occurrences that are renamed are those that are bound to the same abstraction. For example, an alpha-conversion of ?x.?x.x could result in ?y.?x.x, but it could not result in ?y.?x.y. The latter has a different meaning from the original.
Second, alpha-conversion is not possible if it would result in a variable getting captured by a different abstraction. For example, if we replace x with y in ?x.?y.x, we get ?y.?y.y, which is not at all the same.
In logic, extensionality refers to principles that judge objects to be equal if they have the same external properties. It is the opposite concept of intensionality, which is concerned with whether two descriptions are intended to be the same or not.... , which in this context is that two functions are the same if and only if
If and only if
If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements.... they give the same result for all arguments. Eta-conversion converts between ? x. fx and f whenever x does not appear free in f.
This conversion is not always appropriate when lambda expressions are interpreted as programs. Evaluation of ? x. fx can terminate even when evaluation of f does not.
Arithmetic in lambda calculus
There are several possible ways to define the natural number
Natural number
In mathematics, a natural number can mean either an element of the Set = *n = = ? = ? ... s in lambda calculus, but by far the most common are the Church numerals, which can be defined as follows:
In mathematics and computer science, higher-order functions or functional are function s which do at least one of the following:*take one or more functions as an input... —it takes a single-argument function f, and returns another single-argument function. The Church numeral n is a function that takes a function f as argument and returns the n-th composition of f, i.e. the function f composed with itself n times. This is denoted f(n) and is in fact the n-th power of f (considered as an operator); f(0) is defined to be the identity function. Such repeated compositions (of a single function f) obey the laws of exponents
Exponentiation
Exponentiation is a mathematics operation , written 'an', involving two numbers, the base a and the exponentn.... , which is why these numerals can be used for arithmetic. Note that 0 returns x itself, i.e. it is essentially the identity function, and 1returns the identity function. (Also note that in Church's original lambda calculus, the formal parameter of a lambda expression was required to occur at least once in the function body, which made the above definition of 0 impossible.)
We can define a successor function, which takes a number n and returns n + 1 by adding an additional application of f:
SUCC := ? nfx. f (nfx)
Because the m-th composition of f composed with the n-th composition of f gives the m+n-th composition of f, addition can be defined as follows:
PLUS := ? mnfx. nf (mfx)
PLUS can be thought of as a function taking two natural numbers as arguments and returning a natural number; it can be verified that
PLUS 2 3 and 5
are equivalent lambda expressions. Since adding m to a number n can be accomplished by adding 1 m times, an equivalent definition is:
PLUS := ? nm. m SUCC n
Similarly, multiplication can be defined as
MULT := ? mnf . m (nf)
Alternatively
MULT := ? mn. m (PLUS n) 0,
since multiplying m and n is the same as repeating the "add n" function m times and then applying it to zero.
The predecessor function defined by PRED n = n - 1 for a positive integer n and PRED 0 = 0 is considerably more difficult. The formula
PRED := ? nfx. n (? gh. h (gf)) (? u. x) (? u. u)
can be validated by showing inductively that if T denotes (? gh. h (gf)), then T(n)(? u. x) = (? h. h(f(n-1)(x)) ) for n > 0. Two other definitions of PRED are given below, one using conditionals and the other using pairs. With the predecessor function, subtraction is straightforward. Defining
SUB := ? mn. n PRED m,
SUB mn yields m - n when m > n and 0 otherwise.
Logic and predicates
By convention, the following two definitions (known as Church booleans) are used for the boolean values TRUE and FALSE:
TRUE := ? xy. x
FALSE := ? xy. y
Then, with these two ?-terms, we can define some logic operators (these are just possible formulations; other expressions are equally correct):
AND := ? p q. p q p
OR := ? p q. p p q
NOT := ? p a b. p b a
IFTHENELSE := ? p a b. p a b
We are now able to compute some logic functions, for example:
AND TRUE FALSE
= (? p q. p q p) TRUE FALSE ?ß TRUE FALSE TRUE
= (? x y. x) FALSE TRUE ?ß FALSE
and we see that AND TRUE FALSE is equivalent to FALSE.
A predicate is a function which returns a boolean value. The most fundamental predicate is ISZERO which returns TRUE if its argument is the Church numeral 0, and FALSE if its argument is any other Church numeral:
ISZERO := ? n. n (? x. FALSE) TRUE
The following predicate tests whether the first argument is less-than-or-equal-to the second:
LEQ := ? m n. ISZERO (SUB m n),
and since m = n iff LEQ m n and LEQ n m, it is straightforward to build a predicate for numerical equality.
The availability of predicates and the above definition of TRUE and FALSE make it convenient to write "if-then-else" expressions in lambda calculus. For example, the predecessor function can be defined as' '
PRED := ? n. n (? g k. ISZERO (g 1) k (PLUS (g k) 1) ) (? v. 0) 0
which can be verified by showing inductively that n (? g k. ISZERO (g 1) k (PLUS (g k) 1) ) (? v. 0) is the "add n - 1" function for n > 0.
In mathematics, Church encoding is a means of embedding data and operators into the lambda calculus, the most familiar form being the Church numerals, a representation of the natural numbers using lambda notation.... . For example, PAIR encapsulates the pair (x,y), FIRST returns the first element of the pair, and SECOND returns the second.
PAIR := ? xyf. fxy
FIRST := ? p. p TRUE
SECOND := ? p. p FALSE
NIL := ? x. TRUE
NULL := ?p. p (?x y.FALSE)
A linked list can be defined as either NIL for the empty list, or the PAIR of an element and a smaller list. The predicate NULL tests for the value NIL.
As an example of the use of pairs, the shift-and-increment function that maps (m, n) to (n, n+1) can be defined as
F := ? x. PAIR (SECOND x) (SUCC (SECOND x))
which allows us to give perhaps the most transparent version of the predecessor function:
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... 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
Factorial
In mathematics, the factorial of a negative and non-negative numbers integer n, denoted by n!, is the Product of all positive integers less than or equal to n.... 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, which takes a function f as an argument and returns another function that takes n as an argument:
g := ? fn. (1, if n = 0; and n·f(n-1), if n>0).
The function that g returns is either the constant 1, or n times the application of the function f to n-1. Using the ISZERO predicate, and boolean and algebraic definitions described above, the function g can be defined in lambda calculus.
However, g by itself is still not recursive; in order to use g to create the recursive factorial function, the function passed to g as f must have specific properties. Namely, the function passed as f must expand to the function g called with one argument -- and that argument must be the function that was passed as f again!
In other words, f must expand to g(f). This call to g will then expand to the above factorial function and calculate down to another level of recursion. In that expansion the function f will appear again, and will again expand to g(f) and continue the recursion. This kind of function, where f = g(f), is called a fixed-point of g, and it turns out that it can be implemented in the lambda calculus using what is known as the paradoxical operator or fixed-point operator and is represented as Y -- the Y combinator
Fixed point combinator
A fixed point combinator is a higher-order function that computes a fixed point of other functions. This operation is relevant in programming language theory because it allows the implementation of recursion in the form of a rewrite rule, without explicit support from the language's runtime engine.... :
Y = ? g. (? x. g (xx)) (? x. g (xx))
In the lambda calculus, Y g is a fixed-point of g, as it expands to:
Y g
? h. ((? x. h (xx)) (? x. h (xx))) g
(? x. g (xx)) (? x. g (xx))
g ((? x. g (xx)) (? x. g (xx)) - Compare with the previous step
g (Yg).
Now, to complete our recursive call to the factorial function, we would simply call g (Yg) n, where n is the number we are calculating the factorial of.
Given n = 5, for example, this expands to:
(? n.(1, if n = 0; and n·((Y g)(n-1)), if n>0)) 5
1, if 5 = 0; and 5·(g(Y g)(5-1)), if 5>0
5·(g(Y g) 4)
5·(? n. (1, if n = 0; and n·((Y g)(n-1)), if n>0) 4)
5·(1, if 4 = 0; and 4·(g(Y g)(4-1)), if 4>0)
5·(4·(g(Y g) 3))
5·(4·(? n. (1, if n = 0; and n·((Y g)(n-1)), if n>0) 3))
5·(4·(1, if 3 = 0; and 3·(g(Y g)(3-1)), if 3>0))
5·(4·(3·(g(Y g) 2)))
...
And so on, evaluating the structure of the algorithm recursively. Every recursively defined function can be seen as a fixed point of some other suitable function, and therefore, using Y, every recursively defined function can be expressed as a lambda expression. In particular, we can now cleanly define the subtraction, multiplication and comparison predicate of natural numbers recursively.
In mathematics, a natural number can mean either an element of the Set = *n = = ? = ? ... s is a computable function
Computable function
Computable functions are the basic objects of study in recursion theory. The set of computable functions is equivalent to the set of Turing-computable functions and partial recursive functions.... if and only if
If and only if
If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements.... there exists a lambda expression f such that for every pair of x, y in N, F(x)=y if and only if fx =ßy, where x and y are the Church numerals corresponding to x and y, respectively and =ß meaning equivalence with beta reduction. This is one of the many ways to define computability; see the Church-Turing thesis for a discussion of other approaches and their equivalence.
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 undecidability could be proven. As is common for a proof of undecidability, the proof shows that no computable function
Computable function
Computable functions are the basic objects of study in recursion theory. The set of computable functions is equivalent to the set of Turing-computable functions and partial recursive functions.... can decide the equivalence. Church's thesis is then invoked to show that no algorithm can do so.
Church's proof first reduces the problem to determining whether a given lambda expression has a normal form. A normal form is an equivalent expression which cannot be reduced any further. Then he assumes that this predicate is computable, and can hence be expressed in lambda calculus. Building on earlier work by Kleene and constructing a Gödel numbering for lambda expressions, he constructs a lambda expression e which closely follows the proof of Gödel's first incompleteness theorem. If e is applied to its own Gödel number
Gödel number
In mathematical logic, a G?del numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its G?del number.... , a contradiction results.
Procedural programming can sometimes be used as a synonym for imperative programming , but can also refer to a programming paradigm based upon the concept of the procedure call.... can be understood in terms of the lambda calculus, which provides the basic mechanisms for procedural abstraction and procedure (subprogram) application.
Reification is a process through which a computable/addressable object - a resource - is created in a system, as a proxy for a non computable/addressable object.... "functions" and makes them first-class object
First-class object
In computing, a first-class object , in the context of a particular programming language, is an entity which can be used in programs without restriction .... s, which raises implementation complexity when implementing lambda calculus. A particular challenge is related to the support of higher-order functions, also known as the Funarg problem
Funarg problem
Funarg is an abbreviation for "functional argument"; in computer science, the funarg problem relates to a difficulty in implementing function s as first-class objects in stack-oriented programming language implementations.... . Lambda calculus is usually implemented using a virtual machine
Virtual machine
In computer science, a virtual machine is a software implementation of a machine that executes programs like a real machine.Definitions... approach. The first practical implementation of lambda calculus was provided in 1963 by Peter Landin, and is know as the SECD machine
SECD machine
The SECD machine is a highly influential virtual machine intended as a target for functional programming compilers. The letters stand for Stack, Environment, Code, Dump, the internal registers of the machine.... . Since then, several optimized abstract machines for lambda calculus were suggested, such as the G-machine and the Categorical abstract machine
Categorical abstract machine
Categorical abstract machine ? is the model of computation of a program, which preserves the abilities of applicative, functional or compositional style.... .
The most prominent counterparts to lambda calculus in programming are functional programming languages, which essentially implement the calculus augmented with some constants and datatypes. Lisp
Lisp programming language
Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older.... uses a variant of lambda notation for defining functions, but only its purely functional subset ("Pure Lisp
Lispkit Lisp
Lispkit Lisp is a lexical scoping, purely functional subset of Lisp programming language developed as a testbed for functional programming concepts.... ") is really equivalent to lambda calculus.
An example of a lambda function in Lisp:
(lambda (x) (* x x))
Above Lisp example evaluates to a first class function. The symbol lambda introduces the function. Next is a list of arguments. This function has only one argument: x. Next are expressions that are executed. Here we have one expression (* x x) which multiplies x by x.
Functional languages are not the only ones to support functions as first-class object
First-class object
In computing, a first-class object , in the context of a particular programming language, is an entity which can be used in programs without restriction .... s. Numerous imperative languages
Imperative programming
In computer science, imperative programming is a programming paradigm that describes computation in terms of statement s that change a program state .... , e.g. Pascal
Pascal (programming language)
Pascal is an influential imperative programming and Procedural programming programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structure.... , have long supported passing subprograms as arguments to other subprograms. In C
C (programming language)
C is a general-purpose computer programming language originally developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories to implement the Unix operating system.... and the C-like subset of C++
C++
C++ is a general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level programming language and low-level programming language language features.... the equivalent result is obtained by passing ''pointers'' to the code of functions (subprograms). Such mechanisms are limited to subprograms written explicitly in the code, and do not directly support higher-level functions. Some imperative object-oriented languages have notations that represent functions of any order; such mechanisms are available in C++
C++
C++ is a general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level programming language and low-level programming language language features.... , Smalltalk
Smalltalk
Smalltalk is an Object-oriented programming, Type system, reflection computer programming programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human?computer symbiosis." It was designed and created in part for educational use, more so for constructionist learning, at PARC by Al... and more recently in Eiffel
Eiffel (programming language)
Eiffel is an International Organization for Standardization-standardized, object-oriented programming language designed to enable programmers to efficiently develop extensible, reusable, reliable software.... ("agents") and C# ("delegates"). As an example, the Eiffel "inline agent" expression
agent (x: REAL): REAL do Result := x * x end
denotes an object corresponding to the lambda expression ? x . x*x (with call by value). It can be treated like any other expression, e.g. assigned to a variable or passed around to routines. If the value of square is the above agent expression, then the result of applying square to a value a (ß-reduction) is expressed as square.item ([a]), where the argument is passed as a tuple
Tuple
In mathematics, a tuple is a sequence of a specific number of values, called the components of the tuple. These components can be any kind of mathematical objects, where each component of a tuple is a value of a specified type.... .
Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python's core syntax and semantics are Minimalism , while the standard library is large and comprehensive.... example of this uses the form of functions:
func = lambda x: x ** 2
This creates a new anonymous function and names it func which can be passed to other functions, stored in variables, etc. Python can also treat any other function created with the standard statement as first-class object
First-class object
In computing, a first-class object , in the context of a particular programming language, is an entity which can be used in programs without restriction .... s.
The same holds for Smalltalk expression
[ :x | x * x ]
This is first-class object (block closure), which can be stored in variables, passed as arguments, etc.
A similar C++ example (using the Boost.Lambda library):
stdfor_each(c.begin, c.end, stdcout << _1 * _1 << stdendl);
Here the standard library function for_each iterates over all members of container 'c', and prints the square of each element. The _1 notation is Boost.Lambda's convention (originally derived from Boost.Bind) for representing the first placeholder element (the first argument), represented as x elsewhere.
A delegate is a form of Type safety function pointer used by the .NET Framework. Delegates specify a Method to call and optionally an Object to call the method on.... taking a variable and returning the square. This function variable can then be passed to other methods (or function delegates)
//Declare a delegate signature
delegate double MathDelegate(double i);
//Create a delegate instance
MathDelegate f = delegate(double i) ;
/* Passing 'f' function variable to another method, executing,
and returning the result of the function
*/
double Execute(MathDelegate f)
In C# 3.0, the language has lambda expressions in a form similar to python or lisp. The expression resolves to a delegate like in the previous example but the above can be simplified to below.
//Create a delegate instance
MathDelegate f = i => i * i;
Execute(f);
// or more simply put
Execute(i => i * i);
Reduction strategies
Whether a term is normalising or not, and how much work needs to be done in normalising it if it is, depends to a large extent on the reduction strategy used. The distinction between reduction strategies relates to the distinction in functional programming languages between eager evaluation
Eager evaluation
Eager evaluation or strict evaluation is the evaluation strategy in most traditional programming languages.In eager evaluation an Expression is evaluated as soon as it gets bound to a variable.... and lazy evaluation
Lazy evaluation
In computer programming, lazy evaluation is the technique of delaying a computation until such time as the result of the computation is known to be needed.... .
The following uses the term 'redex', short for 'reducible expression'. For example, (? x. M) N is a beta-redex; ? x. M x is an eta-redex if x is not free in M. The expression to which a redex reduces is called its reduct; using the previous example, the reducts of these expressions are respectively M[x:=N] and M.
Full beta reductions: Any redex can be reduced at any time. This means essentially the lack of any particular reduction strategy — with regard to reducibility, "all bets are off".
Applicative order: The rightmost, innermost redex is always reduced first. Intuitively this means a function's arguments are always reduced before the function itself. Applicative order always attempts to apply functions to normal forms, even when this is not possible.
ml may stand for* millilitre , a thousandth of a litre * Malayalam language * .ml, the top-level Internet domain for MaliML may stand for:... and imperative languages like C and Java) are described as "strict", meaning that functions applied to non-normalising arguments are non-normalising. This is done essentially using applicative order, call by value reduction (see below), but usually called "eager evaluation".
Normal order: The leftmost, outermost redex is always reduced first. That is, whenever possible the arguments are substituted into the body of an abstraction before the arguments are reduced.
Call by name: As normal order, but no reductions are performed inside abstractions. For example ? x.(? x.x)x is in normal form according to this strategy, although it contains the redex (? x.x)x.
Call by value: Only the outermost redexes are reduced: a redex is reduced only when its right hand side has reduced to a value (variable or lambda abstraction).
Call by need: As normal order, but function applications that would duplicate terms instead name the argument, which is then reduced only "when it is needed". Called in practical contexts "lazy evaluation". In implementations this "name" takes the form of a pointer, with the redex represented by a thunk
Thunk
The word thunk has at least three related meanings in computer science. A "thunk" may be:* a piece of code to perform a delayed computation * a feature of some virtual function table implementations ... .
Applicative order is not a normalising strategy. The usual counterexample is as follows: define O = ?? where ? = ? x. xx. This entire expression contains only one redex, namely the whole expression; its reduct is again O. Since this is the only available reduction, O has no normal form (under any evaluation strategy). Using applicative order, the expression KIO = (? x y . x)(? x.x)O is reduced by first reducing O to normal form (since it is the rightmost redex), but since O has no normal form, applicative order fails to find a normal form for KIO.
In contrast, normal order is so called because it always finds a normalising reduction if one exists. In the above example, KIO reduces under normal order to I, a normal form. A drawback is that redexes in the arguments may be copied, resulting in duplicated computation (for example, (? x.xx)((? x.x)y) reduces to ((?x.x)y)((?x.x)y) using this strategy; now there are two redexes, so full evaluation needs two more steps, but if the argument had been reduced first, there would now be none).
The positive tradeoff of using applicative order is that it does not cause unnecessary computation if all arguments are used, because it never substitutes arguments containing redexes and hence never needs to copy them (which would duplicate work). In the above example, in applicative order (? x.xx)((? x.x)y) reduces first to (? x.xx)y and then to the normal order yy, taking two steps instead of three.
Most ''purely'' functional programming languages (notably Miranda
Miranda
Miranda is commonly a person's name:* Miranda * Miranda Miranda may also refer to:In People:* Francisco de Miranda, Venezuelan independence revolutionary.... and its descendents, including Haskell
Haskell (programming language)
Haskell is a standardized, purely functional programming language with non-strict programming language, named after logician Haskell Curry. The goals of the language are described as:... ), and the proof languages of theorem provers, use ''lazy evaluation
Lazy evaluation
In computer programming, lazy evaluation is the technique of delaying a computation until such time as the result of the computation is known to be needed.... '', which is essentially the same as call by need. This is like normal order reduction, but call by need manages to avoid the duplication of work inherent in normal order reduction using ''sharing''. In the example given above, (? x.xx)((? x.x)y) reduces to ((?x.x)y)((?x.x)y), which has two redexes, but in call by need they are represented using the same object rather than copied, so when one is reduced the other is too.
A note about complexity
While the idea of beta reduction seems simple enough, it is not an atomic step, in that it must have a non-trivial cost when estimating computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity ... . To be precise, one must somehow find the location of all of the occurrences of the bound variable ''V'' in the expression ''E'', implying a time cost, or one must keep track of these locations in some way, implying a space cost. A naïve search for the locations of ''V'' in ''E'' is ''O''(''n'')
Big O notation
In mathematics, big O notation describes the asymptotic analysis of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.... in the length ''n'' of ''E''. This has led to the study of systems which use explicit substitution
Explicit substitution
In computer science, Explicit substitution is an umbrella term used to describe several calculi based on the Lambda calculus that pay special attention to the formalization of the process of substitution.... . Sinot's director string
Director string
In mathematics, in the area of lambda calculus and computation, directors or director strings are a mechanism for keeping track of the free variables in a Expression .... s offer a way of tracking the locations of free variables in expressions.
Parallelism and concurrency
The Church-Rosser property of the lambda calculus means that evaluation (ß-reduction) can be carried out in ''any order'', even in parallel. This means that various nondeterministic evaluation strategies
Evaluation strategy
In computer science, an evaluation strategy is a set of rules for determining the evaluation of expression in a programming language. Emphasis is typically placed on subprogram or operators ? an evaluation strategy defines when and in what order the arguments to a function are evaluated, when they are substituted into the function, and wha... are relevant. However, the lambda calculus does not offer any explicit constructs for parallelism
Parallel computing
Parallel computing is a form of computing in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved Concurrency .... . One can add constructs such as Futures to the lambda-calculus. Other process calculi have been developed for describing communication and concurrency.
Semantics
The fact that lambda calculus terms act as functions on other lambda calculus terms, and even on themselves, led to questions about the semantics of the lambda calculus. Could a sensible meaning be assigned to lambda calculus terms? The natural semantics was to find a set ''D'' isomorphic to the function space ''D'' → ''D'', of functions on itself. However, no nontrivial such ''D'' can exist, by cardinality
Cardinality
In mathematics, the cardinality of a set is a measure of the "number of Element of the set". For example, the set A = contains 3 elements, and therefore A has a cardinality of 3.... constraints because the set of all functions from ''D'' into ''D'' has greater cardinality than ''D''.
Dana Stewart Scott is the emeritus Hillman University Professor of computer science, Philosophy, and mathematical logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California.... showed that, if only continuous functions
Scott continuity
In mathematics, a Function between two partially ordered sets P and Q is Scott-continuous if it limit preserving function all directed suprema, i.e.... were considered, a set or domain
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory.... ''D'' with the required property could be found, thus providing a model
Model theory
In mathematics, model theory is the study of mathematical Structure such as Group , fields, graph , or even models of set theory, using tools from mathematical logic.... for the lambda calculus.
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages.... of programming languages.
Structure and Interpretation of Computer Programs is a textbook published in 1985 about general computer programming concepts from MIT Press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman.... . The MIT Press. ISBN 0-262-51087-1.
Hendrik Pieter Barendregt .
Barendregt, Hendrik Pieter, ''The Type Free Lambda Calculus'' pp1091-1132 of ''Handbook of Mathematical Logic'', North-Holland (1977) ISBN 0-7204-2285-X
American Journal of Mathematics is a bimonthly mathematics journal published by the Johns Hopkins University Press, founded in 1878 by James Joseph Sylvester.... , 58 (1936), pp. 345–363. This paper contains the proof that the equivalence of lambda expressions is in general not decidable.
American Journal of Mathematics is a bimonthly mathematics journal published by the Johns Hopkins University Press, founded in 1878 by James Joseph Sylvester.... , 57 (1935), pp. 153–173 and 219–244. Contains the lambda calculus definitions of several familiar functions.
Landin, Peter, ''A Correspondence Between ALGOL 60 and Church's Lambda-Notation'', Communications of the ACM
Communications of the ACM
Communications of the ACM is the flagship monthly journal of the Association for Computing Machinery . First published in 1957, CACM is sent to all ACM members, currently numbering about 80,000.... , vol. 8, no. 2 (1965), pages 89-101. Available from the . A classic paper highlighting the importance of lambda-calculus as a basis for programming languages.
Larson, Jim, . A gentle introduction for programmers.
Schalk, A. and Simmons, H. (2005) ''. Notes for a course in the Mathematical Logic MSc at Manchester University.
''Some parts of this article are based on material from FOLDOC
Free On-line Dictionary of Computing
The Free On-line Dictionary of Computing is an online, searchable, encyclopedic dictionary of computing subjects. It was founded in 1985 by Denis Howe and is hosted by Imperial College London.... , used with permission.''
Portable Document Format is a file format created by Adobe Systems in 1993 for document exchange. PDF is used for representing two-dimensional documents in a manner independent of the application software, hardware, and operating system.... )
Portable Document Format is a file format created by Adobe Systems in 1993 for document exchange. PDF is used for representing two-dimensional documents in a manner independent of the application software, hardware, and operating system.... )
Portable Document Format is a file format created by Adobe Systems in 1993 for document exchange. PDF is used for representing two-dimensional documents in a manner independent of the application software, hardware, and operating system.... )
Portable Document Format is a file format created by Adobe Systems in 1993 for document exchange. PDF is used for representing two-dimensional documents in a manner independent of the application software, hardware, and operating system.... )
L. Allison, ''''
Chris Barker, ''''
Georg P. Loczewski,
Bret Victor, ''''
'''' on
''''
a simple yet powerful pure calculus interpreter
Mike Thyer, , a graphical Java applet demonstrating alternative reduction strategies.
