## Quick Reference

A formalism for representing functions and ways of combining functions, invented around 1930 by the logician Alonzo Church. The following are examples of λ-expressions:

λ*x*.*x* denotes the **identity function**, which simply returns its argument;

λ*x*.*c* denotes the **constant function**, which always returns the constant *c* regardless of its argument;

λ*x*.*f*(*f*(*x*) denotes the composition of the function *f* with itself, i.e. the function that, for any argument *x*, returns *f*(*f*(*x*).

Much of the power of the notation derives from the ability to represent higher-order functions. For example, λ*f*.λ*x*.*f*(*f*(*x*) denotes the (higher-order) function that, when applied to a function *f*, returns the function obtained by composing *f* with itself.

λ*f*.λ*x*.*f*(*f*(*x*)

As well as a notation, the λ-calculus comprises rules for **reducing** λ-expressions to equivalent ones. The most important is the rule of β-**reduction**, by which an expression of the form (λ*x.e*_{1})(*e*_{2}) reduces to *e*_{1} with all free occurrences of *x* replaced by *e*_{2}. For example, (λ*x.f*(λ*x.x,x*)(*a*) reduces to *f*(λ*x.x,a*) As a second example, involving a functional variable, the expression (λ*f.f*(*a*)(λ*x.g*)(*x,b*) reduces to (λ*x.g*(*x,b*)(*a*) and hence to *g*(*a,b*)

(λ*x.e*_{1})(*e*_{2})

(λ*x.f*(λ*x.x,x*)(*a*)

*f*(λ*x.x,a*)

(λ*f.f*(*a*)(λ*x.g*)(*x,b*)

(λ*x.g*(*x,b*)(*a*)

*g*(*a,b*)

In theoretical terms, the formalism of λ-calculus can be shown to be equivalent in expressive power to that of Turing machines. It has a special role in the study of programming languages: one can point to its influence on the design of functional languages such as J. McCarthy's Lisp; to P. Landin's reduction of Algol 60 to λ-calculus, and to D. Scott's construction of a set-theory meaning for the full unrestricted λ-calculus — a construction that ushered in the theory of domains in the denotational semantics of programming languages.

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.