1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/part2.tex Fri Sep 26 22:39:40 2008 -0700
1.3 @@ -0,0 +1,778 @@
1.4 +\begin{frame}[fragile]
1.5 + \frametitle{A little bit about JSON}
1.6 +
1.7 + A popular interchange format for structured data: simpler than XML,
1.8 + and widely supported.
1.9 +
1.10 + Basic types:
1.11 + \begin{itemize}
1.12 + \item Number
1.13 + \item String
1.14 + \item Boolean
1.15 + \item Null
1.16 + \end{itemize}
1.17 +
1.18 + Derived types:
1.19 + \begin{itemize}
1.20 + \item Object: unordered name/value map
1.21 + \item Array: ordered collection of values
1.22 + \end{itemize}
1.23 +\end{frame}
1.24 +
1.25 +\begin{frame}[fragile]
1.26 + \frametitle{JSON in Haskell}
1.27 +
1.28 +\begin{lstlisting}
1.29 +data JSValue
1.30 + = JSNull
1.31 + | JSBool !Bool
1.32 + | JSRational !Rational
1.33 + | JSString JSString
1.34 + | JSArray [JSValue]
1.35 + | JSObject (JSObject JSValue)
1.36 +\end{lstlisting}
1.37 +
1.38 +\end{frame}
1.39 +
1.40 +\begin{frame}[fragile]
1.41 + \frametitle{What is a \lstinline!JSString!?}
1.42 +
1.43 + We hide the underlying use of a \lstinline!String!:
1.44 +\begin{lstlisting}
1.45 +newtype JSString = JSONString { fromJSString :: String }
1.46 +
1.47 +toJSString :: String -> JSString
1.48 +toJSString = JSONString
1.49 +\end{lstlisting}
1.50 +
1.51 + We do the same with JSON objects:
1.52 +\begin{lstlisting}
1.53 +newtype JSObject a = JSONObject { fromJSObject :: [(String, a)] }
1.54 +
1.55 +toJSObject :: [(String,a)] -> JSObject a
1.56 +toJSObject = JSONObject
1.57 +\end{lstlisting}
1.58 +\end{frame}
1.59 +
1.60 +\begin{frame}[fragile]
1.61 + \frametitle{JSON conversion}
1.62 +
1.63 + In Haskell, we capture type-dependent patterns using
1.64 + \emph{typeclasses}:
1.65 + \begin{itemize}
1.66 + \item The class of types whose values can be converted to and from
1.67 + JSON
1.68 + \end{itemize}
1.69 +\begin{lstlisting}
1.70 +data Result a = Ok a | Error String
1.71 +
1.72 +class JSON a where
1.73 + readJSON :: JSValue -> Result a
1.74 + showJSON :: a -> JSValue
1.75 +\end{lstlisting}
1.76 +\end{frame}
1.77 +
1.78 +\begin{frame}[fragile]
1.79 + \frametitle{Bool as JSON}
1.80 +
1.81 + Here's a simple way to declare the \lstinline!Bool! type as an
1.82 + instance of the \lstinline!JSON! class:
1.83 +\begin{lstlisting}
1.84 +instance JSON Bool where
1.85 + showJSON = JSBool
1.86 +
1.87 + readJSON (JSBool b) = Ok b
1.88 + readJSON _ = Error "Bool parse failed"
1.89 +\end{lstlisting}
1.90 +
1.91 + This has a design problem:
1.92 + \begin{itemize}
1.93 + \item We've plumbed our \lstinline!Result! type straight in
1.94 + \item If we want to change its implementation, it will be painful
1.95 + \end{itemize}
1.96 +\end{frame}
1.97 +
1.98 +\begin{frame}[fragile]
1.99 + \frametitle{Hiding the plumbing}
1.100 +
1.101 + A simple (but good enough!) approach to abstraction:
1.102 +\begin{lstlisting}
1.103 +success :: a -> Result a
1.104 +success k = Ok k
1.105 +
1.106 +failure :: String -> Result a
1.107 +failure errMsg = Error errMsg
1.108 +\end{lstlisting}
1.109 + Functions like these are sometimes called ``smart constructors''.
1.110 +\end{frame}
1.111 +
1.112 +\begin{frame}[fragile]
1.113 + \frametitle{Does this affect our code much?}
1.114 + We simply replace the explicit constructors with the functions we
1.115 + just defined:
1.116 +\begin{lstlisting}
1.117 +instance JSON Bool where
1.118 + showJSON = JSBool
1.119 +
1.120 + readJSON (JSBool b)
1.121 + = success b
1.122 + readJSON _ = failure "Bool parse failed"
1.123 +\end{lstlisting}
1.124 +\end{frame}
1.125 +
1.126 +\begin{frame}
1.127 + \frametitle{JSON input and output}
1.128 +
1.129 + We can now convert between normal Haskell values and our JSON
1.130 + representation. But...
1.131 + \begin{itemize}
1.132 + \item ...we still need to be able to transmit this stuff over the
1.133 + wire.
1.134 + \end{itemize}
1.135 +
1.136 + Which is more fun to mull over? Parsing!
1.137 +\end{frame}
1.138 +
1.139 +\begin{frame}
1.140 + \frametitle{A functional view of parsing}
1.141 +
1.142 + Here's a super-simple perspective:
1.143 + \begin{itemize}
1.144 + \item Take a piece of data (usually a sequence)
1.145 + \item Try to apply an interpretation to it
1.146 + \end{itemize}
1.147 +
1.148 + How might we represent this?
1.149 +\end{frame}
1.150 +
1.151 +\begin{frame}[fragile]
1.152 + \frametitle{A basic type signature for parsing}
1.153 +
1.154 + Take two type variables, i.e. placeholders for types that we'll
1.155 + substitute later:
1.156 + \begin{itemize}
1.157 + \item \lstinline!s!---the state (data) we want to parse
1.158 + \item \lstinline!a!---the type of its interpretation
1.159 + \end{itemize}
1.160 + We get this generic type signature:
1.161 +\begin{lstlisting}
1.162 +s -> a
1.163 +\end{lstlisting}
1.164 + Let's make the task more concrete:
1.165 + \begin{itemize}
1.166 + \item Parse a \lstinline!String! as an \lstinline!Int!
1.167 + \end{itemize}
1.168 +\begin{lstlisting}
1.169 +String -> Int
1.170 +\end{lstlisting}
1.171 + What's missing?
1.172 +\end{frame}
1.173 +
1.174 +\begin{frame}[fragile]
1.175 + \frametitle{Parsing as state transformation}
1.176 +
1.177 + After we've parsed one \lstinline!Int!, we might have more data in
1.178 + our \lstinline!String! that we want to parse.
1.179 +
1.180 + How to represent this? Return the transformed state and the result
1.181 + in a tuple.
1.182 +\begin{lstlisting}
1.183 +s -> (a,s)
1.184 +\end{lstlisting}
1.185 + We accept an \emph{input state} of type \lstinline!s!, and return a
1.186 + \emph{transformed state}, also of type \lstinline!s!.
1.187 +\end{frame}
1.188 +
1.189 +\begin{frame}[fragile]
1.190 + \frametitle{Parsing is composable}
1.191 +
1.192 + Let's give integer parsing a name:
1.193 +\begin{lstlisting}
1.194 +parseDigit :: String -> (Int, String)
1.195 +\end{lstlisting}
1.196 +
1.197 + How might we want to parse two digits?
1.198 +\begin{lstlisting}
1.199 +parseTwoDigits :: String -> ((Int,Int), String)
1.200 +parseTwoDigits s =
1.201 + let (i,t) = parseDigit s
1.202 + (j,u) = parseDigit t
1.203 + in ((i,j),u)
1.204 +\end{lstlisting}
1.205 +\end{frame}
1.206 +
1.207 +\begin{frame}[fragile]
1.208 + \frametitle{Chaining parses more tidily}
1.209 +
1.210 + It's not good to represent the guts of our state explicitly using
1.211 + pairs:
1.212 + \begin{itemize}
1.213 + \item Tying ourselves to an implementation eliminates wiggle room.
1.214 + \end{itemize}
1.215 +
1.216 + Here's an alternative approach.
1.217 +\begin{lstlisting}
1.218 +newtype State s a = State {
1.219 + runState :: s -> (a, s)
1.220 + }
1.221 +\end{lstlisting}
1.222 +
1.223 + \begin{itemize}
1.224 + \item A \lstinline!newline! declaration \emph{hides} our
1.225 + implementation. It has no runtime cost.
1.226 + \item The \lstinline!runState! function is a \emph{deconstructor}: it
1.227 + exposes the underlying value.
1.228 + \end{itemize}
1.229 +\end{frame}
1.230 +
1.231 +\begin{frame}[fragile]
1.232 + \frametitle{Chaining parses}
1.233 +
1.234 + Given a function that produces a result and a new state, we can
1.235 + ``chain up'' another function that accepts its result.
1.236 +\begin{lstlisting}
1.237 +chainStates :: State s a -> (a -> State s b) -> State s b
1.238 +chainStates m k = State chainFunc
1.239 + where chainFunc s =
1.240 + let (a,t) = runState m s
1.241 + in runState (k a) t
1.242 +\end{lstlisting}
1.243 +
1.244 + Notice that the result type is compatible with the input:
1.245 + \begin{itemize}
1.246 + \item We can chain uses of \lstinline!chainStates!!
1.247 + \end{itemize}
1.248 +\end{frame}
1.249 +
1.250 +\begin{frame}[fragile]
1.251 + \frametitle{Injecting a pure value}
1.252 +
1.253 + We'll often want to leave the current state untouched, but inject a
1.254 + normal value that we can use when chaining.
1.255 +
1.256 +\begin{lstlisting}
1.257 +pureState :: a -> State s a
1.258 +pureState a = State $ \s -> (a, s)
1.259 +\end{lstlisting}
1.260 +\end{frame}
1.261 +
1.262 +\begin{frame}[fragile]
1.263 + \frametitle{What about computations that might fail?}
1.264 +
1.265 + Try these in in \texttt{ghci}:
1.266 +\begin{verbatim}
1.267 +Prelude> head [1,2,3]
1.268 +1
1.269 +Prelude> head []
1.270 +\end{verbatim}
1.271 + What gets printed in the second case?
1.272 +\end{frame}
1.273 +
1.274 +\begin{frame}[fragile]
1.275 + \frametitle{One approach to potential failure}
1.276 +
1.277 + The Prelude defines this handy standard type:
1.278 +\begin{lstlisting}
1.279 +data Maybe a = Just a
1.280 + | Nothing
1.281 +\end{lstlisting}
1.282 +
1.283 + We can use it as follows:
1.284 +\begin{lstlisting}
1.285 +safeHead (x:_) = Just x
1.286 +safeHead [] = Nothing
1.287 +\end{lstlisting}
1.288 + Save this in a source file, load it into \texttt{ghci}, and try it
1.289 + out.
1.290 +\end{frame}
1.291 +
1.292 +\begin{frame}[fragile]
1.293 + \frametitle{Some familiar operations}
1.294 +
1.295 + We can chain \lstinline!Maybe! values:
1.296 +\begin{lstlisting}
1.297 +chainMaybes :: Maybe a -> (a -> Maybe b)
1.298 + -> Maybe b
1.299 +chainMaybes Nothing k = Nothing
1.300 +chainMaybes (Just x) k = k x
1.301 +\end{lstlisting}
1.302 + This gives us \emph{short circuiting} if any computation in a chain
1.303 + fails:
1.304 + \begin{itemize}
1.305 + \item \lstinline!Maybe! is the Ur-exception.
1.306 + \end{itemize}
1.307 +
1.308 + We can also inject a pure value into a \lstinline!Maybe!-typed
1.309 + computation:
1.310 +\begin{lstlisting}
1.311 +pureMaybe :: a -> Maybe a
1.312 +pureMaybe x = Just x
1.313 +\end{lstlisting}
1.314 +\end{frame}
1.315 +
1.316 +\begin{frame}[fragile]
1.317 + \frametitle{What do these types have in common?}
1.318 +
1.319 + Chaining:
1.320 +\begin{lstlisting}
1.321 +chainMaybes :: Maybe a -> (a -> Maybe b)
1.322 + -> Maybe b
1.323 +chainStates :: State s a -> (a -> State s b)
1.324 + -> State s b
1.325 +\end{lstlisting}
1.326 +
1.327 + Injection of a pure value:
1.328 +\begin{lstlisting}
1.329 +pureState :: a -> State s a
1.330 +pureMaybe :: a -> Maybe a
1.331 +\end{lstlisting}
1.332 +
1.333 + \begin{itemize}
1.334 + \item Abstract away the type constructors, and these have
1.335 + \emph{identical} types!
1.336 + \end{itemize}
1.337 +\end{frame}
1.338 +
1.339 +\begin{frame}[fragile]
1.340 + \frametitle{Monads}
1.341 +
1.342 + More type-related pattern capture, courtesy of typeclasses:
1.343 +\begin{lstlisting}
1.344 +class Monad m where
1.345 + -- chain
1.346 + (>>=) :: m a -> (a -> m b) -> m b
1.347 +
1.348 + -- inject a pure value
1.349 + return :: a -> m a
1.350 +\end{lstlisting}
1.351 +\end{frame}
1.352 +
1.353 +\begin{frame}[fragile]
1.354 + \frametitle{Instances}
1.355 +
1.356 + When a type is an \emph{instance} of a typeclass, it supplies
1.357 + particular implementations of the typeclass's functions:
1.358 +\begin{lstlisting}
1.359 +instance Monad Maybe where
1.360 + (>>=) = chainMaybes
1.361 + return = pureMaybe
1.362 +
1.363 +instance Monad (State s) where
1.364 + (>>=) = chainStates
1.365 + return = pureState
1.366 +\end{lstlisting}
1.367 +\end{frame}
1.368 +
1.369 +\begin{frame}[fragile]
1.370 + \frametitle{Chaining with monads}
1.371 +
1.372 + Using the methods of the \lstinline!Monad! typeclass:
1.373 +\begin{lstlisting}
1.374 +parseThreeDigits =
1.375 + parseDigit >>= \a ->
1.376 + parseDigit >>= \b ->
1.377 + parseDigit >>= \c ->
1.378 + return (a,b,c)
1.379 +\end{lstlisting}
1.380 +
1.381 + Syntactically sugared with \lstinline!do!-notation:
1.382 +\begin{lstlisting}
1.383 +parseThreeDigits = do
1.384 + a <- parseDigit
1.385 + b <- parseDigit
1.386 + c <- parseDigit
1.387 + return (a,b,c)
1.388 +\end{lstlisting}
1.389 + This now looks suspiciously like imperative code.
1.390 +\end{frame}
1.391 +
1.392 +\begin{frame}
1.393 + \frametitle{Haven't we forgotten something?}
1.394 +
1.395 + What happens if we want to parse a digit out of a string that
1.396 + doesn't contain any?
1.397 + \begin{itemize}
1.398 + \item We'd like to ``break the chain'' if a parse fails.
1.399 + \item We have this nice \lstinline!Maybe! type for representing
1.400 + failure.
1.401 + \end{itemize}
1.402 +
1.403 + Alas, we can't combine the \lstinline!Maybe! monad with the
1.404 + \lstinline!State! monad.
1.405 + \begin{itemize}
1.406 + \item Different monads do not combine.
1.407 + \end{itemize}
1.408 +\end{frame}
1.409 +
1.410 +\begin{frame}[fragile]
1.411 + \frametitle{But this is awful! Don't we need lots of boilerplate?}
1.412 +
1.413 + Are we condemned to a world of numerous slightly tweaked custom
1.414 + monads?
1.415 +
1.416 + We can \emph{adapt} the behaviour of an underlying monad.
1.417 +\begin{lstlisting}
1.418 +newtype MaybeT m a = MaybeT {
1.419 + runMaybeT :: m (Maybe a)
1.420 + }
1.421 +\end{lstlisting}
1.422 +\end{frame}
1.423 +
1.424 +\begin{frame}[fragile]
1.425 + \frametitle{Can we inject a pure value?}
1.426 +\begin{lstlisting}
1.427 +pureMaybeT :: (Monad m) => a -> MaybeT m a
1.428 +pureMaybeT a = MaybeT (return (Just a))
1.429 +\end{lstlisting}
1.430 +\end{frame}
1.431 +
1.432 +\begin{frame}[fragile]
1.433 + \frametitle{Can we write a chaining function?}
1.434 +
1.435 +\begin{lstlisting}
1.436 +chainMaybeTs :: (Monad m) => MaybeT m a -> (a -> MaybeT m b)
1.437 + -> MaybeT m b
1.438 +
1.439 +x `chainMaybeTs` f = MaybeT $ do
1.440 + unwrapped <- runMaybeT x
1.441 + case unwrapped of
1.442 + Nothing -> return Nothing
1.443 + Just y -> runMaybeT (f y)
1.444 +\end{lstlisting}
1.445 +\end{frame}
1.446 +
1.447 +\begin{frame}[fragile]
1.448 + \frametitle{Making a \lstinline!Monad! instance}
1.449 +
1.450 + Given an underlying monad, we can stack a \lstinline!MaybeT! on top
1.451 + of it and get a new monad.
1.452 +\begin{lstlisting}
1.453 +instance (Monad m) => Monad (MaybeT m) where
1.454 + (>>=) = chainMaybeTs
1.455 + return = pureMaybeT
1.456 +\end{lstlisting}
1.457 +
1.458 +\end{frame}
1.459 +
1.460 +\begin{frame}[fragile]
1.461 + \frametitle{A custom monad in 2 lines of code}
1.462 +
1.463 + A parsing type that can short-circuit:
1.464 +\begin{lstlisting}
1.465 +{-# LANGUAGE GeneralizedNewtypeDeriving #-}
1.466 +
1.467 +newtype MyParser a = MyP (MaybeT (State String) a)
1.468 + deriving (Monad, MonadState String)
1.469 +\end{lstlisting}
1.470 +
1.471 + We use a GHC extension to automatically generate instances of
1.472 + non-H98 typeclasses:
1.473 + \begin{itemize}
1.474 + \item \lstinline!Monad!
1.475 + \item \lstinline!MonadState String!
1.476 + \end{itemize}
1.477 +\end{frame}
1.478 +
1.479 +\begin{frame}[fragile]
1.480 + \frametitle{What is \lstinline!MonadState!?}
1.481 +
1.482 + The \lstinline!State! monad is parameterised over its underlying
1.483 + state, as \lstinline!State s!:
1.484 + \begin{itemize}
1.485 + \item It knows nothing about the state, and cannot manipulate it.
1.486 + \end{itemize}
1.487 + Instead, it implements an interface that lets us query and modify
1.488 + the state ourselves:
1.489 +\begin{lstlisting}
1.490 +class (Monad m) => MonadState s m
1.491 + -- query the current state
1.492 + get :: m s
1.493 +
1.494 + -- replace the state with a new one
1.495 + put :: s -> m ()
1.496 +\end{lstlisting}
1.497 +\end{frame}
1.498 +
1.499 +\begin{frame}[fragile]
1.500 + \frametitle{Parsing text}
1.501 +
1.502 + In essence:
1.503 + \begin{itemize}
1.504 + \item Get the current state, modify it, put the new state back.
1.505 + \end{itemize}
1.506 +
1.507 + What do we do on failure?
1.508 +\begin{lstlisting}
1.509 +string :: String -> MyParser ()
1.510 +string str = do
1.511 + s <- get
1.512 + let (hd,tl) = splitAt (length str) s
1.513 + if str == hd
1.514 + then put tl
1.515 + else fail $ "failed to match " ++ show str
1.516 +\end{lstlisting}
1.517 +\end{frame}
1.518 +
1.519 +\begin{frame}
1.520 + \frametitle{Shipment of fail}
1.521 +
1.522 + We've carefully hidden \lstinline!fail! so far. Why?
1.523 + \begin{itemize}
1.524 + \item Many monads have a \emph{very bad} definition:
1.525 + \lstinline!error!.
1.526 + \end{itemize}
1.527 +
1.528 + What's the problem with \lstinline!error!?
1.529 + \begin{itemize}
1.530 + \item It throws an exception that we can't catch in pure code.
1.531 + \item It's only safe to use in catastrophic cases.
1.532 + \end{itemize}
1.533 +\end{frame}
1.534 +
1.535 +\begin{frame}
1.536 + \frametitle{Non-catastrophic failure}
1.537 +
1.538 + A bread-and-butter activity in parsing is \emph{lookahead}:
1.539 + \begin{itemize}
1.540 + \item Inspect the input stream and see what to do next
1.541 + \end{itemize}
1.542 +
1.543 + JSON example:
1.544 + \begin{itemize}
1.545 + \item An object begins with ``\texttt{\{}''
1.546 + \item An array begins with ``\texttt{[}''
1.547 + \end{itemize}
1.548 +
1.549 + We look at the next input token to figure out what to do.
1.550 + \begin{itemize}
1.551 + \item If we fail to match ``\texttt{\{}'', it's not an error.
1.552 + \item We just try ``\texttt{[}'' instead.
1.553 + \end{itemize}
1.554 +\end{frame}
1.555 +
1.556 +\begin{frame}
1.557 + \frametitle{Giving ourselves alternatives}
1.558 +
1.559 + We have two conflicting goals:
1.560 + \begin{itemize}
1.561 + \item We like to keep our implementation options open.
1.562 + \item Whether \lstinline!fail! crashes depends on the underlying monad.
1.563 + \end{itemize}
1.564 + We need a safer, \emph{abstract} way to fail.
1.565 +\end{frame}
1.566 +
1.567 +\begin{frame}[fragile]
1.568 + \frametitle{MonadPlus}
1.569 +
1.570 + A typeclass with two methods:
1.571 +\begin{lstlisting}
1.572 +class Monad m => MonadPlus m where
1.573 + -- non-fatal failure
1.574 + mzero :: m a
1.575 +
1.576 + -- if the first action fails,
1.577 + -- perform the second instead
1.578 + mplus :: m a -> m a -> m a
1.579 +\end{lstlisting}
1.580 + To upgrade our code, we replace our use of \lstinline!fail! with
1.581 + \lstinline!mzero!.
1.582 +\end{frame}
1.583 +
1.584 +\begin{frame}[fragile]
1.585 + \frametitle{Writing a MonadZero instance}
1.586 +
1.587 + We can easily make any stack of \lstinline!MaybeT! atop another
1.588 + monad a \lstinline!MonadPlus!:
1.589 +\begin{lstlisting}
1.590 +instance Monad m => MonadPlus (MaybeT m) where
1.591 + mzero = MaybeT $ return Nothing
1.592 +
1.593 + a `mplus` b = MaybeT $ do
1.594 + result <- runMaybeT a
1.595 + case result of
1.596 + Just k -> return (Just k)
1.597 + Nothing -> runMaybeT b
1.598 +\end{lstlisting}
1.599 + We simply add \lstinline!MonadPlus! to the list of typeclasses we
1.600 + ask GHC to automatically derive for us.
1.601 +\end{frame}
1.602 +
1.603 +\begin{frame}[fragile]
1.604 + \frametitle{Using \lstinline!MonadPlus!}
1.605 +
1.606 + Given functions that know how to parse bits of JSON:
1.607 +\begin{lstlisting}
1.608 +parseObject :: MyParser [(String,JSValue)]
1.609 +parseArray :: MyParser [JSValue]
1.610 +\end{lstlisting}
1.611 +
1.612 + We can turn them into a coherent whole:
1.613 +\begin{lstlisting}
1.614 +parseJSON :: MyParser JSValue
1.615 +parseJSON =
1.616 + (parseObject >>= \o -> return (JSObject o))
1.617 + `mplus`
1.618 + (parseArray >>= \a -> return (JSArray a))
1.619 + `mplus`
1.620 + ...
1.621 +\end{lstlisting}
1.622 +\end{frame}
1.623 +
1.624 +\begin{frame}[fragile]
1.625 + \frametitle{The problem of boilerplate}
1.626 +
1.627 + Here's a repeated pattern from our parser:
1.628 +\begin{lstlisting}
1.629 +foo >>= \x -> return (bar x)
1.630 +\end{lstlisting}
1.631 + These brief uses of variables, \lstinline!>>=!, and
1.632 + \lstinline!return! are redundant and burdensome.
1.633 +
1.634 + In fact, this pattern of applying a pure function to a monadic
1.635 + result is ubiquitous.
1.636 +\end{frame}
1.637 +
1.638 +\begin{frame}[fragile]
1.639 + \frametitle{Boilerplate removal via lifting}
1.640 +
1.641 + We replace this boilerplate with \lstinline!liftM!:
1.642 +\begin{lstlisting}
1.643 +liftM :: Monad m => (a -> b) -> m a -> m b
1.644 +\end{lstlisting}
1.645 + We refer to this as \emph{lifting} a pure function into the monad.
1.646 +
1.647 +\begin{lstlisting}
1.648 +parseJSON =
1.649 + (JSObject `liftM` parseObject)
1.650 + `mplus`
1.651 + (JSArray `liftM` parseArray)
1.652 +\end{lstlisting}
1.653 +
1.654 + This style of programming looks less imperative, and more
1.655 + applicative.
1.656 +\end{frame}
1.657 +
1.658 +\begin{frame}
1.659 + \frametitle{The Parsec library}
1.660 +
1.661 + Our motivation so far:
1.662 + \begin{itemize}
1.663 + \item Show you that it's \emph{really easy} to build a monadic
1.664 + parsing library
1.665 + \end{itemize}
1.666 +
1.667 + But we must concede:
1.668 + \begin{itemize}
1.669 + \item Maybe you simply want to parse stuff
1.670 + \end{itemize}
1.671 +
1.672 + Instead of rolling your own, use Daan Leijen's Parsec library.
1.673 +\end{frame}
1.674 +
1.675 +\begin{frame}
1.676 + \frametitle{What to expect from Parsec}
1.677 +
1.678 + It has some great advantages:
1.679 + \begin{itemize}
1.680 + \item A complete, concise EDSL for building parsers
1.681 + \item Easy to learn
1.682 + \item Produces useful error messages
1.683 + \end{itemize}
1.684 +
1.685 + But it's not perfect:
1.686 + \begin{itemize}
1.687 + \item Strict, so cannot parsing huge streams incrementally
1.688 + \item Based on \lstinline!String!, hence slow
1.689 + \item Accepts, and chokes on, left-recursive grammars
1.690 + \end{itemize}
1.691 +\end{frame}
1.692 +
1.693 +\begin{frame}[fragile]
1.694 + \frametitle{Parsing a JSON string}
1.695 + An example of Parsec's concision:
1.696 +\begin{lstlisting}
1.697 +jsonString = between (char '\"') (char '\"')
1.698 + (many jsonChar)
1.699 +\end{lstlisting}
1.700 +
1.701 + Some parsing combinators explained:
1.702 + \begin{itemize}
1.703 + \item \lstinline!between! matches its 1st argument, then its 3rd,
1.704 + then its 2nd
1.705 + \item \lstinline!many! runs a parser until it fails
1.706 +\item It returns a list of parse results
1.707 + \end{itemize}
1.708 +\end{frame}
1.709 +
1.710 +\begin{frame}[fragile]
1.711 + \frametitle{Parsing a character within a string}
1.712 +\begin{lstlisting}
1.713 +jsonChar = char '\\' >> (p_esc <|> p_uni)
1.714 + <|> satisfy (`notElem` "\"\\")
1.715 +\end{lstlisting}
1.716 + Between quotes, \lstinline!jsonChar! matches a string's body:
1.717 + \begin{itemize}
1.718 + \item A backslash must be followed by an escape
1.719 + (``\lstinline!\n!'') or Unicode (``\lstinline!\u2fbe!'' ⾾)
1.720 + \item Any other character except ``\lstinline!\!'' or
1.721 + ``\lstinline!"!'' is okay
1.722 + \end{itemize}
1.723 +
1.724 + More combinator notes:
1.725 + \begin{itemize}
1.726 + \item The \lstinline!>>! combinator is like \lstinline!>>=!, but
1.727 + provides only sequencing, not binding
1.728 + \item The \lstinline!satisfy! combinator uses a pure predicate.
1.729 + \end{itemize}
1.730 +\end{frame}
1.731 +
1.732 +\begin{frame}[fragile]
1.733 + \frametitle{Your turn!}
1.734 +
1.735 + Write a parser for numbers. Here are some pieces you'll need:
1.736 +\begin{lstlisting}
1.737 +import Numeric (readFloat, readSigned)
1.738 +import Text.ParserCombinators.Parsec
1.739 +import Control.Monad (mzero)
1.740 +\end{lstlisting}
1.741 +
1.742 + Other functions you'll need:
1.743 + \begin{itemize}
1.744 + \item \lstinline!getInput!
1.745 + \item \lstinline!setInput!
1.746 + \end{itemize}
1.747 +
1.748 + The type of your parser should look like this:
1.749 +\begin{lstlisting}
1.750 +parseNumber :: CharParser () Rational
1.751 +\end{lstlisting}
1.752 +\end{frame}
1.753 +
1.754 +\begin{frame}
1.755 + \frametitle{Experimenting with your parser}
1.756 +
1.757 + Simply load your code into \texttt{ghci}, and start playing:
1.758 +\begin{verbatim}
1.759 +Prelude> :load MyParser
1.760 +*Main> parseTest parseNumber "3.14159"
1.761 +\end{verbatim}
1.762 +\end{frame}
1.763 +
1.764 +\begin{frame}[fragile]
1.765 + \frametitle{My number parser}
1.766 +
1.767 +\begin{lstlisting}
1.768 +parseNumber = do
1.769 + s <- getInput
1.770 + case readSigned readFloat s of
1.771 + [(n, s')] -> setInput s' >> return n
1.772 + _ -> mzero
1.773 + <?> "number"
1.774 +\end{lstlisting}
1.775 +\end{frame}
1.776 +
1.777 +%%% Local Variables:
1.778 +%%% mode: latex
1.779 +%%% TeX-master: "slides"
1.780 +%%% TeX-PDF-mode: t
1.781 +%%% End: