Hey all,
One of my applications uses effectful as its effect stack that I’d like to also use Megaparsec with. As Megaparsec exports the MonadParsec mtl-style class, I was thinking it would be best to try to create a Parsec effect (rather than running ParsecT on top of Eff directly), but I’ve been running into some issues with making the Alternative instance work properly.
The full code (modulo the relevant packages) can be found here.
The core conceit of this work is that Megaparsec is pretty complicated, so instead of reinventing the wheel, we can store the structure of the parser as Eff effects, then when the time comes build a ParsecT to actually run the parse. This works seamlessly on the coding side, but the actual parser semantics don’t seem to be preserved properly – specifically, it doesn’t seem to backtrack at all. A minimal example that doesn’t work is running the parser string "a" <|> string "b" on the corpus b (works when run with ParsecT directly, does not work when run via runParsec').
My understanding of the underlying problem here is that throwError () <|> anything reduces to throwError () under Effectful’s NonDet semantics, meaning that when we strip off the outer Parsec effect, the second branch doesn’t get explored even if it would cause parsing to succeed.
I figured that we could resolve this by creating a bespoke interpreter that reduced the NonDet effect first to interpret a :<|>: b as ParsecT’s instance of Alternative, thus restoring backtracking. However, this doesn’t seem to have had any effect, the parser still fails and tells me that "a" was expected.
It’s worth noting that, if I adjust runParsec' to use NonDet and treat a parse failure as Empty, we get backtracking back, but then we lose the accumulated error state. I tried to fix this by keeping a Writer that accumulated parse errors, but this seemed to fall over when given more complex composite parsers (not included in code snippet, can provide on request if people think this is the right way to go).
At this point, I’m at my wit’s end. Does anyone else better-versed in the effect landscape have wisdom to give here?
EDIT: I am aware that effectful struggles with effects that need to suspend and resume a given computation, e.g. ContT, which suggests that I might just be hosed here. However, I’m a bit ashamed to say that I don’t really understand how that actually comes into play in practice here – in my head, the continuations are an internal implementation detail that are hidden away entirely under the ParsecT that gets built when interpreting Eff (NonDet : Parsec e s : es) a, and shouldn’t need interact with Eff at all.