Evan Martin (evan) wrote in evan_tech,
Evan Martin


The original reason I thought to mention that Packrat paper again was to mention the other parsing paper from the same site. It's at least worth skimming through the introduction for this snippet:
Chomsky's generative system of grammars, from which the ubiquitous context-free grammars (CFGs) and regular expressions (REs) arise, was originally designed as a formal tool for modelling and analyzing natural (human) languages. Due to their elegance and expressive power, computer scientists adopted generative grammars for describing machine-oriented languages as well. The ability of a CFG to express ambiguous syntax is an important and powerful tool for natural languages. Unfortunately, this power gets in the way when we use CFGs for machine-oriented languages that are intended to be precise and unambiguous.
The relative power of different languages (in the Chomsky hierarchy sense) is another one of those things I really want to learn more about.

I've been carrying around two textbooks from college with the intent of rereading them: one is the linear algebra one I've recently resumed, and the other on the theory of computation, which is all about this stuff. It's actually conveniently the only citation from the wikipedia article on context-free grammars.

I've had this on my mind recently, especially now that I'm surrounded with Japanese. Human languages may all be derived from the same proto-language but they've had plenty of time to diverge, in the sense that I don't think developments in English really affected the structure of Japanese, and both are pretty different from the native American languages. And so while human languages definitely have similar core ideas (nouns, verbs, time) there is surprising variation in parameters I wouldn't naively expect to vary -- for example, it's arguable that Chinese doesn't have adjectives, and I find even the concept of "word" to be pretty fuzzy around the edges.

Computer languages, by contrast, haven't had the opportunity to develop in isolation from each other. (Additionally, the quote above, which is what recently set me off on this tack, points out that our theory of expressing computer languages is itself derived from a theory that was trying to model human languages.) There have been a few genuinely different approaches: lisp, surely, and maybe smalltalk, but generally all the the people working on these things read each other's papers and write code in each other's languages. I've often wondered how much that lack of biodiversity is keeping us back. (You can find a more ranty exposition of the same idea in this post from Steve.)

This is why I'm so interested in Haskell: it's not that I necessarily think their approach is more useful (certainly you'll still see plenty of ruby code here), but I love that they are trying something really different, y'know, shaking up some of the fundamental parameters and finding out what effects that has. It's even better when things like Packrat parsing or free asynchronous exceptions or interesting concurrency support* fall out of those decisions.

I feel the same way about the Perl6 community, even though I don't see myself ever using the language: they're willing to do some crazy stuff and potentially (probably? :P) fail, but at least they'll try to break new ground.

* New readers of this LJ will find some great discussions on SMP linked from that post from our resident grungy CPU expert [aka not me]. Also a followup here.
Tags: go read, papers, personal, programming languages

  • münchen

    On that note: I'm living in Munich for the next week plus a few days. Do I know anyone around here? (PS: The LJ → PubSubHubbub → Reader…

  • deb/rpm diffing tools

    Dear Linux hackers, Chrome tends to push minor updates (often security) pretty frequently. We'd like to operate as a good member of the Linux…

  • emacs

    I've been using vim for a very long time -- over ten years -- but over those years I've envied more and more the way emacs integrates other software.…

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.