Help needed: Restrictions of proc-notation with RebindableSyntax

Edward Kmett ekmett at
Wed Dec 21 13:10:39 UTC 2016

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. 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! =)


On Wed, Dec 21, 2016 at 4:00 AM, Henrik Nilsson <
Henrik.Nilsson at> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the ghc-devs mailing list