Write Yourself a Scheme in 48 Hours/Parsing
Making project scaffolding and getting parsec
editWe'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:
$ 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
editNow, 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):
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:
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:
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:
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
editNext, 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.)
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:
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
editRight 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:
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:
- An
Atom, which stores a String naming the atom - A
List, which stores a list of other LispVals (Haskell lists are denoted by brackets); also called a proper list - 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 - A
Number, containing a Haskell Integer - A
String, containing a Haskell String - 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:
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:
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:
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:
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:
parseExpr :: Parser LispVal
parseExpr = parseAtom
<|> parseString
<|> parseNumber
And edit readExpr so it calls our new parser:
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
| Exercises |
|---|
|
Recursive Parsers: Adding lists, dotted lists, and quoted datums
editNext, we add a few more parser actions to our interpreter. Start with the parenthesized lists that make Lisp famous:
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:
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:
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:
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.
| Exercises |
|---|
|