4 ms·
The Derivation of Y Combinator
- fadmmatt 17y agoNifty. I wrote up an alternate derivation based on fixed points for my compilers students: http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/ 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.
- andreyf 17y agoI think you misquoted S&S on the front there, I believe the quote is "That this manages to work is truly remarkable".
- fadmmatt 17y agoThanks! Will fix.
- andreyf 17y agoVery 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?
- fadmmatt 17y agoThe role the YC plays in this case is hiding the memoization. The memoizing Y combinator is the same as the Y combinator, except it doesn't re-compute inputs it's already seen. Writing recursive functions in "Y-combinator style" is a way to expose internal recursive call sites to external inspection and manipulation. The Y combinator version still grows the stack.
- scott_s 17y agoYou 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.
- fadmmatt 17y agoStay tuned: I'll be giving another crazy lambda talk at PLDI 2010 this summer.
- pkrumins 17y agoGood one. Thanks for sharing!
- calcnerd256 17y agoI 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 17y agoCan you show the derivation steps you take?
- calcnerd256 17y agoSure. Myf = f(Myf) yyf = f(yyf) Suppose yxf = f(xxf) for all x. Now y is simply (lambda x f . f(xxf)) Note that this doesn't get you the applicative-order version we want, but it does satisfy the definition of Y My = (lambda x . x x) (lambda x f . f (x x f)) = (lambda x f . f (x x f)) (lambda x f . f (x x f)) = (lambda f . f ((lambda a g . g (a a g)) (lambda a g . g (a a g)) f)) etc.
- btilly 17y agoFor yet another alternate derivation, see http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.h.... I find that one the easiest to understand, possibly in part because it is the one that I came up with. :-)
- amix 17y agoA derivation of Y Combinator in JavaScript (using the fac function): http://amix.dk/blog/post/19239 http://amix.dk/blog/post/19239
- Panoramix 17y agoThat'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 17y agoFixed-point combinators are useful for memoizing or otherwise modifying recursive functions: http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/ http://matt.might.net/articles/implementation-of-recursive-f...