Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics.

Lambda calculus consists of constructing lambda terms and performing reduction operations on them. In the simplest form of lambda calculus, terms are built using only the following rules:^[a]

1. ${\textstyle x}$: A variable is a character or string representing a parameter.
2. ${\textstyle (\lambda x.M)}$: A lambda abstraction is a function definition, taking as input the bound variable ${\displaystyle x}$ (between the λ and the punctum/dot .) and returning the body ${\textstyle M}$.
3. ${\textstyle (M\ N)}$: An application, applying a function ${\textstyle M}$ to an argument ${\textstyle N}$. Both ${\textstyle M}$ and ${\textstyle N}$ are lambda terms.

The reduction operations include:

• ${\textstyle (\lambda x.M)\rightarrow (\lambda y.M)}$ : α-conversion, renaming the bound variables in the expression. Used to avoid name collisions.
• ${\textstyle ((\lambda x.M)\ N)\rightarrow (M)}$ : β-reduction,^[b] replacing the bound variables with the argument expression in the body of the abstraction.

If De Bruijn indexing is used, then α-conversion is no longer required as there will be no name collisions. If repeated application of the reduction steps eventually terminates, then by the Church–Rosser theorem it will produce a β-normal form.

Variable names are not needed if using a universal lambda function, such as Iota and Jot, which can create any function behavior by calling it on itself in various combinations.

Explanation and applications

Lambda calculus is Turing complete, that is, it is a universal model of computation that can be used to simulate any Turing machine.^[3] Its namesake, the Greek letter lambda (λ), is used in lambda expressions and lambda terms to denote binding a variable in a function.

Lambda calculus may be untyped or typed. In typed lambda calculus, functions can be applied only if they are capable of accepting the given input's "type" of data. Typed lambda calculi are weaker than the untyped lambda calculus, which is the primary subject of this article, in the sense that typed lambda calculi can express less than the untyped calculus can. On the other hand, typed lambda calculi allow more things to be proven. For example, in the simply typed lambda calculus it is a theorem that every evaluation strategy terminates for every simply typed lambda-term, whereas evaluation of untyped lambda-terms need not terminate (see below). One reason there are many different typed lambda calculi has been the desire to do more (of what the untyped calculus can do) without giving up on being able to prove strong theorems about the calculus.

Lambda calculus has applications in many different areas in mathematics, philosophy,^[4] linguistics,^[5][6] and computer science.^{[7] [8]} Lambda calculus has played an important role in the development of the theory of programming languages. Functional programming languages implement lambda calculus. Lambda calculus is also a current research topic in category theory.^[9]

History

Lambda calculus was introduced by mathematician Alonzo Church in the 1930s as part of an investigation into the foundations of mathematics.^[10][c] The original system was shown to be logically inconsistent in 1935 when Stephen Kleene and J. B. Rosser developed the Kleene–Rosser paradox.^[11][12]

Subsequently, in 1936 Church isolated and published just the portion relevant to computation, what is now called the untyped lambda calculus.^[13] In 1940, he also introduced a computationally weaker, but logically consistent system, known as the simply typed lambda calculus.^[14]

Until the 1960s when its relation to programming languages was clarified, the lambda calculus was only a formalism. Thanks to Richard Montague and other linguists' applications in the semantics of natural language, the lambda calculus has begun to enjoy a respectable place in both linguistics^[15] and computer science.^[16]

Origin of the λ symbol

There is some uncertainty over the reason for Church's use of the Greek letter lambda (λ) as the notation for function-abstraction in the lambda calculus, perhaps in part due to conflicting explanations by Church himself. According to Cardone and Hindley (2006):

By the way, why did Church choose the notation “λ”? In he stated clearly that it came from the notation “${\displaystyle {\hat {x}}}$” used for class-abstraction by Whitehead and Russell, by first modifying “${\displaystyle {\hat {x}}}$” to “${\displaystyle \land x}$” to distinguish function-abstraction from class-abstraction, and then changing “${\displaystyle \land }$” to “λ” for ease of printing.

This origin was also reported in . On the other hand, in his later years Church told two enquirers that the choice was more accidental: a symbol was needed and λ just happened to be chosen.

Dana Scott has also addressed this question in various public lectures.^[17] Scott recounts that he once posed a question about the origin of the lambda symbol to Church's former student and son-in-law John W. Addison Jr., who then wrote his father-in-law a postcard:

Dear Professor Church,

Russell had the iota operator, Hilbert had the epsilon operator. Why did you choose lambda for your operator?

According to Scott, Church's entire response consisted of returning the postcard with the following annotation: "eeny, meeny, miny, moe".

Informal description

Motivation

Computable functions are a fundamental concept within computer science and mathematics. The lambda calculus provides simple semantics for computation which are useful for formally studying properties of computation. The lambda calculus incorporates two simplifications that make its semantics simple. The first simplification is that the lambda calculus treats functions "anonymously;" it does not give them explicit names. For example, the function

${\displaystyle \operatorname {square\_sum} (x,y)=x^{2}+y^{2}}$

can be rewritten in anonymous form as

${\displaystyle (x,y)\mapsto x^{2}+y^{2}}$

(which is read as "a tuple of x and y is mapped to ${\textstyle x^{2}+y^{2}}$").^[d] Similarly, the function

${\displaystyle \operatorname {id} (x)=x}$

can be rewritten in anonymous form as

${\displaystyle x\mapsto x}$

where the input is simply mapped to itself.^[d]

The second simplification is that the lambda calculus only uses functions of a single input. An ordinary function that requires two inputs, for instance the ${\textstyle \operatorname {square\_sum} }$ function, can be reworked into an equivalent function that accepts a single input, and as output returns another function, that in turn accepts a single input. For example,

${\displaystyle (x,y)\mapsto <!--\; \mapsto \; -->x^2+}$Zdroj:https://en.wikipedia.org?pojem=Lambda_calculus
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---