How to reinvent the Y combinator

[slideshare id=12319464&w=425&h=355&sc=no]

(If you connected to this page from China, you may need to use VPN to view the above slides.) I don't believe in the doctrine "Don't reinvent the wheels". I believe that one can never learn the essence of anything without reinventing it (intentionally or not). Once you reinvent a thing, you can never forget it -- because otherwise you can just reinvent it again. Today I found that I forgot how to derive the definition of the Y combinator. I learned it several years ago from an online article, but now the search term "Y combinator" only brings news about startups (sigh). I attempted it for two hours, but still couldn't make the leap from the "poor man's Y" to "Y". Finally, I opened my good old friend The Little Schemer. Alas. Chapter 9 tells me exactly how to reinvent Y. Thank you Dan Friedman and Matthias Felleisen! To prevent myself from forgetting how to derive Y again, I made a slide to record my understanding of it. It is slightly different from the ways of the recent version of The Little Schemer, but I think it's easier to understand. I hope it can help some people (including the future me). So here it is. Exercise: The Y combinator derived from this tutorial only works for direct recursion, try to derive the Y combinator for mutual recursive functions, for example the following two functions even and odd. [code language="clojure"] (define even (lambda (x) (cond [(zero? x) #t] [(= 1 x) #f] [else (odd (sub1 x))]))) (define odd (lambda (x) (cond [(zero? x) #f] [(= 1 x) #t] [else (even (sub1 x))]))) [/code]