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.

3 Comments

I wonder how in current Marpa::XS, and future Marpa::OO would "code reuse" look like.

There are cases where you want to use the same grammar to drive different output, e.g. parse C declaration and:


  • create equivalent of h2xs - convert .h C header files to Perl extensions
  • create an "explain" part of cdecl
  • generate Fortran 2003 bindings for C code using iso_c_binding intrinsic module

Sometimes you also extends grammar, like e.g. going from simple calculator to scientific calculator, or from parsing C declarations to parsing C.

Yeah, I've also wanted to be able to inherit and extend grammars to support different dialects of a language.

About Jeffrey Kegler

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