Ocean of Awareness

Jeffrey Kegler's blog about Marpa, his new parsing algorithm, and other topics of interest

Jeffrey's personal website

Google+

Marpa resources

The Marpa website

The Ocean of Awareness blog: home page, chronological index, and annotated index.

Sat, 21 Jan 2012


Marpa and OO

Both publicly and privately I hear from folks who tell me that Marpa is an OO superclass waiting to happen. I can see their point. If there ever was a case for code reuse, the Marpa algorithm is one. On the other hand, any non-trivial use of Marpa requires additional semantics, so that the Marpa classes walk, swim and quack very much like abstract type classes.

Furthermore, the additional semantics that Marpa needs comes in pieces -- semantic actions. And even though these pieces often share little code with each other, they interact heavily as part of a specific structure. This means that their semantics are tightly coupled, both to each other and to Marpa. In short, Marpa's semantic actions look a lot like the methods of a subclass.

Not that there aren't issues. In particular, if Marpa were a superclass, its subclasses wouldn't know which methods they needed to implement until after the grammar was fully specified -- in other words until deep into runtime. But if you're into OO, there are no problems, just interesting challenges.

A top priority with me is to empower those who have ideas for alternative Marpa interfaces, whether object-oriented or not. Currently, Marpa::XS is divided into two layers. The core algorithm is in a C library (libmarpa). The interface code is the upper layer. Written in Perl, this upper layer calls libmarpa. But in Marpa::XS, libmarpa's interface was not documented, and frankly the Marpa::XS version of libmarpa was so hackish that it needed to be rewritten before it could be effectively and clearly documented. In the development version of Marpa, Marpa::R2, this rewrite has been completed, and the libmarpa documentation is now underway.

With a documented libmarpa interface, authors of new Marpa interfaces can totally bypass the current Marpa::XS interface. And in terms of speed, they'll start the race with an advantage -- Marpa::R2 is 20% faster than Marpa::XS.

But why wait for Marpa::R2 to try out your ideas? At the cost of a modest overhead, a new OO interface can be layered on top of Marpa::XS. The new interface can simply define a default action to Marpa::XS, one that implements your wrapper's semantics. Supplying an OO context to Marpa's semantic actions is easy. All Marpa::XS's actions receive as their first argument a "per-parse variable". The per-parse variable can be initialized to anything the upper layer wants. A wrapper object could pass itself to Marpa's semantic actions as their per-parse variable. Marpa::XS's semantic actions can then easily use the wrapper object to call one of the wrapper's methods, passing it the semantic action's other arguments.


posted at: 10:41 | direct link to this entry

§         §         §