5 ms·

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 b

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: https://news.ycombinator.com/item?id=17391071 https://news.ycombinator.com/item?id=17391071

naasking 8y ago
> 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.
- zzzcpan 8y ago
  Without functions you have a compiler, not combinator. Functions is what makes it a nice usable thing.
  - naasking 8y ago
    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. Are you going to argue that this isn't a combinator library: https://yanniss.github.io/streams-popl17.pdf https://yanniss.github.io/streams-popl17.pdf
    - zzzcpan 8y ago
      > 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.
      - naasking 8y ago
        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.
        zzzcpan 8y ago
        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.
        naasking 8y ago
        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.

naasking 8y ago

> 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.

zzzcpan 8y ago
Without functions you have a compiler, not combinator. Functions is what makes it a nice usable thing.
- naasking 8y ago
  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. Are you going to argue that this isn't a combinator library: https://yanniss.github.io/streams-popl17.pdf https://yanniss.github.io/streams-popl17.pdf
  - zzzcpan 8y ago
    > 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.
    - naasking 8y ago
      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.
      - zzzcpan 8y ago
        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.
        naasking 8y ago
        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.