Background for chapter 02.

Parser combinators

Commit a9178695 ("Make a real compiler.", 2023-05-29) adds a new module, ParserComb.hs, 165 lines, and its name is not a metaphor: it is a small, self-contained parser-combinator library — a Prsr-style toolkit in the lineage of Wadler/Hutton parsing, built from ordinary Haskell type classes (Functor, Applicative, Monad, Alternative) rather than a parser generator or an external grammar file. Parse.hs, a second new module (204 lines), uses it to parse the surface syntax chapter 02 introduces. This doc walks the library itself; chapter 02 walks what it's used for.

1. The parser type

a9178695:ParserComb.hs, lines 22–44 (LastFail, Res, Prsr together, quoted whole):

data LastFail
  = LastFail Int [(String, [String])]
  deriving (Show)

noFail :: LastFail
noFail = LastFail maxBound []

longest :: LastFail -> LastFail -> LastFail
longest lf1@(LastFail l1 x1) lf2@(LastFail l2 x2) =
  case compare l1 l2 of
    LT -> lf1
    GT -> lf2
    EQ -> LastFail l1 (x1 ++ x2)

longests :: [LastFail] -> LastFail
longests [] = undefined
longests xs = foldl1 longest xs

data Res s a = Many [(a, (String, s))] LastFail
  deriving (Show)

newtype Prsr s a = P { runP :: (String, s) -> Res s a}
instance Show (Prsr s a) where show _ = "<<Prsr>>"

Strip away the error bookkeeping and the shape is the textbook one: a parser is a function from the remaining input to a result. Two things about this particular function are worth noticing before anything else:

It's not String -> Maybe (a, String). Res s a is Many [(a, (String, s))] LastFail — a list of (result, leftover) pairs, not one. This parser doesn't commit to the first successful parse; it can return several, and parseDie (a9178695:Parse.hs, lines 82–87) is the place that decides what to do if there's more than one: exactly one result is accepted, zero results becomes a formatted "found X, expected Y" message (formatFailed, a9178695:ParserComb.hs lines 101–113 — a live transcript of its output is in chapter 02's "Try it" exercise 2), and more than one becomes error $ "Ambiguous:\n" ++ ....
Prsr s a carries a second type parameter, s, threaded alongside the string. This is a stateful parser — s is arbitrary parser state, not fixed by the library. Parse.hs instantiates it as type P a = Prsr [Int] a, an indentation-column stack, and gets a full Haskell-style layout rule (section 4 below) without ParserComb.hs knowing anything about layout at all.
LastFail Int [(String, [String])] records, independent of whichever parse eventually succeeds, the furthest point the parser ever reached before failing, plus what it was expecting there (Int is a length — the parser measures "how far into the input" by how much string is left, so smaller remaining length means further progress; longest is misleadingly named — it's picking the shortest leftover, i.e. the parse that consumed the most). That's the raw material for a "found X, expected Y" error message, threaded through every combinator whether it succeeds or not.

2. Sequencing and choice: the type-class plumbing

Everything downstream — do-notation, <*>, <|> — comes from four instances, quoted whole (a9178695:ParserComb.hs, lines 46–75):

instance Functor (Prsr s) where
  fmap f p = P $ \ t ->
    case runP p t of
      Many aus lf -> Many [ (f a, u) | (a, u) <- aus ] lf

instance Applicative (Prsr s) where
  (<*>) = ap
  pure a = P $ \ t -> Many [(a, t)] noFail

instance Monad (Prsr s) where
  return = pure
  p >>= k = P $ \ t ->
    case runP p t of
      Many aus plf ->
        let xss = [ runP (k a) u | (a, u) <- aus ]
        in  let (rss, lfs) = unzip [ (rs, lf) | Many rs lf <- xss ]
            in  Many (concat rss) (longests $ plf : lfs)

instance MonadFail (Prsr s) where
  fail m = P $ \ (r, _) -> Many [] (LastFail (length r) [("fail", [m])])

instance MonadState s (Prsr s) where
  get = P $ \ t@(_, s) -> Many [(s, t)] noFail
  put s = P $ \ (f, _) -> Many [((), (f, s))] noFail

instance Alternative (Prsr s) where
  empty = P $ \ (r, _) -> Many [] (LastFail (length r) [("empty", ["<empty>"])])
  p <|> q = P $ \ t ->
    case (runP p t, runP q t) of
      (Many a lfa, Many b lfb) -> Many (a ++ b) (longest lfa lfb)

pure a succeeds without consuming input, returning a — the base case for sequencing. p >>= k is "parse with p, then for every result p produced, run k on it and parse with the resulting parser" — for a single-result parser this would just be function composition, but because Many can hold several (a, leftover) pairs, >>= runs k once per result and concatenates. Alternative's p <|> q runs both p and q on the same input and returns both sets of successes concatenated (a ++ b) — this is not "try p, fall back to q on failure" in the usual sense; both branches always run, both branches' results are kept (genuine ambiguity, not just backtracking), and only the two LastFail records get merged via longest.

That last point matters enough that the library ships a second, differently -behaved choice operator right next to it (a9178695:ParserComb.hs, lines 77–84):

-- Left biased choice
(<|<) :: Prsr s a -> Prsr s a -> Prsr s a
p <|< q = P $ \ t ->
  case runP p t of
    Many [] lfa ->
      case runP q t of
        Many b lfb -> Many b (longest lfa lfb)
    r -> r

<|< only tries q if p produced no results at all — ordinary committed choice, the behavior most parser-combinator tutorials call <|>. Parse.hs reaches for <|< exactly where determinism matters (a { for a real curly brace versus the indentation-triggered virtual one, section 4) and plain <|> everywhere the grammar is allowed to stay ambiguous and let parseDie sort it out later.

3. The primitives that touch characters

Above the type-class layer, ParserComb.hs defines the handful of functions that actually look at the input. satisfy, char, and eof (a9178695:ParserComb.hs, lines 119–141, string elided — same shape):

satisfy :: String -> (Char -> Bool) -> Prsr s Char
satisfy msg f = P $ \ t ->
  case t of
    (c:cs, s) | f c -> Many [(c, (cs, s))] noFail
    (cs, _) -> Many [] (LastFail (length cs) [("satisfy", [msg])])

char :: Char -> Prsr s Char
char c = P $ \ t ->
  case t of
    (c':cs, s) | c == c' -> Many [(c, (cs, s))] noFail
    (cs, _) -> Many [] (LastFail (length cs) [("char", [show c])])

...

eof :: Prsr s ()
eof = P $ \ t ->
  case t of
    ("", _) -> Many [((), t)] noFail
    (cs, _) -> Many [] (LastFail (length cs) [("eof", ["end-of-file"])])

Every one of them is the same four lines: look at the first character (or the whole string, for eof), succeed-and-consume or fail-and-record-why. satisfy takes an explicit msg string for its own failure record — the "lower case", "upper case", "digit", "symbol" strings visible in Parse.hs's error output (chapter 02's "Try it", exercise 2) all originate as this msg argument.

Above that, three more pieces of plumbing (a9178695:ParserComb.hs, lines 86–90 and 143–147, two separate spots in the file, quoted whole each):

emany :: Prsr s a -> Prsr s [a]
emany p = esome p <|< pure []

esome :: Prsr s a -> Prsr s [a]
esome p = (:) <$> p <*> emany p

...

(<?>) :: Prsr s a -> String -> Prsr s a
p <?> e = P $ \ t ->
--  trace ("<?> " ++ show e) $
  case runP p t of
    Many rs (LastFail l xs) -> Many rs (LastFail l [(m, e:es) | (m, es) <- xs ])

emany/esome are "zero-or-more" and "one-or-more" — the standard Kleene star and plus, mutually recursive in the usual way (esome p parses one p then emany p for the rest; emany p is esome p, or nothing). The library's export list also re-exports plain many and some unchanged from Control.Applicative (the --hiding (many, some) comment on the import Control.Applicative line is commented out — the import isn't actually restricted) — so Parse.hs has both the Alternative-derived many/some and this module's own eager emany/ esome in scope side by side, and in this range consistently reaches for the e-prefixed ones. <?> is the labeling combinator: run p, and if it produced any failure record, prepend e to every expectation string in it — this is how pKeyword, pSymbol, and friends attach a human-readable name ("module", "=", "int") to a failure that would otherwise just say "symbol" or "lower case".

4. One production, read aloud

Parse.hs builds a whole grammar this way — pModule, pDef, pExpr, pCase, and so on — each one a single <$>/<*>/<|> expression built from smaller parsers. Here is the top one, quoted whole (a9178695:Parse.hs, lines 94–95):

pModule :: P Module
pModule = Module <$> (pKeyword "module" *> pUIdent <* pKeyword' "where") <*> pBlock pDef

Read aloud: to parse a module, first parse the keyword module (*> discards its result — a keyword carries no data), then an uppercase identifier (pUIdent — this becomes the module name), then the keyword where (<* again discards it), then a block of definitions (pBlock pDef — a layout-delimited, semicolon-separated list of pDef, described below). Package the identifier and the definition list into a Module value with Module <$> ... <*> .... Nothing here is bespoke parsing code; it's four already-defined parsers (pKeyword, pUIdent, pKeyword', pBlock) glued with three already-defined combinators (<$>, *>/<*, <*>).

pBlock and its neighbors are worth a second look, because they show the s type parameter from section 1 earning its keep — a Haskell-style layout rule (real {/;/} or indentation-inferred ones) implemented entirely as user-level parsers over Prsr [Int] a, no changes to ParserComb.hs required (a9178695:Parse.hs, lines 176–204, quoted whole):

pLCurl :: P ()
pLCurl = pSym '{' <|< softLC
  where softLC = do
          msp <- pIndent
          case msp of
            Nothing -> fail "\\n"
            Just sp -> do
--              traceM ("push " ++ show (length sp))
              modify $ \ st -> length sp : st

pRCurl :: P ()
pRCurl = pSym '}' <|> softRC
  where softRC = do
          is <- get
          if null is then
            fail "}"
           else do
            put (tail is)
            eof

pSemi :: P ()
pSemi = pSym ';'

pBlock :: P a -> P [a]
pBlock p = do
  pLCurl
  as <- esepBy p pSemi
  pRCurl
  pure as

pLCurl opens a block: either a literal {, or — via <|<, committed choice, since a real { should never also try the indentation path — softLC, which reads the indentation of the next line (pIndent, not shown here) and pushes its column onto the state stack with modify. pRCurl closes one: a literal }, or softRC, which pops the stack — and, notably, only succeeds if that pop is followed immediately by eof, which is how the whole toy currently gets away with never emitting a virtual close-brace on dedent inside the file (pWhite, elsewhere in Parse.hs, injects } characters back into the input stream directly via inject, for the general case). esepBy (not shown; esepBy1 plus an empty-list fallback, both ordinary user code built from emany and <|>) handles the semicolon-separated middle. None of pLCurl, pRCurl, pSemi, or esepBy are ParserComb.hs exports with special status — they're Parse.hs-local functions built the same way pModule is, out of the same eleven-ish primitives from sections 2–3.

5. Why this style suits incremental growth

That's the actual payoff of writing the parser this way rather than, say, hand-rolling a state machine or reaching for a parser-generator tool: a new piece of syntax is a new combinator expression, built from the same building blocks, dropped in next to the others — not a rewrite of a recursive-descent function pushed to sixteen cases from twelve. It already happens once inside this very range: commit 4030f721 ("Parse more") adds a parenthesized-operator form ((+), to write an operator as an ordinary identifier) in twelve added lines total: a new pOper/ pOper' pair (nine of the twelve) built from esome/satisfy/guard exactly like every other parser in the file, pSymbol adjusted to reuse pOper' instead of repeating its definition, and one new alternative appended to pAExpr with <|>. chapter 03 does this repeatedly at larger scale — let, infix operators, tuples, list syntax, do-notation each land as a handful of new p-something definitions, not a restructuring of ParserComb.hs, which is untouched through all of it. The parser type from section 1 already has everything later syntax needs (sequencing, choice, state, error tracking); growing the language is purely additive at the grammar layer.

Learning from MicroHs

Parser combinators

1. The parser type

2. Sequencing and choice: the type-class plumbing

3. The primitives that touch characters

4. One production, read aloud

5. Why this style suits incremental growth