C++ ist doch lazy!

In meinem Artikel Rekursion, Verarbeitung von Listen und Bedarfsauswertung zu den Charakteristiken der funktionalen Programmierung habe ich geschrieben: Die Geschichte der Bedarfsauswertung in C++ ist kurz. Leider habe ich meine Rechnung ohne Templates gemacht. Die zwei fortgeschrittene Template Techniken CRTP und Expression Templates basieren auf der Bedarfsauswertung.

CRTP

Doch was heißt CRTP? Das Akronym CRTP steht für das C++ Idiom Curiously Recurring Template Pattern und bezeichnet eine Technik in C++, in der eine Klasse Derived von einem Klassen-Template Base abgeleitet wird, die Derived als Template-Argument besitzt: 

template<class T>
class Base{
...
};

class Derived : public Base<Derived>{
...
};

Wenn das nicht verwirrend ist und was hat das ganze mit Bedarfsauswertung zu tun? Zuerst zur Laziness (Bedarfsauswertung).

Lazy durch und durch

Die entscheidende Beobachtung für das Verständnis des CRTP Idiom ist, dass die Instanziierung einer Methode eines Klassen-Templates dann erst geschieht, wenn sie benötigt wird. Beweis gefällig?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// lazy.cpp

#include <iostream>

template<class T> 
struct Lazy{
    void func() { std::cout << "func" << std::endl;}
    void func2(); // not defined
};

int main(){
  
  std::cout << std::endl;
    
  Lazy<int> lazy;
  lazy.func();
  
  std::cout << std::endl;
    
}

Obwohl die Methode func2 (Zeile 8) der Klasse Lazy lediglich deklariert ist, akzeptiert der Compiler das Programm. Da die Funktion func2 nicht aufgerufen wird, benötigt sie auch keine Definition.

Genau diese Beobachtung nützt das CRTP Idiom aus, da die Definition einer Methode eines Klassen-Templates dann erst benötigt wird, wenn diese Methode aufgerufen wird. Bei der Instanziierung der Basisklasse ist die Deklaration der Methode ausreichend. Damit lässt sich statischer Polymorphismus implementieren.

Statischer Polymorphismus

Statischer Polymorphismus ist dem dynamischen Polymorphismus sehr ähnlich. Im Gegensatz zum dynamischen Polymorphismus mit der Hilfe von virtuellen Methoden, findet beim statischen Polymorphismus der Dispatch des Methodenaufrufs zur Compilezeit statt. Damit sind wir mitten in der Domäne des CRTP Idioms.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

// crtp.cpp

#include <iostream>

template <typename Derived>
struct Base{
  void interface(){
    static_cast<Derived*>(this)->implementation();
  }
  void implementation(){
    std::cout << "Implementation Base" << std::endl;
  }
};

struct Derived1: Base<Derived1>{
  void implementation(){
    std::cout << "Implementation Derived1" << std::endl;
  }
};

struct Derived2: Base<Derived2>{
  void implementation(){
    std::cout << "Implementation Derived2" << std::endl;
  }
};

struct Derived3: Base<Derived3>{};

template <typename T>
void execute(T& base){
    base.interface();
}


int main(){
  
  std::cout << std::endl;
  
  Derived1 d1;
  execute(d1);
    
  Derived2 d2;
  execute(d2);
  
  Derived3 d3;
  execute(d3);
  
  std::cout << std::endl;
  
}

In dem Funktions-Template execute (Zeile 29 - 32) wende ich den statischen Polymorphismus an. Auf jedem Argument base rufe ich die Methode base.interface auf. Die Methode Base::interface in Zeile 7 - 9 ist der Dreh -und Angelpunkt des CRTP Idioms. Die Methode dispatched auf die Implementierung der abgeleiteten Klasse: static_cast<Derived*>(this)->implementation(). Dies ist möglich, da die Methode erst dann instanziiert wird, wenn sie aufgerufen wird. Zu diesem Zeitpunkt sind die abgeleiteten Klassen Derived1, Derived2 und Derived3 fertig definiert. Daher kann die Methode Base::interface Details ihrer abgeleiteten Klassen verwenden. Besonders interessant ist die Methode Base::implementation (Zeile 10 - 12). Sie dient Derived3 (Zeile 27) als Defaultimplementierung für den statischen Polymorphismus. 

Zum Abschluss noch die Ausgabe des Programms.

Zugegeben, das Beispiel hat nur einem Zweck gedient. Die Mechanismen hinter dem statischen Polymorphismus vorzustellen. Doch ein überzeugendes Beispiel bin ich bisher schuldig geblieben.

Mixins mit CRTP

Mixins sind ein beliebtes Konzept im Entwurf von Klassen, neuen Code in eine bestehende Klasse einzumischen. So es in Python sehr beliebt, mittels Mehrfachvererbung das Verhalten einer Klasse zu verändern. Im Gegensatz zu C++ ist es in Python zulässig, dass die Definition einer Methode mehrfach in Basisklassen definiert werden kann. Python verwendet die Methode, die in der Method Resolution Order (MRO) an vorderster Stelle steht.

Mixins lassen sich hingegen in C++ mit CRTP umsetzen. Ein prominentes Beispiel ist die Klasse std::enable_shared_from_this. Mir ihr lassen sich Objekte erzeugen, die einen std::shared_ptr auf sich zurückgeben. Dazu muss die Klasse der zu teilenden Objekte öffentlich von std::enable_shared_from_this abgeleitet werden. Somit steht in der Klasse die Methode shared_from_this zur Verfügung, mit der sich std::shared_ptr auf sich erzeugen lassen. Die Details zu std::enable_shared_from_this habe ich in dem Artikel Besonderheiten des std::shared_ptr vorgestellt.

Ein weiteres typisches Beispiel für ein Mixin ist eine Klasse, die um die Fähigkeit erweitert werden soll, ihre Instanzen auf Gleichheit und Ungleichheit zu vergleichen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

// crtpEquality.cpp

#include <iostream>
#include <string>

template<class Derived>
class Equality{};

template <class Derived>
bool operator == (Equality<Derived> const& op1, Equality<Derived> const & op2){
  Derived const& d1 = static_cast<Derived const&>(op1);     
  Derived const& d2 = static_cast<Derived const&>(op2); 
  return !(d1 < d2) && !(d2 < d1);
}

template <class Derived>
bool operator != (Equality<Derived> const& op1, Equality<Derived> const & op2){
  Derived const& d1 = static_cast<Derived const&>(op1);     
  Derived const& d2 = static_cast<Derived const&>(op2); 
  return !(op1 == op2);
}

struct Apple:public Equality<Apple>{
  Apple(int s): size{s}{};
  int size;
};

bool operator < (Apple const& a1, Apple const& a2){
  return a1.size < a2.size;
}

struct Man:public Equality<Man>{
  Man(std::string n): name{n}{}
  std::string name;
};

bool operator < (Man const& m1, Man const& m2){
  return m1.name < m2.name;
}


int main(){
  
  std::cout << std::boolalpha << std::endl;
  
  Apple apple1{5};
  Apple apple2{10}; 
  std::cout << "apple1 == apple2: " << (apple1 == apple2) << std::endl;
    
  Man man1{"grimm"};
  Man man2{"jaud"};
  std::cout << "man1 != man2: " << (man1 != man2) << std::endl;
  
  std::cout << std::endl;
    
}

So ist für die Klassen Apple und Man lediglich der  Kleiner-Operator (Zeile 28 und 37) überladen. Für meine weitere Argumentation verwende ich der Einfachheit halber nur noch die Klasse Man. Man ist in Zeile 32 - 35 öffentlich von der Klasse Equality<Man> abgeleitet. Für Klassen der Struktur Equality<Derived> ist sowohl der Gleichheitsoperator (Zeile 9 - 14) als auch der Ungleichheitsoperator (Zeile 16 - 21) definiert. Während der Ungleichheitsoperator die Implementierung des Gleichheitsoperators(Zeile 20) verwendet, nützt der Gleichheitsoperator aus, das auf Instanzen der Struktur Derived der Kleiner-Operator definiert ist (Zeile 13). Sowohl der Gleichheitsoperator als auch der Ungleichheitsoperator konvertieren ihre Operanden in Derived const&: Derived const& d1 = static_cast<Derived const&>(op1).

Damit lassen sich Instanzen von Apple und Man auf Gleichheit bzw. Ungleichheit prüfen.

 Wie geht's weiter?

Neben dem CRTP Idiom basieren Expression Templates auf der Bedarfsauswertung. Expression Templates sind "structures representing a computation at compile time, which structures are evaluated only as needed to produce efficient code for the entire computation" (https://en.wikipedia.org/wiki/Expression_templates). As needed, genau darum geht es bei der Bedarfsauswertung und damit im nächsten Artikel. 

Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Hole dir dein E-Book. Unterstütze meinen Blog.