$\lambda$ -calculus is known as the world’s tiniest universal programming language that adopts the functional programming paradigm.

When I first learned its concepts, I was frustrated about the formulas and iterative variable substitutions. I also felt hard to understand how some fundamental functions (such as successor, logical) were derived.

After digging more into it, I realized $\lambda$ -calcus shared the same spirit with many other languages (in fact, $\lambda$ served as the foundation for many other languages) that support functional programming paradigm, such as Python. It used a minimal subset of concepts from the other modern languages while it was ensured to be Turing complete.

Let’s first review some basic concepts of $\lambda$ -calculus.

Basic concepts of $\lambda$ -calculus

In short, $\lambda$ -calculus is all about operations (a.k.a functions). All other concepts in a programming languages (such as numbers, conditional logics, and bools) are built upon functions. I somehow tasted a flavor of minimalism for the inventor of this language.

The core idea of $\lambda$ -calculus is that by defining several fundamental operations (a.k.a functions) properly, we can gradually build the whole world layer by layer using these fundamental functions*. This is exactly the spirit of functional programming that is applied to an extreme extent.

Please review the introductory material to understand the following examples.

variable or name: a representation of function, or application. It usually is a mathmatical symbol, such as $\theta$ .
function: the implementation of function using variables. It follows a formula pattern as below.

\lambda <variables>.<variables>|<applications>

application: the calling of function on some other variables. It follows a formula pattern as below.

<variable><variable>

Some classic examples

numbers as functions

$0 \equiv \lambda sz.z$

$1 \equiv \lambda sz.s(z)$

$n \equiv \lambda sz.s(s(..(s(z))..))$
bools as functions

$T \equiv \lambda xy.x$

$F \equiv \lambda xy.y$
conditional logic as functions

$ifelse \equiv \lambda cxy.cxy$

These functions look like magics at the first glance. To reveal the insight, this tutorial will walk you through their underlying meanings, and the perceptual process to derive these formulas, and ultimately provide their Python implementations to help you understand.

Python implementation of $\lambda$ -calculus

We have to now change our mindsets to discard any unnecessary concepts in python, such as operators, strings, bool, numbers, if, while and etc. The only keyword we can use is basically lambda. And this is exactly where the name of lambda function originates from.

Arithmetic

Let’s think about Numbers first. How can we define a number as function? Numbers are just symbols with an order, therefore it certainly can be functions, as long as the functions have some sort of order.

With the concept of order in mind, we now can treat a number as the transformation of another number. In formula, it becomes,

n = f(m)

Where $n, m$ are different numbers.

Let’s try more, what if we want to get a third number from $m$ by using $n$ as an intermediator.

l = g(n) = g(f(m))

Hooray, now number $l$ is a second-order function of $m$ . One can think of a more convenient way, what if $g=f$ ? Now we have a more elegant definition of numbers.

Given the origin of numbers $0$ (think it as a variable), and a consistent transformer function $S$ that transforms a number to its adjacent counterpart, the next number $1$ (think it as a variable) may be defined as,

1 = S(0)

Then

2 = S(1)

And so on,

Substitute them only using $S$ and $0$ , we can get a $n$ th-order function for number $n$ ,

n = S(S..S(0)))

Now the format becomes closer to the formula we’ve seen before in previous section, writing as a function in pseudocode,

function n (S, 0):
    return S(S(..S(0)))

This is exactly the same with the formula in the previous section.

number functions $0, 1, ..., n$ in Python

Input code

# a function representing the fundamental operation: number zero.
# The real meaning of this function is it always return the second parameter.
zero = lambda s: lambda zero: zero

# The real meaning of function one is it applies function s to the second parameter __once__.
one = lambda s: lambda zero: s(zero)

# The real meaning of function two is it applies function s to the second parameter __twice__.
two = lambda s: lambda zero: s(s(zero))

three = lambda s: lambda zero: s(s(s(zero)))

It is important to also understand the real meanings of number functions zero, one, two. In the above derivation, we assumed function s is a transformer function between two numbers. But in reality, s could be any function. Here we use a function plus_one for test purpose, meaning it will add 1 to an input number. Input code

plus_one = lambda x: x + 1

Applying function zero to any other functions would result in an identity function $\lambda x.x$ . Input code

identity = zero(plus_one)
identity(0), identity(1)

Output results

(0, 1)

Applying function one to another function x would result in a function that will apply function x once to the input. Input code

plus_one_once = one(plus_one)
plus_one_once(0), plus_one_once(1)

Output results

(1, 2)

Applying function two to another function x would result in a function that will apply function x twice to the input. Input code

plus_one_twice = two(plus_one)
plus_one_twice(0), plus_one_twice(1)

Output results

(2, 3)

Similarly, applying function n to another function x would result in a function that will apply function x n times to the input.

successor function $S$ in Python

We’ve used the $S$ without defining it in the number functions, because we don’t have to transform a number to another in the examples above. Now, we will explore to define $S$ . Let’s first analyze the role of successor $S$ in terms of the functionality it represents. Literally, it means transforming a number function n so that n applies function s one more time than n to the input m. Let’s first define a function that applies s n times, which according to the meaning of number function, would be,

n(s)

Let’s then apply this function to another input m,

n(s)(m)

Now we need to apply s one more time,

s(n(s)(m))

Or

n(s)(s(m))

Hooray, we’ve got the successor function

S

now, writing as a function formula,

S(n, s, m): s(n(s)(m))

In Python, we can easily define this function with lambda, Input code

successor = lambda n: (lambda s: lambda m: s(n(s)(m)))

Now, let’s test the successor function using number functions and plus_one. Input code

# the successor of function one should be function two named as `new_two`
new_two = successor(one)

Input code

new_plus_one_twice = new_two(plus_one)
original_plus_one_twice = two(plus_one)
# The new function `two` and the original function `two` are the same
new_plus_one_twice(100) == original_plus_one_twice(100)

Output results

True

Input code

new_three = successor(two)
new_plus_one_triple_times = new_three(plus_one)
new_plus_one_triple_times(100)

Output results

We can also chain the function successor to get later number functions. Input code

# applying successor three times on number function `zero` to get number function `three`
new_three = successor(successor(successor(zero)))
new_plus_one_triple_times = new_three(plus_one)
new_plus_one_triple_times(100)

Output results

Based on functions zero and successor, more complex arithmetic functions such as add, mimus, predecessor, multiple, divide may be defined.

predecessor function $P$ in Python

Predecessor function can be derived using only functions successor and zero (Note that it is impossible to define all number functions from zero to infinite numbers n, we have to rely on successor and predecessor given an arbitrary number function n).

The predecessor of number function $n = \lambda sz.s(...s(z))$ may be literally described as,

Transform function n so that it applies function s one less time to variable z.

Because we only have access to function zero, n and successor function, we cannot go back from function n to n-1. But instead, going forward from zero using successor to n, while preserving the status of previous number n-1 in the process.

To achieve that, we can consider using two variables, as a pair, one stores the current number function n and the previous stores the previous number function n-1.

(n, n-1)

We start from the pair of zero function and its predecessor, which is assumed to be also zero.

(0, 0)

And apply the successor function $S$ to the first variable in the pair,

S(0)

Create a new pair using this new variable and the original variable,

(S(0), 0) = (1, 0)

Apply this repeatatively,

(S(S(0)), S(0)) = (S(1), 1) = (2, 1)

For n times,

(S(S(..S(0)))), S(..S(0))) = (n, n-1)

Then get the second variable as the predecessor of function n.

We can divide the process into three fundamental functions.

Pair function $p$ : that accepts two variables and apply a function to the two variables.
Selector function $T$ and $F$ : $T$ accepts two variables and returns the first one and $F$ accepts two variables and returns the second one.
Pair successor function $\theta$ : that accepts a pair function with variables $a$ and $b$ and transforms it into a new pair where the first element is the successor of a and the second element is a.

Then we will use the three fundamental functions to form the predecessor function.

Pair function $p$

Literally, pair function means applying function z to two variables a and b.

p = \lambda z.zab

In Python, it becomes, Input code

pair = lambda a: lambda b: lambda z: z(a)(b)

Input code

# this means applying successor to one and two sequentially

one_and_plus_one_pair = pair(one)(plus_one)
zero_and_plus_one_pair = pair(zero)(plus_one)

plus_one_twice = one_and_plus_one_pair(successor)
plus_one_once = zero_and_plus_one_pair(successor)
plus_one_twice(0), plus_one_once(0)

Output results

(2, 1)

Selector functions: $T$ and $F$

Selector functions mean that the function can select the first or second element between two variables.

T = \lambda xy.x

F = \lambda xy.y

In Python, they become, Input code

first = lambda x: lambda y: x
second = lambda x: lambda y: y

Input code

plus_one_once = first(one)(two)(plus_one)

# or
plus_one_twice = second(one)(two)(plus_one)

plus_one_once(0), plus_one_twice(0)

Output results

(1, 2)

Combining selector and pair function, we can have functions to extract the first or second element in a pair. Input code

one_two_pair = pair(one)(two)
new_one = one_two_pair(first)
new_two = one_two_pair(second)
plus_one_once = new_one(plus_one)
plus_one_twice = new_two(plus_one)

plus_one_once(0), plus_one_twice(0)

Output results

(1, 2)

Pair successor function $\theta$

$\theta$ function transforms a pair to a new pair where the first element is the successor of the first element of the original pair, and second pair is the first element of the original pair.

\theta = \lambda pz.z(S(pT))(pT)

The result function would also be a pair function.

In Python, Input code

theta = lambda p: lambda z: pair(successor(p(first)))(p(first))(z)

Input code

successor_of_first_and_original_first_pair = theta(pair(zero)(zero))
new_one = successor_of_first_and_original_first_pair(first)
new_zero = successor_of_first_and_original_first_pair(second)
new_one(plus_one)(0), new_zero(plus_one)(0)

Output results

(1, 0)

Predecessor

Now we have all building blocks theta, pair, first and second functions. We may define the predecessor function as following according to the iterative derivation before,

P = \lambda n.n(\theta)(p00)F

We first apply $\theta$ $n$ times,

n(\theta)

Then apply this function to the pair of zero and zero,

n(\theta)(p00)

Now we get $(n, n-1)$ , to select $n-1$ , we apply this pair function to selector function $F$ to get the second element,

n(\theta)(p00)F

Or in Python as, Input code

predecessor = lambda n: n(theta)(pair(zero)(zero))(second)

Input code

new_zero = predecessor(zero)
new_zero_from_one = predecessor(one)
new_one = predecessor(two)
new_two = predecessor(three)

new_zero(plus_one)(1), new_zero_from_one(plus_one)(1), new_one(plus_one)(1), new_two(plus_one)(1)

Output results

(1, 1, 2, 3)

Addition $A$ and subtraction $M$ functions in Python

Addition function $A$

Given two number functions $n$ and $m$ , the addition function $A$ might be interpreted as applying successor function $S$ $n$ times to $m$ .

Therefore, we can have,

n + m := nSm

As an additional function,

A := \lambda nm.nSm

In Python, we can have, Input code

add = lambda n: lambda m: n(successor)(m)

Similarly, we use function plus_one for testing. Input code

five = add(two)(three)
plus_one_five_times = five(plus_one)
plus_one_five_times(0)

Output results

Subtraction function $M$

In similar way, given two number functions $n$ and $m$ , the subtraction function $M$ might be interpreted as applying predecessor function $P$ $m$ times to $n$ .

Therefore, we can have,

n - m := mPn

As an additional function,

M := \lambda nm.mPn

In Python, we can have, Input code

subtract = lambda n: lambda m: m(predecessor)(n)

Similarly, we use function plus_one for testing. Input code

# 3 - 2
one = subtract(three)(two)
plus_one_once = one(plus_one)
plus_one_once(0)

Output results

Input code

# 2 - 3, because we didn't define negative numbers, this will result in zero function, 
# which voids the applied function.
zero = subtract(two)(three)
do_nothing = zero(plus_one)
do_nothing(3) == 3

Output results

True

Multiplication function $T$ in Python

We will defer the discussion of division function $D$ to the next post (about conditional), because we need to use conditional functions.

For multiplication function, assume two number functions $n$ and $m$ , $n \times m$ might be interpreted as applying function $P$ $m$ times first to get a function that can be applied again $n$ times, and then applying this function to successor function $S$ on number function $0$ to get the final number function $m \times n$ .

In equation,

m \times n := n(m(S))(0)

In a compact way,

T := \lambda nm.n(mS)0

In Python, Input code

multiply = lambda n: lambda m: n(m(successor))(zero)

Use function plus_one for testing. Input code

# 2 x 3
six = multiply(two)(three)
plus_one_six_times = six(plus_one)
plus_one_six_times(0)

Output results

Input code

# 0 x 3
zero_new = multiply(zero)(three)
do_nothing = zero_new(plus_one)
do_nothing(2) == 2

Output results

True