As part of my ongoing effort to make progress in Haskell (that’s one of my goals for 2016!), I’m following the MOOC on functionnal programming by Erik Meijer on edX.
The first lessons were pretty basic stuff, and I got through them quickly. Lesson 7 is about Functional parsers and M(scary). This is where I encountered my first difficulties, and I thought it would be an interesting writing. I already used parser combinators in Haskell before (mainly Parsec and Attoparsec), but never really understood how they worked, or at least not enough to implement one myself. So here is my take on the subject. Don’t expect really advanced stuff! It’s just an introduction to the basic concepts, on which we could build more complex and useful tools. In particular, I won’t talk about:
- How to report errors.
- How to recover from errors.
- How to write a parser for a concrete grammar.
Instead I’ll focus on:
- What a parser is.
- How to make parsers compose.
- How to use do notation to implement more complex parsers.
One of the interesting facts about writing your own parser combinators library, is that you will learn (or consolidate) other knowledges in the process, like: Functors, Applicatives and, of course, Monads, and more generaly, how to design DSL in Haskell. I already knew about this concepts (at least, that’s what I thought…), but knowing what something is from a high level of abstraction, is not the same as knowing how to implement it on a concrete type (like a Parser)!
So what’s a parser?
We can view a Parser as something that consumes some input, and outputs a structured representation of what was consumed. For the sake of simplicity, we’ll only consume strings (Haskell type String). So that would be something like:
type Parser a = String -> a
Here a represents the type of what is built from the stream of characters (String). This could be a syntactic tree, or a list of numbers, or anything else. For example a parser that is able to recognize a string like "[1, 2, 3, 4]" could have the type: Parser [Int] (expended to String -> [Int]), which means it takes a String and output a list of integers.
But we’re missing two important properties of a Parser:
- It can fail to parse something.
- It can partially consume its input.
To take into account the first point, we could return Maybe a instead of a (resulting in Nothing in case of failure). Note that we could also use a richer type like Either to handle parsing errors. And for the second point, we can return a tuple of a a and a String, which represents the part of the string that wasn’t consumed by the parser. The type would then become:
data Parser a = Parser { runParser :: String -> Maybe (a, String) }
As an example of a parser that would fail, if you take our previous parser that is able to handle a list of integers, if you give it the string "[1 ,2", it will fail, and return Nothing.
Similarly, if we feed the parser with "[1, 2, 3, 4]toto", it will consume the part of the string that represents the list of integers, and leave "toto" as a remaining input. Thus the result would be: Just ([1, 2, 3, 4], "toto").
Let’s implement some very basic parsers:
failure :: Parser a
failure = Parser $ s -> Nothing
return :: a -> Parser a
return a = Parser $ s -> Just (a, s)
oneChar :: Parser Char
oneChar = Parser $ s -> case s of
[] -> Nothing
(c:xs) -> Just (c, xs)
Let’s test these parsers:
runParser failure "Hello Parser!"
Nothing
runParser (return 42) "Hello Parser!"
Just (42, "Hello Parser!")
runParser oneChar "Hello Parser!"
Just ('H',"ello Parser!")
runParser oneChar ""
Nothing
The basic parsers seem to behave as expected. We get Nothing in case of failure, and they are able to partially consume the input. So all is good, but what about more complex parsers? We would like to parse strings, or more complex patterns. Let’s try to recognize a string from the input, using our basic parsers:
string :: String -> Parser String
string "" = return ""
string (c1:xs1) = Parser $ s ->
case runParser oneChar s of
Nothing -> Nothing
Just (c2, rest) ->
if c1 == c2
then case runParser (string xs1) rest of
Nothing -> Nothing
Just (match, rest2) -> Just (c2:match, rest2)
else Nothing
runParser (string "Hello") "Hello Parser!"
Just ("Hello", " Parser!")
runParser (string "Hello") "Foo Bar"
Nothing
runParser (string "") "Hello Parser!"
Just ("","Hello Parser!")
This isn’t very convenient (but it works)… Because we have to write the boilerplate to compose parsers over and over. Hopefully, we know a famous structure that allows composition in Haskell, and this is called Monad (and I won’t make yet another tutorial on Monads, so I will assume you already are familiar with this concept). That means we could avoid all the boilerplate, by making our Parser type an instance of Monad. This would allow us to use the do syntax to cleanly compose our parsers! Sweet!
To do so, we’ll have to make our Parser an instance of: Functor, Applicative and Monad.
Parser is a Functor
First of all, our Parser is an instance of Functor, which means we can map functions over the result of our parsing:
instance Functor Parser where
fmap f p = Parser $ s ->
case runParser p s of
Nothing -> Nothing
Just (a, rest) -> Just (f a, rest)
parse42 :: Parser Int
parse42 = (fmap read $ string "42")
runParser parse42 "42 is the answer!"
Just (42, " is the answer!")
Parser is an Applicative
Secondly, we can make our parser an instance of Applicative. This part wasn’t obvious for me. All the examples I found were about instances for easy types like Maybe, but I found a Parser to be pretty different. But thanks to the types and some use-cases (that you’ll find below), I figured the following implementation (which will hopefully be correct…):
instance Applicative Parser where
pure a = Parser $ s -> Just (a, s)
p1 <*> p2 = Parser $ s ->
case runParser p1 s of
Nothing -> Nothing
Just (f, rest) -> case runParser p2 rest of
Nothing -> Nothing
Just (a, rest2) -> Just (f a, rest2)
The usefulness of the previous instance might not be obvious, but it allows us to lift some function inside the realm of parsers. For example if we want to take the result of several parsers and then group their results into a tuple, we can do it using Applicatives:
parseTuple :: Parser (Char, Char)
parseTuple = (,) <$> oneChar <*> oneChar
runParser parseTuple "ab"
Just (('a', 'b'), "")
This is the kind of constructs we will use to convert the raw parsed structure into our own types (e.g: an AST).
data AST =
Foo String
| Bar String
| Pair Char Char
deriving (Show)
parseFoo, parseBar, parsePair :: Parser AST
parseFoo = Foo <$> string "foo"
parseBar = Bar <$> string "bar"
parsePair = Pair <$> oneChar <*> oneChar
runParser parseFoo "foo bar"
runParser parseBar "bar baz"
runParser parsePair "xyz"
Just (Foo "foo", " bar")
Just(Bar "bar", " baz")
Just (Pair 'x' 'y', "z")
Parser is a Monad
Last but not least, our parser is a Monad. Which means it must implement: >>=, >>, return and fail:
instance Monad Parser where
p >>= f = Parser $ s -> case runParser p s of
Nothing -> Nothing
Just (a, rest) -> runParser (f a) rest
p1 >> p2 = Parser $ s -> case runParser p1 s of
Nothing -> Nothing
Just (_, rest) -> runParser p2 rest
return = pure
fail _ = Parser (const Nothing)
Thanks to this definition we can use the do syntactic sugar, which will ease the implementation of more complex parsers. Let’s see what we can do.
char :: Char -> Parser Char
char c = do
c1 <- oneChar
if c == c1
then return c1
else failure
runParser (char 'H') "Hello!"
runParser (char 'e') "Hello!"
Just(‘H’,“ello!”)
Nothing
We can also implement a cleaner version of our string parser (found above):
string' :: String -> Parser String
string' [] = return []
string' (c:xs) = do
c1 <- char c
rest <- string' xs
return (c1:rest)
runParser (string' "Hello") "Hello"
runParser (string' "Hello") "Foo"
Just("Hello", "")
Nothing
The do notation makes it very easy to combine parsers! We now have some basic building blocks that we could use to implement more parsing combinators: choice, many, option, etc. But I’ll leave it as an exercise.
Moreover, it would be interesting to implement an error reporting mechanism, as well as position tracking (to locate errors in the input), but I’ll leave it for another blog-post (or as an exercise for the reader!).
What I learned while reinventing the wheel
Implementing (very) basic parsing combinators led me to better understand the foundation of libraries like Parsec or Attoparsec, and to implement not so trivial instances of typeclasses like Applicatives and Monads. Although basic, I think it’s a good way to be more familiar with the DSL-like capabilities of Haskell, and to feel the power that the language offers in term of domain-specific modeling.
Comments
Post a Comment