6 ms·

Translating a C++ parser to Haskell

109 points by yomritoyj 9y ago

Peaker 9y ago
Attoparsec is fast, but used to have bad error messages. How do the 2 parsers compare w.r.t error messaging? Haskell has Parsec/Megaparsec which have better error messages, but are extremely slow.
- kccqzy 9y ago
  I don't think Parsec is "extremely slow." It's not as fast as attoparsec, but not bad either. Trifecta has the best error messages, but takes some more work to fully make the error messages great.
  - Peaker 9y ago
    In my experience using Parsec, it was extremely slow. Took around 20 seconds to parse a few hundred thousand lines (almost no backtracking, too). Attoparsec/parsec have very similar APIs. I wonder why it cannot parse optimistically with attoparsec, and in case of failure - re-parse with parsec to get a nice error message. This should yield the best of both worlds?
    - mrkgnao 9y ago
      Megaparsec is more actively maintained than Parsec (which it's a fork of). You could try that. It's not as fast as attoparsec, but it's close.
  - mrkgnao 9y ago
    Trifecta has poor documentation. I've been thinking about reading the Idris parser to learn trifecta/parsers.
    - axman6 9y ago
      Trifecta is best used via the parsers library, which is fairly well documented. This also (in theory) allows you to switch which parser you use between trifecta, parsec, attoparsec and even ReadP. I say in theory because the the semantics of these libraries differ.
    - quchen 9y ago
      I recommend the much smaller project by Merijn, lambda-except [1]. I learned Trifecta from it, and it’s really not all that difficult, just embarassingly poorly documented. I then wrote the parser for my STGi project based on Trifecta, so that may also be worth a look. [1]: https://github.com/merijn/lambda-except https://github.com/merijn/lambda-except [2]: https://github.com/quchen/stgi/blob/master/src/Stg/Parser/Parser.hs https://github.com/quchen/stgi/blob/master/src/Stg/Parser/Pa...
- Gabriel439 9y ago
  The trick is to use the `parsers` library, which lets you switch out parsing backends. You can prototype with the `trifecta` library (which has good error messages) and then switch to `attoparsec` when you're done For this specific post, the main thing I do is ignore the error messages and just look at where parsing fails by retrieving the leftovers when it fails (using the lower-level `parse` function). Usually that gave me enough of a clue to figure out what was going wrong.
logicchains 9y ago
Note to the author, I found this post extremely hard to read on mobile. I had to scroll horizontally as the text wouldn't all fit on screen, and zooming seemed broken. When attempting to zoom or horizontally scroll it would sometimes randomly click some invisible popout that would take me to another page.
- mrkgnao 9y ago
  Blogger is actively hostile to phone browsers. For horizontal scrolling, you can try dragging at an angle (to fool the page-change JS) and then vertically scrolling to negate the vertical component of the first motion. It becomes pretty natural after a while :/
- Gabriel439 9y ago
  Author here: yes, this bothers me, too (especially the horizontal scroll switching to another post). I'm not sure how to disable that since Blogger doesn't provide a way to disable this. However, I may be able to fix the zooming. This was triggered by the switch to syntax highlighting using Pandoc which wraps each code block in a scrollable frame if it exceeds the given size. I can probably fix that with appropriate CSS although it will take me some time to figure it out.
- tekacs 9y ago
  It would be good to see a fix from this from upstream (but the poster notes that this isn't necessarily simple) of course, but... To propose another hack, I've found that 'Request Desktop Site' in your mobile browser's menu works well for articles like these (it just reverts to desktop layout).
pjmlp 9y ago
Nice article, just one small pedantic remark. > Note that Haskell type synonyms reverse the order of the types compared to C++. This is true in the context of the article when compared with the presented typedef definitions, however the modern way to do type synonyms in C++ is via using declarations, which are very similar to the Haskell ones. using Path = string; using PathSet = set<Path>;
- lordvon 9y ago
  "Using" also allows you to have templated aliases, unlike typedefs. There's really no reason to use typedefs.
  - jchw 9y ago
    Well, of course, there is ONE reason: Having to use old compilers or old standards for other reasons. I imagine a lot of people are in that place with C++. Personally I've followed C++ for a long time as a hobby and it seems like it's finally getting to where it wants to be. But I'll talk to someone who works writing C++ and the idea of being able to use C++17 is a distant dream. For Open Source developers and hobbyists though, you might as well take advantage of whatever features Clang+GCC+MSVC offer. I wish someone would standardize `#pragma once` so I don't have to feel guilty using it.
    - lordvon 9y ago
      Yeah so the only reason you wouldn't use 'using' is when you can't :) Modern c++ is awesome. I definitely appreciate being able use c++14 where I work (as well as 'pragma once'). I really look forward to being able to use c++17.
    - pjmlp 9y ago
      > I wish someone would standardize `#pragma once` so I don't have to feel guilty using it. It is called C++ Modules Technical Specification. :)
Veedrac 9y ago
The C++ code here is exactly the kind of thing that game developers complain about when they say C++ encourages inefficiency. Calling Haskell fast because it merely draws with that doesn't really make sense in this context. Yes, it's as fast as C++ code that doesn't care in the slightest about efficiency, but people use C++ for the times when they do. E: As some quick examples, peeking an istream in a loop is extremely inefficient[1], yet is done pervasively. The Derivation type has a bunch of separately allocated strings, and a lot of types like std::map<string, DerivationOutput> are pointer filled. To check whether a string starts with "r:", they allocate a _new string_ and compare it, rather than just doing a normal string comparison. [1] https://godbolt.org/g/27o9od https://godbolt.org/g/27o9od
- Gabriel439 9y ago
  What is the reason that `peek` is inefficient? Is it just because it is a function call that is not inlined or is there another reason?
  - Veedrac 9y ago
    Really it's the other way around: peek is complex so the compiler didn't inline it. In essence, you do a virtual call which I think winds you up in https://github.com/gcc-mirror/gcc/blob/1cb6c2eb3b8361d850be8e8270c597270a1a7967/libstdc%2B%2B-v3/include/bits/istream.tcc#L620 https://github.com/gcc-mirror/gcc/blob/1cb6c2eb3b8361d850be8... which itself redirects to a whole bunch of stuff. The virtual call alone is a lot more expensive than a simple pointer dereference, and though it's possible proper inlining might have alleviated some of this problem, you're not particularly likely to see it come close to something that's efficient by design.
    - pjmlp 9y ago
      What does the profiler say regarding overall program execution time?
      - Veedrac 9y ago
deleted 9y ago
[deleted]

109 points by yomritoyj 9y ago

Attoparsec is fast, but used to have bad error messages. How do the 2 parsers compare w.r.t error messaging? Haskell has Parsec/Megaparsec which have better error messages, but are extremely slow.

kccqzy 9y ago
I don't think Parsec is "extremely slow." It's not as fast as attoparsec, but not bad either. Trifecta has the best error messages, but takes some more work to fully make the error messages great.
- Peaker 9y ago
  In my experience using Parsec, it was extremely slow. Took around 20 seconds to parse a few hundred thousand lines (almost no backtracking, too). Attoparsec/parsec have very similar APIs. I wonder why it cannot parse optimistically with attoparsec, and in case of failure - re-parse with parsec to get a nice error message. This should yield the best of both worlds?
  - mrkgnao 9y ago
    Megaparsec is more actively maintained than Parsec (which it's a fork of). You could try that. It's not as fast as attoparsec, but it's close.
- mrkgnao 9y ago
  Trifecta has poor documentation. I've been thinking about reading the Idris parser to learn trifecta/parsers.
  - axman6 9y ago
    Trifecta is best used via the parsers library, which is fairly well documented. This also (in theory) allows you to switch which parser you use between trifecta, parsec, attoparsec and even ReadP. I say in theory because the the semantics of these libraries differ.
  - quchen 9y ago
    I recommend the much smaller project by Merijn, lambda-except [1]. I learned Trifecta from it, and it’s really not all that difficult, just embarassingly poorly documented. I then wrote the parser for my STGi project based on Trifecta, so that may also be worth a look. [1]: https://github.com/merijn/lambda-except https://github.com/merijn/lambda-except [2]: https://github.com/quchen/stgi/blob/master/src/Stg/Parser/Parser.hs https://github.com/quchen/stgi/blob/master/src/Stg/Parser/Pa...
Gabriel439 9y ago
The trick is to use the `parsers` library, which lets you switch out parsing backends. You can prototype with the `trifecta` library (which has good error messages) and then switch to `attoparsec` when you're done For this specific post, the main thing I do is ignore the error messages and just look at where parsing fails by retrieving the leftovers when it fails (using the lower-level `parse` function). Usually that gave me enough of a clue to figure out what was going wrong.

logicchains 9y ago

Note to the author, I found this post extremely hard to read on mobile. I had to scroll horizontally as the text wouldn't all fit on screen, and zooming seemed broken. When attempting to zoom or horizontally scroll it would sometimes randomly click some invisible popout that would take me to another page.

mrkgnao 9y ago
Blogger is actively hostile to phone browsers. For horizontal scrolling, you can try dragging at an angle (to fool the page-change JS) and then vertically scrolling to negate the vertical component of the first motion. It becomes pretty natural after a while :/
Gabriel439 9y ago
Author here: yes, this bothers me, too (especially the horizontal scroll switching to another post). I'm not sure how to disable that since Blogger doesn't provide a way to disable this. However, I may be able to fix the zooming. This was triggered by the switch to syntax highlighting using Pandoc which wraps each code block in a scrollable frame if it exceeds the given size. I can probably fix that with appropriate CSS although it will take me some time to figure it out.
tekacs 9y ago
It would be good to see a fix from this from upstream (but the poster notes that this isn't necessarily simple) of course, but... To propose another hack, I've found that 'Request Desktop Site' in your mobile browser's menu works well for articles like these (it just reverts to desktop layout).

pjmlp 9y ago

Nice article, just one small pedantic remark. > Note that Haskell type synonyms reverse the order of the types compared to C++. This is true in the context of the article when compared with the presented typedef definitions, however the modern way to do type synonyms in C++ is via using declarations, which are very similar to the Haskell ones. using Path = string; using PathSet = set<Path>;

lordvon 9y ago
"Using" also allows you to have templated aliases, unlike typedefs. There's really no reason to use typedefs.
- jchw 9y ago
  Well, of course, there is ONE reason: Having to use old compilers or old standards for other reasons. I imagine a lot of people are in that place with C++. Personally I've followed C++ for a long time as a hobby and it seems like it's finally getting to where it wants to be. But I'll talk to someone who works writing C++ and the idea of being able to use C++17 is a distant dream. For Open Source developers and hobbyists though, you might as well take advantage of whatever features Clang+GCC+MSVC offer. I wish someone would standardize `#pragma once` so I don't have to feel guilty using it.
  - lordvon 9y ago
    Yeah so the only reason you wouldn't use 'using' is when you can't :) Modern c++ is awesome. I definitely appreciate being able use c++14 where I work (as well as 'pragma once'). I really look forward to being able to use c++17.
  - pjmlp 9y ago
    > I wish someone would standardize `#pragma once` so I don't have to feel guilty using it. It is called C++ Modules Technical Specification. :)

Veedrac 9y ago

The C++ code here is exactly the kind of thing that game developers complain about when they say C++ encourages inefficiency. Calling Haskell fast because it merely draws with that doesn't really make sense in this context. Yes, it's as fast as C++ code that doesn't care in the slightest about efficiency, but people use C++ for the times when they do. E: As some quick examples, peeking an istream in a loop is extremely inefficient[1], yet is done pervasively. The Derivation type has a bunch of separately allocated strings, and a lot of types like std::map<string, DerivationOutput> are pointer filled. To check whether a string starts with "r:", they allocate a _new string_ and compare it, rather than just doing a normal string comparison. [1] https://godbolt.org/g/27o9od https://godbolt.org/g/27o9od

Gabriel439 9y ago
What is the reason that `peek` is inefficient? Is it just because it is a function call that is not inlined or is there another reason?
- Veedrac 9y ago
  Really it's the other way around: peek is complex so the compiler didn't inline it. In essence, you do a virtual call which I think winds you up in https://github.com/gcc-mirror/gcc/blob/1cb6c2eb3b8361d850be8e8270c597270a1a7967/libstdc%2B%2B-v3/include/bits/istream.tcc#L620 https://github.com/gcc-mirror/gcc/blob/1cb6c2eb3b8361d850be8... which itself redirects to a whole bunch of stuff. The virtual call alone is a lot more expensive than a simple pointer dereference, and though it's possible proper inlining might have alleviated some of this problem, you're not particularly likely to see it come close to something that's efficient by design.
  - pjmlp 9y ago
    What does the profiler say regarding overall program execution time?
    - Veedrac 9y ago

deleted 9y ago

[deleted]