Lambda calculus

In mathematical logic, the lambda calculus (also written as λ-calculus) is a formal system for expressing computation based on function abstraction and application using variable binding and substitution.

Uses your system voice; voice and rate in settings.

≈ 13 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematical logic, the lambda calculus (also written as λ-calculus) is a formal system for expressing computation based on function abstraction and application using variable binding and substitution. Untyped lambda calculus, the topic of this article, is a universal machine, i.e. a model of computation that can be used to simulate any Turing machine (and vice versa).

It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. In 1936, Church found a formulation which was logically consistent, and documented it in 1940. The lambda calculus consists of a language of lambda terms, which are defined by a formal syntax, and a set of transformation rules for manipulating those terms.

In BNF, the syntax is e ::= x \mid \lambda x\text{.}e \mid e \, e, where variables x,y,z range over an infinite set of names. Terms M,N,t,s,e,f range over all lambda terms. This corresponds to the following inductive definition: A variable x is a valid lambda term.

An abstraction is a lambda term (\lambda x\text{.}t) where t is a lambda term, referred to as the abstraction's body, and x is the abstraction's parameter variable, An application is a lambda term (t\,s) where t and s are lambda terms. A lambda term is syntactically valid if it can be obtained by repeated application of these three rules.

For convenience, parentheses can often be omitted when writing a lambda term—see for details. Within lambda terms, any occurrence of a variable that is not a parameter of some enclosing \lambda is said to be free.

Any free occurrence of x in a term M is bound in \lambda x\text{.}M . Any free occurrence of any other variable within M remains free in \lambda x\text{.}M . For example, in the term x\,y , both x and y occur free. In (\lambda x\text{.}x\,y) , y is free, but x in the body (i.e. after the dot) is not free, and is said to be bound (to the parameter).

While y is free in (\lambda x\text{.}x\,y) , it is bound in (\lambda y\text{.}\lambda x\text{.} x\,y) . There are two occurrences of x in (\lambda y\text{.} (\lambda x\text{.} x\,y)\, x) – one is bound, and the other is free. \operatorname{FV}(M) is the set of free variables of M , i.e. such variables that occur free in M at least once. It can be defined inductively as follows: \operatorname{FV}(x)=\{x\} \operatorname{FV}(M_1M_2)=\operatorname{FV}(M_1)\cup \operatorname{FV}(M_2) \operatorname{FV}(\lambda x\text{.}M)=\operatorname{FV}(M)\backslash \{x\} The notation M[x := N] denotes capture-avoiding substitution: substituting N for every free occurrence of x in M , while avoiding variable capture.

This operation is defined inductively as follows: x[x := N] = N ; y[x := N] = y if y \ne x . (M_1 M_2)[x := N] = (M_1[x := N]) (M_2[x := N]) . (\lambda y\text{.}M)[x := N] has three cases: If y = x , becomes \lambda x\text{.}M ( x is bound; no change). If y \notin \operatorname{FV}(N) , becomes \lambda y\text{.}(M[x := N]) . If y \in \operatorname{FV}(N) , first α-rename \lambda y\text{.}M to \lambda y'\text{.}(M[y := y']) with y' fresh to avoid name collisions, then continue as above.

It becomes (\lambda y'\text{.}(M[y:=y']))[x:=N] with y'\notin \operatorname{FV}(M)\cup\operatorname{FV}(N) . There are several notions of "equivalence" and "reduction" that make it possible to reduce lambda terms to equivalent lambda terms. α-conversion captures the intuition that the particular choice of a bound variable, in an abstraction, does not (usually) matter. If y \notin \operatorname{FV}(M) , then the terms \lambda x\text{.}M and \lambda y\text{.}M[x := y] are considered alpha-equivalent, written \lambda x\text{.}M \equiv_{\alpha} \lambda y\text{.}M[x := y] . The equivalence relation is the smallest congruence relation on lambda terms generated by this rule.

For instance, \lambda x\text{.}x and \lambda y\text{.}y are alpha-equivalent lambda terms. The β-reduction rule states that a β-redex, an application of the form (\lambda x\text{.}t) s , reduces to the term t [ x := s] . For example, for every s , ( \lambda x \text{.} x ) s \to x[ x := s ] = s . This demonstrates that \lambda x \text{.} x really is the identity.

Similarly, ( \lambda x \text{.} y ) s \to y [ x := s ] = y , which demonstrates that \lambda x \text{.} y is a constant function. η-conversion expresses extensionality and converts between \lambda x \text{.} f x and f whenever x does not appear free in f . It is often omitted in many treatments of lambda calculus. The term redex, short for reducible expression, refers to subterms that can be reduced by one of the reduction rules.

For example, (\lambda x\text{.}M)\,N is a β-redex in expressing the substitution of N for x in M . The expression to which a redex reduces is called its reduct; the reduct of \lambda x\text{.}M\,N is M[x:=N] . \operatorname{square\_sum}(x, y) = x^2 + y^2 can be rewritten in anonymous form as (x, y) \mapsto x^2 + y^2 (which is read as "a tuple of x and y is mapped to x^2 + y^2 "). Similarly, the function \operatorname{id}(x) = x can be rewritten in anonymous form as x \mapsto x where the input is simply mapped to itself.

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 \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, (x, y) \mapsto x^2 + y^2 can be reworked into x \mapsto (y \mapsto (x^2 + y^2)) This method, known as currying, transforms a function that takes multiple arguments into a chain of functions each with a single argument. Function application of the \operatorname{square\_sum} function to the arguments (5, 2), yields at once ((x, y) \mapsto x^2 + y^2)(5, 2) = 5^2 + 2^2 = 29 , whereas evaluation of the curried version requires one more step \Bigl(\bigl(x \mapsto (y \mapsto x^2 + y^2)\bigr)(5)\Bigr)(2) = (y \mapsto 5^2 + y^2)(2) // the definition of x has been used with 5 in the inner expression.

This is like β-reduction. = 5^2 + 2^2 // the definition of y has been used with 2 . Again, similar to β-reduction. = 29 to arrive at the same result. In lambda calculus, functions are taken to be 'first class values', so functions may be used as the inputs, or be returned as outputs from other functions.

For example, the lambda term \lambda x.x represents the identity function, x \mapsto x . Further, \lambda x.y represents the constant function x \mapsto y , the function that always returns y , no matter the input. As an example of a function operating on functions, the function composition can be defined as \lambda f. \lambda g. \lambda x. (f ( g x)) . Now, to perform the recursive call to the factorial function for an argument n, we would simply call .

Given n = 4, for example, this gives: Every recursively defined function can be seen as a fixed point of some suitably defined higher order function (also known as functional) closing over the recursive call with an extra argument. Therefore, using , every recursive function can be expressed as a lambda expression.

In particular, we can now cleanly define the subtraction, multiplication, and comparison predicates of natural numbers, using recursion. When Y combinator is coded directly in a strict programming language, the applicative order of evaluation used in such languages will cause an attempt to fully expand the internal self-application (x x) prematurely, causing stack overflow or, in case of tail call optimization, indefinite looping.

A delayed variant of Y, the Z combinator, can be used in such languages. It has the internal self-application hidden behind an extra abstraction through eta-expansion, as (\lambda v.x x v) , thus preventing its premature expansion: Z = \lambda f.(\lambda x.f (\lambda v.x x v)) \ (\lambda x.f (\lambda v.x x v))\ .

T( , ) := I T( , N) := K N ,     if is not free in N T( , M N) := S T( , M) T( , N) In either case, a term of the form T( ,N) P is reduced by having the initial combinator I, K, or S grab the argument P, just like β-reduction of N P would do. I returns that argument.

K N throws the argument away, just like N does when has no free occurrence in N. S passes the argument on to both subterms of the application, and then applies the result of the first to the result of the second, just like MN is the same as M N . The combinators B and C are similar to S, but pass the argument on to only one subterm of an application (B to the "argument" subterm and C to the "function" subterm), thus saving a subsequent K if there is no occurrence of in one of the subterms. In comparison to B and C, the S combinator actually conflates two functionalities: rearranging arguments, and duplicating an argument so that it may be used in two places.

The W combinator does only the latter, yielding the B, C, K, W system as an alternative to SKI combinator calculus. Adding an additional rule before the last one, T( , N x) := N ,     if is not free in N expresses \eta -reduction, since N x is the same as N  in such a case, and avoids creating the longer sequence S (K N) I. There is no algorithm that takes as input any two lambda expressions and outputs or depending on whether one expression reduces to the other.

More precisely, no computable function can decide the question. This was historically the first problem for which undecidability could be proven. As usual for such a proof, computable means computable by any model of computation that is Turing complete.

In fact computability can itself be defined via the lambda calculus: a function F: N → N of natural numbers is a computable function if and only if there exists a lambda expression f such that for every pair of x, y in N, F(x)=y if and only if f  = β   , where and are the Church numerals corresponding to x and y, respectively and = β meaning equivalence with β-reduction. See the Church–Turing thesis for other approaches to defining computability and their equivalence.

Church's proof of uncomputability first reduces the problem to determining whether a given lambda expression has a normal form. 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 that closely follows the proof of Gödel's first incompleteness theorem. If is applied to its own Gödel number, a contradiction results. (lambda x: x**2) The above example is an expression that evaluates to a first-class function.

The symbol lambda creates an anonymous function, given a list of parameter names—just the single argument x , in this case—and an expression that is evaluated as the body of the function, x**2 . Anonymous functions are sometimes called lambda expressions.

Pascal and many other imperative languages have long supported passing subprograms as arguments to other subprograms through the mechanism of function pointers. However, function pointers are an insufficient condition for functions to be first class datatypes, because a function is a first class datatype if and only if new instances of the function can be created at runtime.

Such runtime creation of functions is supported in Smalltalk, JavaScript, Wolfram Language, and more recently in Scala, Eiffel (as agents), C# (as delegates) and C++11, among others. Landin, Peter, A Correspondence Between ALGOL 60 and Church's Lambda-Notation, Communications of the ACM, vol. 8, no. 2 (1965), pages 89–101. Available from the ACM site.

A classic paper highlighting the importance of lambda calculus as a basis for programming languages. Larson, Jim, An Introduction to Lambda Calculus and Scheme. A gentle introduction for programmers.

Early life

Schalk, A. and Simmons, H. (2005) An introduction to λ-calculi and arithmetic with a decent selection of exercises. Notes for a course in the Mathematical Logic MSc at Manchester University.

A paper giving a formal underpinning to the idea of 'meaning-is-use' which, even if based on proofs, it is different from proof-theoretic semantics as in the Dummett–Prawitz tradition since it takes reduction as the rules giving meaning. Hankin, Chris, An Introduction to Lambda Calculi for Computer Scientists, Monographs/textbooks for graduate students: Sørensen, Morten Heine and Urzyczyn, Paweł (2006), Lectures on the Curry–Howard isomorphism, Elsevier, is a recent monograph that covers the main topics of lambda calculus from the type-free variety, to most typed lambda calculi, including more recent developments like pure type systems and the lambda cube.

It does not cover subtyping extensions. covers lambda calculi from a practical type system perspective; some topics like dependent types are only mentioned, but subtyping is an important topic. Documents A Short Introduction to the Lambda Calculus-(PDF) by Achim Jung A timeline of lambda calculus-(PDF) by Dana Scott A Tutorial Introduction to the Lambda Calculus-(PDF) by Raúl Rojas Lecture Notes on the Lambda Calculus-(PDF) by Peter Selinger Graphic lambda calculus by Marius Buliga Lambda Calculus as a Workflow Model by Peter Kelly, Paul Coddington, and Andrew Wendelborn; mentions graph reduction as a common means of evaluating lambda expressions and discusses the applicability of lambda calculus for distributed computing (due to the Church–Rosser property, which enables parallel graph reduction for lambda expressions).

Graham Hutton, Lambda Calculus, a short (12 minutes) Computerphile video on the Lambda Calculus Helmut Brandl, Step by Step Introduction to Lambda Calculus David C. Keenan, To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reduction L. Allison, Some executable λ-calculus examples Georg P. Loczewski, The Lambda Calculus and A++ Bret Victor, Alligator Eggs: A Puzzle Game Based on Lambda Calculus LCI Lambda Interpreter a simple yet powerful pure calculus interpreter Lambda Calculus links on Lambda-the-Ultimate Mike Thyer, Lambda Animator, a graphical Java applet demonstrating alternative reduction strategies. Implementing the Lambda calculus using C++ Templates Shane Steinert-Threlkeld, "Lambda Calculi", Internet Encyclopedia of Philosophy Anton Salikhmetov, Macro Lambda Calculus

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375757475 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001375757475 · captured 2026-09-19 · ledger · version history

Cite this page as: encyclopegia.org, “Lambda calculus”, snapshot enwiki-001375757475. https://encyclopegia.org/a/lambda-calculus

Sources cited in this revision

27 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.