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.
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.
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.
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.
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 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 uninteresti…
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?
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.
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.
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 calculu…
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'.
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 cond…
Your iterate function as written relies on a top-level define feature, which pure lambda calculus lacks (motivating the use of fixed-point combinators).
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 cond…
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.