Skip to content

Instantly share code, notes, and snippets.

@houtianze
Last active August 2, 2024 07:07
Show Gist options
  • Save houtianze/b274e4b975a28fe08aee681699c3f7d0 to your computer and use it in GitHub Desktop.
Save houtianze/b274e4b975a28fe08aee681699c3f7d0 to your computer and use it in GitHub Desktop.
On Y Combinator

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 caculate 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

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.

@sawthinkar
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment