Re: Incremental parsing and left folds

Adam Langley wrote:

On Feb 1, 2008 9:35 AM, Bryan O'Sullivan wrote:

...

It wouldn't be hard to take bytestringparser and perform the same transformation on it as Adam Langley did with his IncrementalGet parser for strict-binary. I've been skipping it due to lack of time, but it's an obviously right thing to do.

I think the hurdle here would be that you can't easily rollback the state. Normally, in a parser one can just take the current state and revert to that if a parsing path fails. However, in an incremental parser, of the style of IncrementalGet, rolling back the state would mean that the additional data which has been supplied to the parser, via continuations, will be lost and needs to be resupplied. That's a non-solution because the caller shouldn't need to know anything about the internals of the parser.

I think one could get around this by having a couple of states, the latter being a list of all the additional ByteStrings that the parser has received. Then, after having prospectively failed a certain parse path, the failure must include the list of additional data, which can be merged into the new state for the next prospective path. This failure value must be internal and, at the top level, translated into a more user-friendly failure.

Unless something special is done, this also means that the incremental parser couldn't walk over huge streams of data, because it would still be holding all the input in case it gets reverted. Of course, the top level cannot be reverted, so maybe it's worth special casing this.

Would 'Parallel Parsing Processes' help here? See http://www.haskell.org/haskellwiki/Research_papers/Functional_pearls For a version that is easy to understand and implement, see Chuan-kai Lin's Unimo paper available from the author's home page. Cheers Ben