Post

Before I start in on this: be aware I’m mostly writing this to force myself to understand something by writing it down. If you get anything out of it, consider it a bonus. I will be deriving Y() in JavaScrpit, and giving a version in Ruby.

After stumbling on this article on Raganwald last year (thoroughly interesting site by the way), I was initially intrigued and then totally frustrated by not being able to understand what the hell this Y combinator thing was. It’s of limited practical use to me, but it bugs me when I can’t wrap my brain around something. This is an attempt to remedy said frustration. You may find this Wikipedia article and Richard Gabriel’s The Why of Y (PDF, examples in Scheme) useful as we go along. I’ve cobbled this together from other articles linked from Raganwald and found through Google.

I assume we’re all familiar with the idea of a function as something that takes some input value and returns some output value. Say, the function for squaring numbers:

The fixed points of a function are any input values for which f ( x ) is equal to x . So, the fixed points of f ( x ) = x ² are 0 and 1.

Now, in mathematics and in any language that supports first-class functions (that is, functions that can be passed around as data), we have things called higher-order functions. These are functions that take another function as input, or return a function as output, or both. The fixed point of a higher order function f is another function p such that f ( p ) = p . (It may be more helpful to think in terms of functions actually being executed. The previous statement is equivalent to the statement that f ( p )( x ) = p ( x ) for all values of x .) Y (the Y combinator) is a special function that returns the fixed points of higher-order functions, that is to say:

Y is commonly use to allow anonymous recursion without assuming your host language supports it. Let’s say I want a function that calculates the factorial of a number: