I’ve been mentoring for GSOC for a couple of years now. This one is the best (the Fusion 0x project of last year’s GSOC was also highly successful, but it was Hartmut Kaiser who mentored that). Thomas is an amazing student! A++, if there’s such a thing.

Here’s Thomas’ post on the Boost mailing list:

Ladies and Gentlemen,

I proudly announce that the port of phoenix3 is completed! All  testcases pass! (some with minor modifications)

So, What is next? Here is my proposed schedule:

• fix some minor issues
• improve boost.bind compatibility: make all boost.bind testcases pass
• implement all boost.lambda testcases and make them pass, as far as it is reasonable
• add support for C++0x lambdas
• make interoperability testcases for std::function, boost::function
• adapt the documentation
• clean up code (some parts are a little messy as of now)
• improve compile time

Did I miss something?

This is a very tight schedule, I may not be able to finish all points during the GSoC period. Any help will be appreciated. Additionally a review of the current code is highly appreciated to point out some defects that might exist.

The code can be checked out at:
https://svn.boost.org/svn/boost/sandbox/SOC/2010/phoenix3

I will be happy to answer your questions!

Additionally I would like to thank Joel de Guzman and Eric Niebler for their great assistance and initial designs!

So why is this relevant? Here’s more from Eric Niebler:

Let me expand a bit on Thomas’ post with my own perspective. Currently, the expressions created by Boost.Bind, Boost.Lambda and Boost.Phoenix2 are black boxes. You can pass them to std algorithms for evaluation, but that’s about it.

In contrast, the expressions created by Boost.Phoenix3 will the Proto expressions. If Phoenix3 is the compiler of a C++-in-C++ domain specific language, then the Proto expression is the intermediate form. It will be documented and part of the Phoenix3 API. The grammar for valid Phoenix3 expressions will also be documented and extensible. For the first time, we will have a way to generate C++-like expression trees, just like the C++ compiler itself does. We have a standard way (Proto) to traverse and manipulate them. Sure, you can just evaluate them as you could before, but now you can do much more. For instance, you can define your own Proto transforms to:

• Do various optimizations, just like a real compiler
• Add your own custom evaluation strategies for operations on your types
• Rewrite Phoenix3 expressions for parallel execution, or whatever
• ???!!!

Essentially, it means Phoenix3 is a white box, an open platform. Third parties can use just the Phoenix3 front end and intermediate form, substituting their own back ends to make the expressions mean and do completely different and domain-specific things.

Expect to see Phoenix3 expressions showing up in other DSEL contexts. It’s hard to predict how people will use this. The possibilities are really limitless.

See the “Best Practices” page here.

Michael Caisse of Object Modeling Designs designed this cool Spirit inspired T-shirt. I love it so much. If you like Spirit as much as we do, you can get one from Michael here: http://objectmodelingdesigns.com/swag.html

I have to admit I was not sure how people would react to this kind of talk. It was not one of the usual, sophisticated, well thought through, and cutting edge presentations normally seen at BoostCon. This talk was merely a conversation with the attendees about Boost’s history guided by Spirits evolution. In the end I was relieved to see people reacted positively. Some came to me afterwards saying they enjoyed listening. For all of you not being at BoostCon, here are the slides: Spirit: History and Evolution.

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!

I just wrote a parser for S-expressions (that will be the basis of ASTs and intermediate types in my planned “write-a-compiler” article series). The parser itself is easy, but as always, I spent more time on the underlying data structures.

What are S-expressions? S-expressions, also called sexps, are recursive, list based, data structures. Being recursive, they can represent hierarchical information. S-expressions are parenthesized prefix expressions, known for their use in LISP (and its sibling Scheme). Here’s a simple sexp:

(* 2 (+ 3 4))

The sexp above corresponds to this infix expression:

(2 * (3 + 4))

S-expressions are simple and infinitely powerful beasts as evident in applications that use LISP as their scripting language. They can represent code and data. Some people even use S-expressions as a suitable (and terser!) replacement for XML. The in-memory data structures are very easy to use, transform and manipulate, traverse and compile or accumulate results from.

The plan is to use S-expressions as our AST representation and embed a minimal LISP/Scheme interpreter IN the compiler. This implies that along the way, we’ll be building an S-expression parser and a LISP/Scheme interpreter. How cool is that? … We’re talking about scripting the compiler with an interpreter!

I needed a dynamic data type that can represent the S-expressions. I called it utree, short for universal-tree. I want it to be as simple as it can be and fast and tight in memory footprint. Boost variant was simply out of the question (I used it in one early prototypes). For one, it failed a basic requirement (tight memory footprint). The padding and the way it aligns the “what-type” integer member is quite wasteful. It uses a conservative alignment using the worst alignment of the types in the union. Thus if you have a type in there that aligns to 8 bytes, variant requires another 8 bytes just for the type discriminator! Try it out:

struct x { void* a; void* b; void* c; };
/***/
std::cout << sizeof(x) << std::endl;
std::cout << sizeof(boost::variant<x, int, double>) << std::endl;

I get: 12 and 24 respectively (32 bit system).

I ended up with 40 bytes in my initial prototype (using STL containers and variant) and later squeezed that to 24 (minimum). I did away with variant in my latest version and got 16 bytes. In this case, I “stole” unused padding bits from the data to store the discriminator.   With this 16 bytes, I have nil, bool, int, double, string and (double linked) list. The string itself steals memory when it can (i.e. it stores the string in the union when it can and only uses the heap when needed). The string steals as much as it can. So, on 32 bit systems, it can store in-situ as much as 14 bytes. That’s a lot for storing simple strings like symbols and identifiers. On 64 bit systems, you can store a lot more in-situ and minimize heap usage more.

At this point, I feel like writing my own variant type that can do such things (intrusive variant?). Barring the use of Boost.Variant, I needed to write my own data structures (double linked list). I really wanted to use Boost.Intrusive which is quite efficient, but because I had to squeeze my own variant in there, I had to make use of unions which require PODs!

Here’s the work in progress:
http://boost-spirit.com/dl_more/scheme/scheme_v0.2/

Here’s the utree API:

    ///////////////////////////////////////////////////////////////////////////
    // The main utree (Universal Tree) class
    // The utree is a hierarchical, dynamic type that can store:
    //  - a nil
    //  - a bool
    //  - an integer
    //  - a double
    //  - a string (textual or binary)
    //  - a (doubly linked) list of utree
    //  - a reference to a utree
    //
    // The utree has minimal memory footprint. The data structure size is
    // 16 bytes on a 32-bit platform. Being a container of itself, it can
    // represent tree structures.
    ///////////////////////////////////////////////////////////////////////////
    class utree
    {
    public:

        typedef utree value_type;
        typedef detail::list::node_iterator<utree> iterator;
        typedef detail::list::node_iterator<utree const> const_iterator;
        typedef utree& reference;
        typedef utree const& const_reference;
        typedef std::ptrdiff_t difference_type;
        typedef std::size_t size_type;

        struct nil {};

        utree();
        explicit utree(bool b);
        explicit utree(unsigned int i);
        explicit utree(int i);
        explicit utree(double d);
        explicit utree(char const* str);
        explicit utree(char const* str, std::size_t len);
        explicit utree(std::string const& str);
        explicit utree(boost::reference_wrapper<utree> ref);

        utree(utree const& other);
        ~utree();

        utree& operator=(utree const& other);
        utree& operator=(bool b);
        utree& operator=(unsigned int i);
        utree& operator=(int i);
        utree& operator=(double d);
        utree& operator=(char const* s);
        utree& operator=(std::string const& s);
        utree& operator=(boost::reference_wrapper<utree> ref);

        template <typename F>
        typename F::result_type
        static visit(utree const& x, F f);

        template <typename F>
        typename F::result_type
        static visit(utree& x, F f);

        template <typename F>
        typename F::result_type
        static visit(utree const& x, utree const& y, F f);

        template <typename F>
        typename F::result_type
        static visit(utree& x, utree const& y, F f);

        template <typename F>
        typename F::result_type
        static visit(utree const& x, utree& y, F f);

        template <typename F>
        typename F::result_type
        static visit(utree& x, utree& y, F f);

        template <typename T>
        void push_back(T const& val);

        template <typename T>
        void push_front(T const& val);

        template <typename T>
        iterator insert(iterator pos, T const& x);

        template <typename T>
        void insert(iterator pos, std::size_t, T const& x);

        template <typename Iter>
        void insert(iterator pos, Iter first, Iter last);

        template <typename Iter>
        void assign(Iter first, Iter last);

        void clear();
        void pop_front();
        void pop_back();
        iterator erase(iterator pos);
        iterator erase(iterator first, iterator last);

        utree& front();
        utree& back();
        utree const& front() const;
        utree const& back() const;

        utree& operator[](std::size_t i);
        utree const& operator[](std::size_t i) const;

        void swap(utree& other);

        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;

        bool empty() const;
        std::size_t size() const;
    };

    bool operator==(utree const& a, utree const& b);
    bool operator<(utree const& a, utree const& b);
    bool operator!=(utree const& a, utree const& b);
    bool operator>(utree const& a, utree const& b);
    bool operator<=(utree const& a, utree const& b);
    bool operator>=(utree const& a, utree const& b);

Continue reading »