4 ms·

Three Little Birds – Deriving the Y Combinator

74 points by eggsby 14y ago

Just what the world needs, another post explaining the y combinator! Hope someone can glean some information from this, I learned a fair bit in writing it :)

tesmar2 14y ago
Jim Weirich derives the Y combinator in pure Ruby here: http://vimeo.com/45140590 http://vimeo.com/45140590 EDIT: Correct video http://www.youtube.com/watch?v=FITJMJjASUs http://www.youtube.com/watch?v=FITJMJjASUs It is some of the ugliest ruby code I have ever seen, but it was something amazing to watch happen live.
- eggsby 14y ago
  Nice, I enjoyed Jim's talk where he derived the combinator using clojure[1]. In it he referenced another talk that he cites as an influence, "Programming With Nothing"[2] by Tom Stuart where he writes fizzbuzz in ruby using only lambda application. Finding the SKI calculus was a similar revelation to me, that such simple combinators could represent any lambda term is such a huge idea! 1: http://www.infoq.com/presentations/Y-Combinator http://www.infoq.com/presentations/Y-Combinator 2: http://rubymanor.org/3/videos/programming_with_nothing/ http://rubymanor.org/3/videos/programming_with_nothing/
- baddox 14y ago
  Is the Ruby hiding in that video? I briefly skimmed it and all I saw was JavaScript.
  - tesmar2 14y ago
    You are correct, I edited the comment with the right video.
raganwald 14y ago
Where did I misplace my +100 wand? Great post, combinators are a not-so-hidden passion of mine and they inspire a lot of really practical applications in JavaScript and Ruby.
- eggsby 14y ago
  Thanks! I actually got the bug to write this post from reading your wonderful js combinator book[1] over the holiday, which reminded me that I also had a copy of To Mock a Mockingbird in my to read pile. When I got to the bit where Smullyan describes the first sage bird (He explains: "This is quite simple ... for any bird x, Θx = M(Lx). Since x is fond of M(Lx) and M(Lx) = Θx, then x is fond of Θx, which means that Θ is a sage bird."), I felt like I had been hit by a brick wall as it was anything but simple for me, having previously grasped at understanding the y combinator. Only by understanding the discrete moving parts was I able to finally wrap my head around what was going on. Like many others when I had my a-ha! moment I wanted to share. Thank you for making content like this digestible! 1: https://leanpub.com/javascript-allonge https://leanpub.com/javascript-allonge
brianberns 14y ago
As a professional programmer with a strong interest in functional programming, but none of the formal background, I should be the perfect reader for this article. Unfortunately, I found it to be a complete syntactic and semantic mess. I'll enumerate a few of the problems that tripped me up as I read: * The underlying metaphor is poorly explained. E.g. The identity bird: "when you call out a bird to it it simply calls that bird back to you". The notion of "calling out a bird" is awkward and confusing. On first reading, it seems to imply that one calls out the name of a bird, which is simply wrong. I understand that birds represent higher-order functions, but if I didn't, I would never grasp it from reading this article. (I doubt that Smullyan was this sloppy in his original description of the metaphor.) * The mockingbird "duplicates its input". No, it doesn't. It applies its input to itself, which is totally different from duplicating it. The next sentence is also confusing at best: "If you call some bird x to the mockingbird it will call back as if the bird x had called out to itself". The phrase "as if" is wrong and misleading, and bird x is not calling out some unspecified value to itself. A better description is that the mockingbird function calls out bird x to bird x. That's a huge difference. * I had to read this phrase about five times before I could parse it: "The mental giants who computed before computers spoke to this magical bird chiefly for this purpose". And once parsed and understood, it still fails to explain why we're suddenly talking about factorials instead of birds. What makes this bird metaphorically "mechanical" or "foreign" is mysterious. It just does factorials somehow because it doesn't "follow the rules of regular combinator birds but it will follow some". Come again? * The next sentence is where I started to give up: "Initially we call the strange factorial out to the mockingbird, which calls back the same thing as calling the strange bird to itself". Is the "fact" variable supposed to be the strange factorial? What is the strange bird? None of this terminology actually appears in the function that is supposedly being explained here. I had to ignore the text and work out the purpose of the function myself. I'm sure there's value in this metaphor - I love the other Smullyan books that I've read and have a lot of respect for his careful puzzle-making. But I'm afraid this article doesn't do him justice as written.
- lmm 14y ago
  I found http://www.arcfn.com/2009/03/y-combinator-in-arc-and-java.html http://www.arcfn.com/2009/03/y-combinator-in-arc-and-java.ht... a much clearer explanation of what the Y combinator is and why it's useful.

74 points by eggsby 14y ago

Just what the world needs, another post explaining the y combinator! Hope someone can glean some information from this, I learned a fair bit in writing it :)

tesmar2 14y ago

Jim Weirich derives the Y combinator in pure Ruby here: http://vimeo.com/45140590 http://vimeo.com/45140590 EDIT: Correct video http://www.youtube.com/watch?v=FITJMJjASUs http://www.youtube.com/watch?v=FITJMJjASUs It is some of the ugliest ruby code I have ever seen, but it was something amazing to watch happen live.

eggsby 14y ago
Nice, I enjoyed Jim's talk where he derived the combinator using clojure[1]. In it he referenced another talk that he cites as an influence, "Programming With Nothing"[2] by Tom Stuart where he writes fizzbuzz in ruby using only lambda application. Finding the SKI calculus was a similar revelation to me, that such simple combinators could represent any lambda term is such a huge idea! 1: http://www.infoq.com/presentations/Y-Combinator http://www.infoq.com/presentations/Y-Combinator 2: http://rubymanor.org/3/videos/programming_with_nothing/ http://rubymanor.org/3/videos/programming_with_nothing/
baddox 14y ago
Is the Ruby hiding in that video? I briefly skimmed it and all I saw was JavaScript.
- tesmar2 14y ago
  You are correct, I edited the comment with the right video.

raganwald 14y ago

Where did I misplace my +100 wand? Great post, combinators are a not-so-hidden passion of mine and they inspire a lot of really practical applications in JavaScript and Ruby.

eggsby 14y ago
Thanks! I actually got the bug to write this post from reading your wonderful js combinator book[1] over the holiday, which reminded me that I also had a copy of To Mock a Mockingbird in my to read pile. When I got to the bit where Smullyan describes the first sage bird (He explains: "This is quite simple ... for any bird x, Θx = M(Lx). Since x is fond of M(Lx) and M(Lx) = Θx, then x is fond of Θx, which means that Θ is a sage bird."), I felt like I had been hit by a brick wall as it was anything but simple for me, having previously grasped at understanding the y combinator. Only by understanding the discrete moving parts was I able to finally wrap my head around what was going on. Like many others when I had my a-ha! moment I wanted to share. Thank you for making content like this digestible! 1: https://leanpub.com/javascript-allonge https://leanpub.com/javascript-allonge

brianberns 14y ago

As a professional programmer with a strong interest in functional programming, but none of the formal background, I should be the perfect reader for this article. Unfortunately, I found it to be a complete syntactic and semantic mess. I'll enumerate a few of the problems that tripped me up as I read: * The underlying metaphor is poorly explained. E.g. The identity bird: "when you call out a bird to it it simply calls that bird back to you". The notion of "calling out a bird" is awkward and confusing. On first reading, it seems to imply that one calls out the name of a bird, which is simply wrong. I understand that birds represent higher-order functions, but if I didn't, I would never grasp it from reading this article. (I doubt that Smullyan was this sloppy in his original description of the metaphor.) * The mockingbird "duplicates its input". No, it doesn't. It applies its input to itself, which is totally different from duplicating it. The next sentence is also confusing at best: "If you call some bird x to the mockingbird it will call back as if the bird x had called out to itself". The phrase "as if" is wrong and misleading, and bird x is not calling out some unspecified value to itself. A better description is that the mockingbird function calls out bird x to bird x. That's a huge difference. * I had to read this phrase about five times before I could parse it: "The mental giants who computed before computers spoke to this magical bird chiefly for this purpose". And once parsed and understood, it still fails to explain why we're suddenly talking about factorials instead of birds. What makes this bird metaphorically "mechanical" or "foreign" is mysterious. It just does factorials somehow because it doesn't "follow the rules of regular combinator birds but it will follow some". Come again? * The next sentence is where I started to give up: "Initially we call the strange factorial out to the mockingbird, which calls back the same thing as calling the strange bird to itself". Is the "fact" variable supposed to be the strange factorial? What is the strange bird? None of this terminology actually appears in the function that is supposedly being explained here. I had to ignore the text and work out the purpose of the function myself. I'm sure there's value in this metaphor - I love the other Smullyan books that I've read and have a lot of respect for his careful puzzle-making. But I'm afraid this article doesn't do him justice as written.

lmm 14y ago
I found http://www.arcfn.com/2009/03/y-combinator-in-arc-and-java.html http://www.arcfn.com/2009/03/y-combinator-in-arc-and-java.ht... a much clearer explanation of what the Y combinator is and why it's useful.