Share this page

Learn X in Y minutes

Where X=Lambda Calculus

Lambda Calculus

Lambda calculus (λ-calculus), originally created by Alonzo Church, is the world’s smallest programming language. Despite not having numbers, strings, booleans, or any non-function datatype, lambda calculus can be used to represent any Turing Machine!

Lambda calculus is composed of 3 elements: variables, functions, and applications.

Name Syntax Example Explanation
Variable <name> x a variable named “x”
Function λ<parameters>.<body> λx.x a function with parameter “x” and body “x”
Application <function><variable or function> (λx.x)a calling the function “λx.x” with argument “a”

The most basic function is the identity function: λx.x which is equivalent to f(x) = x. The first “x” is the function’s argument, and the second is the body of the function.

Free vs. Bound Variables:

Evaluation:

Evaluation is done via β-Reduction, which is essentially lexically-scoped substitution.

When evaluating the expression (λx.x)a, we replace all occurences of “x” in the function’s body with “a”.

You can even create higher-order functions:

Although lambda calculus traditionally supports only single parameter functions, we can create multi-parameter functions using a technique called currying.

Sometimes λxy.<body> is used interchangeably with: λx.λy.<body>


It’s important to recognize that traditional lambda calculus doesn’t have numbers, characters, or any non-function datatype!

Boolean Logic:

There is no “True” or “False” in lambda calculus. There isn’t even a 1 or 0.

Instead:

T is represented by: λx.λy.x

F is represented by: λx.λy.y

First, we can define an “if” function λbtf that returns t if b is True and f if b is False

IF is equivalent to: λb.λt.λf.b t f

Using IF, we can define the basic boolean logic operators:

a AND b is equivalent to: λab.IF a b F

a OR b is equivalent to: λab.IF a T b

a NOT b is equivalent to: λa.IF a F T

Note: IF a b c is essentially saying: IF(a(b(c)))

Numbers:

Although there are no numbers in lambda calculus, we can encode numbers using Church numerals.

For any number n: n = λf.fn so:

0 = λf.λx.x

1 = λf.λx.f x

2 = λf.λx.f(f x)

3 = λf.λx.f(f(f x))

To increment a Church numeral, we use the successor function S(n) = n + 1 which is:

S = λn.λf.λx.f((n f) x)

Using successor, we can define add:

ADD = λab.(a S)n

Challenge: try defining your own multiplication function!

For more advanced reading:

  1. A Tutorial Introduction to the Lambda Calculus
  2. Cornell CS 312 Recitation 26: The Lambda Calculus
  3. Wikipedia - Lambda Calculus

Got a suggestion? A correction, perhaps? Open an Issue on the Github Repo, or make a pull request yourself!

Originally contributed by Max Sun, and updated by 0 contributor(s).