Edit: Hosting back up, split over Ubuntu One and Amazon S3. Should be good for awhile! Sorry for any inconvenience.
So I recently gave a talk to the Triangle Area Functional Programmer's Group about Monadic Parser Combinators. If you don't know what these are, they essentially constitute a formalism for creating purely functional parsers by building them up from simpler ones. I really dig their minimal elegance, pure functionality and the fact that they are a monad that isn't the list or maybe monad, which is always what people use as examples. Oh, and the whole thing is in Emacs Lisp, which I think has lots of didactic benefits.
Oh Where Can I Get A Screencast of this Fascinating Talk??
If you'd like to see the talk, I've create a screencast of it in either AVI or OGV format. If you can use Ogg Video (and you should) that version is a lot cleaner looking and easier to read.
I'd like to point everyone to Drew Crampsie's SMUG Library for Common Lisp. Although I develop the MPCs from the ground up in the screencast, the basic shape of the library owes itself to Drew's very nice implementation notes on the library. And SMUG is more powerful in a variety of ways too. Check it out.
As usual, the whole talk (which is a series of elisp files) is available on my github.
10 comments:
I think I've accidentally done something fairly similar in Python.
I started writing my own parser library, so that I could implement yet another version of Markdown after reading about PEGs, but I didn't really keep any PEG stuff in there.
https://github.com/Singletoned/pegger
What I have come up with seems very similar to what you've done. There are parsing functions that accept a pattern and some text, and they return a tree node (sexps) and remaining text.
I hadn't thought of the idea that if you match x, then create a new parser y, but I think it would be quite trivial to add.
I have added an extra level of indirection as the parsing functions aren't meant to be used directly by users, and so there are classes with nice names that represent patterns (which is what the user deals), that makes it easier for them. An example is my (partial) Markdown parser:
https://github.com/Singletoned/markdown3
In there, for the ordered and unordered lists, you can see how you can use functions to compose 'patterns'.
Anyway, I think I now have a better name for what I'm want to achieve (Monadic Parsing), and some material I can go away and read.
Thanks
Ed
Ed, sounds fascinating. I actually thought really hard about implementing this talk in Python, but I couldn't find a good enough metaprogramming system to implement the binding form.
The binding form `parser-let*` is the equivalent (for this one monad) of Haskell's do notation. Combining parsers is considerably less clean without some kind of `do-like` notation. It sounds like your library makes it easy enough, however. I'm going to check it out.
In my library, you don't combine parsers, you combine patterns. Patterns have a type (OneOf, AllOf, etc) and there's a dispatcher that looks up the type of the pattern and dispatches to the relevant parser function.
The parser functions then recursively dispatch based on the subpatterns in a pattern.
I should emphasise that at the moment it is all horrendously inefficient, but there are some easy gains to be made by caching the generated patterns.
Anyway, I'd be keen to receive any feedback on it, particularly as my CS knowledge is quite weak, and this all fell out by accident.
I'm sure you computer science is pretty powerful - it isn't my background either, so if you are working as a programmer, you are probably more advances than I am. I'll take a look at it sometime just to see if I have any suggestions, though.
Programming is tons of fun, isn't it?
Fantastic talk, I thoroughly enjoyed this from start to finish. I've had a play with Haskell and dived straight in, and was blown away by both the power of them (in terms of expression), yet the inherent simplicity. Seeing this area explored from the ground up has only grown my appreciation for them! Likewise, seeing monads applied to Lisp in a practical manor has also been enlightening - and certainly motivating for me to leverage the power of monadic operations in some of my other code.
Good pace, and well presented - I hope you do more!
Awww shucks, 'tweren't nothin'.
Seriously, though - thanks. You should check out some of the other posts about monads on this blog if you liked this!
I just realized I made some stunning typos up there. Ooops! I promise, I am literate!
I have been using emacs for a little over a year and just starting to scratch the surface of functional programming. Really cool stuff, thanks so much for making this screencast. I learned a ton.
Dave, thanks for the feedback. It is always great to hear from someone who got something out of things I make.
thanks for putting up the screencast
Post a Comment