On Y Combinator

on.y.combinator.md

Hopefully this may speed your groking of the forking torturing Y Combinator a little bit.

Disclaimer: I don't assert what I say here is accurate, or even correct (I'm not authorative, obviously), but it's my understanding and I'm sharing in the hope that someone who also struggles on the Y Combinator may benefit a tad.

Prerequisite Understandings

• In Lambda Caculus, everything is a Lambda Caculus (Anonymous function that takes one parameter). And the best thing is that, ... drump roll ..., it's Turing Complete. So theoretically, it can calculate anything a computer can.
• In this note, I use the term function, which (I think) means Lambda Caculus, to sound (at least to myself) more accustomed.

The definition of Y Combinator

• Y = λf.(λx.f (x x)) (λx.f (x x)) (From: Wikipedia. This is quite technical, but if you want to go deep...)
• Language specific implementation: https://gist.github.com/redraiment/6445345

What does Y Combinator do?

• Given a function f that:

  • takes a function and returns another. (So it's a high-order function (at least order or 2?))
  • has at least one fixed point function g: g == f(g)
  • can be applied to the Y Combinator

  Then the Y Combinator, when applied to function f, will find one of its fixed point: i.e. let g = Y(f); then g == f(g)

How does Y Combinator gets a function's fixed point

• Refer to Wikipedia again for the proof. (Again, quite technical）

What is Y Combinator useful for?

• (The only main usage I know of) It can implement recursive functions in Lambda Caculus, in which recursive function is not natively supported (Becasue Lambda Caculus is anonymous function, thus it can't directly call itself (no name given to be called)). Apply Y Combinator to a factory/generator/seeding function will give you the normally recursively-defined fucntion.

Illustration

(Using pseudo Javascript syntax) Recursive function rf:

rf = function(x) {
  y = logicA()
  ret = rf(y)
  logicB(ret)
}

Its factory:

rff = function(f, x) {
  return function(f) {
    function(x) {
      y = logicA()
      ret = f(y)
      logicB(ret)
    }
  }
}

Then rf is equivalent to Y(rff), but Y(rff) is not recursively written.

Explanations and the trick

• rff is a "wannabe" no-recursive factory for recursive function rf, it will truely be the factory rff only when the f parameter passed in is the same as the function it returns: i.e. when f == rff(f). So this parameter (function) f is its fixed point. Y(rff) will return such a fix point (function), and this fixed point is the equivalence of the recursive function rf (rff now generates the fixed point, which is the recursive function). Amazing right?

How does Y Combinator magically transform this factory function rff to the recursive function rf?

(My explanation) It first creates 2 "normal" factory functions (let's name them to refer) rfa and rfb, then it puts rfa as the input parameter f of rfb and returns this new function (the recursive function rf's equivalence) rfc. When rfc is called, it performs the logic and call the function f, which is just itself, recursion thus comes alive.