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

Subject: Re: [proto] Thoughts on traversing proto expressions and reusing grammar
From: Eric Niebler (eric_at_[hidden])
Date: 2010-10-20 23:11:49

On 10/20/2010 7:49 AM, Thomas Heller wrote:
> I worked a little on trying to simplify that whole grammar with 
> rules that have thing a bit. Forgive me, but i changed the name to Visitor. 
> Why? Simply because i think this is what is done here. We visit a specific 
> node which happened to match our rule.

Most tree traversal algorithms "visit" each node, but the term "Visitor"
means something very, very specific: the Gang-of-Four Visitor Design
Pattern. It implies an OO hierarchy, a virtual "Dispatch" member that
accepts a visitor, and a 2nd dispatch to an "Accept" member of the
visitor object. It is used to "add" members to an OO hierarchy post-hoc
by putting them in a visitor instead of having to change every type in
your hierarchy.

If you don't have something like that, then don't call it Visitor. If
you do, then we need to reformulate this design to make that pattern
more explicit. Otherwise, it will cause no end of confusion.

Historical note: I originally called the "data" parameter of Proto
transforms "visitors". During the review, there was such a hue and cry
(for good reason) that I had to change it. True story.

> Here it goes:
>     namespace detail
>     {
>         template <
>             typename Grammar, typename Visitor, typename IsRule = void>
>         struct algorithm_case
>             : Grammar
>         {};

Why inherit from Grammar here instead of:

  : proto::when<
        Grammar
      , typename Visitor::template visit<Grammar>
    >

?

>         template <
>             typename Rule, typename Visitor, int RulesSize = Rule::size>
>         struct algorithm_case_rule;
> 
>         template <typename Rule, typename Visitor>
>         struct algorithm_case_rule<Rule, Visitor, 1>
>             : proto::when<
>                   typename Rule::rule0
>                 , typename Visitor::template visit<typename Rule::rule0>
>               >
>         {};
> 
>         // add more ...
> 
>         template <typename Grammar, typename Visitor>
>         struct algorithm_case<Grammar, Visitor, typename Grammar::is_rule>
>             : algorithm_case_rule<Grammar, Visitor>
>         {};
> 
>         // algorithm is what 
>         template <typename Cases, typename Visitor>
>         struct algorithm
>             : proto::switch_<algorithm<Cases, Visitor> >
>         {
>             template <typename Tag>
>             struct case_
>                 : algorithm_case<
>                       typename Cases::template case_<Tag>
>                     , Visitor
>                   >
>             {};
>         };

Well that's pretty clever. I like the CRTP with switch_ and sticking the
cases right there. I almost looks like a regular switch statement. Why
didn't I think of that?

>         template <typename Grammar>
>         struct rule
>         {
>             typedef void is_rule;
> 
>             static int const size = 1;
>             typedef Grammar rule0;
>         };
> 
>         template <
>             typename Grammar0 = void
>           , typename Grammar1 = void
>           , typename Grammar2 = void
>           , typename Dummy = void>
>         struct rules;
> 
>         template <typename Grammar>
>         struct rules<Grammar>
>         {
>             typedef void is_rule;
> 
>             static int const size = 1;
>             typedef Grammar rule0;
>         };
> 
>          // add more ... 
>     }
> 
> Making your example:
> 
> // A collection of actions indexable by rules.
> struct MyActions
> {
>     template<typename Rule>
>     struct action;
> };
> 
> // An easier way to dispatch to a tag-specific sub-grammar
> template<typename Tag, typename Actions>
> struct MyCases
>   : proto::not< proto::_ >
> {};
> 
> struct MyCasesImpl
> {
>     template<typename Tag>
>     struct case_
>       : MyCases<Tag, Actions>
>     {};
> };
> 
> // Define an openly extensible grammar using switch_
> template<typename Actions = MyActions>
> struct MyGrammar
>   : detail::algorithm< MyCasesImpl, Actions>
> {};
> 
> // Define a grammar rule for int terminals
> struct IntTerminalRule
>   : proto::terminal<int>
> {};
> 
> // Define a grammar rule for char terminals
> struct CharTerminalRule
>   : proto::terminal<char>
> {};
> 
> // OK, handle the terminals we allow:
> template<>
> struct MyCases<proto::tag::terminal>
>   : proto::rules<
>         IntTerminalRule
>       , CharTerminalRule
>     >
> {};
> 
> // Now, populate the MyActions metafunction class
> // with the default actions:
> 
> template<>
> struct MyActions::action< IntTerminalRule >
>   : DoIntAction
> {};
> 
> template<>
> struct MyActions::action< CharTerminalRule >
>   : DoCharAction
> {};

It took a while, but I see what you're up to. You've pushed complexity
into the generic "algorithm" class. (Not the greatest name, but I can't
do better at the moment.) The benefit here is the cleaner separation
between rules and actions, and the nicer syntax for specifying the rules
associated with a tag. E.g.:

  rules<A,B,C>

where A, B, and C are simple Proto rules without semantic actions,
instead of:

  proto::or_<
      rules_with_actions<A, Actions>
    , rules_with_actions<B, Actions>
    , rules_with_actions<C, Actions>
  >

... which conflates grammar with actions in an unpleasant way. That's a
significant improvement. I ported my mini-Phoenix to use this, and I
like it. (See attached.)

Now the outstanding question is: does this control flow really mirror
the Visitor design pattern, and if so can we jigger this to more closely
match that pattern? If so, we could make this easier to use and understand.

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com