[boost] Spirit and typeof [was typeof]

From: Joel de Guzman (joel_at_[hidden])
Date: 2004-05-04 02:36:51

Arkadiy Vertleyb wrote:
> "Joel de Guzman" <joel_at_[hidden]> wrote
> 
>>I would love to incorporate this stuff into Spirit !!!
>>1) It would simplify grammars a lot. 2) It would give
>>a significant performance boost 3) It would reduce the
>>generated code size by as much as 80%.
> 
> 
> Just out of curiousity, why would performance be affected?

1) No more virtual function for rules.

2) The Spirit grammar implementation employs a workaround to make
it accept any type of scanner by delaying the instantiation of
rules (the culprits) at parse time when the scanner type is known.
Such a scheme is possible if the typed-definition (a nested template
class) is a static object in the "parse" function. This scheme involves
some esoteric tricks to make it multi-thread safe. These tricks bloat
the code and degrade the performance considerably.

>>Spirit would definitely benifit from Arkadiy's typeof. I'd like to
>>offer this challenge to Arkadiy. If you can easily retrofit Spirit
>>with a generic typeof/auto facility, I would love to make it an
>>integral part of the library.
> 
> 
> I accept. 

Cool!

> I would first have to get better acqainted with Spirit, though.
> May I ask a few preliminary questions:
> 
> 1) Does Spirit operate exclusively on the library-defined classes/templates
> or some user-defined types are also involved (ease of use issue)?

Spirit operates *mostly* (but not exclusively) on library-defined classes.
It is possible for clients to write their own parsers. On some rare occassions,
people do write their own parsers.

> 2) Do Spirit templates usualy accept type template parameters or integral
> values are often used as well (ease of registration issue)?

A few accept integral constants (the subrule comes to mind).

> 3) If we wanted to represent a spirit expression as a tree, where each node
> would be a type (leaf) or a template, what would be a reasonable amount of
> nodes, default template parameters excluded (limitations/compile speed
> issue)?

That's hard to estimate. I've seen rules that break the compiler limits
of newer compilers such as VC7.1. But, then again, the general recommendation
is to always break down rules to smaller fragments.

> 4) How many typeofs would be reasonable to expect per translation unit
> (compile speed issue)?

This is also hard to estimate. Ditto, the general recommendation
is to always break down rules to smaller fragments.

> Considering my current schedule, I am not expecting to be ready by tomorrow
> :)  May take me a week or two to produce some result.  Is this OK?

Take as much time as you want. I'd be willing to help in any way I can.
My ultimate goal is to eliminate all rules, hence making all parsers
fully polymorphic. I'm sure that would involve some new facilities to
make forward rules work. Consider the calculator for example.

Here's how I envision the calculator will be once we have auto and
typeof:

     struct calc : grammar<calc>
     {
         auto
         definition() const
         {
             forward_rule<1> expression;

             auto group        = '(' >> expression >> ')';
             auto factor       = integer | group;
             auto term         = factor >> *(('*' >> factor) | ('/' >> factor));
             return expression = term >> *(('+' >> term) | ('-' >> term));
         }
     };

forward_rule<1> borrows from the subrule technique. It is necessary
because expression is used *before* it is defined. Think of it as
a placeholder like phoenix::arg1 and LL::_1.

The base grammar class uses CRTP, as usual. It will probably be
written as:

     template <typename Derived>
     struct grammar : parser<Derived>
     {
         grammar()
             : start(derived().definition()) {}

         Derived const&
         derived() const
         {
             return *static_cast<Derived const*>(this);
         }

         typeof(derived().definition()) start;
     };

It will contain a single member named "start".

I'll give you CVS access to Spirit (tell me your SF login). I'd like
to start a new CVS branch for typeof/auto experimentations. This would
involve not only Spirit but Phoenix as well. I have a feeling that this
will take more than a week or two. Yet, I'm sure that the results would
be gratifying, at the very least.

Thanks you and Regards,
-- 
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net