Variadic tuple<..> — imperative meta programming
Since my last two posts (here and here) are about how … might unpack and generate code if it were very smart, I thought I’d bring up a more difficult case. How do you build templated constructors inside the variadic template tuple class?
Remember, this is all fantasy code. The … operator will not actually be able to do any of this. Also remember this problem can be solved by defining tuple using a recursive first/rest typelist scheme (see the current Boost implementation).
At first glance it might appear that it’s easy to define a constructor. Just do this.
/* fantasy code -- will not work */
template< typename ... TYPEs >
class
tuple
{
// Member variables - not a legal use of ...
private:
TYPEs ...
values;
// Constructor
public:
tuple( TYPEs && ... args)
: values( std::forward( args)) ...
{ }
/* .. etc .. */
};
This is pretty good, but we’d like to make all the arguments optional. So we could do this.
/* fantasy code -- will not work */
template< typename ... TYPEs >
class
tuple
{
// Member variables
private:
TYPEs ...
values;
// Constructor
public:
tuple( TYPEs && ... args = TYPEs( ))
: values( std::forward( args)) ...
{ }
/* .. etc .. */
};
I think the double … expansion in the parameter list works. I’m pretty sure you only specify … immediately before the variable to be packed, and that all the already-packed variables in the expression will be unpacked at the same time. So you don’t specify … again after TYPEs( ).
In any case, this still needs improvement. This requires that all TYPEs have a copy constructor even if they are going to be default constructed. We really want a bunch of constructors, taking zero, one, two, etc arguments.
/* fantasy code -- will not work */
template< typename ... TYPEs >
class
tuple
{
// Member variables
private:
TYPEs ...
values;
// Generate a family of constructors (not legal C++).
// If TYPEs has three types <A, B, C> this
// generates four constructors:
// constructor( )
// constructor( A &&)
// constructor( A &&, B &&)
// constructor( A &&, B &&, C &&)
for... ( size_t
N = 0
; N <= sizeof...( TYPEs )
; ++ N )
{
public:
tuple( TYPEs && unpack...( N ) args)
: values( std::forward( args)) ...
{ }
}
/* .. etc .. */
};
Yikes, that’s not C++, and we’re not in Kansas anymore. In this fantasy code for… is a meta keyword, interpreted by the compiler and producing a series of constructors. And unpack…(N) only unpacks the first N items in the packed variable TYPEs, and not the entire list.
Instead of for… in the above example we could use plain old for and say the compiler should run code that is not in a code-defining context. But we’d still need to quote or emit the tokens inside the loop above. Something like this.
/* fantasy code -- will not work */
template< typename ... TYPEs >
class
tuple
{
/* .. etc .. */
for ( size_t
N = 0
; N <= sizeof...( TYPEs )
; ++ N )
{
emit {
public:
tuple( TYPEs && unpack...( N ) args)
: values( std::forward( args)) ...
{ }
}
}
/* .. etc .. */
};
This implementation is still incomplete however. The constructor methods themselves should be templated so you can construct tuples from values with convertible types. With that in mind, here is the last implementation.
/* fantasy code -- will not work */
template< typename ... TYPEs >
class
tuple
{
// Member variables
private:
TYPEs ...
values;
// Generate a family of constructors.
// If TYPEs has three types <A, B, C> this
// generates four constructors with compatible
// types:
// template< >
// constructor( )
// template< typename AC >
// constructor( AC &&)
// template< typename AC, typename BC >
// constructor( AC &&, BC &&)
// template< typename AC, typename BC, typename CC >
// constructor( AC &&, BC &&, CC &&)
for... ( size_t
N = 0
; N <= sizeof...( TYPEs )
; ++ N )
{
public:
template< typename generate...( N ) ARG_TYPEs >
tuple( ARG_TYPEs && ... args)
: values( std::forward( args)) ...
{ }
}
/* .. etc .. */
};
This introduces the fantasy generate...(N) meta function to generate a template parameter list of N typenames. This also unpacks values and args at the same time (and in parallel) even though values is packed from TYPEs while args is packed from ARG_TYPES. And args usually packs fewer names than values.
This kind of imperative code generation is sometimes easier to create and understand than the declarative templates C++ currently provides. But it also adds more syntax and keywords to C++, which is plenty complicated already. And a declarative solution that isn't as restrictive as C++ templates may be a better than this imperative suggestion. So I'm not advocating any of this stuff. I'm just thinking out loud, writing it down to see what it looks like.
Variadic tuple<..> — the get<N>() method
In my last post I talked about how a naive implementation of tuple might be easier to understand, and I showed how you might define the member values with the … operator, if only … were very smart about unpacking (which it isn’t).
The get<N>() method presents additional challenges.
/* fantasy code -- will not work */
template< typename ... TYPEs >
class
tuple
{
// Member variables
private:
TYPEs ...
values;
// Generalized get<N>( ) template method
private:
template< size_t >
void
get( ) const
{ BOOST_STATIC_ASSERT( false); }
// Specialized get<N>( ) methods:
// get<0>( ), get<1>( ), get<2>( ), etc
// Introduces indexof...(), which is like sizeof...()
public:
template< >
decltype( values ) &
get< indexof...( values ) >( )
{ return values ; }
...
// Specialized get<N>( ) const methods
public:
template< >
decltype( values ) const &
get< indexof...( values ) >( ) const
{ return values ; }
...
/* .. etc .. */
};
You can see how this would work if only … could unpack to create a bunch of method specializations. This also requires indexof…(values) which expands into 0, 1, 2, 3 and so on as it unpacks the member variables packed into values.
This would also have to work when a type was const or a reference. But that’s a topic for another day.
Variadic tuple<..> — clever vs obvious
I mentioned in my previous post how the tuple<..> template class will be defined with variadic template parameters in the future.
template< typename ... TYPEs > class tuple;
How do you define the body of a template like that? The implementation described in N2080 (see section A.1 on page 10) essentially defines tuple as a recursive series of base classes, where tuple<A,B,C> inherits from tuple<B,C> which in turn inherits from tuple<C>. In this implementation, tuple<A,B,C> only has to provide a member for type A, while tuple<B,C> provides the member for B and tuple<C> provides the member for type C.
// Based on implementation in N2080
template< typename ... TYPEs >
class
tuple;
// Specialization for empty tuple
template< >
class
tuple< >
{ };
// Specialization for non-empty tuples
template< typename Head, typename ... Tail >
class
tuple< Head, Tail ... >
: private tuple< Tail ... >
{ protected:
Head m_head;
/* .. etc .. */
};
This is truly a beautiful solution, elegant and clever. It’s too bad the types end up in reverse order, which will matter in C++0x when tuple becomes a POD type. The restrictions on POD are loosening in C++0x, partly to make them work with tuple.
The above implementation would mean you’d have to reverse the values in an initialization list.
// Reverse the values in the initialization list.
tuple< double, char > my_tuple = { 'A', 3.2345 };
Probably the nicest way to solve the reverse problem is to make Head variadic instead of Tail.
/* .. as above .. */
// Specialization for non-empty tuples
template< typename ... Head, typename Tail >
class
tuple< Head ..., Tail >
: private tuple< Head ... >
{ protected:
Tail m_tail;
/* .. etc .. */
};
I’m pretty sure that will work — I’ll check it when I get a compliant C++ compiler. This solution should be obvious, but people like me are used to thinking of a list as a single-link chain of cons cells, where car is Head and cdr is Tail. The pattern matching in Erlang also encourages <Head,Tail…> thinking instead of <Head…,Tail>.
The current Boost (1_37) implementation solves this problem by making the tail a member variable instead of a supertype. It’s a little more complicated than that — Boost cannot use variadic template params of course. And Boost uses the boost::tuples::details::cons struct to implement the recursive typelist. But it boils down to a head member var followed by tail.
Another possibility is to work from a reversed typelist.
# include <boost/mpl/assert.hpp> # include <boost/mpl/list.hpp> # include <boost/mpl/reverse.hpp> # include <boost/mpl/front.hpp> # include <boost/mpl/pop_front.hpp> # include <boost/type_traits/is_same.hpp> namespace mpl = boost::mpl; using boost::is_same; typedef mpl::list< int, float, double >::type typelist; typedef mpl::reverse< typelist >::type reversed_typelist; typedef mpl::front< reversed_typelist >::type head_reversed; typedef mpl::pop_front< reversed_typelist >::type tail_reversed; typedef mpl::front< tail_reversed >::type second_reversed; BOOST_MPL_ASSERT( (is_same< head_reversed, double >)); BOOST_MPL_ASSERT( (is_same< second_reversed, float >));
But at this point I have to confess that as much as I love clever recursive solutions, what I really want is a dumb iterating solution. After all, the … operator is an iterator of sorts. It expands a packed term into a sequence of resolved terms. I was naively hoping that something like this would work.
/* This is probably illegal */
template< typename ... TYPEs >
class
tuple
{
protected:
TYPEs ... values;
/* .. etc .. */
};
I just feel this is clearly expressed, even if it’s not flashingly brilliant.
But I’m pretty sure … only generates comma-separated lists. So it can be used in template and function parameter lists, and to generate a comma-separated list of expressions. But it won’t work in the situation above. Don’t quote me on this however — I haven’t messed with gcc4.3 in experimental C++0x mode yet.