Lambda calculus

In <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>, lambda calculus (also written as λ-calculus) is a <a href="/facts/Formal_system/KaeDAjK7">formal system</a> for expressing <a href="/facts/Computability/VpnJUkPN">computation</a> based on function <a href="/facts/Abstraction_(computer_science)/hAnxmJle">abstraction</a> and <a href="/facts/Function_application/p4auE0QF">application</a> using variable <a href="/facts/Name_binding/HbBx9mpM">binding</a> and <a href="/facts/Substitution_(algebra)/GwWdQf0m">substitution</a>. Untyped lambda calculus, the topic of this article, is a <a href="/facts/Universal_machine/2klpb1qQ">universal machine</a>, a <a href="/facts/Model_of_computation/nJr8mHSI">model of computation</a> that can be used to simulate any <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> (and vice versa). It was introduced by the mathematician <a href="/facts/Alonzo_Church/b7D52Itv">Alonzo Church</a> in the 1930s as part of his research into the <a href="/facts/Foundations_of_mathematics/yjpbbUkt">foundations of mathematics</a>. In 1936, Church found a formulation which was logically consistent, and documented it in 1940.
Lambda calculus consists of constructing lambda terms and performing reduction operations on them. A term is defined as any valid lambda calculus expression. In the simplest form of lambda calculus, terms are built using only the following rules:

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

<ul><li>
 
 
 
 (
 λ
 x
 .
 M
 [
 x
 ]
 )
 →
 (
 λ
 y
 .
 M
 [
 y
 ]
 )
 
 
 {\textstyle (\lambda x.M[x])\rightarrow (\lambda y.M[y])}
 
 : α-conversion, renaming the bound variables in the expression. Used to avoid <a href="/facts/Name_collision/ktvJfzBB">name collisions</a>.</li>
<li>
 
 
 
 (
 (
 λ
 x
 .
 M
 )
  
 N
 )
 →
 (
 M
 [
 x
 :=
 N
 ]
 )
 
 
 {\textstyle ((\lambda x.M)\ N)\rightarrow (M[x:=N])}
 
 : β-reduction, replacing the bound variables with the argument expression in the body of the abstraction.</li></ul>
If <a href="/facts/De_Bruijn_index/MCN7dhr5">De Bruijn indexing</a> is used, then α-conversion is no longer required as there will be no name collisions. If <a href="/facts/Reduction_strategy_(lambda_calculus)/JIK9F4cb">repeated application</a> of the reduction steps eventually terminates, then by the <a href="/facts/Church%E2%80%93Rosser_theorem/dkfn5o4K">Church–Rosser theorem</a> it will produce a <a href="/facts/Beta_normal_form/6vX3NEte">β-normal form</a>.
Variable names are not needed if using a universal lambda function, such as <a href="/facts/Iota_and_Jot/n4mzYfIz">Iota and Jot</a>, which can create any function behavior by calling it on itself in various combinations.

Lambda calculus open-in-new

Lambda calculus