Lambda Calculus (also written as𝜆-calculus)
- is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution
- is a universal model of computation that can be used to simulate any Turing machine
- it was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics
Introduction
Syntax & Semantics
Lambda calculus consists of constructing lambda terms and performing reduction operations on them. In the simplest form of lambda calculus, terms are built using only the following rules:
|
Syntax |
Name |
Description |
|---|---|---|
|
𝑥 |
Variable |
A character or string representing a parameter or mathematical/logical value. |
|
(𝜆𝑥.𝑀) |
Abstraction |
A function definition (𝑀 is a lambda term). The variable 𝑥 becomes bound in the expression. |
|
(𝑀 𝑁) |
Application |
Applying a function to an argument. 𝑀 and 𝑁 are lambda terms. |
producing expressions such as: (𝜆𝑥.𝜆𝑦.(𝜆𝑧.(𝜆𝑥.𝑧 𝑥) (𝜆𝑦.𝑧 𝑦)) (𝑥 𝑦)). Parentheses can be dropped if the expression is unambiguous. For some applications, terms for logical and mathematical constants and operations may be included.
The reduction operations include:
|
Operation |
Name |
Description |
|---|---|---|
|
(𝜆𝑥.M[𝑥]) → (𝜆𝑦.𝑀[𝑦]) |
𝛼-conversion |
Renaming the bound variables in the expression. Used to avoid name collisions. |
|
((𝜆𝑥.𝑀) 𝐸) → (𝑀[𝑥 := 𝐸]) |
𝛽-reduction |
Replacing the bound variables with the argument expression in the body of the abstraction. |
If De Bruijn indexing is used, then α-conversion is no longer required as there will be no name collisions. If the repeated application of the reduction steps eventually terminates, then by the Church–Rosser theorem it will produce a 𝛽-normal form.
Variable names are not needed if using a universal lambda function, such as Iota and Jot, which can create any function behavior by calling it on itself in various combinations.
Examples
Assume TRUE and FALSE are encoded in the following way:
- TRUE = 𝜆𝑥.𝜆𝑦. 𝑥
- FALSE = 𝜆𝑥.𝜆𝑦. 𝑦
NOT can be encoded the following way:
- NOT = 𝜆𝑥. 𝑥 FALSE TRUE
For example, given 𝑥 = TRUE, then:
- (𝜆𝑥. 𝑥 FALSE TRUE) TRUE
- TRUE FALSE TRUE
- 𝜆𝑥.𝜆𝑦. 𝑥 FALSE TRUE
- FALSE
AND and OR can be encoded in the following ways:
- AND = 𝜆𝑥.𝜆𝑦. 𝑥 𝑦 FALSE
- OR = 𝜆𝑥.𝜆𝑦. 𝑥 𝑦 𝑦