The Derivation of Y Combinator
catonmat.net
catonmat.net
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.
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?
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.
HN has had some growing pains, but there's still something special here.
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
Myf = f(Myf)
yyf = f(yyf) (lambda x f . f(xxf)) 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))