Learning path

Full curriculum

Full curriculum

Unit content

Beta reduction and normal forms

A lambda-calculus function call is modeled by beta reduction. When an abstraction is applied to an argument,

$$(\lambda x.e)\ v \to_\beta e[v/x],$$

the argument replaces the function's bound parameter using capture-avoiding substitution.

For example,

$$(\lambda x.x\ x)(\lambda y.y)$$

reduces first to

$$(\lambda y.y)(\lambda y.y)$$

and then to $\lambda y.y$.

An expression of the form $(\lambda x.e)\ v$ is a beta redex: a reducible expression. An expression containing no beta redex is in beta-normal form.

Not every term has a normal form. The self-application

$$\Omega=(\lambda x.x\ x)(\lambda x.x\ x)$$

reduces back to itself forever.

A term can also contain several redexes, so reduction may have choices. The lambda calculus is confluent: if a term can reduce along different paths to normal forms, those normal forms agree up to alpha-equivalence. Confluence does not guarantee termination, but it means reduction order does not create two incompatible final answers when a normal form is reached.