The S&D parser I was referring to was based on tracking FIRST sets, and provided a nice linear time parsing bound for (infinite) LL(1) grammars. (You can't really compute FOLLOW sets without knowing the grammar has a finite number of productions, but FIRST sets work perfectly well with infinite grammars.) By doing so you can transform parsing into more or less a series of map lookups for dispatch.

You need to carry a set of all characters that a parser will consume in the case of legal parses, and whether or not the parser accepts the empty parse. http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf mentions this style of FIRST-set tracking parser as the original motivation for arrows.

Of course, they didn't see fit to stop puttering around with parsers after 1998, so referring to "the S&D parser" is quite ambiguous! =)

-Edward

On Wed, Dec 21, 2016 at 4:00 AM, Henrik Nilsson <Henrik.Nilsson@nottingham.ac.uk> wrote:

Hi Edward,
CC Others,

On 12/21/2016 05:15 AM, Edward Kmett wrote:

Arrows haven't seen much love for a while. In part this is because many
of the original applications for arrows have been shown to be perfectly
suited to being handled by Applicatives. e.g. the Swiestra/Duponcheel
parser that sort of kickstarted everything.

Thanks for a very thorough reply.

A quick side-remark: a parser library due to Sweistra (and maybe
Dupncheel, I can't remember) used an applicative structure a long time
before applicatives became apkicatives and even idioms. (I used a
variation of this library myself for the Freja compiler around 1995.
Freja was part of my PhD work and was close to what Haskell looked like at the time.)

I've never used arrows for parsing, or seen the need for arrows in that
context, but find arrows a very good fit for many EDSLs, including
stream-processing/FRP/Yampa of course, along with other circuit-like
abstractions, which I'd say were the original motivation for arrows.
Altenkirch have also used arrow-like notions in the context of quantum
computation. More recently for probabilistic programming and
Bayesian inference. Except then that the current hard-wired "pseudo-
product" in particular often gets in the way. Along with the fact
that there is no good support for constrained arrows (or monads).

Best,

/Henrik

This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please send it back to me, and immediately delete it.
Please do not use, copy or disclose the information contained in this
message or in any attachment. Any views or opinions expressed by the
author of this email do not necessarily reflect the views of the
University of Nottingham.

This message has been checked for viruses but the contents of an
attachment may still contain software viruses which could damage your
computer system, you are advised to perform your own checks. Email
communications with the University of Nottingham may be monitored as
permitted by UK legislation.