Proto for Boost mailing list page: [proto] Thoughts on traversing proto expressions and reusing grammar

Subject: [proto] Thoughts on traversing proto expressions and reusing grammar
From: Thomas Heller (thom.heller_at_[hidden])
Date: 2010-10-04 09:49:59

Hi,

I spent some time on thinking how one could make the traversal of a proto 
expression tree easier. I know want to share my findings with you all, and 
propose a new addition to proto.

My first idea was to decouple grammars from transforms, to follow the idea of 
separation of data and algorithm. Currently, a transform is only applyable 
when a certain expression is matched, this is good and wanted, though 
sometimes you get yourself into a situation that requires you to reformulate 
your grammar, and just exchange the transform part.
Let me give you an example of a comma separated list of proto expression you 
want to treat like an associative sequence:

    opt1 = 1, opt2 = 2, opt3 = 3

A proto grammar matching this expression would look something like this:

   using namespace proto;

   struct not_found {};

   template <int N>
   struct opt {};

   struct term : terminal<opt<_> > {};
   struct spec : when<assign<term, terminal<_> >, _value(_right)>
   struct pack :
       or_<
           when<
                comma<pack, spec>
              , if_<
                    matches<_left(_right), _state>()
                  , spec(_right)
                  , pack(_left)
                >
           >
         , when<
               spec
             , if_<
                    matches<_left, _state>()
                  , spec
                  , not_found()
                >
           >
       >
    {};

    proto::terminal<opt<0> >::type const opt1;
    proto::terminal<opt<1> >::type const opt2;
    proto::terminal<opt<2> >::type const opt3;

    template <typename Expr, typename Opt>
    typename boost::result_of<pack(Expr const&, Opt const&)>::type
    extract(Expr const& expr, Opt const& opt)
    {
        return pack()(expr, opt);
    }

This code works and everybody is happy, right?
Ok, what will happen if we want to calculate the number of options we 
provided in our expression?
The answer is that we most likely need to repeat almost everything from 
pack. except the transform part:

   struct size :
       or_<
           when<
                comma<pack, spec>
              , mpl::plus<size(_left), size(_right)>()
           >
         , when<
               spec
             , mpl::int_<1>()
           >
       >
    {};

Now think of it if you are having a very complicated grammar, c&p the whole 
grammar, or even just parts of it no fun.

My solution to this problem is proto::visitor (see attached):

the signature looks like the following:

    template <
        template <typename> class Visitor
      , template <typename> class Grammar
    >
    struct visitor;

So, visitor is implemented in terms of proto::switch_, What it does is the 
following: Every tag that is encountered gets dispatched to the Grammar 
template specified by the user, is that grammar matched the expression, the 
transform Visitor<Tag> is called.

Let me demonstrate this with our little example above:

   template <typename Tag>
   struct option_grammar // provide a default, don't match anything
      : proto::not_
   {};

   template <template <typename> Visitor>
   struct option_visitor
      : proto::visitor<Visitor, option_grammar>
   {};

   template <>
   struct option_grammar<proto::tag::terminal>
      : proto::terminal<proto::_>
   {};

   template <>
   struct option_grammar<proto::tag::assign>
      : proto::assign<term, proto::terminal<proto::_> >
   {};

   template <>
   struct option_grammar<proto::tag::comma>
      : proto::comma<option_grammar, spec >
   {};

With the defintions of spec and term from the above, this is the grammar  
which matches our expressions. the defintion of our two proto transforms now 
becomes the following:

   template <typename Tag> struct option_eval : proto::_ {};
   
   typedef option_visitor<option_eval> pack;

   template <>
   struct option_eval<proto::tag::terminal>
      : proto::_value
   {};

   template <>
   struct option_eval<proto::tag::assign>
       : if_<
           matches<_left, _state>()
         , pack(_right)
         , not_found()
       >
   {};

   template <>
   struct option_eval<proto::tag::comma>
      : if_<
          matches<_left(_right), _state>()
        , pack(_right(_right))
        , pack(_left)
      >
   {};

How the size calculation would look like is left as an exercise ;)

I hope the motivation and the need for what i called proto::visitor gets 
clear :)

I hear you people scream: what about compile times, when i define my DSL and 
different transforms to the proto trees, i most of the time only need a tiny 
subset of my actual grammar, won't compile times be even higher with this 
approach?
The short answer is no. It seems compile time of proto transforms is not 
really dependent on the grammar's complexity but on the complexity of the 
expressions (I did some basic tests for this, if you don't believe me, i can 
deliver it ;)).

The next thing i wanted to share is about traversals. While working with 
this visitor idea i searched for a good and easy way to specify traversals 
of proto trees. My search was soon over, because, calling transforms 
recursively is what makes proto traverse the tree. I will try to formulate 
some traversal orders in one of my next mails.

Greetings, Thomas