David Nolen on Parsing With Derivatives

It's been a long time coming, but we have the fantastic David Nolen (http://swannodette.github.io/), lead developer of Clojurescript (https://github.com/clojure/clojurescript) (among other things) presenting at PWLNYC. He'll be presenting Parsing with Derivatives (http://matt.might.net/papers/might2011derivatives.pdf) by Matthew Might (http://matt.might.net/), David Darais (http://david.darais.com/), & Daniel Spiewak (https://twitter.com/djspiewak). It's a heralded paper that has a super interesting follow-up (https://arxiv.org/pdf/1604.04695.pdf) (On the Complexity and Performance of Parsing with Derivatives), has influenced (http://swannodette.github.io/2016/06/03/tools-for-thought)clojure.spec (http://clojure.org/about/spec), and this helpful video (https://www.youtube.com/watch?v=ZzsK8Am6dKU)!

Abstract

We present a functional approach to parsing unrestricted context-free grammars based on Brzozowski's derivative of regular expressions (https://en.wikipedia.org/wiki/Brzozowski_derivative). If we consider context-free grammars as recursive regular expressions, Brzozowski's equational theory extends without modification to context-free grammars (and it generalizes to parser combinators). The supporting actors in this story are three concepts familiar to functional programmers - laziness, memoization and fixed points; these allow Brzozowski's original equations to be transliterated into purely functional code in about 30 lines spread over three functions.

Yet, this almost impossibly brief implementation has a drawback: its performance is sour - in both theory and practice. The culprit? Each derivative can double the size of a grammar, and with it, the cost of the next derivative.

Fortunately, much of the new structure inflicted by the derivative is either dead on arrival, or it dies after the very next derivative. To eliminate it, we once again exploit laziness and memoization to transliterate an equational theory that prunes such debris into working code. Thanks to this compaction, parsing times become reasonable in practice.

We equip the functional programmer with two equational theories that, when combined, make for an abbreviated understanding and implementation of a system for parsing context-free languages.

Bio

David Nolen (http://swannodette.github.io/) (@swannodette (https://twitter.com/swannodette/)) is a Software Engineer for Cognitect (http://cognitect.com/) and the lead developer of ClojureScript (https://github.com/clojure/clojurescript). He likes making music, playing Go (http://swannodette.github.io/baduk/baduk/2016/01/08/hello-baduk.html), and reading interesting papers.

------------------------------------------------------------------------

http://photos2.meetupstatic.com/photos/event/a/5/4/a/600_433302314.jpeg

TwoSigma (https://www.twosigma.com/) - Platinum Sponsor of the New York chapter

------------------------------------------------------------------------

Details

Doors open at 7 pm; the presentation will begin at 7:30 pm, and, yes, there will be refreshments of all kinds and pizza.

A little different than previous PWLs, you'll have to check-in with security with your Name/ID. Definitely sign-up if you’re going to attend–unfortunately people whose names aren’t entered into the security system in advance won’t be allowed in.

After David presents his work, we will open up the floor to discussion and questions.

We hope that you'll read the paper(s) before the meetup, but don't stress if you can't. If you have any questions, thoughts, or related information, please visit #pwlnyc (https://paperswelove.slack.com/messages/pwlnyc/) on slack (http://papersweloveslack.herokuapp.com/), our GitHub repository (https://github.com/papers-we-love/papers-we-love), where you can also find the papers, or add to the discussion on this event's thread.

Additionally, if you have any papers you want to add to the repository above (papers that you love!), please send us a pull request (https://github.com/papers-we-love/papers-we-love/pulls). Also, if you have any ideas/questions about this meetup or the Papers-We-Love org, just open up an issue.

August's meetup is also sponsored by

http://photos4.meetupstatic.com/photos/event/8/b/5/9/600_452975673.jpeg