Deriving the Y Combinator in JavaScript in 7 Steps

igstan.ro

71 points·rdtsc··9 comments

For an alternate and very different explanation, see mine at http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.h.... It does it in 3 steps.

Your explanation is great!

As a third option, if you'd like to have the relevant CS terminology, see Matt Might's derivation, also in JavaScript, at http://matt.might.net/articles/implementation-of-recursive-f....

Thanks for the link. Really nice resource on CS stuff.

Yet no mention of lambda calculus (or combinatory logic) anywhere in the article.

Nor that it requires untyped lambdas.

I haven't mentioned anything about those subjects for a few reasons: 1. I don't know that much about them yet; 2. the post would have gotten pretty lengthy and hairy; 3. I didn't meant the post to be a comprehensive tutorial on fixed point combinators.

While I think I understand lambda calculus enough as to write a little introductory blog post, I can't say the same for combinatory logic.

On the plus side it was an extremely lucid explanation of how the Y combinator is derived. Usually articles on the Y combinator get bogged down with jargon and terminology. By using simple terms your explanation was very readable. If someone wants to learn more of the theory it is one google away. If someone wants to learn how someone might have originally come up with such a device, you article is an excellent starting point.

Agree - haters gonna hate. I really enjoyed the simple, lingo-free derivation.

An excellent introduction to a topic that normally only gets introduced after wading through a lot of lambda calculus - not that there is anything wrong with the more formal approach for CS course but it is nice to see these things receiving a bit more visibility (and nice that it is in JavaScript).

Reply on news.ycombinator.com