Template Metaprogramming in C++

Überblick

  • Template Metaprogramming Überblick:
    TemplateMetaprogramming.jpg

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.
arrowbright 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 arrowbright
        4 * Factorial<3>::value arrowbright
        4 * 3 * Factorial<3>::value arrowbright
        4 * 3 * 2 Factorial<1>::value arrowbright
        4 * 3 * 2 * 1= 4!= 24 arrowbright
        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). arrowbright 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;

}

 

 

ParameterBeschreibungDefaultwert
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.arrowbright 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.arrowbrightSie 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

PureImpure
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 arrowbright 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 arrowbright

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

Introspektionsfähigkeit von C++0x

Abonniere den Newsletter (+ pdf Päckchen)

Beiträge-Archiv

Sourcecode

Neuste Kommentare