symbol-parser
Type-level string (Symbol) parser combinators.
Features
- Define parsers compositionally, largely as you would on the term level.
- Pretty parse errors.
- Hopefully decent performance.
- No runtime cost (you shall find no term-level code here).
Examples
ghci> import Data.Type.Symbol.Parser
ghci> :k! Run (Drop 3 :*>: Isolate 2 NatDec :<*>: (Drop 3 :*>: NatHex)) "___10___FF"
...
= Right '( '(10, 255), "")
Why?
Via GHC.Generics, we may inspect Haskell data types on the type level.
Constructor names are Symbols. Ever reify these, then perform some sort of
checking or parsing on the term level? symbol-parser does the parsing on the
term level instead. Catch bugs earlier, get faster runtime.
Design
Parser basics
(Note that I may omit "type-level" when referring to type-level operations.)
Until GHC 9.2, Symbols were largely opaque. You could get them, but you
couldn't decompose them like you could Strings with uncons :: [a] -> Maybe (a, [a]). Some Haskellers took this as a challenge (see
symbols). But realistically, we needed a bit more compiler
support.
As of GHC 9.2, Symbols may be decomposed via UnconsSymbol :: Symbol -> Maybe (Char, Symbol). We thus design a Char-based parser:
type ParserCh s r = Char -> s -> Result s r
data Result s r = Cont s | Done r | Err E
A parser is a function which takes a Char, the current state s, and returns
some result:
Cont s: keep going, here's the next state s
Done r: parse successful with value r
Err E: parse error, details in the E (a structured error)
Run handles calling the parser Char by Char, threading the state through,
and does some bookkeeping for nice errors.
This is a good first step, but we have some outstanding issues:
- What do we do when we reach the end of the string?
- How do we initialize parser state?
- How do we pass parsers around? (As of 2024-04-20, GHC HEAD does not support
unsaturated type families.)
As always, types are our salvation.
type ParserEnd s r = s -> Either E r
type Parser s r = (ParserChSym s r, ParserEndSym s r, s)
type ParserChSym s r = Char ~> s ~> Result s r
type ParserEndSym s r = s ~> Either E r
We define a parser as a tuple of a character parser, an end handler, and an
initial state. The types ending in Sym are defunctionalization symbols,
which enable us to pass our parsers around as type-level functions. The plumbing
is provided Oleg's fantastic library defun-core.
Example: NatDec
Let's write a parser that parses a natural decimal.
type NatDec = '(NatDecChSym, NatDecEndSym, 0)
type NatDecCh ch acc = NatDecCh' acc (ParseDecimalDigitSym @@ ch)
type family NatDecCh' acc mDigit where
NatDecCh' acc (Just digit) = Cont (acc * 10 + digit)
NatDecCh' acc Nothing = Err -- ...
type NatDecEnd acc = Right acc
-- boring defunctionalization symbol definitions
At each Char, we attempt to parse as a digit. If it's valid, we multiply the
current accumulator by 10 (a left shift) and add the digit value. At the end of
the string, we simply emit the current accumulator.
It can be that easy to define a parser with symbol-parser! But it isn't always.
Combinators get weird thanks to state handling. Take a look at Isolate, then
Then.
Pitfall: Character parsers always consume
There is no backtracking or lookahead, that you do not implement yourself. This
keeps the parser execution extremely simple, but breaks null parsers such as
Drop 0, so these must be handled specially (unless you don't getting mind
stuck type families on misuse).
For concrete examples, see the implementation of Drop and Literal.
Pitfall: Not all parsers are definable
- No changing parser state. Thus, parsers such as
Try :: Parser s r -> Parser (s, [Char]) r are not definable. Parsers may not backtrack.
- Combinators such as
<|> can emulate backtracking, but they are complex and
hard to reason about (they may have bugs!).
Contributing
I would gladly accept further combinators or other suggestions. Please add an
issue or pull request, or contact me via email or whatever (I'm raehik
everywhere).
License
Provided under the MIT license. See LICENSE for license text.
