## The Quest for Minimalism

Over the ages, scientific brains of various domains have been working hard to minimize the number of principles or concepts that lie at the core of their scientific theories.

For instance, in physics, we have the four fundamental interactions that explain every physical phenomenon. In chemistry, the periodic table of elements enumerates the ninety-eight elements that are the building blocks of any matter that appear naturally on earth. All the mathematics can be expressed in the language of set theory and built on top of nine axioms stated by Zermelo and Fraenkel.

In the context of this scientific quest for minimalism, it is natural to ask ourselves, as developers, what is the minimal number of concepts that are required as the foundation of programming?

One possible answer to this question is given by the lambda calculus, a beautiful mathematical theory introduced by Alonozo Church in the 1930s.

In this article, we will see that the answer the lambda calculus gives is that we need only two basic concepts to build all the programming, namely:

- Function definition
- Function application

By a function, we mean a single argument anonymous function.

In order to feel the impact of this answer, we need to clarify that most of the basic concepts of programming languages are not part of the lambda calculus. Basic concepts like numbers, booleans, lists, if statements, function names, multi-argument functions, recursive functions...in fact, all those concepts can be built on top of the lambda calculus, which means that they are not part of the foundations of programming.

## Lambda Calculus in a Nutshell

The original notation for functions in lambda calculus is a bit cryptic. In this article, we are going to use JavaScript arrow function notation to discuss lambda calculus.

In lambda calculus, everything is a single-argument anonymous function. For instance, here is the identity function, an anonymous function that receives an single argument named `x`

and returns it:

```
x => x
```

In lambda calculus, functions are first-class citizens, which means that functions can return functions and that functions can be passed as arguments to other functions.

For instance, here is a function that receives an argument named `x`

and returns a function that constantly returns `x`

:

```
x => (y => x)
```

The only thing that we can do with functions is to apply them on an argument. The argument itself is always a function, because in lambda calculus, everything is a function.

For instance, here is how it looks like to apply the identity function to a unbound variable `z`

:

```
(x => x)(z)
```

A fun thing is that we can apply a function to itself:

```
(x => x)(x => x)
```

and the result is:

```
x => x
```

It's quite unexpected that such a simple language with only single-argument anonymous functions is in fact as powerful as any other programming language. It has been rigorously proven that every piece of any programming language can be "encoded" in lambda calculus. If you are curious and want to learn more about how basic programming concepts are encoded in lambda calculus, be sure to read this succinct but excellent [Introduction to Lambda Calculus (pdf). Among other interesting things, you will learn about Church encoding and how it encodes numbers via Church numerals.

To me, the most incredible aspect of lambda calculus is that it shows us that it is possible to create recursive functions without needing to name functions.

Isn't it mind-blowing?

## Recursion Without Names

Take a moment and think about the way you wrote a recursive function that you wrote in any programming language---for instance, the factorial function. The code of the function refers to the function itself by its own name. For example, here is how I write the factorial function in JavaScript:

```
fact = (n => ((n === 0) ? 1 : n * fact(n - 1)))
```

Referring to the function by its name in the body of the function seems unavoidable. Right?

Well, in lambda calculus, functions have no names. However, as surprising as it might look, it appears that it is possible to write recursive functions without names.

This magic is made possible via an amazing construct called the `Y combinator`

.

Like everything in lambda calculus, the Y combinator is a single-argument anonymous function, and here is its definition:

```
Y =
f =>
(x =>
y => f(x(x))(y))
(x =>
y => f(x(x))(y))
```

At this point, it is not critical to understand the meaning of this definition.

The importance of the Y combinator relies on the fact that it can generate what we call a *fixed point* of any function.

A fixed point of a function `f`

is a point `g`

such that: `f(g)`

equals `g`

.

For example, `0`

is a fixed point of the `square`

function because `0^2`

equals `0`

.

Also, `1`

is a fixed point of the `square`

function because `1^2`

equals 1.

In math, not every function has a fixed point but in lambda calculus, every function is a fixed point that can be found by the Y combinator.

Let's see how.

Given a function `h`

, `Y(h)`

is a fixed point of `h`

. In other words, `h(Y(h))`

equals `Y(h)`

.

Let's prove our claim by "computing" `Y(h)`

following the formal definition:

```
Y(h) =
(x =>
y => h(x(x))(y))
(x =>
y => h(x(x))(y))
```

Now, if we define: `A = (x => y => h(x(x))(y))`

, we have:

```
Y(h) = A(A)
```

Let's unfold the first `A`

:

```
(x =>
y => h(x(x))(y))
(A)
```

Let's compute this expression by replacing `x`

with `A`

:

```
y => h(A(A))(y)
```

which is equivalent to:

```
h(A(A))
```

Notice that `A(A)`

is the same as `Y(h)`

. In other words `h(Y(h)`

equals `Y(h)`

.

With that, we have proven that `Y(h)`

is a fixed point of `h`

.

This proof is so beautiful, so powerful, and so short that I cannot resist the temptation to write it again in a succinct way:

```
Y(h) =
(x =>
y => h(x(x))(y))
(x =>
y => h(x(x))(y))
A = (x => y => h(x(x))(y))
Y(h) = A(A)
Y(h) =
(x =>
y => h(x(x))(y))
(A)
Y(h) = y => h(A(A))(y)
Y(h) = h(A(A))
```

This property of the Y combinator is not only an important theoretical property. It has deep consequences. It allows us to create recursive functions.

Now, we are going to illustrate the creation of recursive functions via the Y combinator with the factorial function.

Let's look again at the code for the factorial function with the usual recursive approach:

```
fact = (n => ((n === 0) ? 1 : n * fact(n - 1)))
```

Now, let's create a function that we call `factGen`

by wrapping the body of `fact`

and replacing `fact`

with an unknown argument called `f`

:

```
factGen = f => (n => ((n === 0) ? 1 : n * f(n - 1)))
```

Notice this small but crucial fact: `factGen(fact)`

equals `fact`

. In other words, `fact`

is a fixed point of `factGen`

. If only we could find a way to generate a fixed point of `factGen`

...

Hahaha...

The Y combinator comes to the rescue: `Y(factGen)`

is a fixed point of `factGen`

. It means that `Y(factGen)`

behaves as the factorial function.

Let's write explicitly the definition of `Y(factGen)`

:

```
(f =>
(x =>
y => f(x(x))(y))
(x =>
y => f(x(x))(y)))
(f => (n => ((n === 0) ? 1 : n * f(n - 1))))
```

On one hand, this expression is highly cryptic (not to say unreadable). On the other hand, you have in front of your eyes the definition of the factorial function using only anonymous functions.

If you don't believe it, take a moment and copy-paste the following JavaScript line in the console of your browser or in your Node environment and see it for yourself:

```
(f =>
(x =>
y => f(x(x))(y))
(x =>
y => f(x(x))(y)))
(f => (n => ((n === 0) ? 1 : n * f(n - 1))))
(5)
```

The result is `120`

which is `5!`

.

Every time I think about the Y combinator, I am overwhelmed again. Recursive anonymous functions seems like a oxymoron, but in fact it is a reality.

Lambda calculus shows us in an elegant way that in order to grasp the foundation of programming, we need only the concept of single-argument anonymous function definition and application. Everything else in programming can be built on top of it. Even recursion, which seems to inherently require the ability to give names to functions, can be derived in lambda calculus. This magic power is made possible via the Y combinator.