鈽濓笍 Back to top

Understand 饾渾-calculus with Python

nbviewer

\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.

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

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

<variable><variable><variable><variable>

, or

<variable>(<variable>)<variable>(<variable>)

Some classic examples

  1. numbers as functions

    0sz.z0 \equiv \lambda sz.z

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

    nsz.s(s(..(s(z))..))n \equiv \lambda sz.s(s(..(s(z))..))

  2. bools as functions

    Txy.xT \equiv \lambda xy.x

    Fxy.yF \equiv \lambda xy.y

  3. conditional logic as functions

    ifelsecxy.cxyifelse \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) n = f(m)

Where n,mn, m are different numbers.

Let's try more, what if we want to get a third number from mm by using nn as an intermediator.

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

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

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

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

Then

2=S(1)2 = S(1)

And so on,

Substitute them only using SS and 00, we can get a nnth-order function for number nn,

n=S(S..S(0)))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,...,n0, 1, ..., n in Python

# 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.

plus_one = lambda x: x + 1

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

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

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

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

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

plus_one_twice = two(plus_one)
plus_one_twice(0), plus_one_twice(1)
(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 SS in Python

We've used the SS 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 SS.

Let's first analyze the role of successor SS 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)n(s)

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

n(s)(m)n(s)(m)

Now we need to apply s one more time,

s(n(s)(m))s(n(s)(m))

Or

n(s)(s(m))n(s)(s(m))

Hooray, we've got the successor function SS now, writing as a function formula,

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

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

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

Now, let's test the successor function using number functions and plus_one.

# the successor of function one should be function two named as `new_two`
new_two = successor(one)
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)
True
new_three = successor(two)
new_plus_one_triple_times = new_three(plus_one)
new_plus_one_triple_times(100)
103

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

# 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)
103

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

predecessor function PP 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=sz.s(...s(z))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,n1) (n, n-1)

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

(0,0) (0, 0)

And apply the successor function SS to the first variable in the pair,

S(0) S(0)

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

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

Apply this repeatatively,

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

For n times,

(S(S(..S(0)))),S(..S(0)))=(n,n1) (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.

  1. Pair function pp: that accepts two variables and apply a function to the two variables.
  2. Selector function TT and FF: TT accepts two variables and returns the first one and FF accepts two variables and returns the second one.
  3. Pair successor function \theta: that accepts a pair function with variables aa and bb 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 pp

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

p=z.zab p = \lambda z.zab

In Python, it becomes,

pair = lambda a: lambda b: lambda z: z(a)(b)
# 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)
(2, 1)

Selector functions: TT and FF

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

T=xy.x T = \lambda xy.x

F=xy.y F = \lambda xy.y

In Python, they become,

first = lambda x: lambda y: x
second = lambda x: lambda y: y
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)
(1, 2)

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

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)
(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.

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

The result function would also be a pair function.

In Python,

theta = lambda p: lambda z: pair(successor(p(first)))(p(first))(z)
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)
(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=n.n()(p00)F P = \lambda n.n(\theta)(p00)F

We first apply \theta nn times,

n()n(\theta)

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

n()(p00)n(\theta)(p00)

Now we get (n,n1)(n, n-1), to select n1n-1, we apply this pair function to selector function FF to get the second element,

n()(p00)Fn(\theta)(p00)F

Or in Python as,

predecessor = lambda n: n(theta)(pair(zero)(zero))(second)
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)
(1, 1, 2, 3)

Addition AA and subtraction MM functions in Python

Addition function AA

Given two number functions nn and mm, the addition function AA might be interpreted as applying successor function SS nn times to mm.

Therefore, we can have,

n+m:=nSm n + m := nSm

As an additional function,

A:=nm.nSm A := \lambda nm.nSm

In Python, we can have,

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

Similarly, we use function plus_one for testing.

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

Subtraction function MM

In similar way, given two number functions nn and mm, the subtraction function MM might be interpreted as applying predecessor function PP mm times to nn.

Therefore, we can have,

nm:=mPn n - m := mPn

As an additional function,

M:=nm.mPn M := \lambda nm.mPn

In Python, we can have,

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

Similarly, we use function plus_one for testing.

# 3 - 2
one = subtract(three)(two)
plus_one_once = one(plus_one)
plus_one_once(0)
1
# 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
True

Multiplication function TT in Python

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

For multiplication function, assume two number functions nn and mm, nmn \times m might be interpreted as applying function PP mm times first to get a function that can be applied again nn times, and then applying this function to successor function SS on number function 00 to get the final number function mnm \times n.

In equation,

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

In a compact way,

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

In Python,

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

Use function plus_one for testing.

# 2 x 3
six = multiply(two)(three)
plus_one_six_times = six(plus_one)
plus_one_six_times(0)
6
# 0 x 3
zero_new = multiply(zero)(three)
do_nothing = zero_new(plus_one)
do_nothing(2) == 2
True

Comments