First Class functions

Funktionale Programmiersprachen zeichnen sich unter anderem durch First Class Functions aus. Was heißt das? Funktionen sind Daten sehr ähnlich: Sie können zur Laufzeit erzeugt, in Datenstrukturen gespeichert, als Argumente oder Rückgabewerte von Funktionen verwendet werden. Klassischerweise dienen gerne Dictionaries zum Speichern von Funktionen. Der Dispatch Table der arithmetischen Grundfunktionen aus Abbildung 1 speichert anonyme Funktionen (Lambda-Funktionen), die auf Anfrage die Ergebnisse liefern. Die Rechenmaschine lässt sich zur Laufzeit um eine neue Rechenoperation erweitern.

Abbildung 1: Funktionale Programmiersprachen zeichnen sich unter anderem durch First Class Functions aus.

Mit den Funktionsobjekt-Wrappern wie "function<double(double,double)>" der kommenden C++-Bibliothekserweiterung und der Lambda-Bibliothek von Boost, ist der Dispatch Table rasch in C++ implementiert. Der künftige C++-Standard C++0x wird Lambda-Ausdrücke als direkte Erweiterung der Kernsprache besitzen.

std::map< const char , function<double(double,double)> > dispTable;
        dispTable.insert( std::make_pair('+', _1 + _2));
        dispTable.insert( std::make_pair('-', _1 - _2));
        dispTable.insert( std::make_pair('*', _1 * _2));
        dispTable.insert( std::make_pair('/', _1 / _2))

Durch die Platzhalterausdrücke "_1" und "_2" wird in C++ ein Lambda-Ausdruck definiert. Zusätzlich muß die Map der Standard Template Library mit dem Typ des Schlüssels und des Wertes, dem Funktionsobjekt, bekannt gemacht werden.

Funktionen höherer Ordnung

Funktionen höherer Ordnung sind Funktionen, welche Funktionen entweder als Argumente annehmen oder als Rückgabewert zurückgeben. Die klassischen Beispiele sind die Funktionen "map", "filter" und die Funktionenfamilie "fold*", da sie typische Anwendungsfälle für die Listenverarbeitung abstrahieren:

• wende eine Funktion sukzessive auf die Elemente einer Liste an
• filtere Elemente aus einer Liste heraus
• reduziere eine Liste auf einen Ausgabewert, indem die Listepaare akkumuliert werden.

Ein paar Beispiele (Abbildung 2) aus Haskell sollen dies verdeutlichen.

Abbildung 2: Die Funktionen höherer Ordnung map, filter und fold*.

Der Ausdruck "(\x -> x*x)" ist die Lambda-Funktion in Haskell, die ein x auf dessen Quadrat abbildet. Die anonyme Funktion kann direkt als Argument der "map"-Funktion verwendet werden. Noch ein paar Worte über die Funktionenfamilie "fold*": Sie ist die mächtigste der drei Funktionen, da durch sie sowohl "map" als auch "reduce" implementiert werden kann. Darüber hinaus existieren Variationen, die die Liste von rechts oder von links, mit und ohne Initialwert reduzieren.

Alle drei Funktionen sind elementare Bausteinchen der funktionalen Programmierung und finden sich in den anderen funktionalen Programmiersprachen wieder. Die imperativen Programmiersprachen Python und C++ bieten sie auch an.