… & Kontext: Funktionen höherer Ordnung

Babel-Bulletin  –  0 Kommentare

"Konsole & Kontext" ist eine gemeinsame Serie von Golo Roden und Michael Wiedeking, in der sich die beiden regelmäßig mit Konzepten der (funktionalen) Programmierung beschäftigen. Während "Konsole & …" die praktische Anwendung dieser Konzepte in JavaScript und Node.js zeigt, erläutert "... & Kontext" deren jeweiligen eher theoretischen Hintergrund.

Eigentlich ist es recht praktisch, wenn Funktionen genauso behandelt werden können wie andere Werte. Die beim letzten Mal beschriebenen Lambda-Ausdrücke können in der Regel also sowohl als Parameter übergeben als auch als Ergebnis einer Funktion geliefert werden. Damit eröffnen sich völlig neue Horizonte, kann man doch nun Funktionen schreiben, die für beliebige Anforderungen die passenden Funktionen liefern können.

Funktionen, die Funktionen liefern, nennt man Funktionen höherer Ordnung. Wie der Name schon sagt, ist das etwas "Höheres" und möglicherweise nicht auf Anhieb zu verstehen. Programmiersprachen, die nicht den Luxus haben, Funktionen als "Bürger erster Klasse" verwenden zu können, müssen sich da meist anders behelfen.

In objektorientierten Sprachen bedient man sich etwa eines Tricks: dem Strategie-Muster. Die Idee dahinter ist ein Objekt, dass die zu verwendende Strategie kapselt. Soll etwa ein Array sortiert werden, gibt es dafür die unterschiedlichsten Methoden, beispielsweise den Quicksort-, den Mergesort-, Bucketsort- und nicht zuletzt den Bubblesort-Algorithmus. Die Algorithmen funktionieren für unterschiedliche Randbedingungen unterschiedlich gut.

So liegt man etwa mit dem Quicksort so lange gut und richtig, solange die Elemente nicht schon vorsortiert sind, da er in diesem Fall von einem Algorithmus mit nahezu logarithmischem Verhalten bezüglich der Größe des Arrays zu einem mit inakzeptabel quadratischem Aufwand wird. Dahingegen degeneriert der Mergesort-Algorithmus nicht, benötigt dafür aber zusätzlichen Speicherplatz, kann also die Sortierung nicht in dem zu sortierenden Array selbst vornehmen. Der Bubblesort versagt in der Regel schon bei kleinen Arrays (was selbst Barack Obama (damals noch Senator) bei einem Interview bei Google zum Besten geben konnte).

Legt man nun für jedes gewünschte Verfahren einen Schlüssel der Art SortType fest (etwa QUICK, MERGE, BUCKET bzw. BUBBLE), kann man eine Funktion anbieten, die Arrays sortiert, wobei der Schlüssel festlegt, wie konkret sortiert werden soll.

// T[] sort(T[] array, SortType type) {
function sort(array : T[], type : SortType) ⟶ T[] {
switch (type) {
case QUICK:
// Quicksort
case MERGE:
// Mergesort
// ...
// usw.
}
}

Das macht nun aber einen sehr unobjektorientierten Eindruck. Und hier kommt das Strategie-Entwurfsmuster ins Spiel. Man definiert ein Interface, dass die grundsätzliche Aufgabe des Sortierens beschreibt.

interface Sorter() {
// T[] sort(T[] array);
sort(array : T[]) ⟶ T[];
}

Nun kann man beliebige Sortierverfahren ergänzen, ohne Zugriff auf obige sort-Funktion haben zu müssen. Deren Implementierung ändert man dann wie folgt:

// T[] sort(T[] array, Sorter sorter) {
function sort(array : T[], sorter : Sorter) ⟶ T[] {
return sorter.sort(array);
}

Um einen beliebigen Sortieralgorithmus zu ergänzen, bedarf es nun nur eines Objekts, das der Schnittstelle Sorter genügt. Dieses Objekt lässt sich nun beliebig konfigurieren, es kann die nötigen Ressourcen beschaffen und so das Array bestmöglich sortieren. Und dieses Objekt lässt sich nach Belieben weiterreichen. Es kann also nicht nur wie demonstriert als Parameter übergeben, sondern auch als Rückgabewert geliefert werden.

// Sorter findBestSorter(Int array_size, Type element_type, Hint hint) {
function findBestSorter(
array_size
: Int,
element_type : Type,
hint
: Hint
) ⟶ Sorter {
// ... best_sorter = new SuperDuperSorter(…) …
return best_sorter;
}

Das Strategie-Muster findet natürlich nicht nur bei diesen komplizierteren Ansprüchen Anklang, sondern beispielsweise auch ganz banal bei der Sortierung der Elemente selbst. Will man etwa ein Array von Personen sortieren, muss man natürlich wissen nach welchem Kriterium sortiert werden soll. Die Personen könnten ja nach dem Nachnamen, dem Vornamen, der Personalnummer, nach dem Geburtsdatum oder nach der Postleitzahl ihres Wohnortes sortiert werden.

interface Comparator<T> {
// Boolean lessOrEqual(T a, T b);
lessOrEqual(a : T, b : T) ⟶ Boolean;
}

Bei vorgegebenem Sortieralgorithmus könnte es demnach einen Comparator geben, der nur wissen muss, wie zwei Werte beziehungsweise Objekte in dem zu sortierenden Array zu vergleichen sind:

// T[] sort(T[] array, Comparator<T> comparator);
function sort(array : T[], comparator : Comparator<T>) ⟶ T[];

Können in einer Programmiersprache Funktionen wie Objekte umhergereicht werden, ist das Strategie-Muster obsolet. Anstatt die Abbildungsvorschrift eher umständlich in ein Objekt verpacken zu müssen, kann die Funktion direkt verwendet werden. Das lässt sich schön am Beispiel des Comparators zeigen. Er bietet eine Funktion, die zum Beispiel bei zwei Personen sagt, ob die eine kleiner oder gleich einer anderen Person ist. Die Schnittstelle für Personen sieht dann wie folgt aus:

// Person[] sort(Person[] array, ((Person, Person) ⟶ Boolean) lessOrEqual);
function sort(
array
: Person[],
lessOrEqual
: ((Person, Person) ⟶ Boolean)
) ⟶ Person[];

Soll ein Personen-Array pa nun nach den Nachnamen sortiert werden, ist eine entsprechende Funktion zu übergeben, die anhand des Nachnamens entscheidet, ob eine Person vor oder hinter einer anderen Person einsortiert werden soll.

result ← sort(pa, (a, b) ⟼ a.lastName ≤ b.lastName)

Bei diesem Beispiel wird davon ausgegangen, dass die Typen in dem gegebenen Lambda-Ausdruck vom Compiler selbstständig ermittelt werden können und dass für die Nachnamen, was auch immer die für einen Typ haben mögen, die Kleiner-oder-gleich-Relation ≤ definiert ist.

Jetzt hat sich der Entwickler also die Mühe gegeben, die Ordnung anhand der Nachnamen festzulegen. Was ist aber, wenn die sort-Funktion in einem Kontext die Sortierreihenfolge umdrehen möchte, ohne den Programmierer erneut bemühen zu wollen? Das könnte beispielsweise bei einer tabellarischen Darstellung des Arrays der Fall sein, bei der der Anwender die Sortierung durch Anklicken der Spaltenüberschrift ändern kann.

Die Umkehrung der Reihenfolge ist unabhängig von der aktuellen Sortierreihenfolge und sogar unabhängig von irgendeinem konkreten Typ. Es kann also eine allgemein gültige Funktion angeboten werden, mit der man die Sortierfunktion so manipulieren kann, dass sie zukünftig in umgekehrter Reihenfolge sortiert. Dazu müssen nämlich nur die Parameter vertauscht werden. Anstatt ab ist also immer nur ba zu berechnen; oder generell statt compare(a, b) nunmehr compare(b, a).

// ((T, T) ⟶ Boolean) invert(((T, T) ⟶ Boolean) compare) {
function invert(compare : ((T, T) ⟶ Boolean)) ⟶ ((T, T) ⟶ Boolean) {
return (a, b) ⟼ compare(b, a);
}

Mit der invert-Funktion lässt sich die Reihenfolge umdrehen. Die Funktion invert bekommt also eine Funktion übergeben und liefert eine neue gleiche Schnittstelle. Das gilt für Lamda-Ausdrücke gleichermaßen wie für Variablen, die auf diese verweisen.

c : ((Person, Person) ⟶ Boolean);
c ← (a, b) ⟼ a.lastName ≤ b.lastName;
sort(array, invert(c));
sort(array, invert((a, b) ⟼ a.lastName ≤ b.lastName));

Eine entsprechend aufgebohrte sort-Funktion würde dann anhand eines reverse-Flags erkennen, ob die Sortierung umzudrehen ist.

// T[] sort(T[] array, ((T, T) ⟶ Boolean) lessOrEqual) {
function sort(
array
: T[],
reverse
: Boolean,
lessOrEqual
: ((T, T) ⟶ Boolean)
) ⟶ T[] {
if (reverse) {
lessOrEqual = invert(lessOrEqual);
}
// alles andere wie bisher
}

Das Schöne ist, dass eine derartige Manipulation von Funktionen wirklich beliebig funktioniert. Denn es muss ja nicht unbedingt möglich sein, dass die Schnittstelle von sort verändert werden kann. Ist dies nämlich der Fall, kann man nur den Aufruf von sort verändern, ohne die Schnittstelle anzufassen.

s : (T[], ((T, T) ⟶ Boolean)) ⟶ T[];
s ← sort;
if (reverse) {
s ← (array, comparator) ⟼ s(array, invert(comparator));
}
s(…); // alles andere wie bisher mit s statt sort

Das letzte Beispiel zeigt, dass es hilfreich ist, irgendeine Möglichkeit zu haben, auf bereits existierende benannte Funktionen zugreifen zu können. Natürlich könnte man auch darauf verzichten und es immer explizit machen, also anstatt ssort ausführlicher

s ← (array, compare) ⟼ sort(array, compare);

schreiben. Aber das ist sehr umständlich, wenn man weiß, dass es genau das ist, was sort macht.

Schöpft man alle Möglichkeiten aus, dann können Funktionen analog zum Fabrik-Muster Funktionen liefern; diese können wieder Funktionen liefern, Funktionen können mit Funktionen kombiniert werden usw. Beispielsweise kann eine Funktion ganz einfach dazu gebracht werden, ihre Parameter und Ergebnisse auszugeben. Ist etwa eine Funktion f : (T, T) ⟶ T gegeben, lässt sich mit logging(f) recht einfach eine protokollierende Variante von f erzeugen, wenn logging wie folgt definiert wurde:

// ((T, T) ⟶ T) logging(f : ((T, T) ⟶ T)) {
function logging(f : ((T, T) ⟶ T)) ⟶ ((T, T) ⟶ T) {
return (a, b) ⟼ {
result : T;
resultf(a, b);
print("(" + a + ", " + b + ") ⟼ " + result);
return result;
}
}

Funktionen lassen sich natürlich auch miteinander kombinieren. Die meisten der obigen Funktionen wurden der Einfachheit halber nur mit Parametern vom Typ T ausgestattet oder mit einem konkreten Typ wie Person. In Wirklichkeit lassen sich viele Funktionen viel allgemeiner definieren und dementsprechend viel allgemeiner verwenden. Nachfolgende Funktion kann beliebige Funktionen f und g miteinander verknüpfen, vorausgesetzt, dass der Rückgabewert von f als Eingabewert von g verwendet werden kann.

function concat(f : (A ⟶ B), g : (B ⟶ C)) ⟶ (A ⟶ C) {
return (a : A) ⟼ g(f(a));
}

f ← concat(sin, cos);
print(f(x)) // ⟼ cos(sin(x))

Ein anderer interessanter Anwendungsfall ist das Definieren von Funktionen, bei denen ein oder mehrere Parameter vorbesetzt werden. Damit wird etwa aus einer Funktion mit zwei Parametern eine mit einem Parameter. So kann aus einer Addition, die eigentlich zwei Parameter hat, eine Inkrement-Funktion plusOne erzeugt werden, indem man einen der Parameter fest mit 1 besetzt.

function curry(f : ((A, B) ⟶ C), a : A) ⟶ (B ⟶ C) {
return (b : B) ⟼ f(a, b);
}

add ← (a, b) ⟼ a + b;
plusOne ← curry(add, 1);
// plusOne ≡ (b) ⟼ 1 + b
mul ← (a, b) ⟼ a · b;
timesTwo ← curry(mul, 2);
// timesTwo ≡ (b) ⟼ 2 · b
timesTwoPlusOne ← concat(timesTwo, plusOne);
// plusOne(timesTwo(b)) ≡ (b) ⟼ 1 + (2 · b)
print(timesTwoPlusOne(3)) // ⟼ 7

Funktionen wie curry und concat sind in "echten" funktionalen Sprachen typischerweise vordefiniert. Diese Funktionen sind so wichtig, dass sie einen eigenen Blog-Eintrag verdienen. Bei der Gelegenheit wird auch geklärt werden, warum die eine Funktion curry heißt.

Bei der hier verwendeten (fiktiven) Sprache wird der Typ nach einem zu definierenden Parameter oder einer zu definierenden Variable geschrieben. Ob das die Lesbarkeit bei Abbildungstypen erhöht, kann jeder für sich entscheiden – weshalb die "normale" Notation jeweils als Kommentar vorangestellt wurde. Die "Pfeiltypen" machen das ganze etwas unübersichtlich, insbesondere deswegen, weil man zunächst nicht weiß, was denn etwa

(T, T) ⟶ Boolean

bedeuten könnte. Mit der Zeit gewöhnt man sich daran und weiß dann deshalb, dass es sich dabei höchstwahrscheinlich um eine Relation handelt. Man kann dem aber trotzdem nicht ansehen, welchem konkreten Zweck das dient; aber auch diese Information lernt man recht bald, aus der näheren Umgebung zu lesen. Unter C# und Java hat man jenes Problem aber ohnehin nicht, denn dort gibt es diese anonymen Pfeiltypen nicht. In C# kann man nur die Delegates nutzen, die immer einen Namen haben. Und in Java 8 muss an entsprechender Stelle immer ein Interface-Name stehen.

Wie eingangs erwähnt, lassen sich die meisten dieser Mechanismen auch mit Hilfe objektorientierter Muster umsetzten – allerdings nicht so bequem und in der Regel nicht so effizient. Trotz der Einfachheit der Beispiele lässt sich vielleicht erahnen, welches Potenzial diese Art der funktionalen Programmierung hat. Und da Funktionen von Nebeneffekten frei sind, können sie auch in nebenläufigen Anwendungen nach Belieben eingesetzt werden. Aber davon soll ein andermal mehr erzählt werden.