I recently wrote code to parse lambda expressions written in a lisp like format, using a small hand-rolled parsing library.
The goal
This code was written as a part of this code-golf challenge not as code-golf, but as a demo for the concept. My goals for this were
- It should be simple enough that by looking over it one should be able to understand what is being parsed.
- It should be self-contained so that if someone wants to dig into the nitty-gritty and understand how it works they can.
I chose Haskell for this because:
- In my experience imperative parsers are more difficult to understand than combinator parsers.
- In my experience combinator parsing has a smaller footprint since it can assemble complex parsers from simple components.
- In my experience it is a joy to write and read parsers in Haskell.
The code then consists of a minimalist "library" of simple helper functions, and the definition of the actual parser. If it is important, you should be able to see exactly how it is presented via the link above.
I'd like to get an idea of how well I achieved these goals and what steps could be taken to better present the idea through code.
Expressions
The goal is to verify that a string is a properly formatted lambda expression, consisting of
abs(abstraction) to introduce a new variable.var(variable) to use a variable.app(application) to apply one lambda to another.
formatted as a lisp list.
For example
(abs x (app (var x) (var x)))
Is a valid expression representing \$\lambda x. x x\$.
Additionally we want to verify the expression doesn't use undeclared variables and doesn't shadow any variables.
So
(abs y (var x))
is not valid because x is not declared. And
(abs y (abs y (abs x (var x))))
is not valid because y is shadowed.
A precise grammar for the valid expressions is given
\$ S\left(C\right) := \left\{ \begin{array}[rr] \ \color{green}{\texttt{(var }}x\color{green}{\texttt{)}} & \textrm{ where } x\in C \\ \color{green}{\texttt{(abs }} x\texttt{ }S(C\cup\{x\})\color{green}{\texttt{)}} & \textrm{ where } x\notin C\\ \color{green}{\texttt{(app }} S(C)\texttt{ }S(C)\color{green}{\texttt{)}} & \end{array} \right. \$
Where valid expressions are strings spanned by this grammar starting from \$S(\{\})\$.
There are two extra things to note:
- The whitespace is intentionally inflexible in this specification.
- Our Parse is not producing a parse tree, only confirming whether an expression meets the specifications.
Library
import Control.Applicative
( liftA2
, Alternative (..)
)
import Control.Monad
( guard
)
newtype Parser a =
Parser (String -> [(String, a)])
apply :: Parser a -> String -> [(String, a)]
apply (Parser p) s =
p s
instance Functor Parser where
fmap func (Parser p) =
Parser $ fmap (map (fmap func)) p
instance Applicative Parser where
pure x =
Parser ( \ string -> [(string, x)] )
liftA2 f (Parser p1) (Parser p2) =
Parser
( \ string -> do
(rem1, res1) <- p1 string
(rem2, res2) <- p2 rem1
return (rem2, f res1 res2)
)
instance Monad Parser where
Parser p >>= f =
Parser
( \ string -> do
(rem1, res1) <- p string
apply (f res1) rem1
)
instance Alternative Parser where
empty =
Parser ( \ _ -> [] )
Parser p1 <|> Parser p2 =
Parser $ ( \ string -> p1 string ++ p2 string )
charBy :: (Char -> Bool) -> Parser Char
charBy predicate =
Parser go
where
go (a : b) =
[ (b, a) | predicate a ]
go [] =
[]
char :: Char -> Parser Char
char x =
charBy (x==)
string :: String -> Parser String
string =
traverse char
choice :: [Parser a] -> Parser a
choice =
foldr (<|>) empty
Parser
lambda :: [String] -> Parser ()
lambda variables =
do
char '('
choice
[ do
string "abs "
name <- some $ charBy (`elem` ['a'..'z'])
guard $ notElem name variables
char ' '
lambda (name : variables)
, do
string "var "
choice (map string variables)
return ()
, do
string "app "
lambda variables
char ' '
lambda variables
]
char ')'
return ()
Description
This uses monadic parsing to get the job done. I build a parser type implement the necessary type classes and a couple of helper functions. The actual parser follows the same structure as the given grammar.
The code does a single pass without any tokenizer. This might be a little odd, but because the domain I think that such would make the code more complex, and we have very rigid white-space rules.
Review
I welcome all feedback on how to make this code more presentable. However the specific questions I would like to prompt are:
- Is
donotation a good choice given my goals? - Was it a good choice to use a single pass method? Might it be more presentable to parse into a tree and then verify certain properties of the tree?
- Are there any subtle Haskell-isms that I have that could easily be removed to make the more approachable to a general audience?
of course keeping my initial goals in mind.
