Another decent example of lambda calculus (factorial in Scheme): http://blogs.msdn.com/b/ashleyf/archive/2008/12/03/the-lambd...
Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
41–50 of 55 posts
Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
#42Great 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?
Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
#43[deleted]
Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
#44[deleted]
Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
#45[deleted]
The Y combinator was in there, also the Z combinator. You just didn't read far enough.
Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
#46Earlier quoted context omitted.
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.
Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
#47The 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?
Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
#48Holy 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.
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.
Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
#49this is the definition of a turing 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.
Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby
#50The 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 back…
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).