Understanding Parser Combinators (2015)
fsharpforfunandprofit.com
fsharpforfunandprofit.com
but if you look at it, the real cost is in closure creation and control transfers (function indirection). functional compilers are already trying really hard to make those costs disappear.
there is some really interesting work lately in manual vectorization of traditionally control flow laden tasks like parsing. i would fully expect some clever people in an appropriate linguistic framework to make frameworks for automating that transformation.
but for me personally I find the parser combinator approach:
o a pretty direct translation of a model you might see in BNF
o considerably easier to maintain/extend/reuse than either external parser generator or recursive descent
o more straightforward in the construction of output values than the traditional approach of a parser generator language
o amenable to a flexible decomposition of layers rather than the traditional scanner/parser split (alot of simple languages dont really need that distinction)
o self contained - removes a big external dependency
o simplifies the build
its a really good default in the absence of other constraints
The implementation of this I'm most familiar with is OCaml's angstrom library.
foobar | foobaz
fooba(r|z)
There are a couple ways around this:
- rewrite into non-turing-complete parsers when possible using heuristics. Ghc supports this, the original motivation was implicit parallelism for facebooks anti-abuse infrastructure
- use a non-monadic dsl. This either makes coding more awkward or forces you to reimplement a bunch of things like if statements
- if you really need performance and error messages use a parser generator instead of an embedded dsl
Ghc inlines functions incredibly aggressively so the higher order combinators don't have a huge cost. Doing this in a jit compiled language will be more expensive. There are also tradeoffs in the primitives you use - you could only have a primitive to check a single char and then use it in a loop to check strings. But even when inlined you won't beat a fine tuned string comparison function this way.
There’s also an elegant technique described in the paper “Parser Derivative Combinators: A functional Pearl” which seems like it should improve performance but never seemed to gain widespread usage. There was an HN discussion of the paper last year:
Using functions is an implementation detail. If you had something like MetaOCaml, or some other quasi-quotations, you can generate optimized code at runtime.
Are you going to argue that this isn't a combinator library: https://yanniss.github.io/streams-popl17.pdf
No, this is trying to stretch the idea to fit compilation stages into it at which point it's no longer as simple and as useful.
But none of this is still flexible enough and simple enough, not as much as a hand written recursive descent parser. Say you are just starting out, such hand written parser is the easiest way to get into parsing. It gets old rather quickly though, a bigger parser becomes harder to change and to reason about. But until you figure out exactly what to parse and what level of performance you need, it's still better to keep all that flexibility and simplicity. And this is where this simple idea of composable higher order recursive descent parsers starts to shine. It keeps all the flexibility and improves on parsing simplicity by sacrificing just a little bit of simplicity locally in rather simple parsing function primitives, where it's not even noticeably harder to reason about.
The rest of your post seems unrelated to anything I've mentioned. Clearly you and I are talking about completely different things. I again suggest you read the link I provided, but it doesn't seem fruitful to continue this thread any further.
Read under shortcomings for some insight here. I'm personally more interested in the ambiguities than performance. But obviously both are critical.
That said, the main benefit of parser combinators for me are that they're super easy and fast to write, and easy to modify. So I tend to use a PC library for prototyping, then if I need more performance I'll rewrite it by hand.
GHC inlines aggressively (when you use -O) so there shouldn't be much function call overhead. As others have commented, the bigger issue is that monadic parsers are generally unable to perform static analysis of the full parse tree and thus identify the aspects which parallel branches have in common, which implies more backtracking and redundant parsing. Some of this can be improved heuristically with rewrite rules, or by explicitly using applicative combinators (which can be statically analyzed) instead of monadic ones.
If you like parsers and Racket this may interest you. I've been wanting to write up a post kinda like this myself, but haven't found the time.
1. https://medium.com/@armin.heller/using-parser-combinators-in... 2. https://medium.com/@armin.heller/parser-combinator-gotchas-2...
They highlight the typical pitfalls of implementing your own parser combinators and I found them very helpful for my understanding of parser combinators.
I am just not sure about f#, but that's probably because I am so used to haskell.