May ’10 08

Finally, the long wait and the preparations for BoostCon 2010 are over. The last weeks were dominated by writing the code and creating the slides for our talk ‘A Framework for RAD Spirit‘. Regular readers of this site probably have already wondered why we have been inactive here since mid-March. Well, that is mainly because of preparing for BoostCon turned out to be too time consuming to leave any room for writing posts and articles.

Our  talk (Joel’s and mine) is about the current status and the preliminary results we achieved while working on the compiler project announced earlier. We settled for applying a Scheme based framework to create a rapid development environment for Spirit parsers. This is a really exciting project which will have long term impact not only on Spirit.

Here is a sneak preview of what we will present at BoostCon.

As you can see, we created a kernel consisting out of a cool data structure called U-tree (essentially a discriminated union), capable of storing any  S-expression. On top of this Joel developed a Scheme compiler/interpreter which first constructs a dynamic expression tree from the S-expression (the compiler) conforming to the usual Scheme execution rules. Executing this expression tree yields the result encoded in the Scheme code which has been stored in the S-expression in the first place (the interpreter).

As a byproduct of this we got the beginnings of a new library – the dynamic counterpart of Boost.Phoenix. It is aimed at dynamic execution trees based on functional programming paradigms. So the Scheme compiler creates a functional data structure which is indistinguishable from an equivalent data structure created from a C++ expression built on top of this new library.

In order to fill the S-expression from Scheme code we developed a Spirit based parser. OTOH, the Scheme generator (written using Karma – what else?) takes any S-expression and converts it back to the equivalent Scheme code.

The (currently) top most layer of the framework consists of a Parser for Qi expressions which creates an S-expression and a corresponding generator converting any S-expression holding a Qi parser back into the equivalent Qi (C++) expression. Naturally, the Qi parser is written using Qi and for the Qi Generator we utilized Karma. The Qi compiler mentioned in the figure takes such an S-expression and produces an execution tree, which – when actually run – parses any input conforming to the initial Qi grammar.

I don’t want to spoil the fun and tell too much at this point, but overall this is not only a nice example of how to write more complex Spirit applications, but it gives you a rapid development platform allowing to quickly test Qi parsers. Moreover, as the whole thing is based on a Scheme kernel, you can write your own Scheme code for additional transformations of the handled S-expressions. In the context of the Qi based S-expressions mentioned above this is equivalent to dynamic parser transformations or arbitrary parser analysis modules. That is pretty powerful stuff!

Joel and I plan to write about what we developed and what we learnt while developing this and we hope to get some of you interested to chime in. There is still a lot to do, we are by no means done with this framework. And, as I mentioned already, I believe this will have an impact far beyond its initial target audience.

But BoostCon is not only about Spirit (even if there will be at least 3 talks about it). We will have a full week packed with sessions presented by well known Boost people speaking about a whole set of interesting topics. Just have a look at the BoostCon schedule to convince yourself. Over the next week I will try to document some of my impressions live from the Physics Center in Aspen (where BoostCon takes place). So stay tuned!

Leave a Reply

preload preload preload