Re: [Boost-users] Sequence of Types, What For?

From: David Abrahams (dave_at_[hidden])
Date: 2006-11-07 17:07:34

"Terry G" <tjgolubi_at_[hidden]> writes:

>>> I've just finished reading C++ Template Metaprogramming again.
>>> I just don't get it.
>>>
>>> Why would someone use a type container?
>>>
>>> I have used enable_if, along with some of the logic functions for 
>>> managing
>>> an overload set.
>>> Otherwise, I'm clueless.
>>>
>>> I'd really like a reference to an MPL primer or some case studies.
>>
>> The book contains a case study in which type sequences are used to
>> describe the rows of a state machine's transition table.  Was that not
>> a sufficient motivating case?
>
> FSMs are not something I'm familiar with. I didn't really notice the vector 
> of rows until recently.
> How is the FSM approach in your book better than arrays of structs?

Containing what?

> I didn't see any advantage, and the supporting code is too complex.

It's actually quite simple (just a few pages long).  If you have to
write lots of FSMs, a little bit of complexity in a framework pays off
as long as the framework makes defining FSMs very simple and
understandable, as ours does.

You have to separate the supporting code from the usage code.  You'd
never use TMP if you only needed to produce a single FSM.  As the book
points out in the first chapter, template metaprogramming is primarily
for library writers targeting a particular problem domain (in this
case, FSMs): it can allow their users to write maximally efficient,
declarative code that expresses their intention in terms of the
domain's own abstractions (in this case, state transition tables).

> There must be an advantage, otherwise, why would you work so hard to
> write these things?

As the book points out, the FSMs generated by the framework as shown
have efficiency comparable to that of handwritten FSMs that use case
statements, and the declaration of the FSM resembles what one might
write down when designing the state machine on a blackboard.

> I'll try to implement a reusable FSM framework, without MPL.
> Then, perhaps, advantages/disadvantages of MPL would be more
> apparent to me.

Perhaps.

> Is there a good way to post hundreds of SLOCs for discussion?  I
> don't have a website.

You could use the Boost vault, I suppose.

> BTW, on the boost website, there are three versions of the FSM player 
> example.

Where?

> A ReadMe.txt to explain the differences would be helpful.
>
>>> Too much pain with very little gain.
>>
>> What, specifically, do you find painful?
>
> Well, you asked...
> I write stuff that I think should work, but the compiler issues tons of 
> error messages.

Did you read the chapter on diagnostics and apply the advice therein?

> Pitfalls like when to use typename.

Did you read the appendix on the typename and template keywords?

> Brain cramps trying to comprehend the compile-time/run-time boundary.
> Recently, I tried to avoid using a large 150-case switch statement using 
> metaprogramming.
> Each MessageNN has a unique static const int TAG member.  They all derive 
> from a common Message base class that has the common message header, 
> including the tag.
> The only thing each case did was something like.
>     switch (msg.tag()) {
>        case Message26::TAG:
>          cout << static_cast<const Message26&>(msg) << endl;
>          break;
>        case Message27::TAG:
>           cout << static_cast<const Message27&>(msg) << endl;
>           break;
>        ...
>     }
> That is, upcast a received message (over a wire) and print it.  

Looks like a good candidate for TMP.

> Virtual 
> functions cannot be used because the message can have no vtbl.
> I eventually just did the big switch like I have for twenty years.
> The pain (frustration) comes from believing there's a "better" way, but not 
> knowing how to realize it.

The FSM example shows the basic technique for "generating a switch"
with TMP... although in this particular case you *might* have been
better off using the preprocessor library (also covered in the book).

> Pain, too, because without a mentor to guide me, I feel like I'm walking 
> around trying to drive in screws with my shiny new hammer.
> Painful because after you get a nifty mpl::vector of MessageTypes, you 
> realize after the 50th message, that it won't scale up to 150.
> Painful because compile times take much longer.  (VC8 takes a lot longer, 
> not sure why).
> Painful because I don't understand the runtime and memory trade-offs 
> anymore.
>
> i.e. painful because it makes me realize how stupid I still am, in spite of 
> all my past successes.  Printf and void* have served me well.

I feel your pain.

>>> Time to ask for help.
>>> Rereading this, it sounds negative.
>>> Really, I think the MPL is really cool!
>>
>> Cool, how can we help?
>
> Do know how to do a mind-meld?  (Spock recoiled, his face white with shock. 
> He had never experienced such chaos before.)
> I need to be patient and ask one question at a time. There is a lot of 
> really difficult material packed into a deceptively slim book.
>
> So, back to that switch statement... is there a better way?

As in the FSM example:

1. Decompose the cases of the switch into separate functions,
something like:

      template <class DerivedMsg, class NextCase>
      struct case_
      {
          static void execute(BaseMsg const& msg)
          {
              if (msg.tag == DerivedMsg::TAG)
                  cout << static_cast<DerivedMsg const&>(msg) << endl;
              else
                  NextCase::execute(msg);
          }
      }

      struct DefaultCase
      {
          static void execute(BaseMsg const& msg)
          { ... }
      };

2. Now use MPL to generate a type like:

   typedef 
     case_<Message0, case_<Message1, case_<Message2, DefaultCase> > > 
   switch_;

   you can do that with the "fold" algorithm over your sequence of
   derived Message types.

3. then invoke switch_(msg)

> BTW, how do compilers handle big switches? How do they find the matching 
> case?

It depends on the compiler and the distribution of values.  If it's
fairly dense they may just do array lookup in a jump table.  Otherwise
they may use perfect hashing.  Otherwise it may just be a chain of
ifs.  If you want the optimizations that come from the first two
schemes, you're better off generating an actual case statement with
the preprocessor library, if possible.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com