Template programming with MPL — XOR example
The Boost extension libraries are a treasure trove of brilliant hackery. The template usage and metaprogramming throughout the libraries is particularly interesting. But it’s also confusing, especially when you first see it. The C++ template language is like a functional language with limited types and obtuse syntax. It has no loops and allows no side effects (no changes to objects or variables after construction). It uses the constructs of C++ in unexpected ways and is very different from normal C++ programming.
The best way to get an idea of how template programming works is to look at it. So here are some examples of how to implement a very simple template function, an XOR predicate that takes two boolean arguments and returns a third.
As a base we start with the templates in type_traits which are included in TR1. We will also use the Boost MPL library, which provides predicates like and_<..>, or_<..>, and not_<..>. MPL also provides the boolean template class bool_<..> and it’s two type-values true_ and false_.
# include <boost/type_traits.hpp> using boost::is_same; // is_same< A, B > is a template function // that compares types A and B. # include <boost/mpl/logical.hpp> using boost::mpl::bool_; using boost::mpl::true_; using boost::mpl::false_; using boost::mpl::and_; using boost::mpl::or_; using boost::mpl::not_; # include <boost/mpl/assert.hpp> // BOOST_MPL_ASSERT(..) and // BOOST_MPL_ASSERT_NOT(..)
In template programming, you assign variable values with typedef. true_ and false_ are variables that evaluate to bool<true> and bool<false>. You can assign them over and over again as long as the value does not change. Typedef variables never change once they are assigned, so they’re not really “variable”. They are constant variables (which sounds like an oxymoron). There is no untypedef.
// true_ is already assigned, but you can // assign it over and over again to an // identical value. typedef bool_<true> true_; typedef bool_<true> true_; typedef bool_<true> true_; // not_<false_> is the same as true_. typedef not_<false_>::type true_;
You can use is_same< A, B > to test if two types are the same. Boost MPL provides a useful ASSERT.
BOOST_MPL_ASSERT( (is_same< true_, true_ >)); BOOST_MPL_ASSERT_NOT( (is_same< true_, false_ >)); BOOST_MPL_ASSERT( (is_same< true_, bool_<true> >));
true_ and false_ are self evaluating. You evaluate an expression or a variable by appending ::type.
// true_, false_, bool_<true>, etc are self evaluating. BOOST_MPL_ASSERT( (is_same< true_, true_::type >)); BOOST_MPL_ASSERT( (is_same< true_, true_::type::type >)); // not_<false_> is an expression. // Tt only yields _true after you evaluate it. BOOST_MPL_ASSERT_NOT( (is_same< true_, not_<false_> >)); BOOST_MPL_ASSERT( (is_same< true_, not_<false_>::type >)); BOOST_MPL_ASSERT( (is_same< true_, or_<true_>::type >));
You may have noticed BOOST_MPL_ASSERT( (..)) has double parentheses around its argument. This is needed because the argument is usually an expression containing commas, and the preprocessor will mis-interpret the commas unless they are buried in parentheses.
You might be tempted by the following macros. But they only work with type expressions that contain no commas.
# define ASSERT_same_types( A, B) \
BOOST_MPL_ASSERT( (is_same< B , A >))
# define ASSERT_different_types( A, B) \
BOOST_MPL_ASSERT_NOT( (is_same< B , A >))
ASSERT_same_types( int, int);
ASSERT_different_types( char, int);
ASSERT_same_types( void(*)(int), void(*)(int) );
ASSERT_different_types( false_, true_::type::type);
// These do not work because of the commas!
// Putting parens around the args doesn't work either.
/*
ASSERT_same_types( true_, and_<true_,true_>::type >));
ASSERT_same_types( int(int,char), int(int,char) >));
ASSERT_same_types( (int(int,char)), (int(int,char)) >));
*/
Notice that and_<..> evaluates its arguments while is_same<..> does not. (This is not strictly true since and_<..> short circuits, but in these examples we can treat it like it evaluates all its args.)
// is_same<..> does not eval its args. Otherwise // you could not use it with types like int. BOOST_MPL_ASSERT( (is_same< int, int >)); // These look the same, but they're not because args // are not evaluated. BOOST_MPL_ASSERT_NOT( (is_same< true_, not_<false_> >)); // You can force evaluation. Only the second arg needs // to be eval'ed in this case. BOOST_MPL_ASSERT( (is_same< true_, not_<false_>::type >)); // Here we force eval of the outer not_<..> because it is an // arg to is_same<..>. But the args to and_<..>, or_<..>, // and not_<..> are automatically evaluated. BOOST_MPL_ASSERT( (is_same< true_, not_<or_<and_<not_<false_>>>>::type >)); // You can force evaluation of args to and_<..> etc, but // the results will just be eval'ed again. Since the // results are self evaluating (true_ or false_), you can // redundantly evaluate them several times and the // expressions will still work. BOOST_MPL_ASSERT( (is_same< true_, not_<or_<and_<not_<false_>::type>::type::type>>::type >));
Now we can finally get to our example template predicate. Here is a definition of xor_test<..> that evals its args. It can be used with MPL functions like and_<..> and or_<..>.
template< typename A, typename B >
struct xor_test
: bool_< A::type::value ^ B::type::value >
{ };
BOOST_MPL_ASSERT_NOT( (xor_test< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_test< false_, false_ >));
BOOST_MPL_ASSERT( (xor_test< true_, false_ >));
BOOST_MPL_ASSERT( (xor_test< false_, true_ >));
BOOST_MPL_ASSERT( (xor_test< false_, or_<true_> >));
I don’t like using the bitwise XOR operator ^ here with boolean args, although it works. I’d prefer to use a boolean operator like ^^ if it existed. Also, I considered replacing : bool< A::type::value ^ B::type::value > with : bool< A::value ^ B::value > because X::value also evaluates X. It works with and_<..>, or_<..> and not_<..> because these classes mimic bool_<..> and provide value as well as type.
When you define an MPL-style template function, you need a typedef XX type; in the template struct to evaluate the template expression. You get that if you inherit from bool_<..>, or you can typedef XX type; yourself.
You also need to figure out if the predicate should evaluate true_ or false_. You can specify that with logic or with template specialization.
The first XOR predicate example inherits from bool_<..> and calculates true/false with and_<..>, or_<..>, and not_<..>.
// xor_1<..> inherits from bool_<..>
template< typename A, typename B >
struct xor_1
: or_< and_< A, not_< B > >, and_< not_< A >, B > >::type
{ };
BOOST_MPL_ASSERT_NOT( (xor_1< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_1< false_, false_ >));
BOOST_MPL_ASSERT( (xor_1< true_, false_ >));
BOOST_MPL_ASSERT( (xor_1< false_, true_ >));
BOOST_MPL_ASSERT( (xor_1< false_, or_<true_> >));
BOOST_MPL_ASSERT( (xor_1< or_<true_>, false_ >));
You don’t have to evaluate the supertype of xor_1<..>. You could say or_<..> instead of or_<..>::type. This stops evaluation of the top-level or_<..>, and it means we are not inheriting directly from bool_<..> but rather from or_<..>. But we still evaluate to a bool_<..> type.
The second XOR example typedefs type explicitly. It also typedefs value_type and tag and defines value and operator bool() (the same as operator value_type()). These make it look more like bool_<..> and work better with MPL.
// xor_2<..> typedefs type instead of inheriting
template< typename A, typename B >
struct xor_2
{
typedef
or_< and_< A, not_< B > >, and_< not_< A >, B > >
type;
typedef bool value_type;
static const value_type value = type::value;
operator value_type() { return value; }
typedef bool_<value> tag;
};
BOOST_MPL_ASSERT_NOT( (xor_2< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_2< false_, false_ >));
BOOST_MPL_ASSERT( (xor_2< true_, false_ >));
BOOST_MPL_ASSERT( (xor_2< false_, true_ >));
BOOST_MPL_ASSERT( (xor_2< false_, or_<true_> >));
BOOST_MPL_ASSERT( (xor_2< or_<true_>, false_ >));
The third example inherits from either true_ or false_ and uses specialization to choose which. Template specialization tends to leave parameters un-evaluated. We wrap the non-evalating base class so we can evaluate explicitly.
// specialization and inheritance
template< typename A, typename B >
struct xor_3_no_eval
: false_
{ };
template< >
struct xor_3_no_eval< true_, false_ >
: true_
{ };
template< >
struct xor_3_no_eval< false_, true_ >
: true_
{ };
template< typename A, typename B >
struct xor_3
: xor_3_no_eval< typename A::type, typename B::type >::type
{ };
BOOST_MPL_ASSERT_NOT( (xor_3< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_3< false_, false_ >));
BOOST_MPL_ASSERT( (xor_3< true_, false_ >));
BOOST_MPL_ASSERT( (xor_3< false_, true_ >));
BOOST_MPL_ASSERT( (xor_3< false_, or_<true_> >));
BOOST_MPL_ASSERT( (xor_3< or_<true_>, false_ >));
The last example predicate typedefs explicitly instead of inheriting from bool_<..>. It also uses a recursive type definition.
// specialization and calculation
template< typename A, typename B >
struct xor_4_no_evalB
{
// We only ever get here if B evals to something
// other than true_ or false_. Maybe we should
// flag this:
// BOOST_STATIC_ASSERT( false);
typedef false_ type;
};
template< typename A >
struct xor_4_no_evalB< A, false_ >
{
// recursive type definition uses xor_4_no_evalB<..>
typedef
typename xor_4_no_evalB< not_< A >, true_ >::type
type;
};
template< typename A >
struct xor_4_no_evalB< A, true_ >
{
typedef
typename not_< A >::type
type;
};
template< typename A, typename B >
struct xor_4
: xor_4_no_evalB< A, typename B::type >::type
{
typedef bool value_type;
static const value_type value = type::value;
operator value_type() { return value; }
typedef bool_< value > tag;
};
BOOST_MPL_ASSERT_NOT( (xor_4< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_4< false_, false_ >));
BOOST_MPL_ASSERT( (xor_4< true_, false_ >));
BOOST_MPL_ASSERT( (xor_4< false_, true_ >));
BOOST_MPL_ASSERT( (xor_4< false_, or_<true_> >));
BOOST_MPL_ASSERT( (xor_4< or_<true_>, false_ >));
So there you have it — five examples of a very simple template XOR predicate.