# Catalogue of Artificial Intelligence Techniques

View Maths as: Images | MathML

## Lambda Calculus

Keywords: alpha conversion, beta reduction, terms

### Categories: Knowledge Representation

Author(s): Alan Smaill

Various formal systems based on that invented by Church to formalise the properties of functions acting on arguments and being combined to form other functions. This involves `lambda-abstraction'. The function $f$ given by:

$f\left(x\right)=x+1$

can be written using lambda-abstraction as:

so that:

$f\left(1\right)=\left(\lambda x.x+1\right)\left(1\right)=2$

Application is written as juxtaposition, e.g., $fx$ for $f\left(x\right)$ . Terms made up using application and lambda abstraction can be manipulated in various ways, e.g., rename bound variables (alpha conversion), and rewrite $\left(\lambda x.fx\right)a$ as $fa$

(beta reduction). Lambda calculus is the formalism that underlies Lisp.

### References:

• Barendregt, H.P., The lambda calculus, its syntax and semantics , North-Holland, Amsterdam and Oxford, 1984 (revised edition ).