Unveränderliche Daten

Rein funktionale Programmiersprachen wie Haskell zeichnen sich vor allem dadurch aus, dass ihre Daten unveränderlich sind. Damit sind Zuweisungen der Form x=x+1 oder entsprechend ++x nicht möglich. Die Konsequenz ist, dass Haskell keine Schleifen, sei es for, while oder until, kennt. Diese basieren auf dem Modifizieren einer Schleifenvariable. Haskell modifiziert keine bestehenden Daten, sondern erzeugt bei Bedarf neue. Dabei verwendet der Haskell Compiler die alten, unveränderliche Daten wieder.

Unveränderliche Daten

Unveränderliche Daten besitzen eine schöne Eigenschaft. Sie sind implizit thread-safe, denn es fehlt ihnen eine notwendige Bedingung für einen kritischen Bereich. Ein kritischer Bereich zeichnet sich dadurch aus, dass zwei oder mehrere Threads gleichzeitig auf ein Datum zugreifen. Zu mindest ein Thread versucht dabei, dieses Datum zu verändern.

Quicksort in Haskell

Schön ist die Unveränderlichkeit der Daten in Haskells Quicksort Algorithmus zu sehen.

qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]

Der Quicksort Algorithmus qsort besteht aus zwei Funktionsdefinitionen. In der ersten Zeile wird der Quicksort, auf der leeren Liste angewandt, definiert. Dies ist die leere Liste. Die zweite Zeile stellt den allgemeinen Fall dar, in dem die Liste aus mindestens einem Element besteht: x:xs. Dabei bezeichnet x den Anfang und xs den Rest der Liste per Konvention.

Die Strategie des Quicksort-Algorithmus lässt sich fast direkt in Haskell ausdrücken. Verwende das erste Element der Liste x, das sogenannte Pivot-Element, füge (++) vor die einelementige Liste [x] alle die Elemente aus xs, die kleiner als x sind (qsort [y | y <- xs, y < x]) und hänge an die Liste [x] all die Elemente aus xs, die mindestens so groß wie x sind (qsort [y | y <- xs, y >= x]). Die Rekursion endet dann, wenn Quicksort auf die leere Liste angewandt wird. Zugegeben, die Kompaktheit von Haskell ist ungewohnt.

Der entscheidende Punkt des Algorithmus ist aber, dass bei jeder Rekursion eine neue Liste erzeugt wird. Wie schaut hingegen eine klassische Implementierung in C++ aus?

Quicksort in C++

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

void quickSort(int arr[], int left, int right) { 
  int i = left, j = right; 
  int tmp; 
  int pivot = arr[abs((left + right) / 2)]; 
  while (i <= j) { 
    while (arr[i] < pivot) i++; 
    while (arr[j] > pivot) j--; 
    if (i <= j) { 
      tmp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = tmp; 
      i++; j--; 
    }
  }
  if (left < j) quickSort(arr, left, j);
  if (i < right) quickSort(arr, i, right);
}

Keine Angst. Ich werde die Funktion nicht erklären. Mir reicht eine simple Beobachtung. In den Zeilen 9 - 11 werden die bestehenden Elemente überschrieben. Der Algorithmus arbeitet daher in-place und setzt veränderliche Daten voraus. Für das Überschreiben der alten mit den neuen Werten hat sich ein schöner Ausdruck in der funktionalen Programmierung etabliert: destructive assignment.

Zu Ehrenrettung von C++ muss ich aber sagen, dass es eine deutlich elegantere Implementierungen des Quicksort Algorithmus in C++ gibt, die auf dem std::partition Algorithmus basieren.

template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last)
 {
    if(first == last) return;
    auto pivot = *std::next(first, std::distance(first,last)/2);
    ForwardIt middle1 = std::partition(first, last, 
                         [pivot](const auto& em){ return em < pivot; });
    ForwardIt middle2 = std::partition(middle1, last, 
                         [pivot](const auto& em){ return !(pivot < em); });
    quicksort(first, middle1);
    quicksort(middle2, last);
 }

Der entscheidende Punkt ist aber, dass std::partition destructive assignment anwendet.

Wie steht es nun um die Unveränderlichkeit der Daten in C++?

Unveränderliche Daten in C++

Die Verwendung von unveränderlichen Daten basiert in C++ auf der Disziplin des Programmierers. Mit konstanten Daten, Template Metaprogrammierung und konstanten Ausdrücken bietet C++ dazu drei Möglichkeiten an. Die Optionen eins und zwei sind schnell vorgestellt, konstante Ausdrücke verdienen dagegen deutlich mehr Aufmerksamkeit.

Konstante Daten

Durch die Anweisung const int value= 1; wird value zum konstanten Wert.

Template Metaprogrammierung

Template Metaprogrammierung findet zur Übersetzungszeit statt. Zur Übersetzungszeit gibt es keine Veränderung. Daher sind alle Werte, die zur Übersetzungszeit ermittelt werden, konstant. Dies trifft natürlich auf die Berechnung von Factorial<5>::value zu.

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

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

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

Wem die kurze Erwähnung von Template Metaprogrammierung zu oberflächlich war, den verweise ich gerne auf meinen Artikel Funktional in C++98. 

Nun aber zu konstanten Ausdrücken und einem großen Sprung in die C++ Zukunft.

Konstante Ausdrücke

 C++11 kennt konstante Ausdrücke. Mit C++14 lassen sich als konstante Ausdrücke deklarierte Funktionen fast wie normale Funktionen verwenden.

C++ unterstützt konstante Ausdrücke in drei Formen: Als Variablen, benutzerdefinierte Typen und Funktionen. Das besondere an konstanten Ausdrücken ist, dass sie zur Übersetzungszeit ausgewertet werden können.

1. Durch den Ausdruck constexpr double pi= 3.14 wird pi zum konstanten Ausdruck. pi ist damit implizit const und muss durch einen konstanten Ausdruck 3.14 initialisiert werden.
2. Damit die Objekte eines benutzerdefinierte Typen zu konstanten Ausdrücken werden, gelten für den Typ einige Einschränkungen. So muss sein Konstruktor leer und selbst ein konstanter Ausdruck sein. So kann das Objekt nur Methoden verwenden, die selbst konstante Ausdrücke sind. Zur Übersetzungszeit sind natürlich auch keine Aufrufe von virtuellen Methoden möglich. Erfüllt der benutzerdefinierte Typ alle Einschränkungen, können seine Objekte zur Übersetzungszeit erzeugt und verwendet werden.
3. Für Funktionen als konstante Ausdrücke gelten ein paar wenige Einschränkungen, damit sie zur Übersetzungszeit ausgeführt werden können. Zum einen müssen alle Argumente konstante Ausdrücke sein. Zum anderen können sie keine statischen und thread-lokalen Daten enthalten.

Welche Mächtigkeit konstante Ausdrücke besitzen, zeigt das folgende Beispiel. In diesem werden benutzerdefinierte Literale verwendet um Entfernungen zur Übersetzungszeit zu berechnen.

 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

// userdefinedLiteralsConstexpr.cpp

#include <iostream>

namespace Distance{

  class MyDistance{
    public:
      constexpr MyDistance(double i):m(i){}

      friend constexpr MyDistance operator+(const MyDistance& a, const MyDistance& b){
        return MyDistance(a.m + b.m);
      }
      friend constexpr MyDistance operator-(const MyDistance& a,const MyDistance& b){
        return MyDistance(a.m - b.m);
      }
	  
      friend constexpr MyDistance operator*(double m, const MyDistance& a){
        return MyDistance(m*a.m);
      }
	  
      friend constexpr MyDistance operator/(const MyDistance& a, int n){
        return MyDistance(a.m/n);
      }
	  
      friend std::ostream& operator<< (std::ostream &out, const MyDistance& myDist){
        out << myDist.m << " m";
        return out;
      }
    private:
      double m;	  
  };

  namespace Unit{
    constexpr MyDistance operator "" _km(long double d){
      return MyDistance(1000*d);
    }
    constexpr MyDistance operator "" _m(long double m){
      return MyDistance(m);
    }
    constexpr MyDistance operator "" _dm(long double d){
      return MyDistance(d/10);
    }
    constexpr MyDistance operator "" _cm(long double c){
      return MyDistance(c/100);
    }
  }
  
}
  
constexpr Distance::MyDistance getAverageDistance(std::initializer_list<Distance::MyDistance> inList){
  auto sum= Distance::MyDistance{0.0};
  for (auto i: inList) sum = sum + i ;
  return sum/inList.size(); 
}


using namespace Distance::Unit;

int main(){

  std:: cout << std::endl;
  
  constexpr auto work= 63.0_km;
  constexpr auto workPerDay= 2 * work;
  constexpr auto abbrevationToWork= 5400.0_m;
  constexpr auto workout= 2 * 1600.0_m;
  constexpr auto shopping= 2 * 1200.0_m;
  
  constexpr auto distPerWeek1= 4*workPerDay-3*abbrevationToWork+ workout+ shopping;
  constexpr auto distPerWeek2= 4*workPerDay-3*abbrevationToWork+ 2*workout;
  constexpr auto distPerWeek3= 4*workout + 2*shopping;
  constexpr auto distPerWeek4= 5*workout + shopping;
  
  constexpr auto averageDistance= getAverageDistance({distPerWeek1,distPerWeek2,distPerWeek3,distPerWeek4});
  
  std::cout << "averageDistance: " << averageDistance << std::endl;        // 255900 m
  
  std::cout << std::endl;

}

Ich will hier nicht die Theorie zu konstanten Ausdrücken und benutzerdefinierten Literalen erschöpfenden erklären. Das habe ich bereits in den Artikeln zu constexpr und benutzerdefinierten Literalen getan. Zwei Beobachtungen sind aber wichtig.

1. Durch die Deklaration constexpr werden alle Variablen, Instanzen der Klasse MyDistance und Funktionen zu konstanten Ausdrücken. Der Compiler führt sie daher zu Compilezeit aus.
2. Bis auf die Ausgabefunktion std::cout sind alle Variablen, Instanzen und Funktionen als konstante Ausdrücke definiert. Das heißt, das ganze Programm wird bereits zur Übersetzungszeit ausgewertet. Damit sind natürlich auch alle verwendeten Variablen und Instanzen unveränderlich. Lediglich das Ergebnis des Programms 255900 m wird zur Laufzeit ausgegeben.

Wie geht's weiter?

Reine Funktionen sind mathematischen Funktionen sehr ähnlich. Sie sind der Grund dafür, das sowohl Haskell als auch Template Metaprogrammierung als rein funktionale Programmiersprache bezeichnet wird. Was genau reine Funktionen sind und mit welchen Einschränkungen sie zu kämpfen haben, das zeigt der nächste 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.