What's new with Marpa

Here's the Marpa "news" from the past few weeks. (Marpa is a new, powerful and fast parser and parsing algorithm. To learn more, check out its web page.)

Revision to the Theory paper

Most of my effort over the past weeks has gone into a paper on the math behind Marpa. I have just uploaded a revised version. I've fixed several typos, including a few nasty ones, for which I apologize. I've also improved the typography and smoothed out the presentation in many places. The basic structure and results of the paper are unchanged. The paper contains pseudocode, a correctness proof, and proofs of my complexity claims.

Deleting old releases

I plan to remove official releases of the various Marpa distributions (Marpa, Marpa::XS, Marpa::PP) that are more than one or two versions old. My guess is that this will release some disk space, and inconvenience nobody.

Updating the distributions

Marpa::XS and Marpa::PP will be updated to make them compatible with a new release of Carp. Carp changed the format of one of its error messages, and since I test diagnostics, the change causes my test suite to fail. Testing diagnostics has paid off for me, but I am updating my tests to be less fussy about the exact format of Carp's feedback. I do NOT plan to update the bare name Marpa, which is an older, deprecated and legacy release.


I continue to work on Marpa::R2, whose first release will feature a 20% speedup, and a documented C language interface. For applications which need stability (and in parsing that's most of them) please prefer Marpa::XS. But I hear from lots of people who want to do things like write new Marpa interfaces, and the main goal of Marpa::R2 is to give them a clear road ahead.


Also underway is another revision of Marpa, called Milarepa. Jetsun Milarepa was Tibet's most notorious black magician. Responsible for the deaths of dozens of his enemies, Milarepa repented and begged Marpa to take him on as a student. Penniless students were often treated by the teachers of the time as more or less slaves, and Marpa made a point of being unusually harsh to the feared Milarepa. Milarepa persevered, and went on to become Marpa's successor and a poet beloved to Tibetans.

My Milarepa project will take the Theory side of Marpa one step further. The difference between the Milarepa and the Marpa::R2 project is that, when my plans involve new code, they become part of Marpa::R2. If my plans are at the mathematical stage, they are, for the moment, part of the Milarepa project.


Typos in the pdf.

2nd page:
* Ruby Sippers Parsing

3rd page:
* abced
* in definition of abcde+ element X{STR} should belong to abcde*{STR}, not abcde{SYM}
* also, you use vocab, then vocab*, but then describe + set with abcde+ instead of vocab+.
* dedicated acceptance rule (acceptRULE) has type SYM in RHS instead of STR or {SYM}

5th page:
* initialDR has startSYM where it should be startSTR

Then I lost track of all details and finished reading in relaxed mode :)

About Jeffrey Kegler

user-pic I blog about Perl, with a focus on parsing and Marpa, my parsing algorithm based on Jay Earley's.