IntroductionToCombinators.lhs

= Introduction to combinators

In this tutorial we will develop a parser for a very simple expression
language, and start learning about the set of combinators which comes
with Parsec.

> import Text.Parsec (ParseError)
> import Text.Parsec.String (Parser)
> import Text.Parsec.String.Parsec (try)
> import Text.Parsec.String.Char (oneOf, char, digit
>                                ,string, letter, satisfy)
> import Text.Parsec.String.Combinator (many1, choice, chainl1, between)
> import Control.Applicative ((<$>), (<*>), (<$), (<*), (*>), (<|>), many)
> import Control.Monad (void, ap)
> import Data.Char (isLetter, isDigit)
> import FunctionsAndTypesForParsing

Let's create a very simple expression language:

> data SimpleExpr = Num Integer
>                 | Var String
>                 | Add SimpleExpr SimpleExpr
>                 | Parens SimpleExpr
>                   deriving (Eq,Show)

It's a bit simple and almost useless at the moment, but we will expand
on this a lot in later tutorials.

Here are some examples:

> simpleExprExamples :: [(String,SimpleExpr)]
> simpleExprExamples =
>     [("a", Var "a")
>     ,("1", Num 1)
>     ,("2 + 3", Add (Num 2) (Num 3))
>     ,("(42)", Parens (Num 42))]

TODO: some more complex examples

Let's write a simple parser for these, and introduce a few things
along the way.

We will write a parser for each constructor separately, then look at
how we can write a parser for all of them together.

==== Num

To parse a number, we need to parse one or more digits, and then read
the resulting string. We can use the combinator 'many1' to help with
this. We will also use do notation.

> num :: Parser SimpleExpr
> num = do
>     n <- many1 digit
>     return (Num (read n))

Let's try it out. TODO: examples

How does it work? First, we parse one or more (many1) digits (digit),
and give the result the name 'n'. Then we convert the string to an
integer using read, and wrap it in a Num constructor.

The many1 function's type looks like this:

```
many1 :: Parser a -> Parser [a]
```

It applies the parser given one or more times, returning the result.

TODO: example show what happens when you use 'many' instead of 'many1'

==== Var

For var, we have to decide on a syntax for the identifiers. Let's go
for a common choice: identifiers must start with a letter or
underscore, and then they can be followed by zero or more letters,
underscores or digits in any combination.

> var :: Parser SimpleExpr
> var = do
>     fc <- firstChar
>     rest <- many nonFirstChar
>     return (Var (fc:rest))
>   where
>     firstChar = satisfy (\a -> isLetter a || a == '_')
>     nonFirstChar = satisfy (\a -> isDigit a || isLetter a || a == '_')

This time, we create two helper parsers: firstChar - which parses a
letter or underscore, and nonFirstChar = which parses a digit, letter
or underscore. This time, we use the 'many' function instead of
'many1': TODO - demonstrate why using examples only.

> add :: Parser SimpleExpr
> add = do
>     e0 <- num
>     void $ char '+'
>     e1 <- num
>     return (Add e0 e1)

There are two simplifications here. We don't have a general simple
expression parser yet, so it only supports parsing adding two number
literals, and we don't deal with whitespace yet, so you must write
"1+2" and not "1 + 2". We will deal with both of these issues below.

We used void to ignore the return of "char '+'". This is not required,
but supresses a warning which you should get (since you are using
-Wall, right?) and I think it is also good style to explicitly say
that the result is being ignored.

To use -Wall in ghci, enter the following at the prompt:

```
*Main> :set -Wall
```

Try it out, then replace the line

```
    void $ char '+'
```

with

```
    char '+'
```

And check you see the warning. Another way of avoiding the warning is
to write this:

```
    _ <- char '+'
```

==== parens

> parens :: Parser SimpleExpr
> parens = do
>     void $ char '('
>     e <- num
>     void $ char ')'
>     return (Parens e)

The same two issues from the 'add' parser apply here: whitespace and
lack of a general simple expression parser, so it just uses the num
parser again instead. Now we will tackle the whitespace issue.

=== whitespace and lexeme parsing

Here is a parser which will skip zero or more whitespace characters.

> whiteSpace :: Parser ()
> whiteSpace = void $ many $ oneOf " \n\t"

In the original parsec documentation, one of the concepts mentioned is
the idea of 'lexeme' parsing. This is a style in which every token
parser should also consume and ignore any trailing whitespace. This is
a simple convention which with a bit of care allows skipping
whitespace exactly once wherever it needs to be skipped. To complete
the lexeme style, we should also always skip leading whitespace at the
top level only.

> parseWithWhitespace :: Parser a -> String -> Either ParseError a
> parseWithWhitespace p = parseWithEof wrapper
>   where
>     wrapper = do
>         whiteSpace
>         p

the wrapper function can also use (>>) to make it a bit shorter:

```
wrapper = whiteSpace >> p
```

Here is a shorter version of this function using (>>):

> parseWithWhitespace' :: Parser a -> String -> Either ParseError a
> parseWithWhitespace' p = parseWithEof (whiteSpace >> p)

Here is the num parser rewritten in the lexeme style:

> lexeme :: Parser a -> Parser a
> lexeme p = do
>            x <- p
>            whiteSpace
>            return x

TODO: review the placement of the function 'lexeme' in all the code
below. Maybe something could be said about all the places that it can
be put.

> num' :: Parser SimpleExpr
> num' = lexeme $ do
>     n <- many1 digit
>     return (Num (read n))

Here it is in action:

```
*Main Data.List> parseWithEof num "1"
Right (Num 1)

*Main Data.List> parseWithEof num " 1"
Left (line 1, column 1):
unexpected " "
expecting digit

*Main Data.List> parseWithEof num "1 "
Left (line 1, column 2):
unexpected ' '
expecting digit or end of input

*Main Data.List> parseWithEof num " 1 "
Left (line 1, column 1):
unexpected " "
expecting digit

*Main Data.List> parseWithWhitespace num' "1"
Right (Num 1)

*Main Data.List> parseWithWhitespace num' " 1"
Right (Num 1)

*Main Data.List> parseWithWhitespace num' "1 "
Right (Num 1)

*Main Data.Lst> parseWithWhitespace num' " 1 "
Right (Num 1)
```

Here are the other functions in lexeme style.

> var' :: Parser SimpleExpr
> var' = lexeme $ do
>     fl <- firstChar
>     rest <- many nonFirstChar
>     return (Var (fl:rest))
>   where
>     firstChar = satisfy (\a -> isLetter a || a == '_')
>     nonFirstChar = satisfy (\a -> isDigit a || isLetter a || a == '_')

> add' :: Parser SimpleExpr
> add' = do
>     e0 <- num'
>     void $ lexeme $ char '+'
>     e1 <- num'
>     return (Add e0 e1)

> parens' :: Parser SimpleExpr
> parens' = do
>     void $ lexeme $ char '('
>     e <- num'
>     void $ lexeme $ char ')'
>     return (Parens e)

In this style, you have to be slightly careful to make sure you call
whitespace at the right points.

Let's try and implement the simpleExpr parser. We can use a function
called 'choice':

> numOrVar :: Parser SimpleExpr
> numOrVar = choice [num', var']

It tries each parser one at a time, finishing with the first one that
succeeds. There are some more details about this later on.

Here is another way to write the numOrVar parser:

> numOrVar' :: Parser SimpleExpr
> numOrVar' = num' <|> var'

In general, you can write 'choice [p0, p1, p2, ...]' as 'p0 <|> p1 <|>
p2 <|> ...'.

TODO: a bunch of examples

Here is the first version of the simpleExpr parser:

> simpleExpr :: Parser SimpleExpr
> simpleExpr = choice [num', var', add', parens']

TODO: a bunch of examples

It works well for some of the parsers, but fails with add': the num'
always partially succeeds first, then fails, so the add' is never
tried. We can rearrange this parser like this:

> simpleExpr' :: Parser SimpleExpr
> simpleExpr' = choice [add', num', var', parens']

TODO: examples again

We have another problem now: when we start parsing the add', see a
num, then fail, it gives up completely. This is because the 'choice'
function (and <|>) will only try the next parser if the parser that
failed consumed no input before failing.

TODO: show examples with satify and choice on 1 char match/no match,
and two char match/no match.

Here is one way to fix it:

> simpleExpr'' :: Parser SimpleExpr
> simpleExpr'' = choice [try add', num', var', parens']

The try function implements backtracking. When this is used in a
choice like this, it means that if the add' parser fails, it will undo
the consumed input and carry on with the next option, instead of
failing completely. If there is another place using try higher up in
the call stack, then we will continue there, otherwise the whole parse
will fail immediately.

The same happens with <|>, we can implement the simpleExpr parser like
this also:

> simpleExpr''' :: Parser SimpleExpr
> simpleExpr''' = try add' <|> num' <|> var' <|> parens'

TODO: show the examples all working

Now we can make 'parens' and 'add' use a general simple expression
parser. Parens is simple:

> parens'' :: Parser SimpleExpr
> parens'' = do
>     void $ lexeme $ char '('
>     e <- simpleExpr'''
>     void $ lexeme $ char ')'
>     return (Parens e)

There is a problem implementing 'add' in the same way:

> add'' :: Parser SimpleExpr
> add'' = do
>     e0 <- simpleExpr'''
>     void $ lexeme $ char '+'
>     e1 <- simpleExpr'''
>     return (Add e0 e1)

It will never return since it calls simpleExpr''' which calls add''
again.

Let's look at another problem:

```
*Main> parseWithWhitespace simpleExpr''' " 1 + 1 + 1"
Left (line 1, column 8):
unexpected '+'
expecting end of input
```

Our parser will only parse one operator, and not a chain of them.

Here is one way to solve it:

> simpleExpr4 :: Parser SimpleExpr
> simpleExpr4 = do
>     e <- term
>     maybeAddSuffix e
>   where
>     maybeAddSuffix e = addSuffix e <|> return e
>     addSuffix e0 = do
>         void $ lexeme $ char '+'
>         e1 <- term
>         maybeAddSuffix (Add e0 e1)
>     term = num' <|> var' <|> parens'

TODO: explain how this works in much more detail

This forces our Add operator to be left associative. This also solves
the previous problem with add calling simpleExpr recursively. There is
lots of discussion about these issues in Parsing theory documents you
can find online, etc..

== general simple expression parser

Here is the all the parser code written out again for clarity.

> numD :: Parser SimpleExpr
> numD = lexeme $ do
>     n <- many1 digit
>     return $ Num $ read n

> varD :: Parser SimpleExpr
> varD = lexeme $ do
>     fl <- firstChar
>     rest <- many nonFirstChar
>     return $ Var (fl:rest)
>   where
>     firstChar = satisfy (\a -> isLetter a || a == '_')
>     nonFirstChar = satisfy (\a -> isDigit a || isLetter a || a == '_')

> parensD :: Parser SimpleExpr
> parensD = do
>     void $ lexeme $ char '('
>     e <- simpleExprD
>     void $ lexeme $ char ')'
>     return $ Parens e

> simpleExprD :: Parser SimpleExpr
> simpleExprD = do
>     e <- term
>     maybeAddSuffix e
>   where
>     maybeAddSuffix e =
>         choice [addSuffix e
>                ,return e]
>     addSuffix e0 = do
>         void $ lexeme $ char '+'
>         e1 <- term
>         maybeAddSuffix (Add e0 e1)
>     term = numD <|> varD <|> parensD


=== Testing with the examples

TODO: write a little manual tester that accepts a parser and a list of
examples, and checks they all parse correctly.

=== Testing with quickcheck

Let's see if we can check with quickcheck. It's a bit tricky testing
parsers in this way, but one way to do something useful is to generate
random asts, convert them to concrete syntax, parse them, and check
the result. We can write a simple 'pretty printer' to convert an ast
to concrete syntax.

==== a pretty printer

TODO: a really simple pretty printer just pasting strings together, no
layout.

==== the quick check code

TODO: write a quickcheck property and arbitary instance and show
running it at the ghci prompt