[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.

[fadmmatt]

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

[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?

[fadmmatt]

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.

[andreyf]

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

[fadmmatt]

Thanks! Will fix.

[pkrumins]

Good one. Thanks for sharing!