Past Meetup

David Nolen on Parsing With Derivatives

This Meetup is past

239 people went

Twitter NYC

249 W 17th St, New York, NY, FL 6 · New York, NY

How to find us

Near 8th Ave. Note: Please make sure you’re signed-up for the meetup, including your first and last name. Without this info you won’t be allowed into the building by security.

Location image of event venue

Details

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.

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

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