Programming With Nothing: FizzBuzz in the lambda calculus in Ruby | Hacker News Reader

Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

experthuman.com

333 pointstomstuart53 comments

I 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!

The 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/ as Tom Stuart's public speaking skills made this a thoroughly enjoyable (if a little mind-bending) talk.

Tom’s talk blew my mind. Can't recommend watching this enough.

I agree. This is presentation was brilliant and I'd really encourage people to watch it.

Gorgeous 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))

Your iterate function as written relies on a top-level define feature, which pure lambda calculus lacks (motivating the use of fixed-point combinators).

No, 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?

Ah, I see. My mistake.

Holy 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.

I don't know.

I see it as a kind of entertaining academic game - a Glass Bead Game, if you will, and I intend the deep allusion - but I wouldn't put too much faith in it teaching you much about the mechanics of compilers. It's one way of decomposing semantics into more simple elements, but it's not the one chosen for almost all practical languages, which after all have to execute on silicon, not in the Lambda calculus.

It doesn't teach anything about parsers, and nor does it exercise much thinking in trees. It does emphasize recursion, but in a way that makes it seem like an absurd roundabout way of doing things, rather than something that more usually simplifies the expression of a program. Above all, it doesn't really demystify how the text of your program changes the coloured lights on your screen. It's a splendidly constructed wonderland, a pyramid of abstraction with nothing but function application at its core, but I don't think it leaves you with a lot more than a sense of having seen something very clever.

(FWIW, nothing in the presentation was new to me, so any residual sense of wonder has faded. Take that into account in my perhaps cynical judgement.)

parsing is in my opinion the crappiest part of compiler writing. I feel pretty safe saying that because we have made tools to automate or near-automate the act of writing parsers for compilers ...

I would argue that there's a big difference between "demystify how the text of your program changes the coloured lights on your screen" and "demystify why the text of your program changes the coloured lights on your screen". if you are interested only in the first question, you might be an engineer. if you are also interested in the second question, you might be a computer scientist...

Parsing is the best understood part of writing compilers; that's why it has tools, not because it is the "crappiest". (If anything, the wealth of free tools available gives a clue as to how fun dealing with it is.) But using the tools well requires some understanding of how they work; and if you're doing an industrial-strength parsing job, you'll probably end up writing the parser by hand, because what a tool gives you - speed in converting specification into implementation - is not usually the constraining factor; rather, functionality and performance of the end result are.

As to your question "why", nothing about the lambda calculus will tell you anything about why your program changes the coloured lights. There is only "how" and "will", by which I mean human agency. There is no answer to "why" here, and there cannot be, because the "why" resides in people's minds. It takes no more extra effort to believe in "if" than beta reduction.

Take that single example: implementing if as a primitive rather than a function with lazily evaluated arguments means greatly increasing practicality at the cost of the sparse beauty of minimalism. 'If' is very common; optimizing it, diagnosing misuses of it, etc. is a lot harder once you've lost it in a forest of function applications.

I agree with everything in your first paragraph and would add the following: parsing is overrated. It's interesting the way that crossword puzzles are. Nothing wrong with that, but it can be a distraction; it's just not that deep a space.

That's not to say that the people who worked out how to do it in the first place weren't brilliant. They were, and it was a hard problem. But it's a solved one.

There are still some fairly hard problems in parsing. For example, doing minimal work to convert a series of text deltas into abstract syntax tree deltas, using caching to avoid throwing away too much. This is highly relevant to IDEs for providing code completion and other analysis, but it's usually solved with a mix of brute force - restarting the whole parse from the top - and trickery, such as skipping uninteresting function bodies, or parsing a much simplified version of the language that ignores many productions.

I didn't know that. Thanks.

I'm not sure I'd necessarily agree with your assessment of parsing as a field in 2011. There are still a lot of unsolved problems going forward --- see Laurence Tratt's excellent article on the subject for a few details: http://tratt.net/laurie/tech_articles/articles/parsing_the_s...

I don't know. Barrkel's example seems better to me because there's an obvious practical need for it. The trouble with most of the work on parsing I see is that it's just not hard to hand-write a parser. I used to avoid doing so, and then I wrote one and was surprised: once you factor in error-handling and whatever other meaningful output your system may need from its parser (e.g. text extents for ASTs), the overall complexity of a hand-written one can easily be less than one made with tools at a supposedly higher level of abstraction. And that's not counting the time it takes to learn the tool (which is not trivial, as they don't always have good debugging support) or the complexity cost of having the tool in one's stack (also not trivial, since they typically have their own languages, complicate the build process, and so on). This experience led me to mentally discount the whole field, hence my perhaps overly dismissive comment.

I fully agree with you that i favor hand-written recursive-descent parsing. However, it still helps to know the theory for error recovering etc.

I agree, there is a big difference between implementation and semantics, but I would normally expect a compilers class to focus on implementation (and I wouldn't expect a typical languages or compilers class to spend half a semester teaching how lambda calculus works as a computation model).

Still; I think that the experience of deriving mentioned language constructs from almost nothing is a great learning experience in itself. It's this kind of teaching - along with efforts as "The Elements of Computing System"[1] - that facilitate an - in my opinion - better learning experience that just 'learning this stuff from the blackboard'.

[1]: http://diycomputerscience.com/courses/course/the-elements-of...

Well, I suspect it would have helped me in my class, since we're using a functional language to implement a compiler. Our final exam from earlier today included a section regarding the lambda calculus. In fact, as I mulled over which incorrect answer to provide, I wished I could have talked previously with tomstuart about the subject.

Yay, I have a new project for this weekend! For those who missed it, he has a github project at (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.

> 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.

This is n=1, of course, but I'm tremendously interested in the subject matter and superficially interested in Haskell. Yet, I don't work with Haskell on a daily basis, so when I see something non-trivial in Haskell, I skim it or put it aside to read later when I have time for study.

Whereas if it's in Ruby, JavaScript, or CoffeeScript, I try to read it immediately. So don't forget the class of slackers who mean to get around to Haskell fluency one day, but not today. We have a great interest in the subject matter and like Haskell in principle even if we're lazy(!) about evaluating Haskell code examples.

true, 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.

It sounds like you would really have enjoyed SICP[1]. I remember feeling exactly what you're describing when I finished the Logo interpreter project. Logo, which (despite its dearth of parentheses) is a type of Lisp, is a surprisingly simple language which is not that far removed from lambda calculus.

[1]: http://mitpress.mit.edu/sicp/

If you have time on your hands in the near future, you should definitely give SICP a go--it really is a brilliant book.

That 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)

Here's a simple recursively defined number system in scheme: https://gist.github.com/1466985

Indeed. This encoding is due to church (http://en.wikipedia.org/wiki/Church_encoding).

Excellent 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.

True, 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.

Yes 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 (full code and all everything)

https://gist.github.com/1372131#file_v2.md (outline/notes)

(please don't make fun of me, Scheme peeps)

This 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.

The 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.

Mark-Jason Dominus did this for Perl, more than a decade ago.

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.

Yeah you can do the full lambda calculus in Python:

https://raw.github.com/sdiehl/church-numbers/master/church.p...

The 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?

Well, 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).

What 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".

I 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

Being on the frontpage here... shouldn't there be an extra section "Recursion, briefly"... (http://en.wikipedia.org/wiki/Y_combinator)

The 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 :)

Great 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?

Eric Kidd?

http://www.randomhacks.net/articles/2005/12/03/why-ruby-is-a...

Another decent example of lambda calculus (factorial in Scheme): http://blogs.msdn.com/b/ashleyf/archive/2008/12/03/the-lambd...

Matt Might has some similar articles on his blog: http://matt.might.net/articles/ (see under "Functional Programming").

You 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.

this is the definition of a turing tarpit.

I think I'd be more inclined to call this version a Church tarpit.

That'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.

Deleted comment

The Y combinator was in there, also the Z combinator. You just didn't read far enough.

Nice coincidence, I spent part of my weekend hacking on an Unlambda FizzBuzz.

Now functional programming and lambda calculus makes sense.

This is un-cking-real.

Thank you.

Reply on news.ycombinator.com