This project is a Lisp interpreter written in Haskell, based on this book. It includes a general-purpose monadic parsing library based on this paper which implements a subset of the Parsec library. The Lisp interpreter is built on top of these parsing functions.
The parsing library in Parsing.hs
features a number of simple and useful combinators that are used to make more powerful parsers. For example:
sat :: (Char -> Bool) -> Parser Char
consumes characters if they satisfy a predicate.
We define char :: Char -> Parser Char
as char c = sat (c ==)
as a parser to match against a specific letter.
We use char
to define string :: String -> Parser String
as string (c:cs) = do {char c; string cs; return (c:cs)}
to recursively match against a specific string.
The parsing library also takes advantage of monads to chain together parsers easily. For example:
We define a utility function many :: Parser a -> Parser [a]
that parses repeated applications of a parser p
. many
relies on a helper function many1 :: Parser a -> Parser [a]
which is defined as many1 p = do {a <- p; as <- manyp; return (a:as)}
. many
is the main way we chain together parsers.
There are many examples of this in Parsing.hs
, namely sepby
, chainr
and chainl
.
This interpreter supports many features of the Lisp language.