8 ms·
Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
- mudgemeister 15y agoThe presentation from which this article is adapted was a definite highlight of the Ru3y Manor conference (and received rapturous applause). I highly recommend watching the video of the original presentation at http://rubymanor.org/3/videos/programming_with_nothing/ http://rubymanor.org/3/videos/programming_with_nothing/ as Tom Stuart's public speaking skills made this a thoroughly enjoyable (if a little mind-bending) talk.
- floehopper 15y agoI agree. This is presentation was brilliant and I'd really encourage people to watch it.
- jgwhite 15y agoTom’s talk blew my mind. Can't recommend watching this enough.
- hendzen 15y agoThat was pretty cool. Interesting to note that the numbers he used are essentially an implementation of the Peano Axioms, where the successor function wraps the predecessor in a lambda. (http://en.wikipedia.org/wiki/Peano_Axioms http://en.wikipedia.org/wiki/Peano_Axioms) Here's a simple recursively defined number system in scheme: https://gist.github.com/1466985 https://gist.github.com/1466985
- rmcclellan 15y agoIndeed. This encoding is due to church (http://en.wikipedia.org/wiki/Church_encoding http://en.wikipedia.org/wiki/Church_encoding).
- patio11 15y agoHoly cow. This could have replaced ~8 weeks of my CS languages/compilers class, and I would have understood the material better at the end of it.
- polymatter 15y agoYay, I have a new project for this weekend! For those who missed it, he has a github project at (https://github.com/tomstuart/nothing https://github.com/tomstuart/nothing) where you can reimplement this yourself, with some tips to help you out. I especially like how he neither uses a fancy academic language which people can dismiss outright for not being practical - like Haskell. But neither do you need ridiculous amounts of boilerplate that obscures the message - like in Java. Ruby is used for real stuff and doesn't have pretentious academic baggage. Edit: spelling.
- finnw 15y ago> a fancy academic language which people can dismiss outright for not being practical - like Haskell Actually that could be a good way to filter your audience. Some of those who would be least likely to appreciate this tutorial (and would be likely to post comments complaining how pointless (no pun intended) it was) would avoid a Haskell article in the first place.
- polymatter 15y agotrue, if you're optimising for an academic discourse. But that also limits its accessibility for any potentially interested who don't know the academic language. I can't be the only one who stopped reading an Ocaml paper merely for not knowing Ocaml. Its clear he's optimising for knowledge transfer as he spent the time to not only post code on github, but provide different branches for those with different backgrounds. I think this tutorial shows what we really mean about Turing equivalence in languages, about how data structures can be represented as functions, and presents a wider point of view that opens up other possible program designs.
- raganwald 15y ago
- i2 15y agoThe same can be done with Python lambdas: >>> ZERO = lambda f: lambda x: x >>> FIVE = lambda f: lambda x: f(f(f(f(f(x))))) >>> to_int = lambda f: f(lambda x: x+1)(0) ... etc.
- freyrs3 15y agoYeah you can do the full lambda calculus in Python: https://raw.github.com/sdiehl/church-numbers/master/church.py https://raw.github.com/sdiehl/church-numbers/master/church.p...
- neilk 15y agoMark-Jason Dominus did this for Perl, more than a decade ago. http://perl.plover.com/lambda/ http://perl.plover.com/lambda/ aka "How to write a 163 line program to compute 1+1" Although I really like the OP's approach since he slowly morphs a program his readers can understand, rather than constructing a programming system from scratch.
- ufo 15y agoThe only thing I miss here is pointing out that you can use function application (\map -> ...)(definition_of_map) instead of defines/assignments. But then the final piece of code would not look as awesome so whatever :)
- jonbro 15y agothis is the definition of a turing tarpit.
- kd0amg 15y agoI think I'd be more inclined to call this version a Church tarpit.
- psykotic 15y agoThat's an easy but in my opinion wrong conclusion to draw. The magic of lambda calculus is that unlike Turing machines it supports building abstractions that let you hoist yourself out of the tarpit and present a usable programming interface to the end user.
- julius 15y agoBeing on the frontpage here... shouldn't there be an extra section "Recursion, briefly"... (http://en.wikipedia.org/wiki/Y_combinator http://en.wikipedia.org/wiki/Y_combinator)
- rbxbx 15y agoYes yes yes, wonderful article. Look forward to watching the video later as well :) I did a lightning talk at SCNA this year which covered similar, if somewhat different, and certainly less comprehensive ground, which may be of interest to readers of this thread/article. http://git.io/objects-as-closures http://git.io/objects-as-closures (full code and all everything) https://gist.github.com/1372131#file_v2.md https://gist.github.com/1372131#file_v2.md (outline/notes) (please don't make fun of me, Scheme peeps)
- gnaritas 15y agoExcellent article, though I had to laugh at the introduction of the if statement just to avoid the appearance of calling the boolean directly, which happens to be exactly how Smalltalk implements its if statements: a direct call to the boolean passing a block as the argument. This approach to programming is how Smalltalk has only a handful of reserved words vs the 80'ish I think Ruby has.
- raganwald 15y agoTrue, however the stated goal here was to replicate the Ruby example more-or-less as-is. Which means building something elegant and then greenspunning cruft on top of it :-) Your comment highlights how simple things we take for granted as basic ideas (like if statements) may not be as axiomatic as we assume.
- raganwald 15y agoI remember an interview with Quincy Jones, where he was asked "Which song do you wish you'd written yourself?" His answer was "Strange Fruit," a tremendously significant Jazz standard (if it's new to you, listen to it without thinking about the lyrics, then read the lyrics and listen to it again). I have to say, this is the essay I wish I had written. It's beautiful by every one of my standards of beauty, most especially in that the journey of writing it appears to be even more attractive than the pleasure of reading it. I'm glad to read it today, Thank you!
- js2 15y agoThis is really wonderful, and I felt like I was reading something Peter Norvig would write (modulo s/Ruby/Python/ not that it matters here). If you enjoyed it, SICP belongs on your reading list.
- lambdapilgrim 15y agoI have been working through SICP. In Chapter 2 they introduce Church Numerals. I wrote a blog post recently demonstrating by the method of substitution how arithmetic operators on Church numerals finally break down to work. Would appreciate your comments about it. EDIT: Here it is: http://lambdapilgrim.posterous.com/numbers-without-numerals http://lambdapilgrim.posterous.com/numbers-without-numerals
- groovy2shoes 15y agoMatt Might has some similar articles on his blog: http://matt.might.net/articles/ http://matt.might.net/articles/ (see under "Functional Programming").
- psykotic 15y agoGorgeous piece of writing! You don't actually need the Y combinator for any of the cases presented like mod, range, etc. Church numeral iterators are more than sufficient for the task. I'll use Haskell to illustrate, but you could easily translate this into his subset of Ruby. -- represent n as a Church numeral iterate 0 f x = x iterate n f x = f (iterate (n-1) f x) -- m modulo n can be calculated with at most m conditional subtraction steps mod m n = iterate m (\x -> if x < n then x else x-n) m -- build the range back to front using a (number, list) pair as state range m n = snd (iterate (n-m) (\(x, xs) -> (x-1, x:xs)) (n-1, [])) The mod implementation is an example of a general pattern. Whenever you can bound the number of iterations in an algorithm as a computable function of the arguments, you can implement the algorithm by computing the upper bound and iterating that many times with an iterator function that acts like the identity once it reaches its base case (for mod, the case is x < n). The range implementation displays another important method called 'tupling' or more generally 'strengthening the induction hypothesis'. It underlies the predecessor/decrement function for Church numerals which the author of the article presents but chooses not to explain; the idea is simple, if rather inspired. Rather than iteratively compute n-1 as a function of n, we will compute a more general datum, the pair (n-1, n). That might seem like a pointless change, but when formulated this way, the problem becomes surprisingly easy: dec n = fst (iterate n (\(_, x) -> (x, x+1)) (0, 0))
- kd0amg 15y agoYour iterate function as written relies on a top-level define feature, which pure lambda calculus lacks (motivating the use of fixed-point combinators).
- psykotic 15y agoNo, iterate is just a helper function to convert a Haskell integer to a Church numeral. If the inputs were directly represented as Church numerals, it wouldn't be needed and you'd just replace every instance of iterate n with n itself. I thought this would be evident to someone who had read the article and understood Church numerals, so I didn't go into detail about it. Does that clear up your confusion?
- bitops 15y agoGreat article, and to me it's further evidence of Lisp's greatness (a great influencer of Ruby). If your primitives are powerful enough, you should be able to build most of the language yourself from the ground up. Wasn't it Paul Graham who said that Ruby is an acceptable Lisp?
- raganwald 15y agoEric Kidd? http://www.randomhacks.net/articles/2005/12/03/why-ruby-is-an-acceptable-lisp http://www.randomhacks.net/articles/2005/12/03/why-ruby-is-a...
- tripa 15y agoNice coincidence, I spent part of my weekend hacking on an Unlambda FizzBuzz.
- MonkeyCoder 15y agoAnother decent example of lambda calculus (factorial in Scheme): http://blogs.msdn.com/b/ashleyf/archive/2008/12/03/the-lambda-calculus.aspx http://blogs.msdn.com/b/ashleyf/archive/2008/12/03/the-lambd...
- deleted 15y ago[deleted]
- deleted 15y ago[deleted]
- anthonyb 15y agoThe Y combinator was in there, also the Z combinator. You just didn't read far enough.
- Cushman 15y agoThe title of this article, "Programming With Nothing", piques my interest. I don't have a strong CS background, so this might be a silly question... But obviously, on a computer, "code" is really data, a series of bytes that instructs the processor what to do. In a literal sense, this sort of lamba calculus implementation isn't far removed from bog standard procedural programming. What's the actual philosophical background here-- what is a function, really? What makes it special?
- nandemo 15y agoWell, all sufficiently strong programming languages are equivalent in the Turing sense, and Turing machines are equivalent to lambda calculus in computational power. That said, lambda calculus is rather different from standard procedural programming. The closest thing to it in the "real world" would be functional languages such as Scheme, ML and Haskell. What makes functions special? I think the article answered that: with very simple ingredients, namely recursive functions that take only 1 argument, you can essentially write any program that you could write with full-fledged Ruby (or any other Turing-complete programming language).
- beza1e1 15y agoWhat is a function? Mathematically a function is a mapping from an input domain to an output domain. In the Lambda calculus a function is essentially a tuple of a variable name and a body lambda expression. Applying the function to an argument lambda expression gives you the body expression, where all ocurrences of the variable name are replaced with the argument expression. Essentially, the function can be understood as an replacement rule. I do not understand what you mean with "special".
- Tyr42 15y agoYou say the Y combinator, as presented, could be done in Haskell, but it's got an infinite type, so it's a bit trickier to get working.
- skylan_q 15y ago! Now functional programming and lambda calculus makes sense. This is un-cking-real. Thank you.