I'm curious about the performance of parser combinator approaches to other parsing methods. It seems that generally they are slower, but is this an innate problem, or could clever techniques improve on this? Anyone done work/research in this area?
So the main performance penalty is that you want to parse
foobar | foobaz
As
fooba(r|z)
But this requires you to analyse your parsers. Virtually all parser combinator libraries in haskell are monadic and most others follow suit. This means you can parse turing complete languages and parsers are very pleasant to write but also all predicates are undecidable and therefore you can't optimize well.
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.
Right, I think you only need monadic bind for semantic predicates. Ordinary semantic actions (i.e. ones that don't feed back into deciding how to parse the rest of the input) can fit smoothly into a parser combinator design without monads, but AFAIK that's not how it's usually done.
Parser combinators are generally slower than a hand-written or code-generated parser. That’s somewhat innate due to the overhead of “threading” (for lack of a better word) your control flow through many function calls. There are some techniques for improving the performance though — some at the compiler level (by having your language compiler fuse some function calls together where feasible) and some by providing additional, specialized function overloads for developers to use.
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:
> Parser combinators are generally slower than a hand-written or code-generated parser. That’s somewhat innate due to the overhead of “threading” (for lack of a better word) your control flow through many function calls
Using functions is an implementation detail. If you had something like MetaOCaml, or some other quasi-quotations, you can generate optimized code at runtime.
Except the functions being composed don't have to operate directly on domain values, they can work on quotations, code fragments, data structures, etc. which themselves then operate on the domain values.
> Except the functions being composed don't have to operate directly on domain values, they can work on quotations, code fragments, data structures, etc. which themselves then operate on the domain values.
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.
I disagree. Consumers of the combinator library see no changes, which means they use the same declarative interface and yet can enjoy dramatically faster runtimes. See the link I provided in my last post.
You are focusing on the wrong things. If you want to treat it like a compiler there are better simpler more suited for performance ways to do it, i.e. making a DSL and a parser generator. And it can and often will be more flexible and easier to deal with, than your idea.
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.
DSL compilers with separate parsers, assemblers and tooling are emphatically not simpler than an EDSL.
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.
I use higher-order parser combinators in a few different languages and its not really that noticable on a modern machine assuming you're parsing human-written source and not gigabytes of json.
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
A lot of the closure creation costs can be eliminated by writing the library in a continuation-passing style, which shoves all of the data into proper arguments, bypassing the need for the closure. Of course, the user of the library is still likely to generate closures.
The implementation of this I'm most familiar with is OCaml's angstrom library.
They can be fast (see for example the Rust parser-combinator library Nom [0] which benchmarks competitively with hand-written parsers). However you likely need some level of metaprogramming to make them fast, as the way they're implemented in, say, Haskell has a lot of function call overhead that's hard to optimize. Nom uses macros, and the generated code tends to look a lot like the sort of state machine you'd write by hand.
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.
> ...as the way they're implemented in, say, Haskell has a lot of function call overhead that's hard to optimize.
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.
They can be as fast as hand written recursive descent parsers, which is what they are under the hood anyway.
But of course this way of writing parsers is like compiling without optimization passes. It can be fast for a lot of things, but not as fast if you can do some optimizations, like moving shared prefixes out of strings to match them only once or use lookup tables instead of iterating over a lot of choices, etc. It requires generating an AST with combinators, not parsing functions directly. Which nullifies the whole point of using parser combinators in the first place.
They highlight the typical pitfalls of implementing your own parser combinators and I found them very helpful for my understanding of parser combinators.
I would really recommend anyone who want's to get a taste of "real" function programming to develop some parser with parser combinators (I developed a java-parser). I started to understand a great deal of functional-programming concepts by using them...and they are so awesome! They are, in my optinion, a prime example where functional programming shines. I think they really had an impact on my journy through programming languages.
I am just not sure about f#, but that's probably because I am so used to haskell.
it's a long time since I read it, but I remember the treatment in Burge's 1975 "Recursive Programming Techniques" being clear, along with other techniques, if you can find a library copy. As far as I know, combinator parsing was introduced there, and I find it's normally worth reading the original literature on a topic. Burge is a classic generally as a follow-on to "The Next 700 Programming Languages".
