<div dir="ltr">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.<div><br></div><div>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. <a href="http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf">http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf</a> mentions this style of FIRST-set tracking parser as the original motivation for arrows.</div><div><br></div><div>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! =)</div><div><br></div><div>-Edward</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 21, 2016 at 4:00 AM, Henrik Nilsson <span dir="ltr"><<a href="mailto:Henrik.Nilsson@nottingham.ac.uk" target="_blank">Henrik.Nilsson@nottingham.ac.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Edward,<br>
CC Others,<span class=""><br>
<br>
On 12/21/2016 05:15 AM, Edward Kmett wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Arrows haven't seen much love for a while. In part this is because many<br>
of the original applications for arrows have been shown to be perfectly<br>
suited to being handled by Applicatives. e.g. the Swiestra/Duponcheel<br>
parser that sort of kickstarted everything.<br>
</blockquote>
<br></span>
Thanks for a very thorough reply.<br>
<br>
A quick side-remark: a parser library due to Sweistra (and maybe<br>
Dupncheel, I can't remember) used an applicative structure a long time<br>
before applicatives became apkicatives and even idioms. (I used a<br>
variation of this library myself for the Freja compiler around 1995.<br>
Freja was part of my PhD work and was close to what Haskell looked like at the time.)<br>
<br>
I've never used arrows for parsing, or seen the need for arrows in that<br>
context, but find arrows a very good fit for many EDSLs, including<br>
stream-processing/FRP/Yampa of course, along with other circuit-like<br>
abstractions, which I'd say were the original motivation for arrows.<br>
Altenkirch have also used arrow-like notions in the context of quantum<br>
computation. More recently for probabilistic programming and<br>
Bayesian inference. Except then that the current hard-wired "pseudo-<br>
product" in particular often gets in the way. Along with the fact<br>
that there is no good support for constrained arrows (or monads).<br>
<br>
Best,<br>
<br>
/Henrik<br>
<br>
<br>
<br>
<br>
<br>
This message and any attachment are intended solely for the addressee<br>
and may contain confidential information. If you have received this<br>
message in error, please send it back to me, and immediately delete it. <br>
Please do not use, copy or disclose the information contained in this<br>
message or in any attachment.  Any views or opinions expressed by the<br>
author of this email do not necessarily reflect the views of the<br>
University of Nottingham.<br>
<br>
This message has been checked for viruses but the contents of an<br>
attachment may still contain software viruses which could damage your<br>
computer system, you are advised to perform your own checks. Email<br>
communications with the University of Nottingham may be monitored as<br>
permitted by UK legislation.<br>
<br>
</blockquote></div><br></div>