Funktional in C++98

C++ ist keine funktionale Programmiersprache, trotzdem erlaubt sie das Programmieren im funktionalen Stil. Doch was sind die funktionalen Feature in C++? Genau diese Frage werde ich in diesem Artikel für C++98 beantworten.

Genau genommen sind es drei Fragen, die ich in diesem und den nächsten Artikel beantworten werde.

• Welche funktionalen Feature bietet C++ an?
• Welche neuen funktionalen Feature erhalten wir mit dem vor der Tür stehenden neuen Standard C++17?
• Was bringt die Zukunft in Form von C++20?

Der große Überblick

Um so viele Fragen zu beantworten bietet sich natürlich ein Zeitstrahl an, der die funktionalen Feature in C++ aneinander reiht.

Die Geschichte zu der funktionalen Programmierung in C++ begann bereits mit dem ersten C++ Standard C++98. Und genau C++98 ist Inhalt dieses Artikels.

C++98

Template Metaprogrammierung

Template Metaprogrammierung ist das Programmieren mit Templates zur Compilezeit. Bei der Template Instanziierung wird der temporäre Sourcecode erzeugt, aus dem der Compiler den ausführbaren Code generiert. Die Abbildung stellt dies schematisch für das Klassen-Template Factorial dar. 

Das Factorial Klassen-Template ist der Klassiker und darf daher in keinem Artikel fehlen, in dem das Wort Template Metaprogrammierung erwähnt wird.

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

// factorial.cpp

#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 << std::endl;

  std::cout << "Factorial<4>::value: " << Factorial<4>::value << std::endl;
  std::cout << "Factorial<5>::value: " << Factorial<5>::value << std::endl;
  
  std::cout << std::endl;

}

Das Programm produziert das erwartete Ergebnis:

Dass das Programm das richtige Ergebnisse erzielt, ist nicht so interessant. Interessant ist vielmehr, welche Mechanismen unter der Decke wirken.

Template Metaprogrammierung ist eine rein funktionale Programmiersprache, die Turing vollständig ist. Das heißt, Template Metaprogrammierung ist eine auch im strengeren Sinne funktionale Programmiersprache (rein funktional) und mit ihre lässt sich alles berechnen, was berechnet werden kann (Turing vollständig).

Worin sich ein rein funktionale Programmiersprache auszeichnet, das werde ich in den nächsten Artikel klären. Nur soviel. Bei der Template-Instanziierung Factorial<5>::value wird das allgemeine Klassen-Template (Zeile 5 - 8) aufgerufen und im Klassenkörper das Klassen-Template Factorial<4>::value aufgerufen. Diese rekursiven Aufrufe enden mit Factorial<0>::value, den in diesem Fall kommt das vollständig spezialisierte Klassen-Template in Zeile 10 - 13 zum Einsatz.

Schematisch dargestellt stößt die Template-Instanziierung Factorial<5>::value zur Compilezeit ein rekursiven Prozess an, so dass das Ergebnis der Berechnung bereits zum Compilezeit vorliegt. Aus der Sicht der ausführbaren Datei ist es kein Unterschied, ob Factorial<5>::value oder 120 in der Ausgabeanweisung von std::cout steht.

Was sind nun die funktionalen Charakteristiken der Template Metaprogrammierung, die sich an dem Klassen-Template Factorial festmachen lassen.

Factorial besitzt keinen Zustand und keine veränderlichen Daten, wendet Rekursion an und wird erst dann ausgeführt, wenn Factorial<5>::value aufgerufen wird.  Das soll es aber schon zur Template Metaprogrammierung gewesen sein. Genauer kannst du das auch in dem Linux-Magazin Artikel Magischer Mechanismus nachlesen.

STL Algorithmen

Was haben die Algorithmen der Standard Template Library (STL) mit der funktionalen Programmierung gemein? Ganz viel. Zum einen war einer ihrer Väter Alexander Stephanov ein großer Fan der funktionalen Programmierung, zum anderen sind viele Algorithmen der STL sogenannte Funktionen höher Ordnung. Funktionen höherer Ordnung sind ein Kerncharakteristik der funktionalen Programmierung.

Funktionen höherer Ordnung sind Funktionen, die andere Funktionen als Argumente annehmen oder zurückgeben können.

Insbesondere die Eigenschaft, dass viele STL Algorithmen Funktionen als Argumente annehmen können, ist der Grund für die Mächtigkeit der STL. Beispiele gefällig? Der Einfachheit halber spreche ich in meinen folgen Zeilen von Containern und nicht Bereichen.

• std::transform modifiziert die Elemente seines Containers mit der Hilfe einer Funktion, die genau ein Argument besitzt.
• std::remove_if entfernt alle Elemente seines Containers, die eine Eigenschaft erfüllen. Die Eigenschaft wird durch ein sogenanntes Prädikat definiert. Ein Prädikat ist eine Funktion, die für ihre Argumente true oder false zurückgibt.
• std::accumulate wendet auf alle Elemente seines Containers paarweise eine Funktion an die, die zwei Argumente besitzt. Der Algorithmus reduziert dabei den Container sukzessive auf einen Wert.

Nun fehlen nur noch alle drei Funktionen in Aktion.

 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

// algorithm.cpp

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main(){

  std::cout << std::endl;

  std::vector<int> myVec{1,2,3,4,5,6,7,8,9};

  std::cout << "original:         ";
  for (auto a: myVec) { std::cout << a << " ";}

  std::cout << "\n\n";
  
  std::transform(myVec.begin(),myVec.end(),myVec.begin(), [](int i){ return i*i; });

  std::cout << "std::transform:   ";
  for (auto a: myVec) { std::cout << a << " ";}
  
  std::cout << "\n\n";
  
  myVec={1,2,3,4,5,6,7,8,9};
  
  auto logicalEnd= std::remove_if(myVec.begin(),myVec.end(), [](int i){ return !((i < 3) or (i > 8)); });
  myVec.erase(logicalEnd,myVec.end());
  
  std::cout << "std::remove_if:   ";
  for (auto a: myVec) { std::cout << a << " ";}
  
  std::cout << "\n\n";
  
  myVec={1,2,3,4,5,6,7,8,9};
  
  std::cout << "std::accumulate:  ";
  auto fak= std::accumulate(myVec.begin(),myVec.end(),1,[](int fir, int sec){ return fir * sec; });
  std::cout << "fak(10): " << fak << std::endl;
  
  std::cout << std::endl;

}

Ich habe bewusst Lambda-Funktionen eingesetzt. Auch wenn die Algorithmen der STL mit allem umgehen können, was sich wie eine Funktion verhält, sollen doch Lamba-Funktion die erste Wahl sein. Erst mit C+11 kennt C++ Lambda-Funktionen. Das trifft natürlich auch auf die drei weiteren Feature aus C++11 zu, die ich in dem Beispiel verwendet habe: Automatische Typableitung mit auto (Zeile 22, 32 und 39) Vereinheitliche Initialisierung (Zeile 12, 26 und 36) und die Range-basierte for-Anweisung (Zeile 22 und 32). 

Das Programm ist insbesondere mit der Ausgabe selbsterklärend. Nur auf eine Besonderheit der Algorithmen der STL will ich in Zeile 28 eingehen. Der std::remove_if Algorithmus entfernt wie alle generischen Algorithmen der STL kein Element aus seinem Container, sondern gibt nur das logische Ende des neuen Containers zurück. Dieses logische Ende verwendet die myVec.erase Methode, die den Container auf seine physikalische Länge kürzt.

Die Methode erase ist kein generischer Algorithmus der STL, sondern eine Methode des std::vector. 

Wie geht's weiter?

Eigentlich wollte ich in diesem Artikel deutlich mehr erzählen. Im nächsten Artikel geht es dann aber mit dem Technical Report 1 aus dem Jahr 2005 weiter. Vor allem interessieren mit die zwei Funktionen std::bind und std::function, die eine ganz neue funktionale Programmiertechnik in C++ hoffähig machen: Partielle Funktionsapplikation. Partielle Funktionsapplikation ist in einer ähnlichen Form in der funktionalen Programmierung als Currying oder auch Schönfinkeln bekannt. Schönfinkeln, wenn das nicht Spannung verspricht?

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.