6 ms·

Parser Combinators in Haskell

115 points by aroccoli 5y ago

cosmic_quanta 5y ago
I love parser combinators. It's a much more natural 'format' than parsing with regular expressions which I have to do at $DAY_JOB. One aspect that I see discussed less often is the idea of 'builder combinators', which are kind of the inverse of parser combinators. There are multiple libraries in Haskell which make it very easy to write HTML/SVG/... this way: https://hackage.haskell.org/package/blaze-html https://hackage.haskell.org/package/blaze-html https://hackage.haskell.org/package/blaze-svg https://hackage.haskell.org/package/blaze-svg I haven't needed to do the same with SQL but I imagine that this already exists as well
- jy14898 5y ago
  Along the same line, there's also invertible syntax descriptions https://gist.github.com/tfausak/a8d7f135bf76e64ea6f35d3be692cbeb https://gist.github.com/tfausak/a8d7f135bf76e64ea6f35d3be692... , which allow one definition to create both a parser and pretty-printer
- jayshua 5y ago
  I like using Elm's JSON library as an example because it's very small. Since there are only a handful of functions you can understand the entire thing pretty easily. Plus, encoding JSON is a great jump-off into the decoding half of the library which is basically a simple parser combinator system. https://package.elm-lang.org/packages/elm/json/latest/ https://package.elm-lang.org/packages/elm/json/latest/
- CornCobs 5y ago
  What are the benefits of these monadic builder interfaces instead of simply pure functions? One can imagine a simple Html type with html tag functions e.g. `div :: [Attributes] -> [Html] -> Html` Instead of using do notation to build up multiple children one would simply supply a list of children. Added benefit of using simpler map/filter/filterMap/mapMaybe vs their monadic counterparts
  - louthy 5y ago
    You can pass contextual state/environment in the monad for trivial data binding
  - jaspervdj 5y ago
    The builder interface has important performance benefits over working with lists: similar to e.g. concatenating many small Strings vs using StringBuilder in Java. The builder interface indeed does not need to be monadic, you can simply append things using <> and get the same benefits. The monadic interface is purely a syntactic enhancement on top of that, to reduce the number of operators you need.
- marginalia_nu 5y ago
  I'm normally a recursive descent-man, but I implemented parsec-style parsing in Java once, just because I was curious to see what the world looked like when it was on fire. I don't have the code as this was just me wasting company time during a hackathon they insisted we all attended. I did get it working, despite the type system I was working in. But yeah. Mistakes were made.
ddek 5y ago
Parser combinators in F# were where I really grasped the utility of a Monad. F# doesn’t have HKT’s, and computational expressions are a little different from Haskell ‘do’. It was the ‘(>>=) = Parser<‘a> -> (‘a -> Parser<‘b>) -> Parser<‘b>’ that flicked the lightswitch in my head.
- contravariant 5y ago
  In .NET I still find it weird that people sometimes implement the visitor pattern without the output type. You'd have to truly think imperatively to consider: void Structure(IVisitor visitor); a good function signature, instead of: A Structure(IParser<A> parser); I mean fair enough that you can't be bothered to implement the functor and monad methods, but it's downright silly to define a function that is incapable of returning output.
  - frabert 5y ago
    In .NET specifically a reason I can think about doing that is that you'd need to implement your visitor twice, as the type argument cannot be void (if I recall correctly).
    - Joker_vD 5y ago
      It can't be void, but writing public sealed class Unit { private static Unit m_value = new Unit(); public static Unit Value => m_value; public Unit() { } public override string ToString() => "()"; public override bool Equals(object obj) => obj is Unit; public override int GetHashCode(object obj) => 0; } and then using it ("return Unit.Value") in place of void is really not that big a problem.
    - contravariant 5y ago
      True, but I just never quite managed to understand why you'd want your visitor to return nothing. And if you did why it was too much hassle to just return '0' or something.
lou1306 5y ago
Since it is not mentioned in the article: Python users may also want to check out pyparsing [0]. It is slightly different from Parsec/FParsec (for instance, it ignores all whitespace by default), but I think it is a really good project. [0]: https://github.com/pyparsing/pyparsing/ https://github.com/pyparsing/pyparsing/
mirekrusin 5y ago
Parser combinators are great ie. in TypeScript [0]. Combinators in general are concise and practical ie. runtime type assertions [1] or generators [2] etc. We use them in several places in production. [0] https://github.com/preludejs/parser https://github.com/preludejs/parser [1] https://github.com/appliedblockchain/assert-combinators https://github.com/appliedblockchain/assert-combinators [2] https://github.com/preludejs/generator/tree/master/src https://github.com/preludejs/generator/tree/master/src
ashton314 5y ago
Rust has a parser combinator library called Nom [^1] that is really a joy to use. I know a little Rust—enough to know what a lifetime is but not so much that I don’t have to keep referring to the documentation when building something. It took me just a few hours with the docs and examples to get a decent parser together. So nice to work with combinators! [^1]: https://github.com/Geal/nom https://github.com/Geal/nom
spekcular 5y ago
Why are parser combinators not given any attention in traditional academic treatments of parsing? Is there some drawback compared to other popular methods? (And why are they relatively more popular on HN and in functional programming communities?) For instance, in the book of Grune and Jacobs on parsing techniques, they are presented as essentially a curiosity (with 2.5 pages of description in a 600+ page book).
- Joker_vD 5y ago
  They have an exponential complexity in general case, I guess that's the reason. There is a way to make them be of polynomial complexity in the worst case, but it requires quite an ingenious memoization technique, coupled with lazy evaluation.
  - ahelwer 5y ago
    Do you have any reading about this or terms I could search to learn more?
    - spekcular 5y ago
      This paper gives the best algorithm I know of, and a sketch of its complexity: http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%20Daniel%20(2010)%20-%20Generalized%20Parser%20Combinators.pdf http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%2....
      - deleted 5y ago
        [deleted]
- Athas 5y ago
  From an academic point of view, most parser combinator libraries are basically LL parsers with backtracking. This is eminently practical (especially if the backtracking part is done well), but from an academic point of view that means they're not very interesting - really just a nicer way of implementing recursive descent parsers. There is of course plenty of academic work specifically on how to implement parser combinator libraries efficiently, how to make them invertible (so they can also produce prettyprinters), provide good error messages, etc.
Zababa 5y ago
An example of a concrete usage of parser combinators and their performance: OCaml's http/af library [1] is a web server that uses parser combinators to implement HTTP 1.1. As for the performance, it's in the ballpark of Go's net/http and Rust's hyper [2]. There's also h2 [3] that implements HTTP 2. They are based on Angstrom [4], which started as a direct port of attoparsec [5], cited in the article. It's great to see all the cross-pollination happening in that space! [1]: https://github.com/inhabitedtype/httpaf https://github.com/inhabitedtype/httpaf [2]: https://github.com/ocaml-multicore/retro-httpaf-bench/pull/17 https://github.com/ocaml-multicore/retro-httpaf-bench/pull/1... [3]: https://github.com/anmonteiro/ocaml-h2 https://github.com/anmonteiro/ocaml-h2 [4]: https://github.com/inhabitedtype/angstrom https://github.com/inhabitedtype/angstrom [5]: https://github.com/haskell/attoparsec https://github.com/haskell/attoparsec
danidiaz 5y ago
This "Design Patterns for Parser Combinators" https://www.youtube.com/watch?v=RwzX1XltOGY https://www.youtube.com/watch?v=RwzX1XltOGY video (an the associated pdf https://dl.acm.org/doi/abs/10.1145/3471874.3472984 https://dl.acm.org/doi/abs/10.1145/3471874.3472984) explains some techniques that are good to know—how to deal with left recursion, for example. It's also notable for being a continuous integration-driven talk!
ra-mos 5y ago
Novice question, when would you use something like this over something like lex/yacc? https://tldp.org/HOWTO/Lex-YACC-HOWTO-4.html https://tldp.org/HOWTO/Lex-YACC-HOWTO-4.html
pizza 5y ago
Is there such a thing as a stochastic parser combinator? E.g. to do Viterbi/HMM decoding, etc. Off-topic: I'd really like to get more and more Haskell features in Python. Playing with the adt library for algebraic data types, and I'd also like to find something to reproduce monads/applicatives/functors/arrows etc
- contravariant 5y ago
  Well here I think the Haskell abstractions chosen here are a bit unfortunate. I mean it's nice to use Applicative and Alternative but when you've got that p <*> (q <|> r) = (p <*> q) <|> (p <*> r) or at least that these are equivalent, then you might want to step back and wonder how on earth distributivity got into it. And after thinking for a few seconds and realizing that the parser which parses the empty string and the parsers which parses nothing correspond to the neutral elements for <*> and <|> respectively you might start to suspect some things. Anyway personally I reckon the proper space for dealing with these questions is by treating the space of parsers as a semiring. Although for parser combinators you break the commutativity of addition, but I can't find a better name than semiring right now. Basically you can show that if you've got something that sends the space of strings to a semiring then you can turn it into a linear map on the semimodule formed by simply multiplying strings and values of the semiring in the obvious way. You then get a semiring of parsers by using composition and addition of linear maps. Parser generators as described in this article are essentially based on the semiring formed by functions with composition as multiplication and f + g = f as addition (note, not commutative). This is wrapped in an 'Either' which also seems to have some semiring structure that I can't be bothered to analyse right now, though I noticed that <*> and <|> translated pretty neatly. Anyway all you have to do to get your Viterbi/HMM equivalent is to use the semiring formed by real numbers with 'max' as multiplication and ordinary multiplication as the addition operator. See also 'Kleene algebra' for more information in this direction.
  - pizza 5y ago
    Awesome, thanks for this info

115 points by aroccoli 5y ago

I love parser combinators. It's a much more natural 'format' than parsing with regular expressions which I have to do at $DAY_JOB. One aspect that I see discussed less often is the idea of 'builder combinators', which are kind of the inverse of parser combinators. There are multiple libraries in Haskell which make it very easy to write HTML/SVG/... this way: https://hackage.haskell.org/package/blaze-html https://hackage.haskell.org/package/blaze-html https://hackage.haskell.org/package/blaze-svg https://hackage.haskell.org/package/blaze-svg I haven't needed to do the same with SQL but I imagine that this already exists as well

jy14898 5y ago
Along the same line, there's also invertible syntax descriptions https://gist.github.com/tfausak/a8d7f135bf76e64ea6f35d3be692cbeb https://gist.github.com/tfausak/a8d7f135bf76e64ea6f35d3be692... , which allow one definition to create both a parser and pretty-printer
jayshua 5y ago
I like using Elm's JSON library as an example because it's very small. Since there are only a handful of functions you can understand the entire thing pretty easily. Plus, encoding JSON is a great jump-off into the decoding half of the library which is basically a simple parser combinator system. https://package.elm-lang.org/packages/elm/json/latest/ https://package.elm-lang.org/packages/elm/json/latest/
CornCobs 5y ago
What are the benefits of these monadic builder interfaces instead of simply pure functions? One can imagine a simple Html type with html tag functions e.g. `div :: [Attributes] -> [Html] -> Html` Instead of using do notation to build up multiple children one would simply supply a list of children. Added benefit of using simpler map/filter/filterMap/mapMaybe vs their monadic counterparts
- louthy 5y ago
  You can pass contextual state/environment in the monad for trivial data binding
- jaspervdj 5y ago
  The builder interface has important performance benefits over working with lists: similar to e.g. concatenating many small Strings vs using StringBuilder in Java. The builder interface indeed does not need to be monadic, you can simply append things using <> and get the same benefits. The monadic interface is purely a syntactic enhancement on top of that, to reduce the number of operators you need.
marginalia_nu 5y ago
I'm normally a recursive descent-man, but I implemented parsec-style parsing in Java once, just because I was curious to see what the world looked like when it was on fire. I don't have the code as this was just me wasting company time during a hackathon they insisted we all attended. I did get it working, despite the type system I was working in. But yeah. Mistakes were made.

ddek 5y ago

Parser combinators in F# were where I really grasped the utility of a Monad. F# doesn’t have HKT’s, and computational expressions are a little different from Haskell ‘do’. It was the ‘(>>=) = Parser<‘a> -> (‘a -> Parser<‘b>) -> Parser<‘b>’ that flicked the lightswitch in my head.

contravariant 5y ago
In .NET I still find it weird that people sometimes implement the visitor pattern without the output type. You'd have to truly think imperatively to consider: void Structure(IVisitor visitor); a good function signature, instead of: A Structure(IParser<A> parser); I mean fair enough that you can't be bothered to implement the functor and monad methods, but it's downright silly to define a function that is incapable of returning output.
- frabert 5y ago
  In .NET specifically a reason I can think about doing that is that you'd need to implement your visitor twice, as the type argument cannot be void (if I recall correctly).
  - Joker_vD 5y ago
    It can't be void, but writing public sealed class Unit { private static Unit m_value = new Unit(); public static Unit Value => m_value; public Unit() { } public override string ToString() => "()"; public override bool Equals(object obj) => obj is Unit; public override int GetHashCode(object obj) => 0; } and then using it ("return Unit.Value") in place of void is really not that big a problem.
  - contravariant 5y ago
    True, but I just never quite managed to understand why you'd want your visitor to return nothing. And if you did why it was too much hassle to just return '0' or something.

lou1306 5y ago

Since it is not mentioned in the article: Python users may also want to check out pyparsing [0]. It is slightly different from Parsec/FParsec (for instance, it ignores all whitespace by default), but I think it is a really good project. [0]: https://github.com/pyparsing/pyparsing/ https://github.com/pyparsing/pyparsing/

mirekrusin 5y ago

Parser combinators are great ie. in TypeScript [0]. Combinators in general are concise and practical ie. runtime type assertions [1] or generators [2] etc. We use them in several places in production. [0] https://github.com/preludejs/parser https://github.com/preludejs/parser [1] https://github.com/appliedblockchain/assert-combinators https://github.com/appliedblockchain/assert-combinators [2] https://github.com/preludejs/generator/tree/master/src https://github.com/preludejs/generator/tree/master/src

ashton314 5y ago

Rust has a parser combinator library called Nom [^1] that is really a joy to use. I know a little Rust—enough to know what a lifetime is but not so much that I don’t have to keep referring to the documentation when building something. It took me just a few hours with the docs and examples to get a decent parser together. So nice to work with combinators! [^1]: https://github.com/Geal/nom https://github.com/Geal/nom

spekcular 5y ago

Why are parser combinators not given any attention in traditional academic treatments of parsing? Is there some drawback compared to other popular methods? (And why are they relatively more popular on HN and in functional programming communities?) For instance, in the book of Grune and Jacobs on parsing techniques, they are presented as essentially a curiosity (with 2.5 pages of description in a 600+ page book).

Joker_vD 5y ago
They have an exponential complexity in general case, I guess that's the reason. There is a way to make them be of polynomial complexity in the worst case, but it requires quite an ingenious memoization technique, coupled with lazy evaluation.
- ahelwer 5y ago
  Do you have any reading about this or terms I could search to learn more?
  - spekcular 5y ago
    This paper gives the best algorithm I know of, and a sketch of its complexity: http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%20Daniel%20(2010)%20-%20Generalized%20Parser%20Combinators.pdf http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%2....
    - deleted 5y ago
      [deleted]
Athas 5y ago
From an academic point of view, most parser combinator libraries are basically LL parsers with backtracking. This is eminently practical (especially if the backtracking part is done well), but from an academic point of view that means they're not very interesting - really just a nicer way of implementing recursive descent parsers. There is of course plenty of academic work specifically on how to implement parser combinator libraries efficiently, how to make them invertible (so they can also produce prettyprinters), provide good error messages, etc.

Zababa 5y ago

An example of a concrete usage of parser combinators and their performance: OCaml's http/af library [1] is a web server that uses parser combinators to implement HTTP 1.1. As for the performance, it's in the ballpark of Go's net/http and Rust's hyper [2]. There's also h2 [3] that implements HTTP 2. They are based on Angstrom [4], which started as a direct port of attoparsec [5], cited in the article. It's great to see all the cross-pollination happening in that space! [1]: https://github.com/inhabitedtype/httpaf https://github.com/inhabitedtype/httpaf [2]: https://github.com/ocaml-multicore/retro-httpaf-bench/pull/17 https://github.com/ocaml-multicore/retro-httpaf-bench/pull/1... [3]: https://github.com/anmonteiro/ocaml-h2 https://github.com/anmonteiro/ocaml-h2 [4]: https://github.com/inhabitedtype/angstrom https://github.com/inhabitedtype/angstrom [5]: https://github.com/haskell/attoparsec https://github.com/haskell/attoparsec

danidiaz 5y ago

This "Design Patterns for Parser Combinators" https://www.youtube.com/watch?v=RwzX1XltOGY https://www.youtube.com/watch?v=RwzX1XltOGY video (an the associated pdf https://dl.acm.org/doi/abs/10.1145/3471874.3472984 https://dl.acm.org/doi/abs/10.1145/3471874.3472984) explains some techniques that are good to know—how to deal with left recursion, for example. It's also notable for being a continuous integration-driven talk!

ra-mos 5y ago

Novice question, when would you use something like this over something like lex/yacc? https://tldp.org/HOWTO/Lex-YACC-HOWTO-4.html https://tldp.org/HOWTO/Lex-YACC-HOWTO-4.html

pizza 5y ago

Is there such a thing as a stochastic parser combinator? E.g. to do Viterbi/HMM decoding, etc. Off-topic: I'd really like to get more and more Haskell features in Python. Playing with the adt library for algebraic data types, and I'd also like to find something to reproduce monads/applicatives/functors/arrows etc

contravariant 5y ago
Well here I think the Haskell abstractions chosen here are a bit unfortunate. I mean it's nice to use Applicative and Alternative but when you've got that p <*> (q <|> r) = (p <*> q) <|> (p <*> r) or at least that these are equivalent, then you might want to step back and wonder how on earth distributivity got into it. And after thinking for a few seconds and realizing that the parser which parses the empty string and the parsers which parses nothing correspond to the neutral elements for <*> and <|> respectively you might start to suspect some things. Anyway personally I reckon the proper space for dealing with these questions is by treating the space of parsers as a semiring. Although for parser combinators you break the commutativity of addition, but I can't find a better name than semiring right now. Basically you can show that if you've got something that sends the space of strings to a semiring then you can turn it into a linear map on the semimodule formed by simply multiplying strings and values of the semiring in the obvious way. You then get a semiring of parsers by using composition and addition of linear maps. Parser generators as described in this article are essentially based on the semiring formed by functions with composition as multiplication and f + g = f as addition (note, not commutative). This is wrapped in an 'Either' which also seems to have some semiring structure that I can't be bothered to analyse right now, though I noticed that <*> and <|> translated pretty neatly. Anyway all you have to do to get your Viterbi/HMM equivalent is to use the semiring formed by real numbers with 'max' as multiplication and ordinary multiplication as the addition operator. See also 'Kleene algebra' for more information in this direction.
- pizza 5y ago
  Awesome, thanks for this info