The Derivation of Y Combinator

[fadmmatt]

Nifty.

I wrote up an alternate derivation based on fixed points for my compilers students:

http://matt.might.net/articles/implementation-of-recursive-f...

It also shows how to exploit the Y combinator to get speed-ups from memoization in JavaScript.

[scott_s]

You gave one of my two favorite talks at PLDI 2006. I have to admit I don't remember most of the technical content now, but damn were you enthusiastic about it. ("And now, super beta!") I also remember the talk because you only found out the day before that you were doing it - I think your adviser had just gone to the ER.

HN has had some growing pains, but there's still something special here.

[andreyf]

Very nice, this seems like it might be my first successful attempt at understanding the importance of the Y combinator. Question:

As an example of the power of this approach, this caching turns the naive, exponential implementation of Fibonacci into the optimized, linear-time version

What role does the YC play in this? Is it not simply due to memoization? Does the Y-combinator version grow the stack?

[andreyf]

I think you misquoted S&S on the front there, I believe the quote is "That this manages to work is truly remarkable".

[pkrumins]

Good one. Thanks for sharing!

[btilly]

For yet another alternate derivation, see http://www.mail-archive.com/[email protected]/msg02716.h.... I find that one the easiest to understand, possibly in part because it is the one that I came up with. :-)

[calcnerd256]

I prefer to start with two definitions and an assumption:

Yf = f(Yf) for all [combinators] f, defines the desired behavior of Y

Mx = xx for all [combinators] x (note that M then equals SII in SKI combinator calculus)

assume there exists a y such that My = Y

proceeding from there, I can derive Y without having to memorize it

[pkrumins]

Can you show the derivation steps you take?

[Panoramix]

That's kind of beautiful. Non-programmer here, so can somebody point me to an application of these beasts? can I use this kind of thing to e.g., speed up something? Not that it would have less merit otherwise. Stretching my brain is already nice in itself.

[mbrubeck]

Fixed-point combinators are useful for memoizing or otherwise modifying recursive functions: http://matt.might.net/articles/implementation-of-recursive-f...

[amix]

A derivation of Y Combinator in JavaScript (using the fac function): http://amix.dk/blog/post/19239