Monaden in C++

Monaden in C++? Was für ein seltsamer Titel für einen Artikel. Doch so seltsam ist er gar nicht. Mit std::optional wird C++17 um eine Monade erweiterte. Die Ranges-Bibliothek von Eric Niebler und die erweiterten Futures, auf die wir in C++20 hoffen dürfen, sind Monaden.

In seinem Secret Lightning Talk auf Meeting C++ 2016 hat Bjarne Stroustrup auf seinen Slides ein paar der neuen Concepts Lite vorgestellt, die wir wohl mit C++20 erhalten werden. Unter anderem waren da auch mathematische Konzepte wie Ring und Monade. Meine Vermutung verstärkt sich immer mehr und mehr. Modernes C++ wird durch mathematische Konzepte für die Zukunft gestählt.

std::optional

std::optional ist durch Haskells Maybe Monade inspiriert. std::optional, das ursprünglich schon in den kleinen Standard C++14 aufgenommen werden sollte, steht für eine Berechnung, die einen Wert enthalten kann. So muss der find-Algorithmus oder die Abfrage eines Hashtabelle damit umgehen können, dass die Anfrage nicht beantwortet werden kann. Gerne werden spezielle Werte, die für das Vorhandensein keines Ergebnisses stehen (sogenannte Nicht-Ergebnisse), verwendet. Als Nicht-Ergebnis haben sich Null-Zeiger, leere Strings oder auch besondere Integer-Wert etabliert. Diese Technik ist aufwändig und fehleranfällig, da diese Nicht-Ergebnisse besonders behandelt werden müssen und sich syntaktisch nicht von einem regulären Ergebnis unterschieden. std::opional erhält im Falle eines Nicht-Ergebnisses keinen Wert. Das Beispiel stellt std::optional genauer vor.

 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

// optional.cpp

#include <experimental/optional>
#include <iostream>
#include <vector>

std::experimental::optional<int> getFirst(const std::vector<int>& vec){
  if (!vec.empty()) return std::experimental::optional<int>(vec[0]);
  else return std::experimental::optional<int>();
}

int main(){
    
    std::vector<int> myVec{1, 2, 3};
    std::vector<int> myEmptyVec;
    
    auto myInt= getFirst(myVec);
    
    if (myInt){
        std::cout << "*myInt: "  << *myInt << std::endl;
        std::cout << "myInt.value(): " << myInt.value() << std::endl;
        std::cout << "myInt.value_or(2017):" << myInt.value_or(2017) << std::endl;
    }
    
    std::cout << std::endl;
    
    auto myEmptyInt= getFirst(myEmptyVec);
    
    if (!myEmptyInt){
        std::cout << "myEmptyInt.value_or(2017):" << myEmptyInt.value_or(2017) << std::endl;
    }
    
}

std::optional befindet sich zum aktuellen Zeitpunkt im Namensraum experimental. Das wird mit C++17 ändern. In der Funktion getFirst in Zeile 7 wird std::optional verwendet. getFirst gibt das erste Element zurück (Zeile 8), falls es existiert. Falls nicht, ein std::optional<int> Objekt (Zeile 9). In der main-Funktion kommen zwei Vektoren zum Einsatz. Die Aufrufe getFirst in Zeile 17 und 27 geben die std::optional Objekte zurück. Im Falle von myInt (Zeile 19) enthält das Objekt einen Wert, im Falle von myEmptyInt (Zeile 29) keinen Wert. Nun lässt sich der Wert von myInt (Zeile 20 - 22) ausgeben. Die Methode value_or in Zeile 22 und 30 gibt abhängig davon, ob das std::optional Objekt einen Wert enthält, diesen oder einen Default-Wert zurück.

Die Abbildung zeigt die Ausgabe des Programms mit Hilfe des online-Compilers auf cpprefence.com.

Erweiterungen der Futures

Modernes C++ unterstützt Tasks.

Tasks sind Paare von std::promise- und std::future-Objekten, die über einen Kanal verbunden sind. Dieser Kanal kann auch über Threadgrenzen hinweg kommunizieren. Der std::promise (Sender) schiebt einen Wert in den Kanal, auf den der std::future (Empfänger) wartet. Dabei kann der Sender seinen Kanal zu dem Empfänger nicht nur für einen Wert, sondern auch eine Benachrichtigung oder eine Ausnahme (eng. Exception) verwenden. Die Details zu Task in C++11 habe ich ausführlich in mehreren Artikeln beschrieben: Task.

Die einfachste Art, einen Promise zu erzeugen, ist das Funktions-Template std::async. Dieser verhält sich wie ein asynchroner Funktionsaufruf.

int a= 2000
int b= 11;
std::future<int> sum= std::async([=]{ return a+b; });
std::cout << sum.get() << std::endl;

Der Aufruf std::async führt mehrere Aktionen aus. Zum einen erzeugt er die beiden Kommmunikationsendpunkte Promise und Future, zum anderen verbindet er sie mit einem Kanal. In dem Promise wird die Lambda-Funktion [=]{ return a+b;} als Arbeitspaket ausgeführt, die sich ihre Argumente a und b aus dem aufrufenden Kontext schnappt. Dabei entscheidet die C++-Laufzeit, ob der Promise in dem gleichen oder einem separaten Thread ausgeführt wird. Entscheidungskriterien können die Größe des Arbeitspakets, die Auslastung des Systems oder auch die Anzahl der Rechenkerne sein.
Mit dem sum.get() Aufruf holt sich der Future (In der Zukunft) sein Ergebnis aus dem Kanal ab. Dies kann er nur einmal. Falls der Promise (Das Versprechen) seinen Wert noch nicht erzeugt hat, blockiert der get-Aufruf des Futures.

Tasks erlauben den deutlich einfacheren und sicheren Umgang mit Threads, den sie besitzen keinen gemeinsamen Zustand. Kritische Wettläufe (eng. race conditions) sind damit unmöglich, Verklemmungen (eng. dead locks) deutlich seltener. Trotzdem besitzt ihre C++11-Umsetzung einen großen Nachteil. Die Komposition von std::future-Objekte ist nicht möglich. Damit räumen die erweiterten Futures in C++20 auf. Die Tabelle stellt die wichtigsten Funktionen der erweiterten Futures vor.

Das folgende Codeschnipsel stelle einige Beispiele aus dem offiziellen Proposal n3721 vor.

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

future<int> f1= async([]() {return 123;});

future<string> f2 = f1.then([](future<int> f) {
     return f.get().to_string(); 
});

future<int> futures[] = {async([]() { return intResult(125); }), 
                         async([]() { return intResult(456); })};

future<vector<future<int>>> any_f = when_any(begin(futures), end(futures));


future<int> futures[] = {async([]() { return intResult(125); }), 
                         async([]() { return intResult(456); })};

future<vector<future<int>>> all_f = when_all(begin(futures), end(futures));

Der Future f2 in Zeile 3 wird dann ausgeführt, wenn der Future f1 fertig ist. Die Verkettung lässt sich natürlich deutlich erweitern: f1.then(...).then(...).then(...). Der Future any_f in Zeile 10 wird ausgeführt, wenn einer seiner Futures fertig ist. Im Gegensatz wird der Future all_f in Zeile 16 ausgeführt, wenn alle seine Future fertig sind.

Eine Frage bleibt natürlich noch bestehen. Was haben Futures mit funktionaler Programmierung gemein? Eine Menge! Die erweiterten Future sind eine Monade. Im Artikel Reine Funktionen wird das Konzept von Monaden genauer erläutert. Die zentrale Idee der Monade ist es, dass eine Monade einen einfachen Typ in einen komplexeren Typ abbildet und die Komposition auf diesem komplexen Typ ermöglicht. Dazu benötigt die Monade natürlich eine Funktion, die den einfachen Typ in den komplexeren Typ hochhebt (eng. lifted). Zum andern benötigt sie eine Funktion, die die Komposition mit dem komplexen Typ ermöglicht. Genau diese Funktionalität erfüllen die Funktion make_ready_future, then und future<future<T>>. make_ready_future transformiert einen einfachen Typ in einen komplexen Typ, einen monadischen Wert. Diese Funktion wird in der Tabelle Einheitsfunktion genannt und besitzt den Namen return in Haskell. Die zwei Funktionen then und future<future<T>> sind äquivalent zu dem bind-Operator in Haskell. Der bind-Operator sorgt dafür, dass ein monadischer Wert in einen anderen monadischen Wert transformiert werden kann. bind stellt die Funktionskomposition in der Monade dar.
Durch die Methode when_any wird std::future sogar zur Monade Plus. Diese setzt in Haskell von ihren Instanzen voraus, das sie Monaden sind und darüber hinaus eine Funktion msum anbieten. Danke seiner erweiterten Monaden Struktur kann std::future das Konzept der Addition auf std::future-Objekten anbieten.

Für eine tiefere Lektüre der anspruchsvollen Materie ist der exzellente Blogartikel von Bartosz Milewski und sein Vorstellung "C++17: I See a Monad in Your Future!" ein unbedingtes Muss.

Wie geht's weiter?

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. Mit dem CRTP Idiom und Expression Templates ist C++ durchaus lazy. Im nächsten Artikel geht es daher mit dem berühmt berüchtigten CRTP Idiom weiter.

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.