2009/11/15 Eugene Kirpichov <span dir="ltr"><<a href="mailto:ekirpichov@gmail.com">ekirpichov@gmail.com</a>></span><br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hey, I've found terrific slides about monoids!<br>
<a href="http://comonad.com/reader/wp-content/uploads/2009/08/IntroductionToMonoids.pdf" target="_blank">http://comonad.com/reader/wp-content/uploads/2009/08/IntroductionToMonoids.pdf</a><br>
Edward Kmett, you rock!<br></blockquote><div><br>Glad you enjoyed the slides. =)<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
There's more <a href="http://comonad.com/reader/2009/iteratees-parsec-and-monoid/" target="_blank">http://comonad.com/reader/2009/iteratees-parsec-and-monoid/</a><br>
- but the second part was too hard for me to read it fully without<br>
special motivation.<br></blockquote><div><br>The iteratees, parsec and monoids talk was mostly to solve a technical problem of my own. The result is a way to build parallel parsers that works quite well for most practical programming language grammars, but requires you to think about parsing a bit sideways and requires a lot of machinery from other areas to make work. <br>
<br>In essence I rely on the fact that in programming languages we typically have a point at which we can resume parsing, or at least lexing, in a context-free manner by locating global invariants of the grammar. <br><br>
These invariants are typically already present and are used to provide error productions in real world compiler grammars, so that the compiler can try to resume parsing. It is a hack, but it is a reasonably efficient hack. =)<br>
<br>To make it work, I have to borrow a lot of machinery from other areas. Iteratees give me a resumable parser, giving that access to its input history lets it backtrack, which lets me bolt them onto parsec, so you can write parsers the way you are used to, at least for the tokens in your language, and then you add a layer on top to deal with the token-stream, which is now available to be reduced monoidally rather than just sequentially.<br>
<br>What I was looking for was a good understanding of what invariants would it make sense to design a language to have so that it could be efficiently parsed in parallel and incrementally reparsed as the user types without having to rescan the whole source file.<br>
<br>-Edward Kmett<br></div></div>