~/work/zolix/tanf/ms/src/template3.cpp.html

Template metaprogramming

// Erwin Unruh, untitled program,
// ANSI X3J16-94-0075/ISO WG21-462, 1994.

template <int i>
struct D
{
    D(void *);
    operator int();
};

template <int p, int i>
struct is_prime
{
    enum { prim = (p%i) && is_prime<(i>2?p:0), i>::prim };
};

template <int i>
struct Prime_print
{
    Prime_print<i-1>    a;
    enum { prim = is_prime<i,i-1>::prim };
    void f() { D<i> d = prim; }
};

struct is_prime<0,0> { enum { prim = 1 }; };
struct is_prime<0,1> { enum { prim = 1 }; };
struct Prime_print<2>
{
    enum { prim = 1 };
    void f() { D<2> d = prim; }
};

void foo()
{
    Prime_print<10> a;
}

// output:
// unruh.cpp 30: conversion from enum to D<2> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<3> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<5> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<7> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<11> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<13> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<17> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<19> requested in Prime_print

Factorial function

Template metaprogramming can inprove efficiency:

int factorial( int n)
{
    return (n==0) ? 1 : n*factorial(n-1)l
}

int main()
{
    cout << factorial(5) << endl;
    return 0;
}

But we can compute the value of the factorial function in compile-time:

// factorial.cpp

#include <iostream>

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

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

// example use
int main()
{
    const int fact5 = Factorial<5>::value;
    std::cout << fact5 << endl;
    return 0;
}

Template Recursion

Factorial<5> --> Factorial<4> --> ... -> Factorial<0>

intermediate classes are in pending state
recursive template instatiation nesting depth is limited

- ISO/ANSI recommend at least 17
- everyday compilers can do much more
- sometimes (g++) nesting depth is parameter

Meta Control Structures

In 1966 Bohm and Jacopini proved, that Turing machine implementation is
equivalent the exsistence of conditional and looping control structures.

// IF

template <bool condition, class Then, class Else>
struct IF
{
    typedef Then RET;
};

template <class Then, class Else>
struct IF<false, Then, Else>
{
    typedef Else RET;
};

This is a partial template specialization, we only specialize it on
condition==false, Then and Else remains parameter.

// if sizeof(int) < sizeof(long) then use long else use int
IF< sizeof(int)<sizeof(long), long, int>::RET  i;

template <typename T, typename S>
IF< sizeof(T)<sizeof(S), S, T>::RET max(T t, S s)
{
    if ( t < s)
        return s;
    else
        return t;
}

Metafunctions as Parameter

In dynamic C++ one can use pointer to function as parameter or return value

// accumulate(n,f) := f(0) + f(1) + ... + f(n)

template <int n, template<int> class F>
struct Accumulate
{
    enum { RET = Accumulate<n-1,F>::RET + F<n>::RET };
};

template <template<int> class F>
struct Accumulate<0,F>
{
    enum { RET = F<0>::RET };
};

template <int n>
struct Square
{
    enum { RET = n*n };
};

cout << Accumulate<3,Square>::RET << endl;

Motivation

This is a motivating example:

int main()
{
    const unsigned int di = 12;
    const unsigned int oi = 014;
    const unsigned int hi = 0xc;

    const unsigned int bi0 = binary_value("1101");
    const unsigned int bi1 = binary<1100>::value;
}

Why in compilation time

- Speed.
- Constantness (array size, enum value must be known in compilation time).
- Compiler control.

template <unsigned long N>
struct binary
{
    static unsigned const value
       = binary<N/10>::value * 2   // prepend higher bits
         + N%10;                   // to lowest bit
};

template <>                           // specialization
struct binary<0>                      // terminates recursion
{
    static unsigned const value = 0;
};

Expression templates

Object-orientation sometimes sacrifies efficiency for readibility and
ease of code maintenance:

Array a, b, c, d, e;

a = b + c + d + e;

This will generate the following pseudo-code:

// pseudocode for a = b + c + d + e

double* _t1 = new double[N];
for ( int i=0; i<N; ++i)
    _t1[i] = b[i] + c[i];

double* _t2 = new double[N];
for ( int i=0; i<N; ++i)
    _t2[i] = _t1[i] + d[i];

double* _t3 = new double[N];
for ( int i=0; i<N; ++i)
    _t3[i] = _t2[i] + e[i];

for ( int i=0; i<N; ++i)
    a[i] = _t3[i];

delete [] _t3;
delete [] _t2;
delete [] _t1;

Performace problems

- For small arrays new andi delete result poor performance: 1/10 of C.
- For medium arrays, overhead of extra loops and memory access add +50%
- For large arrays, the cost of the temporaries are the limitations: by Veldhuizen

minimal expression template implementation

#include <iostream>

using namespace std;

// this class encapsulates the "+" operation.
struct plus
{
    static double apply( double a, double b)
    {
        return a+b;
    }
};

// the node in the parse tree.
template <typename Left, typename Op, typename Right>
struct X
{
    Left    left;
    Right   right;

    X( Left t1, Right t2) : left(t1), right(t2)  { }

    double operator[](int i)
    {
        return Op::apply( left[i], right[i] );
    }
};

struct Array
{
    // constructor
    Array( double *data, int N) : data_(data), N_(N) { }

    // assign an expression to the array
    template <typename Left, typename Op, typename Right>
    void operator=( X<Left,Op,Right> expr)
    {
        for ( int i = 0; i < N_; ++i)
            data_[i] = expr[i];
    }

    double operator[](int i)
    {
        return data_[i];
    }

    double *data_;
    int N_;
};

template <typename Left>
X<Left, plus, Array> operator+( Left a, Array b)
{
    return X<Left, plus, Array>(a,b);
}

int main()
{
    double a_data[] = { 2, 3, 5, 9 };
    double b_data[] = { 1, 0, 0, 1 };
    double c_data[] = { 3, 0, 2, 5 };
    double d_data[4];

    Array A(a_data,4);
    Array B(b_data,4);
    Array C(c_data,4);
    Array D(d_data,4);

    D = A + B + C;

    for ( int i = 0; i < 4; ++i )
        cout << D[i] << " ";
    cout << endl;
}

Traits and policy classes

template <class T>
class matrix
{
public:
    matrix( int i, int j );
    matrix( const matrix &other);
    ~matrix();
    matrix operator=( const matrix &other);

    int rows() const { return x; }
    int cols() const { return y; }

    T& at( int i, int j) throw(indexError);
    T  at( int i, int j) const throw(indexError);
    T& operator()( int i, int j);
    T  operator()( int i, int j) const;

    matrix operator+=( const matrix &other);
private:
    int  x;
    int  y;
    T   *v;
    void copy( const matrix &other);
    void check( int i, int j) const throw(indexError);
};

template <class T>
void matrix<T>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new T[x*y];
    for ( int i = 0; i < x*y; ++i )
        v[i] = other.v[i];
}

// Specializations for POD types

template <>
void matrix<long>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new long[x*y];
    memcpy( v, other.v, sizeof(long)*x*y);
}

Using traits

template <typename T>
struct copy_trait
{
    static void copy( T* to, const T* from, int n)
    {
        for( int i = 0; i < n; ++i )
            to[i] = from[i];
    }
};
template <>
struct copy_trait<long>
{
    static void copy( long* to, const long* from, int n)
    {
        memcpy( to, from, n*sizeof(long));
    }
};

template <class T, class Cpy = copy_trait<T> >
class matrix
{
    //...
};

template <class T, class Cpy>
void matrix<T,Cpy>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new T[x*y];

    Cpy::copy( v, other.v, x*y);
}

Policy classes

template <typename T>
struct is_pod
{
    enum { value = false };
};

template <>
struct is_pod<long>
{
    enum { value = true };
};

template <typename T, bool B>
struct copy_trait
{
    static void copy( T* to, const T* from, int n)
    {
        for( int i = 0; i < n; ++i )
            to[i] = from[i];
    }
};

template <typename T>
struct copy_trait<T, true>
{
    static void copy( T* to, const T* from, int n)
    {
        memcpy( to, from, n*sizeof(T));
    }
};

template <class T, class Cpy = copy_trait<T,is_pod<T>::value> >
class matrix
{
    // ...
};

Typelist

class NullType {};

struct EmptyType {};        // could be instantiated

We now can construct a null-terminated list of typenames:

typedef Typelist< char, Typelist<signed char,
        Typelist<unsigned char, NullType> > > Charlist;

For the easy maintenance, precompiler macros are defined to create Typelists:

#define TYPELIST_1(x)           Typelist< x, NullType>
#define TYPELIST_2(x, y)        Typelist< x, TYPELIST_1(y)>
#define TYPELIST_3(x, y, z)     Typelist< x, TYPELIST_2(y,z)>
#define TYPELIST_4(x, y, z, w)  Typelist< x, TYPELIST_3(y,z,w)>
// :

typedef TYPELIST_3(char, signed char, unsigned char)  Charlist;

//
//  Length
//
template <class TList> struct Length;

template <>
struct Length<NullType>
{
    enum { value = 0 };
};

template <class T, class U>
struct Length <Typelist<T,U> >
{
    enum { value = 1 + Length<U>::value };
};

template <class TList, class T> struct IndexOf;

template <class T>
struct IndexOf< NullType, T>
{
    enum { value = -1 };
};

template <class T, class Tail>
struct IndexOf< Typelist<Head, Tail>, T>
{
private:
    enum { temp = IndexOf<Tail, T>::value };
public:
    enum { value = (temp == -1) ? -1 : 1+temp };
};

Usage

typedef TYPELIST_4(char, signed char, unsigned char, int)  Pod_types;

template <typename T>
struct is_pod
{
    enum { value = ::Loki::TL::IndexOf<Pod_types,T>::value != -1 };
};

template <typename T, bool B>
struct copy_trait
{
    static void copy( T* to, const T* from, int n)
    {
        for( int i = 0; i < n; ++i )
            to[i] = from[i];
    }
};
template <typename T>
struct copy_trait<T, true>
{
    static void copy( T* to, const T* from, int n)
    {
        memcpy( to, from, n*sizeof(T));
    }
};

template <class T, class Cpy = copy_trait<T,is_pod<T>::value> >
class matrix
{
    // ...
};

template <class T, class Cpy>
void matrix<T,Cpy>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new T[x*y];

    Cpy::copy( v, other.v, x*y);
}

Static interface checking

//  Alex Stepanov and Jeremy Siek

template <class T>
class HasClone
{
public:
    static void Constraints()
    {
        T* (T::*test)() const = &T::Clone;
        test;
    }
    HasClone() { void (*p)() = Constraints; }
};

template <class T>
class C : HasClone<T>
{
    // ...
};

Conversion Checking

Most fundamental check is whether a type could be converted to an other.

template <class T, class U>
class Conversion
{
public:
    enum
    {
        exists = sizeof(Test(MakeT()))==sizeof(Small)
    };
    enum
    {
        sameType = false;
    };
private:
    typedef char Small;
    class Big { char dummy[2]; };

    static Small Test(U);
    static Big   Test(...);
    static T     MakeT();
};

typename <class T>
class Conversion<T,T>
{
public:
    enum { exists = 1, sameType = 1 };
};

int main()
{
    std::cout   << Conversion<double, int>::exists <<
                << Conversion<char, char*>::exists <<
                << Conversion<std::vector<int>,std::list<int> >::exists
                << std::endl;
    return 0;
}

Inheritance

The next step is to chech inheritance:

#define SUPERSUBCLASS(T,U)                              \
    ((Conversion<const U*, const T*>::exists  &&        \
    ! (Conversion<const T*, const void*>::sameType))

Compile-Time Assertion

Based on compile-time decision we can decide to abort the program.
This is parallel to run-time assertions:

//  pure declaration
template <bool> class CompileTimeAssert;

//  specialization for true
template <> class CompileTimeAssert<true>  {};

The trick is, that only specialization is exist: the general case has only
declaration. This declaration is neccessary, because otherwise the
specialization would be invalid.

//  usage:
CompileTimeAssert< SUPERSUBCLASS( X, Y) >   MUST_BE_SUPERCLASS;

#include <iostream>

static inline int f(char *s){ return 1;}

template <int N>
struct Fact
{
  enum { begin = sizeof (f("")) };
  enum { value = Fact<N-1>::value * N };
  enum { end = sizeof (f("")) };
};

template <>
struct Fact<1>
{
  enum { begin = sizeof (f("")) };
  enum { value = 1 };
  enum { end = sizeof (f("")) };
};

int main()
{
  std::cout << Fact<6>::value << std::endl;
  return 0;
}
~

$ g++ 31_fact.cpp
31_fact.cpp:18:30: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp:20:28: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<6>’:
31_fact.cpp:25:23:   instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<5>’:
31_fact.cpp:11:3:   instantiated from ‘Fact<6>’
31_fact.cpp:25:23:   instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<4>’:
31_fact.cpp:11:3:   instantiated from ‘Fact<5>’
31_fact.cpp:11:3:   instantiated from ‘Fact<6>’
31_fact.cpp:25:23:   instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<3>’:
31_fact.cpp:11:3:   instantiated from ‘Fact<4>’
31_fact.cpp:11:3:   instantiated from ‘Fact<5>’
31_fact.cpp:11:3:   instantiated from ‘Fact<6>’
31_fact.cpp:25:23:   instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<2>’:
31_fact.cpp:11:3:   instantiated from ‘Fact<3>’
31_fact.cpp:11:3:   instantiated from ‘Fact<4>’
31_fact.cpp:11:3:   instantiated from ‘Fact<5>’
31_fact.cpp:11:3:   instantiated from ‘Fact<6>’
31_fact.cpp:25:23:   instantiated from here
31_fact.cpp:10:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<3>’:
31_fact.cpp:11:3:   instantiated from ‘Fact<4>’
31_fact.cpp:11:3:   instantiated from ‘Fact<5>’
31_fact.cpp:11:3:   instantiated from ‘Fact<6>’
31_fact.cpp:25:23:   instantiated from here
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<4>’:
31_fact.cpp:11:3:   instantiated from ‘Fact<5>’
31_fact.cpp:11:3:   instantiated from ‘Fact<6>’
31_fact.cpp:25:23:   instantiated from here
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<5>’:
31_fact.cpp:11:3:   instantiated from ‘Fact<6>’
31_fact.cpp:25:23:   instantiated from here
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’
31_fact.cpp: In instantiation of ‘Fact<6>’:
31_fact.cpp:25:23:   instantiated from here
31_fact.cpp:12:3: warning: deprecated conversion from string constant to ‘char*’