Y Combinator Explained

gistfile1.txt

Going to use JS to explain.
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 are arguments, and returns a function
fixed-point combinator - a combinator that finds a fixed-point for other functions

If we can find the fixed point, then our recursion will stop.
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, with the factory code by rewriting fib(x) as fibFactory(fib)(x)

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

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 a 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 createFactoryAndCallFn = function(x){
       return ourFactory(createFactoryAndCallFn2)(x);
   }
   var createFactoryAndCallFn2 = function(x){
       return ourFactory(createFactoryAndCallFn1)(x);
   }
   createFactoryAndCallFn(x);
}

We still have a problem here regarding recursion in some languages, namely that createFactoryAndCallFn cannot call createFactoryAndCallFn2 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 createFactoryAndCallFn3 = function(f){
      return function (x){ ourFactory(f)(x);  }
   }

   var createFactoryAndCallFn = createFactoryAndCallFn3(createFactoryAndCallFn3);
   var createFactoryAndCallFn2 = createFactoryAndCallFn3(createFactoryAndCallFn3);

   createFactoryAndCallFn(x);
}


Woah..we just showed that we only need one createFactoryAndCallFn, 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))


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.

In summary, it works because we've tied the factory into actual execution of the function, like a zipper. There are other ways to combinate recursive functions but this happens to be one of the easier ways. Cheers