[Home]Effective MPL

BOOST WIKI | RecentChanges | Preferences | Page List | Links List

Difference (from prior major revision) (minor diff, author diff)
No diff available.

Effective MPL

Jaap Suter, July 22, 2004: This document is out of date and not compatible with the most recent version of the MPL. However, it still makes for an interesting read, so I'll leave it around.

Contributions by: Jaap Suter, Dave Abrahams, Terje Slettebo, Aleksey Gurtovoy, Dirk Gerrits

Errors by: Jaap Suter (so if you find one, blame me at J_Suter-at-telus.net (where -at- equals @) or correct it in the wiki.

All of the example code assumes we are in the ::boost::mpl namespace.

1. Introduction

More information on the MPL can be found at http://www.mywikinet.com/mpl/.

2. Containers

No items yet

3. Meta functions

3.1 Save yourself the typename keyword

To reduce the notational overhead imposed by the specifics of the compile-time domain, many of MPL metafunctions, when fully-curried (provided with all arguments), directly support the interface of the Integral Constant concept:

   // OK, ordinary function invocation
   BOOST_STATIC_ASSERT(not_equal_to< int_c<5>, int_c<0> >::type::value); 

   // also OK!
   BOOST_STATIC_ASSERT(not_equal_to< int_c<5>, int_c<0> >::value); 

This property often allows you to simplify your compile-time conditions:

	apply_if< typename equal_to<N, integral_c<N::value_type, 0> >::type, ...

can be written as:

	apply_if< equal_to<N, integral_c<N::value_type, 0> >, ...

In other words, many of the MPL meta functions provide a ::value member so they can be used as instances of integral_c<>.

3.2 Use inheritance to forward metafunction results

Instead of writing the following:

	template < class T, class P, class Q >
	struct foo
	{
		typedef typename apply_f< T, P, Q >::type type;
	};

You can use inheritance and write it as follows:

	template < class T, class P, class Q >
	struct foo : public apply_f< T, P, Q > {};

4. Iterators

No items yet.

5. Algorithms

Item 5.1, Prefer the standard algorithms to hand written ones

Before you start writing your own algorithms, make sure if the MPL does not already provide one for you. In most cases, the iter_fold algorithm is a very powerful one, and chances are that you can easily implement your own algorithm using iter_fold.

The MPL authors have gone through great length to spare you the troubles of compiler-madness. They provide compiler-workarounds for many compilers meaning that using the standard algorithms will improve the portability of your code.

Programming with the MPL

Item 5.2, Use default template parameters as starting values

Consider the following code that calculates the number of bits equal to one in a given number:

 template < class N >
 struct num_bits_set
 {
      template< class N, class Result >
      struct num_bits_set_impl
      {
           typedef typename apply_if_< equal_to< N, integral_c< typename N::value_type, 0 > >,
                                       Result,
                                       typename num_bits_set_impl< mpl::bitand_< N, typename N::prior >, typename Result::next >::type
                                      >::type type;
      };

      typedef typename num_bits_set_impl< N, integral_c< N::value_type, 0 > >::type type;
  };

For such a simple function, no nested class is neccesary. Instead, write it as follows:

 template < class N, class Result = integral_c< size_t, 0 > >
 struct num_bits_set
 {
      typedef typename apply_if< equal_to< N, integral_c< typename N::value_type, 0 > >,
                                      Result,
                                      typename num_bits_set_impl< mpl::bitand_< N, typename N::prior >, typename Result::next >::type                                    
                               >::type type;
 };

Add a comment to alert the client code they should not touch the default parameter, and you end up with a much simpler meta-function. If you think that hiding an implementation detail in the parameter list is a bad programming practice, remember that we have no choice in many cases. Compiler resources are too scarse so we can't complicate our meta-programming only to achieve better software engineering practices. If more people learn about this idiom, the more accepted it will become. Just remember to add that -don't touch the default parameters- for client code, and all is well.

Item 5.3, Wrap integral constants in types

Consider the following meta-function:

  template< int N >
  struct square
  {
      BOOST_STATIC_CONSTANT( int, value = N * N );  
  };

According to item 5.5, this function shouldn't be written at all since you should use the meta-functions provided with the MPL, but for now let us assume we need the above. Now somebody comes in and needs to square two unsigned integers. What you end up with is a second meta-function for unsigned integers.

Wrong. Just as in regular programming, code duplication is bad in meta-programming. Therefore, you should abstract over the specific type, and write the function as follows:

  template< class N >
  struct square
  {
      typedef integral_c< typename N::value_type, N::value * N::value > type;
  };

And now you can use it as follows:

   square< int_c< 3 > >::type::value;
   square< integral_c< unsigned int, 3 > >::type::value;

See, only one definition and it works for both integers, unsigned integers, and any other that models the number concept (basically providing a value_type member-type, a value member-constant and a bunch of other things).

However, we did complicate the client code. Whereas before we could simply type

   square< 3 >::value

we now need to do:

   square< int_c< 3 > >::type::value;

all to avoid code duplication and achieve genericity. Well, that is not the only advantage. Item 5.4 and 5.5 combined provide another rationale for avoiding direct constants, and prefering constants wrapped in types. All the MPL meta functions work on constants wrapped in types as well, so you better get used to it.

If you use this style of programming for a while you will notice you need the integral constants as template parameters less and less. At some point, most of your code will constantly pass integral_c or likewise types around, and you will hardly ever touch the integral_c<>::value members just because you don't need to.

And in those rare cases where you want to spare your client code from having to use integral_c, you can always provide wrappers:

  template< int N >
  struct square_c     // Needs a different name because overloaded templates don't exist (yet)
  {
     BOOST_STATIC_CONSTANT( int, value = square< int_c< N > >::type::value );
  };

Item 5.4, Beware of using expressions containing operators as template parameters

Ignoring the fact that the following example is completely useless, if you would try to compile this:

  template< int N >
  struct foo
  {
    typedef typename apply_if< bool_c< N == 0 >, 
                      integral_c< int, 0 >
                      foo< N - 1 >, 
                    >::type type;
  };

you will notice that some compilers choke on the line with N == 0 and the line N - 1. This is because they can't deal with operators (or any complicated expressions for that matter) used in template arguments. The biggest problems exist if you use > (greater than), < (less than), >> (right shift), and << (left shift). Code using those operators, perfectly acceptable according to the standard, will not compile on some compilers. Note, this is not just a problem with the MPL, but just a problem in general. More information can be found in the Coding Guidelines for Integral Constant Expressions document by Dr. John Maddock, which can be found on http://www.boost.org/more/int_const_guidelines.htm. That document explicitly mentions this problem under the Don't use any operators in an integral constant expression used as a non-type template parameter item. It also explains why you should use BOOST_STATIC_CONSTANT for constants as class members.

Using the knowledge from that document, the recommended option is to rewrite it as follows:

  template< int N >
  struct foo
  {
    BOOST_STATIC_CONSTANT( bool, equals_zero = (N == 0) ); 
    BOOST_STATIC_CONSTANT( int,  previous    = (N - 1)  );

    typedef typename apply_if< bool_c< equals_zero >, 
                      int_c< 0 >
                      foo< previous >, 
                    >::type type;
  };

And now it will in fact compile. Yet, there is an even better solution to the above described in item 5.5.

Item 5.5, Use the MPL meta-functions instead of built-in operators

Remember the code from item 5.4, which looked as follows:

  template< int N >
  struct foo
  {
    BOOST_STATIC_CONSTANT( bool, equals_zero = (N == 0) ); 
    BOOST_STATIC_CONSTANT( int,  previous    = (N - 1)  );

    typedef typename apply_if< bool_c< equals_zero >, 
                      foo< previous >, 
                      int_c< 0 >
                    >::type type;
  };

Instead of explicitly declaring those constants, we should use the meta-functions that MPL provides:

  template< int N >
  struct foo
  {
    typedef typename apply_if< equal_to< int_c< N >, int_c< 0 > >,
                      foo< typename minus< int_c< N >, int_c< 1 > >::type >, 
                      integral_c< int, 0 >
                    >::type type;
  };

Depending on your taste this may or may not be an improvement. However, remembering item 3 (wrap constanst in types) we should rewrite this as follows:

  template< class N >
  struct foo
  {
    typedef typename apply_if< equal_to< N, integral_c< typename N::value_type, 0 > >,
                      foo< typename minus< N, integral_c< typename N::value_type, 1 > >::type >, 
                      integral_c< typename N::value_type, 0 >
                    >::type type;
  };

And last of all, we recognize that types that model integral_c provide a prior and next members. This leads to the final definition of (our useless) foo:

  template< class N >
  struct foo
  {
    typedef typename apply_if< equal_to< N, integral_c< typename N::value_type, 0 > >,
                      foo< typename N::prior >, 
                      integral_c< typename N::value_type, 0 >
                    >::type type;
  };

We could replace the compare to zero with the MPL not meta function, but even without that the above code remains the most portable, most generic definition.

Item 5.6, Beware of the 'early template instantiation' trap

Some compilers (MSVC-7.0 in my experience) have some difficulties with templates that rely on each other recursively. Consider the following, rather contrived and useless, code:

 template < class A >
 struct outer
 {
     template < class B >
     struct inner
     {
         typedef integral_c< int, B::value > C;
         typedef typename equal_to< C, typename outer< B >::type >::type type;
     };

     typedef typename inner< A >::type type;
 };

Even without a template instantiation (so this is during the definition-parse), this gives the following errors on MSVC-7.0:

  ...\boost\mpl\comparison\equal_to.hpp(36) : error C2275: 'value' : illegal use of this type as an expression
  ...\boost\mpl\comparison\equal_to.hpp(36) : error C2056: illegal expression

Obviously there are no errors in the MPL headers. Instead, the problem is in MSVC. It is called 'early template instantiation' (ETI) and to quote Aleksey Gurtovoy (one of the MPL authors):

''Basically, the source of the problem here is that 'outer' and its nested 'inner' template depend on each other recursively; that, of course, is a perfectly well-formed C++, but such recursive dependence means, in particular, that when parsing the 'inner' template the compiler haven't seen the full definition for the 'outer' itself yet, and sometimes this interacts badly with MSVC's so-called "early template instantiation" bug (you can search the list archive to find out more about that one).''

Notice the word sometimes. In fact, the above example was rather complicated to get together. Anything smaller and it would compile without problems. For example, if I replace the int type with B::value_type (making C the exact same type as B) everything compiles fine. If I pass B directly to the resulting type of inner everything works fine. Rather unpredictable behaviour, and hard to diagnose without experience (in fact, I still don't quite understand the exact conditions under which it happens).

The work-around is as follows (requires the latest MPL sources from CVS):

 #include "boost/mpl/aux_/msvc_never_true.hpp"
 #include "boost/detail/workaround.hpp"

 template < class A >
 struct outer
 {
     template < class B >
     struct inner
     {
         typedef integral_c< int, B::value > C;

         #if BOOST_WORKAROUND(BOOST_MSVC, == 1300)
             typedef typename if_< aux::msvc_never_true< B >,
                                   integral_c< int, 0 >,
                                   typename outer< B >::type
                                 >::type recurse;
         #else
             typedef typename outer< B >::type recurse;
         #endif           

         typedef typename equal_to< C, recurse >::type type;
     };

     typedef typename inner< A >::type type;
 };

This has in fact been tested and it compiles correctly. The MSVC case of the #if statement uses a compile time if_ statement that always compiles to the else part. For some reason this tricks MSVC into compiling this code. The aux::msvc_never_true template just takes any random parameter to make it into a template, but that parameter is never used. Like-wise, the first clause of the if-statement can be anything since it is never used. Hence, we simply used zero above.

Question for Alexsey or Dave: Why not give the aux::msvc_never_true a default parameter defaulting to integral_c< int, 0 > or whatever? Question for Alexsey or Dave: I'm not entirely sure why this tricks MSVC into compiling it. Any details?

Allow me summarize the above.

Problem:

Symptoms: Solution:

Item 5.7, Help your compiler if your own meta-functions need to support lambdas

Not all compilers are able to deal with MPL's lambda facilities in straightforward ways. So if you want to use your own meta functions in lambda expressions, you have to help out a bit.

Item 5.8, Know your compiler limits

Todo, explain some common compiler limits (the number 17, the /Zm? option in MSVC, etc.)

Item 5.9, Unroll loops to relieve your compiler

See http://www.mywikinet.com/mpl/paper/mpl_paper.html#sequences.unrolling and

Item 5.11, Use the established naming conventions

Todo, explain that people should use 'type' and 'value' so everybody knows what to look for in a meta-function or algorithm.

Item 5.12, Avoid direct instantations of meta-function results

Sometimes you need to instantiate the result of a meta-function, for example when doing runtime code selection based on a meta function result:

 void foo( bool_c< true > );		// foo #1
 void foo( bool_c< false > );		// foo #2

 foo( bool_c< true >() ); // Calls foo #1;

Here we explicitly instantiated bool_c<> directly to decide on a certain function. However, more often the bool_c<> will be the result from a complicated meta-function, for example:

 template < class T >
 void bar()
 {
     foo( greater_than< plus< T, int_c< 3 > >, int_c< 3 > >::type() );
 }

This is legal C++, but not all compilers can deal with this. One compiler will, for some odd reason, complain about unexpected commas in more complicated situations. The solution is easy. Just calculate the meta-function result first, and then instantiate it, as follows:

 template < class T >
 void bar()
 {
     typedef typename greater_then< plus< T, int_c< 3 > >, int_c< 3 > >::type type;
     foo( type() );
 }

Item 5.13, Inner template classes may confuse compilers

Sometimes a meta function may use a helper meta function, for example in the following:

	template < class List, class T >
	class meta_fun
	{
	    template < class A, class B >
	    class helper
	    {
		typedef A type;
            };
	public:	
	    typedef typename mpl::fold< List, 
		   	   	        T, 
					helper< mpl::_1, mpl::_2 >
				      >::type type;
	};

Obviously, the helper function would do something more complicated, and you would use the lambda support macros for MSVC (Item 5.7), but this is just to illustrate the example. The problem is that some compilers cannot deal with the above. The errors can be very obscure, and don't seem to point to any related problem at all. However, the solution is easy:

	template < class A, class B >
	class helper
	{
		typedef A type;
	};

	template < class List, class T >
	class meta_fun
	{
		typedef typename mpl::fold< List, 
			 	    	    T, 
					    helper< mpl::_1, mpl::_2 >
					  >::type type;
	};

And now compiles fine. Of course, the above exposes an implementation detail, therefore the inner-class solution is preferred. However, if you get weird errors on some compilers, and all else fails, try the above. If it fixes the problem, you could use an extra namespace ('impl' or 'detail') to put the helper function in.


BOOST WIKI | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited July 28, 2008 3:29 am (diff)
Search:
Disclaimer: This site not officially maintained by Boost Developers