Algorithms

The Y Combinator for Programmers

Illustrated by Leandro Lassmar

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:

  1. Function definition
  2. 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.

Yehonathan Sharvit

author

Yehonathan has been in the Hi-Tech since 2000.

He has worked in various management positions from team leader to VP R&D, mostly in startups, combining strong technical knowledge with management skills. His management style is mostly influenced by Agile methodology and Lean Startup philosophy.

As a functional programming expert, Yehonathan is a regular speaker at Tech events around the world and he is the maintainer of Klipse https://github.com/viebel/klipse - a popular github open source project. He blogs about programming languages at http://blog.klipse.tech.

He has strong academic background: M.Sc. in Mathematics and B.Sc. in Electrical Engineering from Technion institute in Israel.

Leandro Lassmar

illustrator

Leandro Lassmar is an illustrator living in Minas Gerais, Brazil.
He worked in animation studios, currently works for magazines, books and advertising.
It won the SND (society of news design) and ÑH - Lo Mejor del Diseño Periodístico awards.