I have always thought the "Y" in Y Combinator was a reference to Yahoo. I knew their co-founder Paul Graham (the "Lisp guy") had ties with Yahoo (they acquired his company Viaweb) so I just assumed the "Y" must be a shortening of Yahoo, just like YUI. Boy was I wrong.

The realization occurred watching Doug Crockford (the "Javascript guy") reflect on the history of Javascript. Crockford initially thought Javascript was a joke until he found out it had lambdas. He proceeded to present Javascript's version of the Y Combinator, at which point I knew I was an idiot.

A quick read of Y Combinator's FAQ confirmed my embarassing ignorance,

Why did you choose the name "Y Combinator?"The Y combinator is one of the coolest ideas in computer science. It's also a metaphor for what we do. It's a program that runs programs; we're a company that helps start companies.

In the spirit of WTF is F-Bounded Polymorphism, I now ask, WTF is a Y Combinator? From the factorial example above we can see that it has *something* to do with recursion but there is no explicit recursion involved (factorial does not reference factorial).

Here is a Ruby explicit recursive factorial function in which we do reference factorial within the body of the factorial,

We will now try to get rid of this explicit recursion. First, write this as lambdas instead of using **def**, giving us

We can further abstract out factorial as an argument to the lambda,

This reads: define factorial as a function that takes in a fac function and returns another function that takes an integer n. We can now call factorial, passing in factorial as argument, then pass in an integer (here 5).

Let's abstract lambda { |fac| ...} and call it H. Nothing has changed, just less clutter.

In mathematics, this is called a **fixpoint**. We pass an argument to a function and the result is that argument. Here the argument is the factorial function. It could just be a number; for example, zero and one are fixpoints of x = x ^2 (x squared). In lambda calculus speak, when H is applied to factorial the result is factorial. Or, calling H with argument factorial returns factorial. *factorial* is a fixpoint of H.

We would like to generalize this. So let us define a function **Y** that takes in a function and returns a fixpoint of the function. Hey, this is our Y Combinator!

We can now get a recursive factorial function from the non-recursive H function if we had a suitable Y function.

Now here is the crazy part: Y is not recursive. That's correct, Y does not need recursion. Here is the magical Y Combinator in Ruby,

With the Y Combinator we can now do this,

Our non-recursive factorial function looks very much like a recursive factorial function, except it requires a *factorial* argument to work for n > 2. The Y Combinator supplies us with this factorial function argument. You can kind of see how this works even if it's not 100% crystal clear. The *le *(lambda expression) agument is our non-recursive factorial function. We essentially remember the non-recursive factorial function and through a couple of self applications *f.call(f)* we're able to generate a copy of the non-recursive factorial when needed.

To make it a little clearer, let us derive the Y Combinator using regular **def** but without recursion. This time, we'll use a length function as an example. The length function takes in an array and returns the number of elements in the array. Assume arrays have a "rest of" method that returns the remainder of the array (i.e., Array.slice(1..-1)). Also assume we have this "eternity" function that never returns.

Instead of defining a total length function (one that will work with all arrays) let us define a partial length function that only works for arrays of length 0, 1 or 2.

*length_2* still requires a *length_function* which we currently don't have so let's use the *eternity_function*. If we pass in a 3 element array things won't work since the *eternity_function* won't return.

To remove the repetitions we will define a *make_length* function and our *length_2* function will now look like this,

Nothing has changed, *length_2* will still bomb for arrays with more than 2 elements. From the above you can see how we just need to find a way to generate a new copy of *make_length* if we wanted to define *length_3, length_4, length_infinity*.

Instead of passing in the eternity function how about passing in the *make_length* function? Worth a try,

With these changes we can now determine the length of a 3 element array. We can rename our functions,

and with that we have a general length function that will work for all arrays. We've generated a recursive function from a non-recursive one. We are able to essentially create copies of the non-recursive function as needed.

There you have it, the Y Combinator. And to think, all these years, I thought it was the Yahoo Combinator. It's rather mind blowing (my Y Combinator, not my ignorance). What are the characteristics of human life? Intelligence and reproduction. We can think and we can make babies.

Here we demonstrated how code can reproduce, make new copies of itself. Code evolution. First there was the non-reproducing *make_length* function that could only calculate length of zero element arrays. As chance would have it, in the primodial soup was also the Y Combinator function. When *make_length* and Y Combinator mixed we gained the ability to generate new copies of the *make_length* function when needed.

Lots of good information on Y Combinators on the web. My two favorite: The Little Schemer and The Implementation of Functional Programming Languages, which the above is largely a summary of.

## Comments