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).<p>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.<p>I'm glad to read it today,<p>Thank you!
The presentation from which this article is adapted was a definite highlight of the Ru3y Manor conference (and received rapturous applause).<p>I highly recommend watching the video of the original presentation at <a href="http://rubymanor.org/3/videos/programming_with_nothing/" rel="nofollow">http://rubymanor.org/3/videos/programming_with_nothing/</a> as Tom Stuart's public speaking skills made this a thoroughly enjoyable (if a little mind-bending) talk.
Gorgeous piece of writing!<p>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.<p>I'll use Haskell to illustrate, but you could easily translate this into his subset of Ruby.<p><pre><code> -- 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, []))
</code></pre>
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).<p>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:<p><pre><code> dec n = fst (iterate n (\(_, x) -> (x, x+1)) (0, 0))</code></pre>
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. (<a href="http://en.wikipedia.org/wiki/Peano_Axioms" rel="nofollow">http://en.wikipedia.org/wiki/Peano_Axioms</a>)<p>Here's a simple recursively defined number system in scheme:
<a href="https://gist.github.com/1466985" rel="nofollow">https://gist.github.com/1466985</a>
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.
Yes yes yes, wonderful article. Look forward to watching the video later as well :)<p>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.<p><a href="http://git.io/objects-as-closures" rel="nofollow">http://git.io/objects-as-closures</a> (full code and all everything)<p><a href="https://gist.github.com/1372131#file_v2.md" rel="nofollow">https://gist.github.com/1372131#file_v2.md</a> (outline/notes)<p>(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:<p><pre><code> >>> 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.</code></pre>
The title of this article, "Programming With Nothing", piques my interest.<p>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 <i>is</i> a function, really? What makes it 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: <a href="http://lambdapilgrim.posterous.com/numbers-without-numerals" rel="nofollow">http://lambdapilgrim.posterous.com/numbers-without-numerals</a>
Being on the frontpage here... shouldn't there be an extra section "Recursion, briefly"... (<a href="http://en.wikipedia.org/wiki/Y_combinator" rel="nofollow">http://en.wikipedia.org/wiki/Y_combinator</a>)
The only thing I miss here is pointing out that you can use function application (\map -> ...)(definition_of_map) instead of defines/assignments.<p>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.<p>Wasn't it Paul Graham who said that Ruby is an acceptable Lisp?
Another decent example of lambda calculus (factorial in Scheme): <a href="http://blogs.msdn.com/b/ashleyf/archive/2008/12/03/the-lambda-calculus.aspx" rel="nofollow">http://blogs.msdn.com/b/ashleyf/archive/2008/12/03/the-lambd...</a>
Matt Might has some similar articles on his blog: <a href="http://matt.might.net/articles/" rel="nofollow">http://matt.might.net/articles/</a> (see under "Functional Programming").