# Write Yourself a Scheme in 48 Hours/Parsing

## Making project scaffolding and getting `parsec`

We\'ll be using the Parsec
library. To install it, you\'ll need `cabal-install`, which is invoked
with the `cabal` command.

On Debian/Ubuntu: `sudo apt-get install cabal-install`. Alternatively,
you can use ghcup, which works for
many platforms.

After installing `cabal-install`, let\'s make a project:

``` sh
$ cabal update
$ mkdir myProject
$ cd myProject
$ cabal init
```

Now edit `myProject.cabal` such that `parsec` is listed in
`build-depends` listing, in addition to `base`.

Now, the project can be run using `cabal run`:

    Building executable 'myProject' for myProject-0.1.0.0..
    [1 of 1] Compiling Main             ( app/Main.hs )
    Linking myProject-0.1.0.0/x/myProject/build/myProject/myProject ...
    Hello, Haskell!

The last line is the output by the program.

## Writing a Simple Parser

Now, let\'s try writing a very simple parser.

Start by adding these lines to the import section of `app/Main.hs`
(which was generated by `cabal init`):

``` haskell
import Text.ParserCombinators.Parsec hiding (spaces)
import System.Environment
```

This makes the Parsec library functions available to us, except the
`spaces` function, whose name conflicts with a function that we\'ll be
defining later.

Now, we\'ll define a parser that recognizes one of the symbols allowed
in Scheme identifiers:

``` haskell
symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"
```

This is another example of a monad: in this case, the \"extra
information\" that is being hidden is all the info about position in the
input stream, backtracking record, first and follow sets, etc. Parsec
takes care of all of that for us. We need only use the Parsec library
function
`oneOf`,
and it\'ll recognize a single one of any of the characters in the string
passed to it. Parsec provides a number of pre-built parsers: for
example,
`letter`
and
`digit`
are library functions. And as you\'re about to see, you can compose
primitive parsers into more sophisticated productions.

Let\'s define a function to call our parser and handle any possible
errors:

``` haskell
readExpr :: String -> String
readExpr input = case parse symbol "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found value"
```

As you can see from the type signature, `readExpr` is a function (`->`)
from a `String` to a `String`. We name the parameter `input`, and pass
it, along with the `symbol` parser we defined above to the Parsec
function
`parse`.
The second parameter to `parse` is a name for the input. It is used for
error messages.

`parse` can return either the parsed value or an error, so we need to
handle the error case. Following typical Haskell convention, Parsec
returns an
`Either`
data type, using the `Left` constructor to indicate an error and the
`Right` one for a normal value.

We use a `case...of` construction to match the result of `parse` against
these alternatives. If we get a `Left` value (error), then we bind the
error itself to `err` and return \"No match\" with the string
representation of the error. If we get a `Right` value, we bind it to
`val`, ignore it, and return the string \"Found value\".

The `case...of` construction is an example of pattern matching, which we
will see in much greater detail later
on.

Finally, we need to change our main function to call `readExpr` and
print out the result:

``` haskell
main :: IO ()
main = do 
         (expr:_) <- getArgs
         putStrLn (readExpr expr)
```

To compile and run this, you can specify the command line parameters
after the \"executable target\" which the project scaffolding generated
with the call to `init` in the first section. For example:

`$ cabal run myProject $`\
`Found value`\
`$ cabal run myProject a`\
`No match: "lisp" (line 1, column 1):`\
`unexpected "a"`

## Whitespace

Next, we\'ll add a series of improvements to our parser that\'ll let it
recognize progressively more complicated expressions. The current parser
chokes if there\'s whitespace preceding our symbol:

`$ cabal run myProject "   %"`\
`No match: "lisp" (line 1, column 1):`\
`unexpected " "`

Let\'s fix that, so that we ignore whitespace.

First, lets define a parser that recognizes any number of whitespace
characters. Incidentally, this is why we included the `hiding (spaces)`
clause when we imported Parsec: there\'s already a
`spaces`
function in that library, but it doesn\'t quite do what we want it to.
(For that matter, there\'s also a parser called
`lexeme`
that does exactly what we want, but we\'ll ignore that for pedagogical
purposes.)

``` haskell
spaces :: Parser ()
spaces = skipMany1 space
```

Just as functions can be passed to functions, so can actions. Here we
pass the Parser action
`space`
to the Parser action
`skipMany1`,
to get a Parser that will recognize one or more spaces.

Now, let\'s edit our parse function so that it uses this new parser:

``` haskell
readExpr input = case parse (spaces >> symbol) "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found value"
```

We touched briefly on the `>>` (\"bind\") operator in lesson 2, where we
mentioned that it was used behind the scenes to combine the lines of a
do-block. Here, we use it explicitly to combine our whitespace and
symbol parsers. However, bind has completely different semantics in the
Parser and IO monads. In the Parser monad, bind means \"Attempt to match
the first parser, then attempt to match the second with the remaining
input, and fail if either fails.\" In general, bind will have wildly
different effects in different monads; it\'s intended as a general way
to structure computations, and so needs to be general enough to
accommodate all the different types of computations. Read the
documentation for the monad to figure out precisely what it does.

Compile and run this code. Note that since we defined `spaces` in terms
of `skipMany1`, it will no longer recognize a plain old single
character. Instead you *have to* precede a symbol with some whitespace.
We\'ll see how this is useful shortly:

`$ cabal run myProject "   %"`\
`Found value`\
`$ cabal run myProject %`\
`No match: "lisp" (line 1, column 1):`\
`unexpected "%"`\
`expecting space`\
`$ cabal run myProject "   abc"`\
`No match: "lisp" (line 1, column 4):`\
`unexpected "a"`\
`expecting space`

## Return Values

Right now, the parser doesn\'t *do* much of anything---it just tells us
whether a given string can be recognized or not. Generally, we want
something more out of our parsers: we want them to convert the input
into a data structure that we can traverse easily. In this section, we
learn how to define a data type, and how to modify our parser so that it
returns this data type.

First, we need to define a data type that can hold any Lisp value:

``` haskell
data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | String String
             | Bool Bool
```

This is an example of an *algebraic data type*: it defines a set of
possible values that a variable of type LispVal can hold. Each
alternative (called a *constructor* and separated by `|`) contains a tag
for the constructor along with the type of data that the constructor can
hold. In this example, a `LispVal` can be:

1.  An `Atom`, which stores a String naming the atom
2.  A `List`, which stores a list of other LispVals (Haskell lists are
    denoted by brackets); also called a *proper* list
3.  A `DottedList`, representing the Scheme form `(a b . c)`; also
    called an *improper* list. This stores a list of all elements but
    the last, and then stores the last element as another field
4.  A `Number`, containing a Haskell Integer
5.  A `String`, containing a Haskell String
6.  A `Bool`, containing a Haskell boolean value

Constructors and types have different namespaces, so you can have both a
constructor named `String` and a type named `String`. Both types and
constructor tags always begin with capital letters.

Next, let\'s add a few more parsing functions to create values of these
types. A string is a double quote mark, followed by any number of
non-quote characters, followed by a closing quote mark:

``` haskell
parseString :: Parser LispVal
parseString = do
                char '"'
                x <- many (noneOf "\"")
                char '"'
                return $ String x
```

We\'re back to using the `do`-notation instead of the `>>` operator.
This is because we\'ll be retrieving the value of our parse (returned by
`many(noneOf "\"")`) and manipulating it, interleaving some other parse
operations in the meantime. In general, use `>>` if the actions don\'t
return a value, `>>=` if you\'ll be immediately passing that value into
the next action, and `do`-notation otherwise.

Once we\'ve finished the parse and have the Haskell String returned from
`many`, we apply the `String` constructor (from our LispVal data type)
to turn it into a `LispVal`. Every constructor in an algebraic data type
also acts like a function that turns its arguments into a value of its
type. It also serves as a pattern that can be used in the left-hand side
of a pattern-matching expression; we saw an example of this in Lesson
3.1 when we matched our parser
result against the two constructors in the `Either` data type.

We then apply the built-in function
`return`
to lift our `LispVal` into the `Parser` monad. Remember, each line of a
`do`-block must have the same type, but the result of our String
constructor is just a plain old LispVal. `return` lets us wrap that up
in a Parser action that consumes no input but returns it as the inner
value. Thus, the whole `parseString` action will have type
`Parser LispVal`.

The `$` operator is infix function application: it\'s the same as if
we\'d written `return (String x)`, but `$` is right associative and low
precedence, letting us eliminate some parentheses. Since `$` is an
operator, you can do anything with it that you\'d normally do to a
function: pass it around, partially apply it, etc. In this respect, it
functions like the Lisp function
`apply`.

Now let\'s move on to Scheme variables. An
*atom*
is a letter or symbol, followed by any number of letters, digits, or
symbols:

``` haskell
parseAtom :: Parser LispVal
parseAtom = do 
              first <- letter <|> symbol
              rest <- many (letter <|> digit <|> symbol)
              let atom = first:rest
              return $ case atom of 
                         "#t" -> Bool True
                         "#f" -> Bool False
                         _    -> Atom atom
```

Here, we introduce another Parsec combinator, the choice operator
`<|>`.
This tries the first parser, then if it fails, tries the second. If
either succeeds, then it returns the value returned by that parser. The
first parser must fail before it consumes any input: we\'ll see later
how to implement backtracking.

Once we\'ve read the first character and the rest of the atom, we need
to put them together. The \"`let`\" statement defines a new variable
`atom`. We use the list cons operator `:` for this. Instead of `:`, we
could have used the concatenation operator `++` like this
`[first] ++ rest`; recall that `first` is just a single character, so we
convert it into a singleton list by putting brackets around it.

Then we use a case expression to determine which `LispVal` to create and
return, matching against the literal strings for true and false. The
underscore `_` alternative is a readability trick: case blocks continue
until a `_` case (or fail any case which also causes the failure of the
whole `case` expression), think of `_` as a *wildcard*. So if the code
falls through to the `_` case, it always matches, and returns the value
of `atom`.

Finally, we create one more parser, for numbers. This shows one more way
of dealing with monadic values:

``` haskell
parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit
```

It\'s easiest to read this backwards, since both function application
(`$`) and function composition (`.`) associate to the right. The parsec
combinator
many1
matches one or more of its argument, so here we\'re matching one or more
digits. We\'d like to construct a number `LispVal` from the resulting
string, but we have a few type mismatches. First, we use the built-in
function
read
to convert that string into a number. Then we pass the result to
`Number` to get a `LispVal`. The function composition operator `.`
creates a function that applies its right argument and then passes the
result to the left argument, so we use that to combine the two function
applications.

Unfortunately, the result of `many1 digit` is actually a
`Parser String`, so our combined `Number . read` still can\'t operate on
it. We need a way to tell it to just operate on the value inside the
monad, giving us back a `Parser LispVal`. The standard function `liftM`
does exactly that, so we apply `liftM` to our `Number . read` function,
and then apply the result of that to our parser.

We also have to import the Monad module up at the top of our program to
get access to `liftM`:

``` haskell
import Control.Monad
```

This style of programming---relying heavily on function composition,
function application, and passing functions to functions---is very
common in Haskell code. It often lets you express very complicated
algorithms in a single line, breaking down intermediate steps into other
functions that can be combined in various ways. Unfortunately, it means
that you often have to read Haskell code from right-to-left and keep
careful track of the types. We\'ll be seeing many more examples
throughout the rest of the tutorial, so hopefully you\'ll get pretty
comfortable with it.

Let\'s create a parser that accepts either a string, a number, or an
atom:

``` haskell
parseExpr :: Parser LispVal
parseExpr = parseAtom
         <|> parseString
         <|> parseNumber
```

And edit readExpr so it calls our new parser:

``` haskell
readExpr :: String -> String
readExpr input = case parse parseExpr "lisp" input of
    Left err -> "No match: " ++ show err
    Right _ -> "Found value"
```

Compile and run this code, and you\'ll notice that it accepts any
number, string, or symbol, but not other strings:

`$ cabal run myProject "\"this is a string\""`\
`Found value`\
`$ cabal run myProject 25`\
`Found value`\
`$ cabal run myProject symbol`\
`Found value`\
`$ cabal run myProject (symbol)`\
`` bash: syntax error near unexpected token `symbol' ``\
`$ cabal run myProject "(symbol)"`\
`No match: "lisp" (line 1, column 1):`\
`unexpected "("`\
`expecting letter, "\"" or digit`

## Recursive Parsers: Adding lists, dotted lists, and quoted datums

Next, we add a few more parser actions to our interpreter. Start with
the parenthesized lists that make Lisp famous:

``` haskell
parseList :: Parser LispVal
parseList = liftM List $ sepBy parseExpr spaces
```

This works analogously to `parseNumber`, first parsing a series of
expressions separated by whitespace (`sepBy parseExpr spaces`) and then
apply the List constructor to it within the Parser monad. Note too that
we can pass `parseExpr` to
sepBy,
even though it\'s an action we wrote ourselves.

The dotted-list parser is somewhat more complex, but still uses only
concepts that we\'re already familiar with:

``` haskell
parseDottedList :: Parser LispVal
parseDottedList = do
    head <- endBy parseExpr spaces
    tail <- char '.' >> spaces >> parseExpr
    return $ DottedList head tail
```

Note how we can sequence together a series of Parser actions with `>>`
and then use the whole sequence on the right hand side of a
do-statement. The expression `char '.' >> spaces` returns a `Parser ()`,
then combining that with `parseExpr` gives a `Parser LispVal`, exactly
the type we need for the do-block.

Next, let\'s add support for the single-quote syntactic sugar of Scheme:

``` haskell
parseQuoted :: Parser LispVal
parseQuoted = do
    char '\''
    x <- parseExpr
    return $ List [Atom "quote", x]
```

Most of this is fairly familiar stuff: it reads a single quote
character, reads an expression and binds it to `x`, and then returns
`(quote x)`, to use Scheme notation. The `Atom` constructor works like
an ordinary function: you pass it the String you\'re encapsulating, and
it gives you back a LispVal. You can do anything with this LispVal that
you normally could, like put it in a list.

Finally, edit our definition of parseExpr to include our new parsers:

``` haskell
parseExpr :: Parser LispVal
parseExpr = parseAtom
         <|> parseString
         <|> parseNumber
         <|> parseQuoted
         <|> do char '('
                x <- try parseList <|> parseDottedList
                char ')'
                return x
```

This illustrates one last feature of Parsec: backtracking. `parseList`
and `parseDottedList` recognize identical strings up to the dot; this
breaks the requirement that a choice alternative may not consume any
input before failing. The
try
combinator attempts to run the specified parser, but if it fails, it
backs up to the previous state. This lets you use it in a choice
alternative without interfering with the other alternative.

Compile and run this code:

`$ cabal run myProject "(a test)"`\
`Found value`\
`$ cabal run myProject "(a (nested) test)"`\
`Found value`\
`$ cabal run myProject "(a (dotted . list) test)"`\
`Found value`\
`$ cabal run myProject "(a '(quoted (dotted . list)) test)"`\
`Found value`\
`$ cabal run myProject "(a '(imbalanced parens)"`\
`No match: "lisp" (line 1, column 24):`\
`unexpected end of input`\
`expecting space or ")"`

Note that by referring to `parseExpr` within our parsers, we can nest
them arbitrarily deep. Thus, we get a full Lisp reader with only a few
definitions. That\'s the power of recursion.

