Template Metaprogramming in C++

Überblick

Template Metaprogramming Überblick:

Definition

Template Metaprogramming ist eine Metaprogramming Technik in C++, in der der Compiler die Templates zur Compilezeit interpretiert und sie in C++ Source Code transformiert. Dieser temporär erzeugte Sourcecode wird zusammen mit dem restlichen C++ Sourcecode comiliert.

C++ ist eine Zwei-Level-Sprache, den der statische Template Code wird zur Kompilezeit und der resultierende dynamische Code zur Laufzeit ausgeführt

Wie alles begann.

Erwin Unruh entdeckte 1994 bei einem C++ Standard Komitee Treffen, das Templates Berechnungen zur Kompilezeit erlauben
sein berühmtes Programm berechnete


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 -1> :: 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; } };

#ifndef LAST
#define LAST 10
#endif
main () {
    Prime_print<LAST> a;

}

berechnete die Primzahlen zur Kompilezeit

die wesentlichen Fehlermeldungen

|    Type 'enum{}' can't be converted to type 'D<2>' ("primes.cpp",L2/C25).

|    Type 'enum{}' can't be converted to type 'D<3>' ("primes.cpp",L2/C25).
|    Type 'enum{}' can't be converted to type 'D<5>' ("primes.cpp",L2/C25).

|    Type 'enum{}' can't be converted to type 'D<7>' ("primes.cpp",L2/C25).
|    Type 'enum{}' can't be converted to type '<11>' ("primes.cpp",L2/C25).

|    Type 'enum{}' can't be converted to type '<13>' ("primes.cpp",L2/C25).
|    Type 'enum{}' can't be converted to type '<17>' ("primes.cpp",L2/C25).

|    Type 'enum{}' can't be converted to type '<19>' ("primes.cpp",L2/C25).
|    Type 'enum{}' can't be converted to type '<23>' ("primes.cpp",L2/C25).

|    Type 'enum{}' can't be converted to type '<29>' ("primes.cpp",L2/C25).

Wie es funktioniert.

Das folgende Programm berechnet die Fakultät von 4 und 5 zur Compilezeit:


#include <iostream>

template <int N>
struct Factorial{

    static int const value= N * Factorial<N-1>::value;

};

template <>
struct Factorial<1>{
    static int const value = 1;

};

int main(){
    std::cout << Factorial<4>::value << std::endl;

    std::cout << 24::value << std::endl;
    std::cout << Factorial<5>::value << std::endl;

    std::cout << 120 << std::endl;
    return 0;

}

das Programm mit g++ -g -o fakultaet faktultaet.cpp übersetzt und mit objdump -S fakultaetanalysiert, ergibt:

...

int main(){
  4008ce:       55                      push   %rbp
  4008cf:       48 89 e5                mov    %rsp,%rbp
    std::cout << Factorial<4>::value << std::endl;
  4008d2:       be 18 00 00 00          mov    $0x18,%esi                     <<==
  4008d7:       bf 60 10 60 00          mov    $0x601060,%edi
  4008dc:       e8 2f fe ff ff          callq  400710 <_ZNSolsEi@plt>

  4008e1:       48 89 c7                mov    %rax,%rdi
  4008e4:       be 70 07 40 00          mov    $0x400770,%esi
  4008e9:       e8 72 fe ff ff          callq  400760 <_ZNSolsEPFRSoS_E@plt>
    std::cout << 24 << std::endl;
  4008ee:       be 18 00 00 00          mov    $0x18,%esi                     <<==

  4008f3:       bf 60 10 60 00          mov    $0x601060,%edi
  4008f8:       e8 13 fe ff ff          callq  400710 <_ZNSolsEi@plt>
  4008fd:       48 89 c7                mov    %rax,%rdi
  400900:       be 70 07 40 00          mov    $0x400770,%esi
  400905:       e8 56 fe ff ff          callq  400760 <_ZNSolsEPFRSoS_E@plt>
    std::cout << Factorial<5>::value << std::endl;
  40090a:       be 78 00 00 00          mov    $0x78,%esi                     <<==

  40090f:       bf 60 10 60 00          mov    $0x601060,%edi
  400914:       e8 f7 fd ff ff          callq  400710 <_ZNSolsEi@plt>
  400919:       48 89 c7                mov    %rax,%rdi
  40091c:       be 70 07 40 00          mov    $0x400770,%esi
  400921:       e8 3a fe ff ff          callq  400760 <_ZNSolsEPFRSoS_E@plt>
    std::cout << 120 << std::endl;
  400926:       be 78 00 00 00          mov    $0x78,%esi                     <<==

  40092b:       bf 60 10 60 00          mov    $0x601060,%edi
  400930:       e8 db fd ff ff          callq  400710 <_ZNSolsEi@plt>
  400935:       48 89 c7                mov    %rax,%rdi
  400938:       be 70 07 40 00          mov    $0x400770,%esi
  40093d:       e8 1e fe ff ff          callq  400760 <_ZNSolsEPFRSoS_E@plt>
    return 0;
  400942:       b8 00 00 00 00          mov    $0x0,%eax
}

Die Werte von 4! und 5! sind zur Compilezeit bereits ausgerechnet worden.
- 4!= 24= x18
- 5!= 120= x78
- der Ausdruck Factorial<4>::valuewird zu Compilezeit zu
  - Factorial<4>::value
    4 * Factorial<3>::value
    4 * 3 * Factorial<3>::value
    4 * 3 * 2 Factorial<1>::value
    4 * 3 * 2 * 1= 4!= 24
    x18 expandiert

Charakteristiken

Das folgende kleine Programm soll helfen die Charakteristiken von Template Metaprogramming herauszuarbeiten.

das Programm


#include <iostream>

#include <type_traits>

template <typename T>
struct RemoveConst
{
    typedef T type;

};

template <typename T>
struct RemoveConst< const T>

{
    typedef T type;
};


template <typename T>

void checkConst()
{
    if (std::is_const<T>::value == true  ) {

        std::cout << "const " << std::endl;
    }
    else {

        std::cout << "not const" << std::endl;
    }
}

int main(){

  std::cout << "int : "; checkConst<int>();

  std::cout << "const int: "; checkConst<const int>();
  std::cout << "RemoveConst<int>::type > "; 
                checkConst< RemoveConst<int>::type >();

  std::cout << "RemoveConst<const int>::type > : "; 
               checkConst< RemoveConst<const int>::type >();

  typedef RemoveConst<const int>::type NotConstFromConstInt;
  std::cout << "NotConstFromConstInt : "; checkConst< NotConstFromConstInt >();

  NotConstFromConstInt i= 10;

ergibt

grimm@laiard TemplateMetaprogramming $ ./removeConst
int : not const
const int: const
RemoveConst<int>::type > not const
RemoveConst<const int>::type > : not const
NotConstFromConstInt : not const

Metafunktionen

Sind reine Funktionen, die zur Compilezeit ausgeführt werden und auf Metadaten wirken.

werden in Template Metaprogramming durch Klassentemplates implementiert
die Funktion myFunction(arg1,arg2) entspricht der Metafunktion myFunction<Arg1,Arg2>::type
Metafunktionen liefern Metadaten, dies sind Typen und numerische Werte
die Ergebnisse der Metafunktionen werden per Konvention mit dem Member ::type für Typen und dem Member ::valuefür Werte angeboten
- aber auch RET, return wird gerne für das Ergebnis einer numerischen Metafunktion statt value verwendet
Beispiel:
1. die numerische Metafunkion template struct Factorial liefert für den Aufruf Factorial<4>::value das Ergebnis den Wert 24 zurück
2. die Metafunktion template struct RemoveConst liefert für den Aufruf RemoveConst::type den Typ int zurück

Metadaten

Sind immutable Werte, die zur Compilezeit modifiziertwerden können.

Typen
- int, string, float, Container , ...
- Templates
Nicht-Typen
- Integralen Typen
- Enums
- Pointer auf eine Objekte oder Funktionen
- Referenzen auf Objekte oder Funktionen
- Pointer auf Members
Beispiel:
1. Factorial<4>::value ist ein Nicht-Typ
2. RemoveConst::type ist ein Typ

Symbolische Namen

Ersetzen Variablen, und stellen das Ergebnis einer Metafunktionen zur Verfügung.

Typen

typedefs liefern Aliase auf bestehende Typen zurück


template <typename T>

struct RemoveConst
{
    typedef T type;
};

template <typename T>

struct RemoveConst< const T>
{
    typedef T type;
};

typedef T type erklärt einen neuen Typ zur Compilezeit
abhängig davon, ob T const oder nicht const ist, wird das primäre Template oder die Spezialiserung template struct RemoveConst< const T>verwendet
- bei der Spezialisierung wird ein const T angenommen und ein T zurückgegeben

Integrale Konstanten


struct MyConstants{      
  static int const value1= 4;

  enum { value2= 5 };
};

sind die konstanten Ausdrücke, die als Ergebnis einer numerischen Metafunktion verwendet werden können
Beispiel:
1. static int const value= N * Factorial<N-1>::value ist eine Integrale Konstante
2. typedef RemoveConst::type NotConstFromConstInt erklärt einen neuen Typ NonConstFromConstInt, der einen Alias für int darstellt

Pattern Matching

Pattern Matching oder auch Templatespezialisierung ist die case Struktur zur Compilezeit.

beim Template Metaprogramming wird Pattern Matching nach dem best fit Prinzip angewandt (vgl. Exception Handling)
das primäre Klassentemplate, oder der allgemeine Fall, muß zuerst definiert werden
das primäre Klassentemplate template struct RemoveConst wird nur in dem Fall genommen, falls die Templatespezialisierung template struct RemoveConst< const T> nicht angewandt werden kann
Beispiel:
1. template struct Factorial ist das primäre Klassentemplate und template <> struct Factorial<1> das sekundäre Klassentemplate
2. template struct RemoveConst ist das primäre Klassentemplate und template struct RemoveConst< const T> das sekundäre Klassentemplate

Laufzeit- versus Compilzeitberechnung des Fibonacci Algorithmus

Laufzeit


#include <chrono>
#include <iostream>

long int fib(int n){

  if (n==0) return 0;
  if (n==1) return 1;

  return fib(n-1)+fib(n-2);
}

int main(){
  auto begin= std::chrono::monotonic_clock::now();

  std::cout << "fib(10)= " << fib(10) ;
  auto last=  std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

  
  begin= std::chrono::monotonic_clock::now();
  std::cout << "fib(20)= " << fib(20);

  last= std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

  
  begin= std::chrono::monotonic_clock::now();
  std::cout << "fib(30)= " << fib(30);

  last= std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

  
  begin= std::chrono::monotonic_clock::now();
  std::cout << "fib(40)= " << fib(40);

  last= std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

  
  begin= std::chrono::monotonic_clock::now();
  std::cout << "fib(50)= " << fib(50);

  last= std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

  
  begin= std::chrono::monotonic_clock::now();
  std::cout << "fib(50)= " << fib(50);

  last= std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

Compilezeit


#include <chrono>
#include <iostream>

template <int n>
struct fib{
  const static long int value= fib<n-1>::value + fib<n-2>::value;

};

template <>
struct fib<0>{
  const static long int value= 0;

};

template <>
struct fib<1>{
  const static long int value= 1;

};

int main(){
  auto begin= std::chrono::monotonic_clock::now();

  std::cout << "fib(10)= " << fib<10>::value ;
  auto last=  std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

  
  begin= std::chrono::monotonic_clock::now();
  std::cout << "fib(20)= " << fib<20>::value;

  last= std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

  
  begin= std::chrono::monotonic_clock::now();
  std::cout << "fib(30)= " << fib<30>::value;

  last= std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

  
  begin= std::chrono::monotonic_clock::now();
  std::cout << "fib(40)= " << fib<40>::value;

  last= std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() 
            << " seconds" << std::endl;

  
  begin= std::chrono::monotonic_clock::now();
  std::cout << "fib(50)= " << fib<50>::value;

  last= std::chrono::monotonic_clock::now() - begin;

  std::cout <<  " takes " << std::chrono::duration<double>(last).count() << " seconds" << std::endl;

  
}

Vergleich des Laufzeitverhaltens

Das Laufzeit- und Compilezeitverhalten weist ein Paar Besonderheiten auf:

rainer@icho:~> time g++ -std=c++0x -I/usr/include/c++/4.4/ -o fibDyn fibDyn.cpp

real    0m0.266s
user    0m0.224s
sys     0m0.029s

rainer@icho:~> time g++ -std=c++0x -I/usr/include/c++/4.4/ -o fibStat fibStat.cpp

real    0m0.230s
user    0m0.193s
sys     0m0.032s


rainer@icho:~> ./fibDyn
fib(10)= 55 takes 5e-05 seconds
fib(20)= 6765 takes 0.000266 seconds
fib(30)= 832040 takes 0.016401 seconds
fib(40)= 102334155 takes 1.53346 seconds
fib(50)= 12586269025 takes 189.317 seconds
rainer@icho:~> ./fibStat
fib(10)= 55 takes 4.7e-05 seconds
fib(20)= 6765 takes 1e-06 seconds
fib(30)= 832040 takes 1e-06 seconds
fib(40)= 102334155 takes 1e-06 seconds
fib(50)= 12586269025 takes 1e-06 seconds

in fibStat liegen die Werte der fibonacci Aufrufe als Konstanten schon vor, trotzdem ist die Übersetzungszeit von fibStat nur unwesentlich länger als die Compilezeit von fibDyn
die naive Annahme ist aber, das die Laufzeit von fibDyn der Compilezeit von fibStat entspricht, da hier der ähnliche Code ausgeführt wird
Warum lässt sich fibStat so schnell kompilieren?
- Der naive Fibonacci Algorithmus fibDyn und fibStat besitzten ein expotentielles Laufzeitverhalten bzw. Compilezeitverhalten.

Reflexion

Reflexion: (reflection) ist die Fähigkeit eines Programmes, seine Struktur zu kennen (introspection) und gegebenfalls anzupassen (intercession). Grundlegende Konzept für selbst-adaptive Systeme. (Vgl. automatische Parallelisierung)

Introspektion - Metainformationen bereitstellen

Charakteristiken eines Types werden als Trait bezeichnet.

Member Traits

Idee

Assoziiere die Traits mit dem Typ, sodass der Trait über den Typ abgefragt werden kann.

Beispiel

std::string


namespace std{ 
    template<class charT,
             class traits= char_traits<charT>,

             class Allocator= allocator<charT> >
    class basic_string{
   public:

      typedef traits                         traits_type;
      typedef typename traits::char_type     value_type;
      typedef Allocator                      allocator_type;

  ...
}
namespace std{
    typedef basic_string<char> string;

}

Parameter	Beschreibung	Defaultwert
charT	Zeichentyp, den der String enthält.
traits	Der Zeichentyp Trait, der die elementaren Zeichenoperationen definiert.	char_traits
Allocator	Der Allokator des Strings für das Speichermanagment.	allocator

Iteratoren über Container

jeder Standardcontainer besitzt ein Membertrait iterator und const_iterator, sodass das Iterieren über dessen Elemente transparent möglich ist


std::map<std::string,std:string> myTelephonBook;

...
for (std::map<std::string,std::string>::iterator it= 
     myTelephonBook.begin(); it != myTelephonBook.end(); ++it) ...

Traits Klassen

Idee

Fasse die Traits eines Types in einer Klasse zusammen, so das sie gebunden verwendet werden können.

Beispiel: char_traits

definieren die elementaren Zeichenoperationen


    static void
      assign(char_type& __c1, const char_type& __c2)

      { __c1 = __c2; }

      static bool

      eq(const char_type& __c1, const char_type& __c2)

      { return __c1 == __c2; }

      static bool

      lt(const char_type& __c1, const char_type& __c2)

      { return __c1 < __c2; }

      static int

      compare(const char_type* __s1, const char_type* __s2, std::size_t __n);

      static std::size_t
      length(const char_type* __s);

Vergleiche von zwei std:: strings werden an die char_traits delegiert

Traits Templates

Idee

Spezialisiere ein Klassentemplate für die verschiedene Typen, sodass jede Spezialisierung den Trait eines Types darstellt.

Beispiel: numeric_limits<>

numeric_limits<> in definiert die Charakteristiken von numerischen Typen
Basisklasse


template <class T> 
struct numeric_limits {
  static const bool is_specialized = false;

  static T min() throw();
  static T max() throw();

  static const int  digits = 0;
  static const int  digits10 = 0;

  static const bool is_signed = false;
  static const bool is_integer = false;

  static const bool is_exact = false;
  static const int radix = 0;

  static T epsilon() throw();
  static T round_error() throw();

  static const int  min_exponent = 0;
  static const int  min_exponent10 = 0;

  static const int  max_exponent = 0;
  static const int  max_exponent10 = 0;

  static const bool has_infinity = false;
  static const bool has_quiet_NaN = false;

  static const bool has_signaling_NaN = false;
  static const float_denorm_style has_denorm = denorm absent;

  static const bool has_denorm_loss = false;
  static T infinity() throw();

  static T quiet_NaN() throw();
  static T signalign_NaN() throw();

  static T denorm_min() throw();

  static const bool is_iec559 = false;

  static const bool is_bounded = false;
  static const bool is_modulo = false;

  static const bool traps = false;
  static const bool tinyness_before = false;

  static const float_round_style round_style = round_toward_zero;
}
template<>
struct numeric_limits<bool>{

  static const bool is_specialized = true;

  static bool min() throw() { return false; }

  static bool max() throw(){ return true; }

 ...

template<>
struct numeric_limits<char>{

...

template<>

struct numeric_limits<unsigned char>{

Vorteile

leicht mit neuen Typen erweiterbar
Code ist besser portierbar, da Datentypen nach ihren Charakteristiken abgefragt werden können

Beispiel


#include <iostream>
#include <limits>

int main () {
  std::cout << "Maximum value for int: " 
            << std::numeric_limits<int>::max() << std::endl;

  std::cout << "Maximum value for long int: " 
            << std::numeric_limits<long int>::max() << std::endl;

  std::cout << "Maximum value for float: " 
            << std::numeric_limits<float>::max() << std::endl;

  std::cout << "Maximum value for double: " 
            << std::numeric_limits<double>::max() << std::endl; 
  std::cout << "Maximum value for long double: " 
            << std::numeric_limits<long double>::max() << std::endl;

}

ergibt:

Maximum value for int: 2147483647
Maximum value for long int: 9223372036854775807
Maximum value for float: 3.40282e+38
Maximum value for double: 1.79769e+308
Maximum value for long double: 1.18973e+4932

Mit der type_traitsBibliothek des neuen C++0x Standards wird die Introspektion aber auch die Intercession deutlich komfortabler.

Intercession - Codemodifikationen durch Metafunktionen

Ein paar typische Anwendungsfälle zeigen die Mächtigkeit der Codemodifikationen zur Compilezeit. Die Grundlage für Codemodifikationen oder auch Intercession ist die Introspektion.

Kontrollstrukturen

die bekannten Kontrollstrukturen (if, while, do und for) lassen sich als Kompilezeitstrukturen implementieren

statisches if

das kleine Beispielprogramm


#include <cmath>
#include <iostream>
#include <limits>

template<bool condition, typename Then, typename Else>

struct IF{
  typedef Then RET;
};

template<typename Then,typename Else>

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

};

int main(){ 
    IF< (sizeof(int) < sizeof(pow(2,40))), int, long int >::RET i= pow(2,40);

    IF< (sizeof(int) >= sizeof(pow(2,40))), int, long int >::RET j= pow(2,40);

    std::cout << "to small: " << i << std::endl;
    std::cout << "big enough:" << j << std::endl;

ergibt

grimm@laiard TemplateMetaprogramming $ g++ -Wall -o if if.cpp
if.cpp: In function 'int main()':
if.cpp:16: warning: overflow in implicit constant conversion
grimm@laiard TemplateMetaprogramming $ ./if
to small: 2147483647
big enough:1099511627776

der Ausdruck sizeof(int) < sizeof(pow(2,40) wird zur Kompilezeit ausgewertet und ergibt in diesem konkreten Fall true, sodass die Zuweisung von ==pow(2,40) einen Überlauf provoziert
sowohl der Compiler overflow in implicit constant conversion als auch das Ergebnis 2147483647 dokumentieren diesen Überlauf

Werte berechnen

Primzahlen bestimmen

Primzahlen lassen sich natürlich zur Compilezeit bestimmen.


#include <iostream>

template <int n > 
struct NoOfDivisor;

template <int n>
struct IsPrime{
    enum { value = NoOfDivisor<n>::value == 2 ? 1 : 0 };

};

template <int Start, int End>
struct NumDivisorsLoop{

    enum { value = (End % Start == 0 ? 1 : 0)   + 
            NumDivisorsLoop<Start + 1, End>::value };

};
 
template <int End>
struct NumDivisorsLoop<End, End>{

    enum { value = 1 };
};

template <int n>
struct NoOfDivisor{
    enum { value = NumDivisorsLoop<1, n>::value };

};

int main(){
  std::cout << "IsPrime<10>::value: " << IsPrime<10>::value<< std::endl;

  std::cout << "IsPrime<11>::value: " << IsPrime<11>::value<< std::endl;

  std::cout << "IsPrime<12>::value: " << IsPrime<12>::value<< std::endl;

  std::cout << "IsPrime<13>::value: " << IsPrime<13>::value<< std::endl;

}

IsPrimebestimmt, ob n eine Primzahl ist
- n ist genau dann eine Primzahlen, wenn n durch 2 Zahlen geteilt werden kann (1 und n): NoOfDivisor::value == 2
NumDivisorsLoop<1, n> ermittelt die Anzahl aller Teiler von n, indem es rekursiv 1 bis n hochzählt

Das Programm ermittelt das erwartete Ergebnis:

IsPrime<10>::value 0
IsPrime<11>::value 1
IsPrime<12>::value 0
IsPrime<13>::value 1

Typen ermitteln

Optimiertes Kopieren

Ein generisches Kopieralgorithmus für Standardcontainer kann so aussehen:


template<typename I1, typename I2, bool b>

I2 copy_imp(I1 first, I1 last, I2 out, const std::tr1::integral_constant<bool, b>&){

while(first != last){
  *out = *first;

  ++out;
  ++first;
 }
 return out;

}

Jedes Element des Bereiches [first,last[ wird sukzessive an den Bereich [out,...[ kopiert.
Dies geht mit memcpy deutlich schneller.


template<typename T>                                                            
T* copy_imp(const T* first, const T* last, T* out, const std::tr1::true_type&){ 
  memcpy(out, first, (last-first)*sizeof(T));

  return out+(last-first);
}

Die Datenstrukturen müssen aber hinreichend einfach sein um memcpyzu verwenden:

die Iteratoren müssen Pointer sein ( const T* first, const T* last, T* out )
die Iteratoren müssen auf die gleichen Typen verweisen ( <typename T> enthält nur ein Typ)
die Elemente des Containers müssen einen trivialen, vom Compiler automatisch erzeugten, Zuweisungsoperator besitzen ( const std::tr1::true_type& )

Ein Aufruf der Form

 
template<typename I1, typename I2>
I2 copy(I1 first, I1 last, I2 out){

  typedef typename std::iterator_traits<I1>::value_type value_type;
  return copy_imp(first, last, out, std::tr1::has_trivial_assign<value_type>());

}

stösst die richtige copy_imp Implementierung an
durch typedef typename std::iterator_traits<I1>::value_type value_type wird der Typ der Containerelemente bestimmt um ihn anschliessend in std::tr1::has_trivial_assign<value_type> zu nutzen
abhängig vom Ergebniss der Evaluierung wird der optimierte oder generische Kopieralgorithmus verwendet
das Ergebnis des Aufrufs std::tr1::has_trivial_assign<value_type> ist eine Klasse, so dass der Dispatch auf das vierte Argument der copy_imp Methoden vollzogen wird
der Ausdruck typedef integral_constant<bool, true> true_type; definiert eine Spezialisierung true_type von std::tr1::integral_constant<bool, b>

Code erzeugen

Loop unrolling

die zwei Funktionen power berechnen pow(2,10)


#include <iostream>

inline int power(const int& m, const int& n){

  int r = 1;
  for(int k=1; k<=n; ++k) r*= m;

  return r;
}

template<int n>
inline int power(const int& m){

  return power<n-1>(m) * m;
}

template<>
inline int power<1>(const int& m){

  return m;
}

template<>
inline int power<0>(const int& m){

return 1;
}

int main(){
  std::cout << "power(2,10): " << power(2,10) << std::endl;

  std::cout << "power<10>(2): " << power<10>(2) << std::endl;

}

die Ergebnisse sind identisch
```
power(2,10): 1024
power<10>(2): 1024
   
```
es besteht ein feiner Unterschied
- das Funktionstemplate kann verwendet werden, wenn n zur Compilezeit bekannt ist
- in dem Ausdruck power<10>(2) ist 10 ein Compilezeit- und 2 ein Laufzeitargument
- die Templatefunktion wird schon partiell evaluiert, was dazu führt, das zur Laufzeit lediglich *m*m*m*m*m*m*m*m*m für m=2 ausgewertet werden muß
- die for-Schleife existiert zur Laufzeit nicht mehr, da sie zur Compilezeit schon entrollt wurde

Wie müsste eine powerFunktionen aussehen, die vollständig zur Compilezeit evaluiert wird?

Funktionale Subsprache

C++ Template Metaprogramming ist eine rein funktionale Subsprache in C++, die zur Compilezeit ausgeführt wird.

Kernidee

Programme bestehen aus einer Auswertung von Funktionen, die weder einen Zustand noch veränderliche Daten kennen.
Funktionen sind Funktionen im mathematischen Sinn. Ihr Ergebnis hängt nur von der Eingabe ab.

Listenverarbeitung zur Compilzeit

sum und sumWith

Das folgende, eher untypische Metaprogramming, soll den funktionalen Charakter von Template Metaprogramming verdeutlichen. Untypisch, weil es auf integralen Kostanten und nicht auf Typen wirkt. Sowohl sum als auch sumWith summerieren die natürlichen Zahlen auf. sumWith erwartet zusätzlich die Übergabe einer Metafunktion, die vor der Summation auf die natürlichen Zahlen angewandt wird. Dies ist das Klassentemplate template class f.


#include <iostream>
#include <cmath>

template<int ...> struct sum;

template<>struct
sum<>{
    static const int value= 0;

};

template<int i, int ... tail> struct                  // 1 

sum<i,tail...>{
    static const int value= i + sum<tail...>::value;  // 2

};

template <int i>
struct len{
   static const int value= 1;

};

template <int i>
struct id{
  static const int value= i;

};

template <int i>
struct doub{
  static const int value= 2*i;

};

template <int i>
struct sq{
  static const int value= i*i;

};

template<template<int> class f,int ...> struct sumWith;

template<template<int> class f>struct
sumWith<f>{
    static const int value= 0;                                                                                       // 9

};


template<template<int> class f,int head, int ... tail> struct                                                        // 10, 11 

sumWith<f,head,tail...>{                                                                                             // 11
    static const int value= f<head>::value + sumWith<f,tail...>::value;                                              // 11

};


int main(){

  std::cout << "sum<1,2,3,4,5>::value: " 
            << sum<1,2,3,4,5>::value << std::endl;

  std::cout << "sumWith<len,1,2,3,4,5>::value: " 
            << sumWith<len,1,2,3,4,5>::value << std::endl;                          // 3

  std::cout << "sumWith<id,1,2,3,4,5>::value: " 
            << sumWith<id,1,2,3,4,5>::value << std::endl;                           // 4 

  std::cout << "sumWith<doub,1,2,3,4,5>::value: " 
            << sumWith<doub,1,2,3,4,5>::value << std::endl;                         // 5 

  std::cout << "sumWith<sq,1,2,3,4,5>::value: " 
            << sumWith<sq,1,2,3,4,5>::value << std::endl;                           // 6

  std::cout << "distance= sqrt( sumWith<sq,1,2,3,4,5::value): " 
            << sqrt( sumWith<sq,1,2,3,4,5>::value ) << std::endl;                   // 7

  std::cout << "distance= sqrt( sumWith<sq,1,2,3,4,5::value): "  
            << sqrt( 55 ) << std::endl;                                             // 8

};

das Ergebnis ist recht unspektakulär

grimm@laiard TemplateMetaprogramming $ ./sum
sum<1,2,3,4,5>::value: 15
sumWith<len,1,2,3,4,5>::value: 5
sumWith<id,1,2,3,4,5>::value: 15
sumWith<doub,1,2,3,4,5>::value: 30
sumWith<sq,1,2,3,4,5>::value: 55
distance= sqrt( sumWith<sq,1,2,3,4,5::value): 7.4162
distance= sqrt( sumWith<sq,1,2,3,4,5::value): 7.4162

die drei Punkte ...
- bezeichnen die sogenannten Variadic Template Arguments des neuen C++0x Standardards
- Templates können eine beliebige Anzahl von Argument annehmen
- stehen die drei Punkte links vom Bezeichner (1) werden sich gepackt; rechts (2) davon werden sie entpackt
der Ausdruck sqrt( sumWith<sq,1,2,3,4,5>::value ), indem die Metafunktion sumWith<sq,1,2,3,4,5>::value in der Funktion sqrt verwendet wird, erzeugt den gleichen Objektcode wie sqrt( 55 )

map

Neben reduce und filter ist map die klassische funktionale Funktion.

die Ideen von sum und sumWith erlauben es, map als Metafunktion zu formulieren
Besonderheiten:
- der wesentliche Unterschied ist, das die Funktion map keinen Wert, sondern eine neue Liste mit den modifizierten Werten zurückgibt
- std::tuple kann zur Compilezeit nur mit Typen arbeiten, die mittels typedef (4) erklärt werden; dies sind nur Typedeklaration
- dazu müssen die integralen Werte in Typen verpackt werden (1)
- die map Metafunktion ist sehr kompakt (3)
- lediglich zur Ausgabe werden die Typen instanziiert (2)

  
#include <iostream>
#include <tuple>

// Int2Type

template <int v>                                                                                     //1
struct Int2Type {
    const static int value= v;

};

// few class templates for map

struct ApplyId{
    template<typename T>

    struct apply{
      typedef Int2Type<T::value> type;

    };
};

struct MakeTen{
    template<typename T>

    struct apply{
      typedef Int2Type<10> type;
    };

};

struct DoubleMe{
    template<typename T>
    struct apply{

      typedef Int2Type<2*(T::value)> type;
    };

};

struct AbsMe{
    template<typename T>
    struct apply{

      typedef Int2Type< (T::value > 0)? T::value : -(T::value) > type;

    };
};

// helper function for output                                                                          //2

template< typename head >

void showMe( std::tuple< head> ){                                                                         
  std::cout << head::value << "\n";

};

template< typename head, typename ... tail>

void showMe( std::tuple< head, tail ... > ){

  std::cout << head::value << " ," ;
  showMe( std::tuple< tail ...>() );

}


// map function

template<typename F, typename ... Elements> struct map;

template< typename F, typename ... Elements>
struct map<F,std::tuple<Elements ...> >{                                                                  //3

    typedef std::tuple<typename F::template apply<Elements>::type ... > type;                             

};

int main(){

    std::cout << "original tupel: " << std::endl;

    typedef std::tuple<Int2Type<-5>,Int2Type<-4>,Int2Type<-3>,Int2Type<-2>,

                       Int2Type<-1>,Int2Type<0>,Int2Type<1>,Int2Type<2>,
                       Int2Type<3>,Int2Type<4>,Int2Type<5> >constNumbers;                                 //4

    showMe( constNumbers() );

    std::cout << "\napply identitiy: " << std::endl;

    typedef map<ApplyId, constNumbers >::type idConstNumbers;
    showMe( idConstNumbers() );

    std::cout << "\nset each value to 10" << std::endl;
    typedef map<MakeTen, constNumbers >::type makeTenConstNumbers;

    showMe( makeTenConstNumbers() );

    std::cout << "\ndouble each value" << std::endl;

    typedef map<DoubleMe, constNumbers >::type doubleMeConstNumbers;
    showMe( doubleMeConstNumbers() );

    std::cout << "\nabsolute value" << std::endl;
    typedef map<AbsMe, constNumbers >::type absMeConstNumbers;

    showMe( absMeConstNumbers() );

};

ausgeführt ergibt das Programm

grimm@laiard source $ ./map
original tupel:
-5 ,-4 ,-3 ,-2 ,-1 ,0 ,1 ,2 ,3 ,4 ,5

apply identitiy:
-5 ,-4 ,-3 ,-2 ,-1 ,0 ,1 ,2 ,3 ,4 ,5

set each value to 10
10 ,10 ,10 ,10 ,10 ,10 ,10 ,10 ,10 ,10 ,10

double each value
-10 ,-8 ,-6 ,-4 ,-2 ,0 ,2 ,4 ,6 ,8 ,10

absolute value
5 ,4 ,3 ,2 ,1 ,0 ,1 ,2 ,3 ,4 ,5

Funktionen erster Ordnung - first class functions

Funktionen sind Daten sehr ähnlich.

Sie können zur Laufzeit erzeugt, in einer Datenstruktur gespeichert, als Rückgabewert oder Argument einer Funktion verwendet werden.

Metafunktionen sind Klassentemplates. Als solche sind sie Objekte und können wie Daten behandelt werden.

Funktionen höherer Ordnung - higher order functions

Funktionen höherer Ordnung können Funktionen als Argumente annehmen oder als Rückgabewert liefern.

sumWith ist eine Metafunktion, die über die Metafunktionen (len,id,doub,sq) (3-8) parametrisiert wird

reine Funktionen - pure functions

Gegenüberstellung von pure und impure aus Real World Haskell

Pure	Impure
Always produces the same result when given the same parameters	May produce different results for the same parameters
Never has side effects	May have side effects
Never alters state	May alter the global state of the program, system, or world

zur Compilezeit existieren keine Daten, sondern nur Typen und integralen Konstanten
die Ergebnis der Operationen in mySum wird über eine integrale Konstante static const int value= 0 (9) gesichert
wird auf Typen operiert, so wird das Ergebnis als neuer Typ zur Verfügung gestellt

Rekursion anstelle von Schleifen und Zuweisungen

Variablen stehen für unveränderliche Werte und nicht für Speicherstellen, die verändert werden können.

Template Metaprogramming verwendet Rekursion kennt keine Variablen, die bei einem Schleifendurchlauf inkrementiert oder modifiziert werden Rekursion
Variadic Templates vereinfachen den Rekursion in Template Metaprogramming nach dem typischen Muster (head,tail) Muster (11) aus funktionalen Sprachen
- head: erste Element der Liste
- tail: restlichen Elemente der Liste

Verarbeitung von Listen

LISP steht für LISt Processing.

Variadic Templates erleichtern den Arbeiten mit Listen
typische Listen verarbeitende Algorithmen, die Listen annehmen und neue Listen zurückgeben (map,filter,zip,...) sind in C++0x nicht direkt realisierbar, da Klassentemplate keine Variadic Templates zurückgeben können

Kontrolle von Seiteneffekte

Funktionale Programmiersprachen, insbesondere Haskell, legen grossen Wert darauf, Seiteneffekte zu kontrollieren.

Template Metaprogramming ist zwangsläufig rein funktional
den einzigen Seiteneffekt den Template Metaprogramming erzielt, ist das Aufheizen des PC's

Beispiele

Anwendungen

type_traits in C++0x

Alles wird einfacher.

Introspektion mit klassischem C++

Nütze die Type Deduktion des Compilers zur Compilezeit aus.

SameType


template <typename T, typename U>

struct IsSameType{
  enum { value = false };

};

template <typename T>
struct IsSameType<T,T>{

  enum { value = true };
};

für identische Typen wird die Spezialisierung struct IsSameType<T,T> verwendet
bei der Type Dekuktion findet keine Typekonvertierung statt

IsClass

  
template<typename T>
class IsClass{
  private:

    typedef char One;
    typedef struct { char a[2]; } Two;

    template<typename C> static One test(int C::*);
    template<typename C> static Two test(...);

  public:
    enum { Yes = sizeof(IsClass<T>::test<T>(0)) == 1

  
template<typename T>
class IsClass{
  private:

    typedef char One;
    typedef struct { char a[2]; } Two;

    template<typename C> static One test(int C::*);
    template<typename C> static Two test(...);

  public:
    enum { Yes = sizeof(IsClass<T>::test<T>(0)) == 1 };

    enum { No = !Yes };
};

der Template besitz die Werte IsClass::Yes und IsClass::No
1. T in IsClass ist eine Klasse
  - für IsClass::test(0) wird die Typededuktion template static One test(int C::*) (int C::* ist die Syntax für eine Pointer auf eine Memberfunktion, die int zurückgibt)
  - die Methode gibt static One
  - sizeof(static One) ist 1, so das Yes = true gesetzt wird
2. T in IsClass ist keine Klasse
  - der Ausdruck template static Two test(...) gibt für alle Nichtklassen (Ellipse ...) static Two zurück