2010/8/23 Eugene Kirpichov
For example, parser combinators are not so interesting: they are a bunch of relatively orthogonal (by their purpose) combinators, each of which is by itself quite trivial, plus not-quite-higher-order backtracking at the core.
This is only if you're not quite considering generalizing parser combinators to non-backtracking algorithms. The CYK algorithm [1] does not backtrack, it merges partial parsing results. When I thought about it I figured that parser combinators became even more restricted that they in arrow parsers. [1] http://en.wikipedia.org/wiki/CYK_algorithm PS CYK is interesting because it provides parallel parsing opportunities, it can parse many parts of text in parallel and then merge bags of successful parsings into another successful parsings. As CYK does not care about start of sequence it was used to parse grammars on hypergraphs: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.6425 PPS I didn't thought fully about CYK parser combinators yet. But I think that CYK could be an example of something unusual in the accustomed field of parsing.