Muted Alarm

Exploring Parser Combinators in Scala

2009-04-10T17:14:00.004+09:00

One of the nice features of Scala is that it has very flexible syntax. This is especially nice when implementing libraries with the desire to cut down on the syntactical noise that makes doing anything in Java painful on the hands. The most simple example of this is infix operators. Most operators are left associative, and are automatically translated into the corresponding method call. For example, 1 + 2 desugars into 1.+(2).

This combines well with parser combinators, another nice feature of Scala which enables domain-specific languages to be syntactically designed in Scala as well as handled on the backend. Parser combinators are theoretically underpinned by functional programming concepts, and are only possible in Scala due to its support of both functional and object-oriented language paradigms. Also notable is that the parser combinator libraries are libraries; no special compiler support was added just for a parsing library (despite the terse syntax).

Below are some blogs I've read with nice examples of languages cooked up with this functionality:

Baysick is a Scala DSL which approximates a small subset of BASIC. It is not fully compliant due to a few limitations of Scala's syntax, but nevertheless it is visually impressive.

Debashish Ghosh implemented a simple buy/sell order language to demonstrate the simplication possible for not-so-savvy traders, or parsing a human-readable format. What's more, his post also has good background on parser combinators themselves, and shows how to command the Scala-based parser to create POJO's (plain old Java objects) as a result of the parse, which can then be used by client Java applications.

Unfortunately the API documentation for Scala's parser combinators is difficult to traverse due to the complicated class/trait hierarchy. I recommend the parser combinator technical report/mini-book written by Adriaan Moors. His page for the report is here, but the document linked there does not seem to be available. I was able to find the same document here on a related Google Code page.

Soon, I will relate my experiences of using the parser combinator library in my own project. I doubt it will be as complicated as some examples in the guide mentioned above (won't need a Context or scannerless parser) but hopefully some lessons are learned anyway.

Who says static typing has to be ceremonious?

2009-04-07T11:11:00.000+09:00

I refer you to a blog post by Ikai Lan.

When you combine pattern matching, extractors, lazy file streams, and other sugar, things can get pretty silly pretty fast :)

Types are to Python as animals are to ___

2009-04-03T09:24:00.000+09:00

I'm thinking clouds in the sky in the above one. Which is why the following StackOverflow thread is infinitely ironic. What it really comes down to is, the type of an object in Python may or may not correspond to the method interface it implements.

When in Rome, do as the Romans. Thus, when in Python you should only care about method interfaces. If you need to know whether something is a duck and the quack isn't enough, you are doing something wrong (or expecting too much from the poor duck)!

Making sense of the (functional) world

2009-03-30T17:35:00.000+09:00

I stumbled across the original "Lambda the Ultimate" papers by Sussman and Steele and the effect produced from reading them is profound. It is as if someone suddenly lit a huge halogen floodlight into an enormous black cavern. :)

More seriously, several topics such as continuations, continuation-passing-style (CPS) and the compilation of functional languages make about 100 times more sense now. Hopefully I can get back on track and read what I was *supposed* to be reading before the research meeting on Wednesday..

Simple explanation of gradual typing

2008-11-26T14:29:00.000+09:00

I found a page on Jeremy Siek's website that simply explains the basics of gradual type systems. So if you know just a little bit about programming, you can get an idea of what I may be working on in the next few months.

http://ece-www.colorado.edu/~siek/gradualtyping.html