Effect-based implementation?

[spacekitteh]

So, I'm trying to implement a parser using Megaparsec in an effect-style system (specifically, freer-effects) due to a bunch of reasons (performance, modularity, etc. The usual).

While I can wrap it fairly straightforwardly, the continuation-based nature of it seems to be begging for implementation in terms of a freer-based effect system, with a MTL compatibility layer on top.

Is this something that would be plausible to include in the future? Or are you committed to the monad transformer style?

[mrkkrp]

Hey @spacekitteh, thanks for throwing this in here. To be honest with you, the freer-effects package is new for me, I'm in the process of reading the paper now. I'll answer you properly after that.

It looks like monad transformers in their "conventional" form are starting to have many competitors. Another one is ether.

due to a bunch of reasons (performance, modularity, etc. The usual).

Are you sure this approach has strictly better performance? I'm somewhat skeptical about this. Do you have a benchmark for comparison?

There will be work to make Megaparsec 6 a lot faster for things like Text and ByteString, but this will be done via extending the Stream type class, see #206. There are also things I want to steal from Attoparsec to improve performance for Text and ByteString without making Megaparsec less general, of course. I still need to test them to make sure they actually improve the performance in Megaparsec's case.

Again, thanks, the paper looks interesting. When I finish with it, I'll read freer-effects to get a clearer picture.

[spacekitteh]

Are you sure this approach has strictly better performance? I'm somewhat skeptical about this. Do you have a benchmark for comparison?

Yeah, when used with a large monad/effect stack (e.g. parser + unique name generation + state + tracing + io + configuration reader + etc), effects typically perform algorithmically better - there's a few benchmarks in that paper :)

Amusingly, the way you've implemented ParsecT is very similar to how the freer monad is implemented - only it's extendable :)

[mrkkrp]

I've finished reading the paper (which, I have to admit, is most entertaining). I think we should not use this approach in Megaparsec 6 for two reasons:

1. The approach seems to be not faster than MTL, but rather the performance degrades slower with addition of layers. The benchmarks with single layer shows that MTL is not slower and sometimes dramatically faster than this new approach. From my experience in most parsers there are only ParsecT over Identity and occasionally a StateT layer. More than 2 layers is relatively rare, so we should optimize for the common case when we have few layers, thus we should stay with MTL.

2. Megaparec aims to prove a general-purpose, conventional library for parsing. Thus we should follow conventions until they change. Let's wait till a solution with great-enough appeal (capable of replacing MTL for good) appears, then it'll make sense to switch to that. IOW, I prefer to keep Megaprasec's approach conservative in this regard for now.

The low-level continuation-passing code is simple as it is, and let's keep it in this form.

[spacekitteh]

That's a shame. I guess I'll have to fork it.

On Sun, 11 Jun 2017 at 23:08 Mark Karpov notifications@github.com wrote:

Closed #213 https://github.com/mrkkrp/megaparsec/issues/213.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/mrkkrp/megaparsec/issues/213#event-1118521315, or mute the thread https://github.com/notifications/unsubscribe-auth/AB2crI-4Ne1IxzKAlbK1vQUVWfLLCtydks5sC-bAgaJpZM4N2BsN .

[mrkkrp]

Also see this comment: https://www.reddit.com/r/haskell/comments/6hr59m/using_free_monads_in_a_reallife_large_application/dj0jesy/