Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

experthuman.com

Post reply on HN
Print view View original

21–30 of 55 posts

Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

#21

Post by barrkel »

munin wrote: post #19
barrkel wrote: post #18

Earlier quoted context omitted.

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 calculu…

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"…

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.

Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

#22

Post by raganwald »

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!

Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

#24

Post by lambdapilgrim »

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

Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

#25

Post by raganwald »

finnw wrote: post #13
polymatter wrote: post #12

Earlier quoted context omitted.

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…

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

Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

#27

Post by neilk »

i2 wrote: post #7

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.

Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

#28

Post by kd0amg »

munin wrote: post #19
barrkel wrote: post #18

Earlier quoted context omitted.

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 calculu…

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"…

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

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

Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

#29

Post by psykotic »

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

Re: Programming With Nothing: FizzBuzz in the lambda calculus in Ruby

#30

Post by gruseom »

barrkel wrote: post #21
munin wrote: post #19

Earlier quoted context omitted.

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"…

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 y…

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.

Post reply on HN