Y Combinator Explained

gistfile1.txt

I just finally had my mind snap into place with understanding of the Y Combinator. Most explanations I read, even the ones using JS, didn't make much sense and were overly long so here follows my own, much simpler explanation. I will be using JS.


We have fibonacci to start with, very simple recursive function.
It's fixed points are 0 and 1, fib(0) = 0, and fib(1) = 1
That's all a fix point means, when the f(x) == x
They are important because they are the only values at which recursion can cease.

Our Fibonacci Function
======================
function fib(x){
   return x + (x > 0 ? fib(x-1) : 0)
}


If our language doesn't support recursion or use of names before they are actually compiled (same thing),
fib won't exist in the context of fib itself.
So we might decide to write a factory for fib.

function fibFactory(fib){
  return function(x){
   return x + (x > 0 ? fib(x-1) : 0)
  };
}

This factory would be great, if we could use it, but we still have to pass in a fib function in order for
it to work properly.

If we did fibFactory(fibFactory()), we still again, are missing the fib function to pass to the inner
fibFactory call.
Effectively, the fibFactory needs the return value if itself passed to it. It's like an f(x), requiring
f(f(x)) in order to operate. This is different than in the case of the pure fib, that needed just itself
passed to it, not its return.
So we are seeing that fibFactory requires f(f(x))
                    and that fib required f(f)

If we continued down the line, like dumb and dumber, we'd have f(f(f(f(f(..etc...
We see that our quest is to get a fixed point for this. However, it is impossible to do this *without*
intertwining the factory code, with the execution code. Basically, we know fib has a fixed point, we know
our current factory function has no fixed point. By smartly handing off to fibFactory, some smartly
crafted function, fibFactory(...smart Fn...), we can borrow the fib code's fixed point for our factory.

Some vocabulary for kicks:
combinator - a function that only takes functions as arguments, and returns a function
fixed-point combinator - a combinator that finds a fixed-point for other functions

If we can build a function to halt at the fixed point, we have solved the problem.
While the fib(x) function had fixed points of 0 and 1, our fixed point for fibFactory will instead be a
function..still the same exact concept though!

Okay, so lets intertwine the execution code.
Lets create our smartFn stub to resolve dependencies.
We know that at some point, the factory won't be called, ie. the fixed points of the original fib, 0 and
1. We need to create a function which both creates the fib from the factory, and executes the fib at the
same time, this way the fixed point will occur on both the factory and the fib.

function smartFn(x){
   var ourFactory = ....;
   var createFnAndCallFn = function(x){
       return ourFactory(createFnAndCallFn2)(x);
   }
   var createFnAndCallFn2 = function(x){
       return ourFactory(createFnAndCallFn1)(x);
   }
   createFnAndCallFn(x);
}

We still have a problem here regarding recursion in some languages, namely that createFnAndCallFn cannot
call createFnAndCallFn2 until it is actually made, a circular dependency. The important thing to notice is
that these functions are equivelent code-wise.

Let us refactor to get rid of the circular dependency.

function smartFn(x){
   var ourFactory = ....;
   var createTheFnCall = function(f){
      return function (x){ ourFactory(f)(x);  }
   }

   var createFnAndCallFn = createTheFnCall(createTheFnCall);
   var createFnAndCallFn2 = createTheFnCall(createTheFnCall);

   createFnAndCallFn(x);
}


Woah..we just showed that we only need createTheFnCall. Lets further simplify so we can algebraically
create the infamous Y Combinator function.

function smartFn(x){
   var ourFactory = ....;

(
   (function(f){
      return function (x){ ourFactory(f)(x);  }
   }) (function(f){
        return function (x){ ourFactory(f)(x);  }
      })  

)(x);
}

Y should take a factory, and return the combinated source function (fib in this case.)

function Y(factory){
   return factory(smartFn); <--- and we out!
}

The simplification is just some more rewriting but you'll end up getting 
λf.(λx.f (x x)) (λx.f (x x))




In summary...
In order to do recursive functions in a language that doesn't recurse, you create a function factory. That
function factory will require the source function as an argument to it. This is a circular dependency that
seems impossible to resolve -- but only if you constrain yourself to passing the _actual_ original
function as the argument to the factory.

To obtain a fixed point for the function factory, you must "knot" the function factory with execution of
the source function.

That is, you pass a wrapper function to the factory, instead of the original. The wrapper function should
have two actions, it should create the function by calling the factory, and it should execute the function
afterwards, with the arguments passed. The call to the factory should be passed this same wrapper
function. With some smart refactoring, you get the Y Combinato
I've read a lot of stuff on Y Combinator recently and the reason I wanted to explain it is because none of
these sites I found actually explain *why* it works. Now hopefully you understand the 'zipper' theory of
fixed point dependency resolution. No one should be browsing news.ycombinator.com without knowing this!
Cheers!