4 ms·

Nifty. I wrote up an alternate derivation based on fixed points for my compilers students: http://matt.might.net/articles/implementation-of-recursive-fixed-po

Nifty. 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 ago
I think you misquoted S&S on the front there, I believe the quote is "That this manages to work is truly remarkable".
- fadmmatt 17y ago
  Thanks! Will fix.
andreyf 17y ago
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?
- fadmmatt 17y ago
  The 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 ago
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.
- fadmmatt 17y ago
  Stay tuned: I'll be giving another crazy lambda talk at PLDI 2010 this summer.
pkrumins 17y ago
Good one. Thanks for sharing!

andreyf 17y ago

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

fadmmatt 17y ago
Thanks! Will fix.

andreyf 17y ago

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?

fadmmatt 17y ago
The 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 ago

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.

fadmmatt 17y ago
Stay tuned: I'll be giving another crazy lambda talk at PLDI 2010 this summer.

pkrumins 17y ago

Good one. Thanks for sharing!