It’s about time someone started talking about Go again around here, so I picked up the old editor, and (painlessly!) installed Go. Maybe 5 minutes later I had the world’s faster compiler, a test framework, a coverage analyzer and a bunch of stuff besides available on my machine. But what to do? Hello World is so done, so I thought I’d grab my copy of Hutton & Meijer and implement a basic parser combinator.
First off, Go has no generic types, and apparently little incentive to do so. Which makes things slightly more difficult than I’d have liked. After all, Hutton & Meijer’s parser type has the form
type Parser a = String -> [(a, String)]. No matter; we’ll just fake it ’til we make it.
A parser may return 0, 1 or many results. No results means a failure to parse anything. A single result represents an unambiguous parse, and multiple results represent multiple interpretations of the same input: an ambiguous grammar. The simplest parser is the “zero” parser: it consumes no input, and returns no results:
Now before we can continue, Go has an interesting take on object-oriented code. We declare an
interface, and any type whose method set includes all the methods in that interface are “of that type”. It provides Go with a distinctly dynamic flavour (think Smalltalk, Ruby) while remaining statically typed. Alas, Go doesn’t infer types, but we can’t have everything.
So now we have a zero parser. We also need a parser that can actually consume input. Hutton & Meijer call it “item”:
It’s a pity about the weirdness in the middle there: if
ReadRune isn’t supposed to return an error, why’s it in the signature?! Anyway, it could be worse.
Hutton & Meijer go into some detail why they prefer
seq in section 2.3 of their paper, which we won’t go into here. Obviously
bind refers to the monadic operation, but you did see the “Monadic” in “Monadic Parser Combinators”, right? However, I’m not really interested in the monadic part of things in this post. Instead I’d like to dig a bit into how it feels to write Go this way. First we need to adjust the definition of a
Again, the lack of generic types bites us, with Go’s version of C’s
void *. (I exaggerate; it’s not as bad as
void *. I just miss generics.) So what’s it look like to write a
A touch of type inference would help that! OK, but how’s
Bind even implemented? In Go, (a) you add methods to types, not interfaces, and (b) types automatically satisfy interfaces by the methods they understand. What that means is that this kind of thing won’t work:
Now remember that
bind doesn’t care about which parser you have. From Hutton & Meijer we have
Instead we have to write something like this:
For each kind of parser, we have to write a separate
Bind implementation. Which shouldn’t be terribly surprising, given (a) the OO nature of Go and (b) the fact that there’s no inheritance. In this particular case we’re able to pull out the common implementation in the form of a
Func parser, minimising the duplication.