Incremental parsing and left folds

[Ben Franksen]

Adam Langley wrote:
> On Feb 1, 2008 9:35 AM, Bryan O'Sullivan <bos at serpentine.com> 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