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.
So we are at this point:
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