<div>Please pretend I sprinkled primes liberally through the last two code fragments. ;)<br><br></div>
<div class="gmail_quote">On Wed, Aug 19, 2009 at 5:00 PM, Edward Kmett <span dir="ltr"><<a href="mailto:ekmett@gmail.com">ekmett@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">
<div class="gmail_quote">
<div class="im">On Wed, Aug 19, 2009 at 4:21 PM, Ross Paterson <span dir="ltr"><<a href="mailto:ross@soi.city.ac.uk" target="_blank">ross@soi.city.ac.uk</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">
<div>On Wed, Aug 19, 2009 at 01:04:13PM -0400, Edward Kmett wrote:<br>> (*>) and (<*) could be used to apply recognizing parsers for the<br>> discarded half. This makes a huge gain for uu-parsinglib.<br>> uu-parsinglib's P_m monad could be extended just as it has done with<br>
> P_f and P_h to also wrap its existing R monad, which would let it<br>> apply the parser as a recognizer efficiently.<br>><br>> And for parsimony it allows me to treat that side of the alternative<br>> grammar as a right seminearring ignoring the argument, this increases<br>
> sharing opportunities for my grammar fragments, because pure nodes in<br>> recognizers can be treated as epsilons in the grammar and safely elided.<br><br></div>code?</blockquote>
<div> </div></div>
<div>The parsimony case is a bit drastic to post here, because I'd have to basically post the whole library and I haven't released it yet, or rewritten it to accomodate these extra Applicative actions. </div>
<div> </div>
<div>However, I can try to do justice to how uu-parsinglib could use the new members. It currently has several parsers, which have types i'll abridge here.</div>
<div> </div>
<div><span><span>newtype</span> <span>P_h</span> <span>st</span> <span>a</span> <span>=</span> <span>P_h</span> <span>(</span><span>forall</span> <span>r</span> <span>.</span> <span>(</span><span>a</span> <span>-></span> <span>st</span> <span>-></span> <span>Steps</span> <span>r</span><span>)</span> <span>-></span> <span>st</span> <span>-></span> <span>Steps</span> <span>r</span><span>)</span><br>
</span><span>newtype</span> <span>P_f</span> <span>st</span> <span>a</span> <span>=</span> <span>P_f</span> <span>(</span><span>forall</span> <span>r</span> <span>.</span> <span>(</span><span>st</span> <span>-></span> <span>Steps</span> <span>r</span><span>)</span> <span>-></span> <span>st</span> <span>-></span> <span>Steps</span> <span>(</span><span>a</span><span>,</span> <span>r</span><span>)</span><span>)</span><br>
<span>newtype</span> <span>R</span> <span>st</span> <span>a</span> <span>=</span> <span>R</span> <span>(</span><span>forall</span> <span>r</span> <span>.</span> <span>(</span><span>st</span> <span>-></span> <span>Steps</span> <span>r</span><span>)</span> <span>-></span> <span>st</span> <span>-></span> <span>Steps</span> <span>r</span><span>)</span><br>
<a name="1233475dc5ba07a6_line-373"></a><a name="1233475dc5ba07a6_unR"></a><span>newtype</span> <span>P_m</span> <span>state</span> <span>a</span> <span>=</span> <span>P_m</span> <span>(</span><span>P_h</span> <span>state</span> <span>a</span><span>,</span> <span>P_f</span> <span>state</span> <span>a</span><span>)</span> <br>
<br>It uses an 'ExtApplicative' class to let it mix recognizers (R's) with other parsers when you will just be discarding the recognized branch of the result. Note P_f and R are both Applicative, not Monadic.</div>
<div> </div>
<div>I'll just handle (<*) to avoid clutter below.</div>
<div> </div>
<div>
<div><span>class</span> <span>Applicative</span> <span>p</span> <span>=></span> <span>ExtApplicative</span> <span>p</span> <span>where</span><br><a name="1233475dc5ba07a6_line-405"></a> <span>(<</span><span><*</span><span>)</span> <span>::</span> <span>p</span> <span>a</span> <span>-></span> <span>R</span> <span>(</span><span>State</span> <span>p</span><span>)</span> <span>b</span> <span>-></span> <span>p</span> <span>a</span><br>
</div>
<div><span></span> </div>
<div><span>instance</span> <span>ExtApplicative</span> <span>(</span><span>P_h</span> <span>st</span><span>)</span> <span>where</span><br><a name="1233475dc5ba07a6_line-410"></a> <span>P_h</span> <span>p</span> <<span><*</span> <span>R</span> <span>r</span> <span>=</span> <span>P_h</span> <span>(</span> <span>p</span><span>.</span> <span>(</span><span>r</span><span>.</span><span>)</span><span>)</span> <br>
<a name="1233475dc5ba07a6_line-414"></a><span></span></div>
<div><span>instance</span> <span>ExtApplicative</span> <span>(</span><span>P_f</span> <span>st</span><span>)</span> <span>where</span><br><a name="1233475dc5ba07a6_line-415"></a> <span>P_f</span> <span>p</span> <<span><*</span> <span>R</span> <span>r</span> <span>=</span> <span>P_f</span> <span>(</span><span>\</span> <span>k</span> <span>st</span> <span>-></span> <span>p</span> <span>(</span><span>r</span> <span>k</span><span>)</span> <span>st</span><span>)</span><br>
</div></div>
<div>R just discards its phantom type argument. So it is trivially a Functor.</div>
<div> </div>
<div><span>instance</span> <span>Functor</span> <span>(</span><span>R</span> <span>st</span><span>)</span> <span>where</span><br><a name="1233475dc5ba07a6_line-376"></a> <span>fmap</span> _ <span>(</span><span>R</span> <span>r</span><span>)</span> <span>=</span> <span>R</span> <span>r</span><br>
</div>
<div> </div>
<div>Also note that the ExtApplicative case above could not be defined with P_f rather than R. P_f has to deal with its argument, and isn't able to when you would try to apply it like R above. When used applicatively however...</div>
<div> </div>
<div><span>instance</span> <span>Functor</span> <span>(</span><span>P_f</span> <span>st</span><span>)</span> <span>where</span><br><a name="1233475dc5ba07a6_line-146"></a><span> fmap</span> <span>f</span> <span>(</span><span>P_f</span> <span>p</span><span>)</span> <span>=</span> <span>P_f</span> <span>(</span><span>\</span><span>k</span> <span>inp</span> <span>-></span> <span>Apply</span> <span>(</span><span>\</span><span>(</span><span>a</span><span>,</span><span>r</span><span>)</span> <span>-></span> <span>(</span><span>f</span> <span>a</span><span>,</span> <span>r</span><span>)</span><span>)</span> <span>(</span><span>p</span> <span>k</span> <span>inp</span><span>)</span><span>)</span><br>
</div>
<div> </div>
<div>This could be made into a more palatable functor by Yoneda encoding some of the Step GADT constructors, to carry around any mappings, but that is irrelevant to this exposition.</div>
<div> </div>
<div>The P_m monad uses a mechanism for binding history parsers to future parsers, which basically lets the context-free future be glued onto a context-sensitive history.</div>
<div> </div>
<div><span>instance</span> <span>Applicative</span> <span>(</span><span>P_m</span> <span>st</span><span>)</span> <span>=></span> <span>Monad</span> <span>(</span><span>P_m</span> <span>st</span><span>)</span> <span>where</span><br>
<a name="1233475dc5ba07a6_line-209"></a> <span>P_m</span> <span>(</span><span>P_h</span> <span>p</span><span>,</span> <span>_</span><span>)</span> <span>>>=</span> <span>a2q</span> <span>=</span> <br><a name="1233475dc5ba07a6_line-210"></a> <span>P_m</span> <span>(</span> <span>P_h</span> <span>(</span><span>\</span><span>k</span> <span>-></span> <span>p</span> <span>(</span><span>\</span> <span>a</span> <span>-></span> <span>unP_m_h</span> <span>(</span><span>a2q</span> <span>a</span><span>)</span> <span>k</span><span>)</span><span>)</span><br>
<a name="1233475dc5ba07a6_line-211"></a> <span>,</span> <span>P_f</span> <span>(</span><span>\</span><span>k</span> <span>-></span> <span>p</span> <span>(</span><span>\</span> <span>a</span> <span>-></span> <span>unP_m_f</span> <span>(</span><span>a2q</span> <span>a</span><span>)</span> <span>k</span><span>)</span><span>)</span><br>
<a name="1233475dc5ba07a6_line-212"></a> <span>)</span><br></div>
<div>But the same thing can be done with some modifications to P_m to add a possible recognizer (R) as an end-state. These represent a monadic computation with the final batch of applicative or right seminearring operations that end it separated out.<br>
<br><span>newtype</span> <span>P_m'</span> <span>state</span> <span>a</span> <span>=</span> <span>P_m</span> <span>(</span><span>P_h</span> <span>state</span> <span>a</span><span>,</span> <span>P_f</span> <span>state</span> <span>a, R state a</span><span>)</span> <br>
</div>
<div><span>instance</span> <span>Applicative</span> <span>(</span><span>P_m</span> <span>st</span><span>)</span> <span>=></span> <span>Monad</span> <span>(</span><span>P_m</span> <span>st</span><span>)</span> <span>where</span><br>
<a name="1233475dc5ba07a6_line-209"></a> <span>P_m'</span> <span>(</span><span>P_h</span> <span>p</span><span>,</span> <span>_</span><span>)</span> <span>>>=</span> <span>a2q</span> <span>=</span> <br><a name="1233475dc5ba07a6_line-210"></a> <span>P_m'</span> <span>(</span> <span>P_h</span> <span>(</span><span>\</span><span>k</span> <span>-></span> <span>p</span> <span>(</span><span>\</span> <span>a</span> <span>-></span> <span>unP_m'_h</span> <span>(</span><span>a2q</span> <span>a</span><span>)</span> <span>k</span><span>)</span><span>)</span><br>
<a name="1233475dc5ba07a6_line-211"></a> <span>,</span> <span>P_f</span> <span>(</span><span>\</span><span>k</span> <span>-></span> <span>p</span> <span>(</span><span>\</span> <span>a</span> <span>-></span> <span>unP_m'_f</span> <span>(</span><span>a2q</span> <span>a</span><span>)</span> <span>k</span><span>)</span><span>)</span><br>
<a name="1233475dc5ba07a6_line-212"></a> <span>,</span> <span>P_r</span> <span>(</span><span>\</span><span>k</span> <span>-></span> <span>p</span> <span>(</span><span>\</span> <span>a</span> <span>-></span> <span>unP_m'_r</span> <span>(</span><span>a2q</span> <span>a</span><span>)</span> <span>k</span><span>)</span><span>)</span><br>
<span>)</span><br></div>
<div>And then you can drop in special cases for (*>) and (<*) which</div>
<div>mirror the existing code for the ExtApplicative operators of the same name in uu-parsinglib.</div>
<div><span><br><a name="1233475dc5ba07a6_line-419"></a><span>instance</span> <span>Applicative</span> <span>(</span><span>P_m</span> <span>st</span><span>)</span> <span>where</span></span></div>
<div> <span>P_m</span> <span>(</span><span>hp</span><span>,</span> <span>fp,rp</span><span>)</span> <span><*</span> P_m (_,_,<span>r)</span> <span>=</span> <span>P_m</span> <span>(</span><span>hp</span> <span><<*</span> <span>r</span><span>,</span> <span>fp</span> <span><<*</span> <span>r, rp <* r</span><span>)</span> <br>
</div>
<div> </div>
<div> </div>
<div>Now, the a parser written with a substantially unmodified uu-parsinglib can efficiently evaluate the side of the computation that is being ignored because any epsilon productions in that side come for free, so all the fiddly little fmapping that goes on in the Applicative is ignored.</div>
<div> </div>
<div>Doaitse could probably do this better justice than I, as I only have a passing familiarity with the internals of uu-parsinglib. </div>
<div> </div>
<div>parsimony can derive a similar benefit by accumulating a right seminnearring parser as a grammar-algebra off of the base functor for my grammars and applying that grammar when possible for <*'d fragments in a similar fashion, but as it only deals with context-free attribute grammars, it has a simpler job to do.</div>
<a name="1233475dc5ba07a6_line-422"></a>
<div> </div><font color="#888888">
<div>-Edward Kmett</div></font>
<div class="im">
<div> </div>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">
<div>
<div><span></span>_______________________________________________<br>Libraries mailing list<br><a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
</div></div></blockquote></div></div><br></blockquote></div><br>