for rookie C++ (template) programmers

[vijayan121]

there seems to be nothing much happening in the c++ forum today. so here is something to chew on for programmers who are relatively new to templates: c++ can also be used as a metalanguage.

#include <iostream>
using namespace std ;

// compile-time computation of fibonacci numbers
template < int N > struct fibonacci
{
   char error_negetive_N[ N + 1 ] ; // c++0x => use static_assert
   enum { value = fibonacci<N-1>::value + fibonacci<N-2>::value } ;
   char error_integer_overflow[ value ] ; // c++0x => use static_assert
};
template<> struct fibonacci<0> { enum { value = 0 } ; } ;
template<> struct fibonacci<1> { enum { value = 1 } ; } ;

// compile-time if statement
template<bool> struct _if { static inline void new_line() {} };
template<> struct _if<true> 
{ static inline void new_line() { cout << '\n' ; } };

// compile-time for loop
template< int N, int MAX, size_t N_PER_LINE > struct _for
{
  static inline void print_fibonacci_number()
  {
      cout << fibonacci<N>::value << '\t' ;
      _if< N%N_PER_LINE == (N_PER_LINE-1) >::new_line() ;
      _for< N+1, MAX, N_PER_LINE >::print_fibonacci_number() ;
  }
};
template< int MAX, size_t N_PER_LINE > struct _for<MAX,MAX,N_PER_LINE>
{
   static inline void print_fibonacci_number()
   { _if< MAX%N_PER_LINE >::new_line() ; }
} ;

int main()
{
   enum { FROM = 0, TILL = 32, LINE_SZ = 8 } ;
   _for< FROM, TILL, LINE_SZ >::print_fibonacci_number() ;
}
// to see generated assembly along with c++ source code (gcc):
// c++ -c -g -Wa,-a,-ad -Wall -std=c++98 -O3 fib.cpp > fib.asm
/**
>c++ -Wall -std=c++98 fib.cpp && ./a.out
0       1       1       2       3       5       8       13
21      34      55      89      144     233     377     610
987     1597    2584    4181    6765    10946   17711   28657
46368   75025   121393  196418  317811  514229  832040  1346269
*/
// for a discussion/elaboration of the technique, see
// http://ubiety.uwaterloo.ca/~tveldhui/papers/Template-Metaprograms/meta-art.html

[Dave Sinkula]

Further information for those playing along at home:
http://en.wikipedia.org/wiki/Template_metaprogramming

[edit]Oops. Missed the link at the bottom of the code.

[Hamrick]

That's a little much for me, thanks. ;) Template metaprogramming looks cool, but is it really practical?

[vijayan121]

>> looks cool, but is it really practical?

you have already seen one practical use for it; perhaps you have forgotten about it. see thread http://www.daniweb.com/forums/thread82213.html posts #7 and #10 where a trivial metafunction (rebind) was used to solve a genuine programming problem.

though the idea of using c++ as a metalanguage is faily old (see http://ubiety.uwaterloo.ca/~tveldhui/papers/Template-Metaprograms/meta-art.html - originally published in1994) and there has been high excitement among C++ experts about these capabilities of the language, it is true enough that it has not reached the c++ community at large.

here are some references to help you get started
http://safari.oreilly.com/0201704315
http://safari.oreilly.com/0321227255
http://en.wikipedia.org/wiki/Loki_(C++)
http://en.wikipedia.org/wiki/Boost_C++_Libraries
http://www.oonumerics.org/blitz/whatis.html
and something that (astonishingly; this certainly is not comp.lang.c++.moderated) turned up in daniweb yesterday): http://www.daniweb.com/forums/thread88328.html

[Hamrick]

I appreciate your useful help and links, but I don't think I'm smart enough to understand template metaprogramming. Even the simple rebind you showed me before doesn't make any sense...

[Bench]

I appreciate your useful help and links, but I don't think I'm smart enough to understand template metaprogramming. Even the simple rebind you showed me before doesn't make any sense...

its a rather elaborate complicated example of template metaprogramming for a newbie IMHO. Try this as a simpler one :)

template<int N>
struct factorial
{
    enum { value = N * factorial<N-1>::value };
};

template<>
struct factorial<1>
{
    enum { value = 1 };
};

#include <iostream>
int main ()
{
    std::cout << factorial<6>::value << std::endl;
}

[Hamrick]

its a rather elaborate complicated example of template metaprogramming for a newbie IMHO. Try this as a simpler one

That's the one that made me wonder if it was practical. All of the examples that look useful to me are too complicated to understand. All of the examples I can grok are kind of pointless. In the factorial one, you have to give the template a literal. If you know the literal you want, why not just use the factorial answer as a literal instead of some convoluted scheme of finding it at compile time with templates?

I just don't get it. :(

[vijayan121]

>> ...I don't think I'm smart enough to understand template metaprogramming....

it is not as difficult as you make it out to be. strange? yes, initially. hard to understand? not really. a lisper would feel quite at home with this kind of programming. and it would look somewhat eerie to someone with only a c (read classical c++, C#, java) background

>> ...made me wonder if it was practical. All of the examples that look useful to me are too complicated to understand. All of the examples I can grok are kind of pointless

ok, let us try again. here is a useful example. we want to write a (generic, meta) function which copies one sequence to another like std::copy. however, if the source and destination sequences are c-style arrays which can be correctly copied using a memcpy, we want to call memcpy. otherwise, we would iterate and copy element by element. compilers (icc, vc++ 7 or later, gcc 4.1 or later) recognize a call to memcpy and can generate mmx/sse instructions for a fast block copy; we do not want to lose this advantage. but we do not want to break our code if the implementation of the sequence we are copying is modified at some time in the future. we just recompile, safe in the knowledge that our metaprogram will generate either a call to memcpy or do an element by element copy depending on what we are copying.
the code is fairly elaborately annotated; should not be too difficult to follow (unless you start with the assumption that it is going to be intractable).

#include <cstring>
#include <list>
#include <iostream>
using namespace std ;

// is_pointer<T>::result == 1(true) if T is a pointer, 0 otherwise
// is_pointer<T>::pointed_type == type pointed to 
struct nothing {};
template< typename T > struct is_pointer
{
  enum { result = 0 };
  typedef nothing pointed_type ;
};
template< typename T > struct is_pointer<T*> // spec. for pointers
{
  enum { result = 1 };
  typedef T pointed_type ;
};

// has_trivial_copy<T>::result == 1 if type T has a trivial
// bit-wise copy, 0 otherwise
template< typename T > struct has_trivial_copy { enum { result = 0 }; };
template<> struct has_trivial_copy<char> { enum { result = 1 }; };
template<> struct has_trivial_copy<signed char> { enum { result = 1 }; };
template<> struct has_trivial_copy<unsigned char> { enum { result = 1 }; };
template<> struct has_trivial_copy<wchar_t> { enum { result = 1 }; };
template<> struct has_trivial_copy<short> { enum { result = 1 }; };
template<> struct has_trivial_copy<unsigned short> { enum { result = 1 }; };
template<> struct has_trivial_copy<int> { enum { result = 1 }; };
template<> struct has_trivial_copy<unsigned int> { enum { result = 1 }; };
template<> struct has_trivial_copy<long> { enum { result = 1 }; };
template<> struct has_trivial_copy<unsigned long> { enum { result = 1 }; };
template<> struct has_trivial_copy<float> { enum { result = 1 }; };
template<> struct has_trivial_copy<double> { enum { result = 1 }; };
template<> struct has_trivial_copy<long double> { enum { result = 1 }; };
template< typename T > struct has_trivial_copy<T*> { enum { result = 1 }; };
// etc. specialize for other types as needed

// can_convert<S,T>::result == 1 if an implicit conversion exists from
// type S to type T, 0 otherwise
template< typename S, typename T> struct can_convert
{
  static char test_overload_resolution(T) ; // conversion from S=>T 
  struct two_chars { char c[2] ; } ;
  static two_chars test_overload_resolution(...) ;
  static S object_of_type_S() ;
  enum { result = sizeof( test_overload_resolution( object_of_type_S() ) )
                    == sizeof(char) ? 1 : 0 } ;
  // note: sizeof is a compile-time operator, for sizeof(e) 
  // the expression e is evaluated at compile-time wrt type. 
  // in particular e is not evaluated at run-time 
  // ie. int i = 0 ; sizeof(++i) == sizeof(int), will not increment i
  // so functions test_overload_resolution, object_of_type_S 
  // are never called, and they need not be defined
  // (they are strawman functions)
};

// convert an int value to a distinct type: required because
// functions can be overloaded only on types (not values)
template< int N > struct value_to_type {} ;

// copy using memcpy; value_to_type<true>
template< typename ST, typename DT > inline
void do_copy( ST* begin, ST* end, DT* dest, value_to_type<1> )
{
  cout << "memcpy\n" ;
  memcpy( dest, begin, (end-begin)*sizeof(ST) ) ;
}

// copy using loop; value_to_type<false>
template< typename SI, typename DI > inline
void do_copy( SI begin, SI end, DI dest, value_to_type<0> )
{
   cout << "copy element by element\n" ;
   while( begin != end ) *dest++ = *begin++ ;
}

template< typename SI, typename DI > inline
void fast_copy( SI begin, SI end, DI dest )
{
   typedef typename is_pointer<SI>::pointed_type srce_type ;
   typedef typename is_pointer<DI>::pointed_type dest_type ;
   enum
   {
     srce_iter_is_pointer = is_pointer<SI>::result,
     dest_iter_is_pointer = is_pointer<DI>::result,
     srce_has_trivial_copy = has_trivial_copy<srce_type>::result,
     dest_has_trivial_copy = has_trivial_copy<dest_type>::result,
     they_are_of_same_size = sizeof(srce_type)==sizeof(dest_type),
     implicit_conversion_exists = can_convert<srce_type,dest_type>::result
   };
   
   do_copy( begin, end, dest,
            value_to_type< srce_iter_is_pointer &&
                           dest_iter_is_pointer &&
                           srce_has_trivial_copy &&
                           dest_has_trivial_copy &&
                           they_are_of_same_size &&
                           implicit_conversion_exists >() ) ;
}

int main()
{
  enum { N = 100 };
  int a[N] ;
  
  cout << "copy array of int to array of unsigned long: " ;
  unsigned long b[N] ;
  fast_copy( a, a+N, b ) ; // inlined memcpy sizeof(int)==sizeof(long) (i386)
  
  cout << "copy array of int to list: " ;
  list<int> lst(N) ;
  fast_copy( a, a+N, lst.begin() ) ; // no memcpy, list iterator is not a pointer

  // int* c[N] ;
  // fast_copy( a, a+N, c ) ; // error, no conversion fron int => int*
  
  cout << "copy array of int to array of short: " ;
  short s[N] ;
  fast_copy( a, a+N, s ) ; // no memcpy, sizeof(int)>sizeof(short) (i386)
  
  // to keep this example simple, we have not taken care of this
  // will produce incorrect results if sizeof(int)==sizeof(double)!
  // (meta)programming exercise: modify the code to take care of this.
  cout << "copy array of int to array of double: " ;
  double d[N] ;
  fast_copy( a, a+N, d ) ; // no memcpy; sizeof(int)!=sizeof(double) (i386)
}
/**
>g++ -std=c++98 -Wall -O3 fast_copy.cpp && ./a.out
copy array of int to array of unsigned long: memcpy
copy array of int to list: copy element by element
copy array of int to array of short: copy element by element
copy array of int to array of double: copy element by element
*/

note that with good library support like boost.type_traits (type_traits is in TR1, will part of c++0x) this code would have been just a few lines long.

[Bench]

That's the one that made me wonder if it was practical. All of the examples that look useful to me are too complicated to understand. All of the examples I can grok are kind of pointless. In the factorial one, you have to give the template a literal. If you know the literal you want, why not just use the factorial answer as a literal instead of some convoluted scheme of finding it at compile time with templates?

I just don't get it. :(

I understand your frustration.. there's still one or two pages in the book Modern C++ Design that frankly leave my head aching when I try to work out what the examples are actually doing

Yes, the factorial program on its own is rather pointless - it just shows how loops can be unrolled at compile time. Then again, most examples that you find in books are usually contrived, useless programs. I'm sure this can't be the first time you've looked at something in C++ and thought to yourself "Why on earth would I ever want to do this" :)

I think the advantage of template metaprogramming is two-fold. First, there's the minor goal of making your program more efficient, by performing certain routines at compile time. Although, if it were just about fine-tuned optimisation, then I expect most people wouldn't bother.

The more important goal (IMHO) is that doing these processes at compile time means more errors are picked up at compile time - this extra checking can be a huge asset when trying to write more bullet-proof code. If you, the programmer, make a mistake when using the code, the compiler will be the first to kick up a fuss.