Programmiersprachen und Übersetzer
12 - Das Funktionale Programmierparadigma

Graphiken und Animationen

PreviousNext

Wir haben in der letzten Vorlesung das objektorientierte Paradigma besprochen und haben mit einer Kritik beendet. Angetreten ist dieses Paradigma und die damit verbundenen Designprinzipien, um Softwareentwicklung "im Großen", also in großen Softwareprojekten an denen viele Menschen arbeiten, möglich zu machen. Und in dieser Hinsicht hat das OO Paradigma einiges geleistet. Wir sind mit aktuellen Entwicklungsmodellen in der Lage viel viel größere Softwareprojekte zu realisieren, als wir das noch vor 40 Jahren waren. Teilweise ist das auf schnellere Hardware, was zu schnelleren Compile-Test-Zyklen führt, zurückzuführen. Aber das bessere Verständnis für die Probleme, die erst in großen Projekten sichtbar werden, hat ebenso dazu beigetragen. Die Modellierung von Software entlang den Objekten, die sie versucht abzubilden, erleichtert es uns Menschen darüber zu reden. Aber das OO Paradigma ist nicht ohne Kritik, wie wir gesehen haben.

Der grundlegende Konflikt, der bei der Softwareentwicklung großer Projekte auftritt, ist, dass ein solches Projekt viele interagierende Entitäten hat: Auf der Ebene der Entwicklung haben wir viele Menschen, die, verstreut über den ganzen Erdball, gemeinsam an einer Software arbeiten wollen. Dies erfordert einiges an Koordination, aber auch an Kommunikation; die Menschen müssen sich in ihrer Sprache über die Struktur der Software austauschen können (hier hat OO einiges geleistet). Auf der Ebene der Software haben wir ebenfalls viele interagierende Entitäten: Viele Module enthalten eine Vielzahl an Klassen, von denen Objekte instantiiert werden, die alle einen Zustand haben (Persistenz!) und sich gegenseitig Nachrichten zuschicken (Methodenaufruf!). Diese technische Komplexität kommt dann mit der begrenzten geistigen Kapazität von Menschen zusammen: Wir müssen sie verstehen, um sie beherschen zu können und um sie anderen mitteilen zu können.

Jetzt gibt es aber eine Kluft zwischen dem Quellcode, der die Klassen definiert, und dem Universum instantiierter Objekte und damit auch ein Problem: Im Gegensatz zu statischen Codestrukturen sieht man den dynamischen Zustand nicht. Wo der Quellcode, durch die Verwendung des imperativen Paradigmas, relativ lokal abläuft (Eine Zeile nach der anderen), ist der dynamische Zustand viel schwieriger zu fassen. Denn der Zustand eines Objektes ist die Kombination aller Änderungen, die dieses Objekt seit seiner GeburtSiehe Geburt von Objekten. erfahren hat. Wir versuchen diesen dynamischen Zustand besser fassbar zu machen, indem wir Invarianten einführen, die den Raum möglicher Belegungen eingrenzen. Aber selbst mit guten Invarianten müssen wir bei der Entwicklung immer die möglichen Zustände des Objektuniversums in unseren Köpfen nachvollziehen. All zu häufig fallen dabei die Randfälle, wo Objekte gerade noch die Invarianten einhalten, hinten runter und führen zu Softwarefehlern.

Es ist dieses Problem des Zustandsraums, dem sich das funktionale Paradigma annimmt. Mit diesem Paradigma eliminieren wir den veränderlichen Zustand. Lesen Sie den letzten Satz noch einmal, atmen Sie tief durch, und versuchen Sie die Tragweite dieser Entscheidung zu verstehen. Wir verbieten die Veränderung vom ZustandLassen Sie uns das gleich ein bisschen einschränken: Nur das reine funktionale Paradigma geht in dieser Radikalität gegen veränderlichen Zustand vor. Nur wenige Sprachen ziehen dies so extrem durch. Aber selbst abgeschwächte Formen führen zu einem völlig veränderten Nachdenken über Programmiersprachen. Bleiben Sie also dabei, wenn wir jetzt einmal das Extrem ausloten. Dieser radikale Schritt hat eine ganze Reihe von Implikationen, denen wir uns jetzt widmen werden, bevor wir darüber reden, wie man mit einer solch eingeschränkten Sprache nützliche Programme entwerfen kann.

Zunächst müssen wir uns einmal überlegen, was der Zustand eines Programms ist. All die Variablen, die wir haben, die lokalen, die globalen, und die einzelnen Parameter von Funktionsinstanzen. All das ist Zustand. Aber auch die Objekte, die wir nur indirekt über diese Variablen und über Referenzen erreichen könnenSiehe Mark-and-Sweep Garbage Collector., sind der Zustand eines Programms. Immer dann, wenn wir ein existierendes Objekt verändern, benötigen wir das Sprachkonzept "veränderlicher Zustand". Jedes Beschreiben eines Record-Felds, jedes Setzen eines Array-Elements, jedes Verändern einer Variable, all das verändert den existierenden Zustand. All das wollen wir verbieten. Einzig zwei Dinge werden uns gelassen: Wir können neue Objekte parametrisiert erzeugen, und wir können einen bisher ungebundenen Namen an ein existierendes Objekt binden. Etwas flapsiger (und ungenau) ausgedrückt, würde man sagen: Variablen können nicht überschrieben, Objekte nicht verändert werden.

Was hat diese Einschränkung zur Folge? Eine ganze Menge! Bei der Diskussion der OperationenSiehe Operationen und Seiteneffekte. und ihrer Abhängigkeiten haben wir den Begriff der Seiteneffekte eingeführt. Ein Seiteneffekt einer Operation führt dazu, dass die Operation über ihren Rückgabewert hinaus den Zustand der virtuellen Maschine verändert. Und es sind genau diese Seiteneffekte, die wir bei der funktionalen Programmierung verbieten werden.

Durch Seiteneffekte und globalen Zustand kann eine Prozedur einen Zustand besitzen und dadurch bei wiederholtem Aufruf mit denselben Argumenten jedesmal ein anderes Ergebnis liefern. Der globale Zustand, bzw. jeder andere veränderbare Ausführungskontext, agiert in solchen Situationen als Seitenkanal für die Prozedur:

counter = 0
def inc():
    global counter
    counter += 1
    return counter

print [inc(), inc(), inc()]

Wenn wir nun Prozeduren mit mathematischen Funktionen vergleichen, sehen wir, dass es hier eine Lücke gibt. Solche Prozeduren, die ihren Ausführungskontext verändern, sind keine Funktionen im mathematischen Sinne, da ihr Ergebnis nicht nur von ihren Eingabeparametern abhängt. Stellen Sie sich das einmal vor, wie das wäre, wenn die Addition in einem Ganzzahlring jedes Mal ein anderes Ergebnis liefern würde. So könnte ja niemand Mathematik machen! Aber in der Programmierung erlauben wir uns das, wenn wir veränderlichen Zustand haben.

Mit dem funktionalen Paradigma werden Prozeduren also zu echten mathematischen Funktionen, deren Ergebnis nur noch von den übergebenen Argumenten abhängt. Die Ausführung einer solchen Funktion hat keine Seiteneffekte und wir können Sie beliebig oft aufrufen, es wird immer das Gleiche dabei raus kommen. Auf diese Weise schafft es das funktionale Paradigma, dass nicht nur die Ausführung von Quellcode lokal ist, sondern auch, dass der Zustandsraum lokaler wird. Dies erleichtert es ungemein über die Korrektheit eines Programms nachzudenken.

Vergleichen wir die drei Paradigmen, die wir in dieser Vorlesung besprechen, so sehen wir eine Entwicklung in zwei Richtungen, ausgehend vom imperativen Paradigma. Dieses grundlegende Paradigma hat vier Elemente: Sequenzierung, komplexe Datentypen, Prozeduren und veränderlichen Zustand. Damit kann man schon ziemlich viel machen. Das objektorientierte Paradigma erweitert diesen Werkzeugkasten um die Methode, die Zustand und Prozedur vereint. Es entsteht eine Closure, eine Prozedur, die dynamisch erzeugten Zustand mit sich herumträgt (das Objekt, auf dem die Methode aufgerufen wird).

Das funktionale Paradigma geht einen anderen Weg: Anstatt ein weiteres Konzept einzuführen, schränkt es ein grundlegendes Konzept ein: Der veränderliche Zustand verliert seine Veränderlichkeit, was direkt dazu führt, dass Prozeduren zu Funktionen werden. Es hat aber auch zur Folge, dass einige Sprachkonstrukte keinen Nutzen mehr haben bzw. dass andere Konzepte größere Wichtigkeit erlangen.

Durch Seiteneffektfreiheit haben wir keine echten Variablen mehr und keine veränderlichen Objekte. Dies führt direkt dazu, dass Statements ohne Rückgabewerte keinen Sinn mehr haben. Außerdem hatten wir darüber geredetSiehe Iteration: Wiederholte Ausführung., dass Schleifen nur durch Seiteneffekte mit dem restlichen Code kommunizieren können. Beides fällt also in einer rein funktionalen Programmiersprache weg. HaskellEine rein funktionale Programmiersprache kennt einfach keine Schleifen! Alles, was wir an Konzepten in unserem funktionalen Werkzeugkasten (=Paradigma) haben wollen, muss einen Rückgabewert erzeugen, da dies der einzige Kanal ist, um Ergebnisse nach außen kommunizieren zu können. Es muss also alles ein Ausdruck werden.

Es stellt sich allerdings noch die Frage, wie man in einer Welt ohne Schleifen wiederholte Ausführung bewerkstelligen soll. Die Antwort darauf wird dem Erstsemester-Studierenden nicht gefallen: Rekursion. Bei der Rekursion hat jeder Rekursionsschritt einen Rückgabewert und wir können, bis zur Abbruchbedingung, eine variable Anzahl an Rekursionsschritten durchführen. Daher ist Rekursion für das funktionale Paradigma ein essenzielles Konzept.

Jedoch gibt es noch einige andere Fragen, denen wir uns im Folgenden widmen wollen: Wie kann man so überhaupt übersichtlich, effizient, und effektiv programmieren? Man könnte meinen, dass dies alles viel zu beschnitten ist. Aber mit dem funktionalen Paradigma kommen eine ganze Reihe von Sprachkonzepten, die es einfach machen funktional zu programmieren. Diese wollen wir uns im Folgenden anschauen.

Graphiken und Animationen

PreviousNext

Bevor wir uns den Operationen im funktionalen Paradigma zuwenden, müssen wir uns über die Objekte unterhalten. Durch die Freiheit von Seitenffekten sind alle Objekte in einem funktionalen Programm unveränderlich. Es sind also alles Immutable Objects, von denen wir an anderer Stelle schon einmal geredet habenSiehe Fallstudie: Unveränderliche Objekte., die nur bei der Initialisierung vom Konstruktor mit Werten gefüllt werden. Dies führt auch direkt dazu, dass Referenz- und WertemodellSiehe Werte- und Referenzmodell für Variablen. zu einem Punkt zusammenfallen und wir keine Zeigertypen in einer rein funktionalen Sprache brauchen. Die Beschränkung auf unveränderliche Objekte führt aber auch dazu, dass wir andere Datentypen brauchen, mit denen wir dennoch effizient Berechnungen durchführen können.

Um eine Berechnung durchzuführen, geben wir einer Funktion eines (oder mehrere) dieser unveränderlichen Objekte als Argumente mit. Die Funktion kann die Informationen daraus auslesen, kombinieren, und ein neues Objekt mit den Ergebnissen erzeugen, welches dann zurückgegeben wird. Wollen wir ein Feld in einem Objekt "updaten", müssen wir eine Kopie anlegen, in der alle bis auf eines der Felder gleich sind wie im orginalen Objekt. Für die funktionale Programmierung müssen wir also beständig Informationen aus Objekten extrahieren und neue Objekte mit beinahe gleichem Inhalt konstruieren. Auf den ersten Blick mag dies ineffizient sein, aber Übersetzer für die Sprache sind ziemlich gut darin, unnötige Kopien zu vermeiden. Überlassen Sie dieses Problem also erstmal den Übersetzern.

Aber wir haben auch ein Problem auf der Verwendungsebene der Sprache: Nicht jede Datenstruktur eignet sich gleich gut für dieses Muster des partiellen Updatens. Zum einen müssten wir für große monolithische Objekte (wie ein Array) viele Daten kopieren, um ein einzelnes Feld zu verändern, zum anderen wäre es schön Typen und Syntax zu haben, um mit sehr wenig Code Informationen aus Objekten zu extrahieren und neue Objekte anzulegen. Diesen Herausforderungen für funktionale Datenstrukturen wollen wir uns nun widmen.

Partielle Updates von Daten funktionieren mit einigen Datentypen besser als mit anderen. Wie wir schon gesagt haben eignen sich große Arrays eher weniger. Aber welche Datentypen eignen sich denn dann für funktionale Programmierung? Die Antwort darauf sind Datenstrukturen, die aus vielen kleinen Objekten bestehen, die sich gegenseitig hierarchisch referenzieren. Das Paradebeispiel hierfür ist die einfach verkettete Liste. Aber auch Bäume eignen sich ganz gut.

Solche Datenstrukturen eigenen sich daher gut, da man die Datenstruktur (in ihrer Gesamtheit) leicht erweitern kann, ohne die bereits bestehenden Objekte zu modifizieren. So kann man in einer verketteten Liste vorne etwas anhängen, indem man ein neues Listenelement erzeugt, welches auf den bereits existierenden Listenkopf zeigt. Selbst wenn der bereits bestehende Listenkopf an einen anderen Namen gebunden ist, ist das kein Problem: Die neue Liste teilt sich einfach alle, bis auf das erste, Listenelemente mit der alten Liste. Und da alle Elemente unveränderlich sind, bekommen wir niemals ein Problem! Niemals kann es in der Zukunft geschehen, dass eine Operation auf der alten Liste dazu führt, dass die neue Liste sich verändert.

Will man in einer solchen unveränderlichen Struktur ein Element in der Mitte der Liste austauschen, so muss man alle Elemente bis zum betroffenen Element kopieren, da sich ja deren Nachfolger ändert. Allerdings bleiben nur so bereits existierende Listen intakt. Im folgenden Stück Python Code habe ich die Situation auf der Folie für Sie einmal nachempfunden. Die Klasse Elem beschreibt ein Listenelement. Neben dem Wert des Elements (value) und der Referenz auf das folgende Element (next), hat jedes Element eine eindeutige Nummer (__id__), die im Konstruktor gesetzt wird. Auf diese Weise können Sie in der Ausgabe nachvollziehen, welche Listen sich welche Objekte teilen. So hat das Element ([#0] 4 None) die eindeutige Nummer 0, den Wert 4, und keinen (None) Nachfolger.

Die Funktion cat() hängt vorne an die Liste ein neues Element an, während die Funktion setnth() das Nte Element in einer bestehenden Liste austauscht. Dazu geht setnth() die Liste rekursiv durch, bis sie beim entsprechenden Element angekommen ist und erzeugt ein neues Element mit dem neuen Wert. Bei der Rückkehr aus der Rekursion werden die Werte aus der alten Liste kopiert und neu "verzeigert".

class Elem:
    counter = 0
    def __init__(self, value, next):
        self.__id__ = Elem.counter
        Elem.counter +=1

        self.value = value
        self.next = next

    def __str__(self):
        return "([#%s] %s %s)" %(self.__id__, self.value, self.next)


def cat(value, list):
    """Vorne an die List anhaengen"""
    return Elem(value, list)

list_x = cat(2, cat(3, cat(4, None)))
list_y = cat(1, list_x)

print "list_x=", list_x
print "list_y=", list_y

def setnth(list, nth, value):
    """Das n-te Element setzen"""
    if nth == 0:
        return Elem(value, list.next)
    else:
        return Elem(list.value,
                 setnth(list.next,
                        nth - 1,
                        value))

list_xx = setnth(list_y, 1, 400)
print "list_xx=", list_xx

In ähnlicher Weise sind verzeigerte Bäume eine gute funktionale Datenstruktur. Beide haben es gemein, dass die Datenstrukturen rekursiv sind. Ein Kind eines Baumelements ist selbst wieder ein Baum. Bei der Liste ist der Nachfolger wieder eine Liste (oder das Listenendsymbol).

Graphiken und Animationen

PreviousNext

Neben der Verwendbarkeit von Datenstrukturen haben wir allerdings noch eine zweite Dimension, die wir uns für unsere Daten vom funktionalen Paradigma wünschen: Einfache Handhabbarkeit. Es muss einfach sein Objekte zu erzeugen und wieder zu zerlegen. Denn beides werden wir ständig machen, da wir ja keine Modifikationen durchführen werden. Dazu haben sich Aufzählungstypen mit Nutzlast als sehr geeignete Typen heraus gestellt. Kennengelernt haben wir einfache Aufzählungstypen bereits in der Vorlesung über TypenSiehe Skalare Typen. als skalare Datentypen. Dort haben wir gelernt, dass eine Aufzählung einen diskreten und endlichen Wertebereich hat, der von den Entwicklern deklariert wird. Jedes Element einer Aufzählung ist ein möglicher Wert, eine Variante, der Aufzählung.

Nun wollen wir diese Aufzählungen zu zusammengesetzten TypenSiehe Zusammengesetzte Typen. erweitern. Jede Variante der Aufzählung bekommt jetzt noch eine Nutzlast in Form von Feldern (ähnlich wie bei Records). Dabei erlauben wir, dass jede Variante unterschiedliche Felder haben kann. Die Aufzählung selbst wird dabei zu einem einzelnen Datentypen, den wir verwenden können, um Variablen und Parameter zu deklarieren. Die einzelnen Varianten werden zu Konstruktoren, die ihre angehängten Felder als Argumente bekommen, und ein Objekt vom Aufzählungstypen erzeugen.

Diese Art der Aufzählungen ist ähnlich zu den varianten Records (union), allerdings hat jedes Objekt zusätzlich das Wissen, mit welchem Variantenkonstruktor sie erzeugt wurde. Im Gegensatz zu C-union Objekten kann man durch dieses Wissen die einzelnen Felder auch wieder typsicher aus dem Objekt extrahieren. Falls es ihnen leichter fällt C Code zu verstehen, bietet das folgende Stück C Code die gleiche Funktionalität wie der auf den Folien gezeigte Aufzählungstyp Point. Sie müssen zugeben, dass es sich wirklich lohnt, Syntax in der Sprache zu haben, mit der man gleichzeitig die Aufzählungswerte, die Konstruktoren und die Felder deklarieren kann:

#include <stdio.h>

typedef enum {XY, XYZ} PointKind;
struct Point {
    PointKind tag;
    union {
        struct {
            int x;
            int y;
        } XY;
        struct {
            int x;
            int y;
            int z;
        } XYZ;
    };
};

struct Point makeXY(int x, int y) {
    struct Point ret = {
        .tag = XY,
        .XY = { x, y }
    };
    return ret;
}

struct Point makeXYZ(int x, int y, int z) {
    struct Point ret = {
        .tag = XYZ,
        .XYZ = { x, y, z}
    };
    return ret;
}

void handle(struct Point p) {
    switch(p.tag) {
    case XY:
        printf("XY(%d, %d)\n", p.XY.x, p.XY.y);
        break;
    case XYZ:
        printf("XYZ(%d, %d, %d)\n", p.XYZ.x, p.XYZ.y, p.XYZ.z);
        break;
    }
}

int main() {
    struct Point p1 = makeXY(1,2);
    struct Point p2 = makeXYZ(1,2,3);
    handle(p1); handle(p2);
}

In Haskell ist die Syntax für solche Aufzählungstypen sogar noch kompakter und erlaubt es auch sehr einfach Typen für rekursive Datenstrukturen zu definieren. Zusätzlich kommt noch dazu, dass solche rekursiven Typen bei Haskell generisch sindSiehe Polymorphismus: Generische Typen.. Da die Haskell Syntax doch sehr kompakt ist, wollen wir den Ausdruck data Tree T = Leaf T | Node (Tree T) (Tree T) Schritt für Schritt auseinander nehmen.

Das Schlüsselwort data leitet die Deklaration eines neuen Typen ein. Der Name des neuen Typen ist Tree und er hat einen generischen Typparameter T. Instantiiert mit einem Char (Haskell: Tree Char) würde dieser Typ den Typausdruck Tree(Char) erzeugen, einen Baum mit Buchstaben an den Blättern. Auf der rechten Seite des = befinden sich die beiden Varianten dieses Aufzählungstyps (Leaf und Node): Zunächst haben wir die Variante Leaf, die mit einem Feld Nutzlast kommt, welches vom parametrischen Typ T ist. In einem Tree Char würde jedes Blatt also genau einen Buchstaben speichern. Die zweite Variante von Tree ist ein innerer Knoten Node, der zwei Felder hat, die beide vom parametrischen Typ Tree T sind. Im Kontext eines Tree Char heißt dies, dass ein innerer Knoten zwei Felder hat, die wiederum vom Typ Tree Char sind.

Wie im Rust Beispiel sind die Aufzählungsvarianten gleichzeitig Konstruktoren, um Objekte vom Typ Tree T zu instantiieren. Im Beispiel sehen wir, dass die Variable freeTree als ein Tree Char deklariert wird und wir danach einen entsprechenden Baum an den Namen binden. Hier kommen die Variantennamen als Konstruktoren zum Einsatz.

Graphiken und Animationen

PreviousNext

Aber wir wollen Objekte ja nicht nur kompakt erzeugen, sondern sie, und auch andere unveränderliche Objekte, auch kompakt verwenden. Dazu haben sich zwei sehr nah verwandte Konzepte etabliert, mit denen man Objekte wieder zerlegen kann. Mit dem destructuring bind binden wir die einzelnen Subobjekte eines Objekts mittels eines Musters an Namen. Mit dem pattern matching verwenden wir solche Muster, um zwischen unterschiedlichen Varianten eines Aufzählungstyps eine Fallunterscheidung durchzuführen.

Beim destructuring bind, einem Wort für das ich keine deutsche Entsprechung kenne, verwenden wir ein Muster mit freien Variablennamen, um ein Objekt in einer Zuweisung zu zerlegen. Dabei muss das Muster die gleiche Struktur haben, wie das Objekt, das wir zerlegen wollen, sonst schlägt die Zerlegung zur Laufzeit fehl. Ist das Objekt ein Record, so muss das Muster auch aussehen wie ein Record. Ist das Objekt ein Tupel, so muss das Muster auch ein Tupel sein. Im Muster befinden sich anstatt konkreter Werte Namen, die frei, also noch ungebunden, sind. Im Beispiel sieht das dann so aus, dass wir das Tupelobjekt (1,2) zerlegen wollen. Das Muster auf der linken Seite ist (x0, x1) und enthält die freien Namen x0 und x1. Durch das destructuring bind weisen wir die entsprechenden Subobjekte den Namen zu, sodass danach x0 den Wert 1 und x1 den Wert 2 hat.

Destructuring bind sollte bei Ihnen bereits ein Gefühl von Bekanntheit erzeugen, da es sehr ähnlich aussieht wie Unifikation, bei dem wir ja auch Muster aneinander angeglichen haben. Allerdings gibt es zwei bedeutende Unterschiede zur Unifikation: (1) Beim destructuring bind ist ganz klar, dass es ein Muster und eine Vorlage gibt und das Abgleichen nur in eine Richtung geschieht. Bei der Unifikation sind beide Seiten gleichberechtigt. (2) Beim destructuring bind darf jeder freie Name nur genau einmal im Muster auftreten, während bei der Unifikation freie Variablen mehrfach auftreten dürfen. Durch beide Einschränkungen ist das destructuring bind deterministisch und schnell zu bewerkstelligen, während die Unifikation ein NP-vollständiges Problem ist.

Sehr verwandt zum destructuring bind ist das pattern matching, bei dem wir auch strukturelle Muster verwenden, aber diesmal um eine Fallunterscheidung durchzuführen. Der Ablauf ist dann wie ein switch-case: Ein gegebenes Objekt (p1 auf den Folien) wird mit einer Reihe von Mustern verglichen. Das erste Muster, das auf das Objekt passt, führt dazu, dass der entsprechende Arm der Fallunterscheidung selektiert wird. Mittels destructuring bind wird das Muster (Point::XY (x,y))verwendet, um das Objekt zu zerlegen und Teile davon an Namen zu binden, die dann innerhalb der Fallunterscheidung zur Verfügung stehen.

Durch pattern matching kann man sehr kompakt gegen alle Varianten eines Aufzählungstypen mit Nutzlast vergleichen und variantenspezifischen Code ausführen. Im Gegensatz zu einer if-elif-else Kaskade ist es bei diesem Konstrukt für den Übersetzer auch leicht zu prüfen, ob wirklich alle Fälle der Aufzählung abgehandelt wurden oder ob ein Fall vergessen wurde.

Graphiken und Animationen

PreviousNext

Die Entscheidung, keinen veränderlichen Zustand zu erlauben, hat natürlich nicht nur Auswirkungen auf die Objekte, sondern auch auf die Organisation der Operationen. Hier ist die Stellung der Funktionen, die ja nun richtige Funktionen im mathematischen Sinne sind, von besonderer Bedeutung. Diese mathematischere Sicht auf Funktionen führt auch dazu, dass wir die Rolle von Prozeduren/Funktionen innerhalb der Sprache neu überdenken.

Bisher haben wir Operationen und Objekte als zwei unterschiedliche Sphären einer Programmiersprache behandelt. Es gab die Welt der Operationen, in der Kombinationsregeln für Daten definiert sind, und die Welt der Objekte, in der die passiven Datenträger beheimatet sind. Funktionen haben wir in dieser Kategorisierung in die Welt der Operationen gesteckt. Wir haben Funktionen ja sogar als Komplexoperationen, die mittels Funktionsaufruf aktiviert werden, bezeichnet.

In dieser Kategorisierung bekommt eine Funktion mehrere Objekte als Argumente, verarbeitet diese (inzwischen sogar ohne Seiteneffekte) und gibt wieder ein Objekt als Rückgabewert aus. Eine solche Funktion, die nur passive Objekte, die gewissermaßen faul im Speicher herumlungern, verarbeitet, nennen wir Funktion erster Ordnung. In unserer Übungssprache L0 haben wir ausschließlich solche Funktionen.

Aber es gibt auch Funktionen höherer Ordnung, die nicht nur normale Objekte als Argument bekommen können, sondern auch Funktionen. Sie heißen deswegen "von höherer Ordnung", da sie Funktionen sind, die Funktionen verarbeiten. Eine Funktion, die eine Funktion erster Ordnung bekommt, ist demnach eine Funktion zweiter Ordnung. Geben wir diese Funktion wiederum einer dritten Funktion mit, so wäre diese eine Funktion dritter Ordnung. Die Funktionen höherer Ordnung sind also alle Funktionen, die keine Funktionen erster Ordnung sind.

Solche Funktionen höherer Ordnung sind eine ziemlich gebräuchliche Technik. Immer wenn ein Funktionszeiger als Argument auftaucht haben wir eine Funktion höherer Ordnung vor uns. Jede Form von Callback ist ein Indikator für eine Funktion höherer Ordnung. Dies gibt es sogar in der Sprache C, die ja ansonsten eher nicht für ihre semantische Reichhaltigkeit bekannt ist.

Aber selbst wenn es Funktionen höherer Ordnung in einer Sprache gibt, sind Funktionen und Objekte immer noch nicht gleichberechtigt. Wir können zwar mittels Funktionszeigern Funktionen weitergeben, oder sogar als Rückgabewert bekommen, aber wir sind auf jene Funktionen beschränkt, die im Quelltext definiert wurden. In C kann ich zur Laufzeit mittels malloc() eine beliebige Anzahl von Objekten erzeugen, aber ich kann keine einzige Funktion neu erzeugen. In C ist die Menge der existierenden Funktionen nach der Übersetzung abgeschlossen und fix, die Menge der Objekte dagegen dynamisch. Das ist doch total unfair! Ich möchte ebenfalls Funktionen zur Laufzeit erzeugen können. Nur dann herrscht wirkliche Gleichberechtigung zwischen Funktionen und Objekten, dann wenn Funktionen selbst zum Objekt werden.

Bei Sprachen, die Gleichberechtigung für Objekte und Funktionen bieten, sagt man, dass die Funktionen Bürger erster Klasse (first-class citizens) sind. In solchen Sprachen gibt es keinen prinzipiellen Unterschied zwischen Funktionen und Objekten, und man braucht beide Universen nicht mehr als getrennt voneinander ansehen. Wir haben nur noch Objekte, von denen manche aufrufbar und damit Funktionen sind. Wir haben solche Funktionsobjekte schon öfter in Aktion gesehen, ohne sie wirklich zu diskutieren. In Python sind Funktionen solche Bürger erster Klasse und können zur Laufzeit erzeugt werden. Eine Funktion höherer Ordnung kann neue Funktionen erzeugen und zurückgeben. Im Beispiel verarbeitet f() das Funktionsobjekt y() und die Zahl 23, um eine neue Funktion z() zu erzeugen.

Wenn Funktionen von nun an Funktionsobjekte sind, dann brauchen wir auch Operationen, die wir auf ihnen ausführen können. Die einfachste Operation ist dabei der Aufruf, der ein Funktionsobjekt zusammen mit einigen Argumenten als Funktionsinstanz aktiviert. Auf der abstrakten Ebene legt der Aufrufoperator (apply(func, *args)) einen Call-Frame an, bindet die Argumente an die Parameter und startet die Ausführung des Funktionsrumpfes. Aber es gibt noch andere Operationen, die wir auf Funktionsobjekten ausführen können, mit denen wir uns noch beschäftigen werden.

Graphiken und Animationen

PreviousNext

Funktionen höherer Ordnung nehmen einen besonderen Platz in der Welt der Programmiersprachen ein, da sie von einer Auswertungsstrategie abstrahieren können. Die Funktion höherer Ordnung bekommt ein Funktionsobjekt als Argument und kann dies in ihrem Funktionsrumpf an beliebiger Stelle, beliebig oft und mit beliebigen Argumenten aufrufen. Der Rumpf der "äußeren" Funktion bestimmt also eine Auswertungsstrategie, die ihr Benutzer mit beliebigen Funktionalitäten, durch Übergabe von unterschiedlichen Callback-Funktionen, parametrisieren kann. Auf den Folien sehen wir, wie die Funktion outer() eine Auswertungsstrategie einer Funktion auf einem Array mit mindestens zwei Elementen codiert. Aufgerufen mit unterschiedlichen Funktionsobjekten (innerA, innerB) liefert outer() unterschiedliche Ergebnisse, die jedoch nach dem gleichen Muster berechnet werden. Durch Funktionen höherer Ordnung können wir also nicht nur in den passiven Daten, sondern auch in den Verarbeitungsschritten, eine Art prozeduraler Abstraktion vornehmen. Wo die prozedurale Abstraktion ein Vorgehen vollständig abstrahiert hat, kann die funktionale Abstraktion mit Funktionen höherer Ordnung ein Vorgehen partiell abstrahieren und parametrisierbare "Lücken" lassen.

Eines der grundlegensten Konzepte funktionaler Programmierung ist der Lambda-Ausdruck, der es uns erlaubt, anonyme Funktionsobjekte zu erzeugen. Dies muss man im Gegensatz zur normalen Funktionsdefinition sehen, bei der ein Funktionsobjekt erzeugt wird und sofort an einen Funktionsnamen gebunden wird. Das anonyme Funktionsobjekt hat selbst keinen Namen, kann also nicht direkt durch die Namensauflösung gefunden werden. Jedoch kann es, wie jedes Funktionsobjekt, herumgereicht und aufgerufen werden.

Wo die Funktionsdefinition die Funktion in einem statischen KontextStatisch meint hier, dass das Funktionsobjekt über die gesamte Laufzeit existiert, wie dies auch bei globalen Variablen der Fall ist anlegt, erzeugt ein Lambda-Ausdruck ein Funktionsobjekt dynamisch im Kontext des Programmablaufs. Dies hat zur Folge, dass der Lambda-Ausdruck in einem aktiven Auswertungskontext einer bereits laufenden Funktion ausgewertet wird, aus dem der Ausdruck Namen innerhalb des Lambda-Rumpfes binden kannSiehe Lexikalisches Scoping.. Daher sind Lambda-Ausdrücke nicht nur eine bequeme Ersatzschreibweise für Funktionsdefinitionen, sondern haben ihren eigenen Wert. Machen wir das kurz an einem Beispiel fest:

def make_multiplier(factor):
    return lambda x: x * factor

fn = make_multiplier(2)
print [fn, fn(23), make_multiplier(3)(13)]

Im Beispiel definieren wir die Funktion make_multiplier(), die mittels eines Lambda-Ausdruckes Funktionsobjekte erzeugt. Als Argument hat die Funktion den Parameter factor. Der Lambda-Ausdruck erzeugt eine Funktion mit einem Argument x, die zusätzlich den Namen factor aus ihrem dynamischen Aufrufkontext bindet. Jedes Mal, wenn wir make_multiplier aufrufen, wird ein neues Funktionsobjekt erzeugt, dass in seinem partiell gebundenem Auswertungskontext den Namen factor bereits gebunden hat. Etwas abstrakter gesprochen erzeugt make_multiplier() Funktionen, die eine gegebene Zahl mit einem Faktor multiplizieren.

Wir haben bereits erwähnt, dass Funktionen höherer Ordnung Auswertungsstrategien abstrahieren können und wir haben bereits diskutiert, warum einfach-verkettete Listen eine Datenstruktur sind, die gut für die funktionale Programmierung geeignet ist. Da ist es naheliegend, dass sich einige Standardfunktionen höherer Ordnung zur Verarbeitung von Listen herausgebildet haben, die Listenmanipulationen abstrahieren. Wir wollen kurz die drei wichtigsten Funktionen dieser Klasse diskutieren.

Die Funktion map() bildet eine Liste auf eine neu erstellte Liste gleicher Länge ab. Dabei bildet map() jedes Listenelement mittels einer übergebenen Funktion auf ein neues Objekt ab, aus denen die Ergebnisliste erzeugt wird. Durch diese Abstraktion lassen sich viele Konstrukte, die sonst durch iterative Schleifen implementiert werden müssten, im funktionalen Paradigma ausdrücken, ohne die Rekursion über die Liste jedes Mal implementieren zu müssen. Schauen wir uns kurz die rekursive Definition von map() an:

def map(func, sequence):
    if not sequence:
        return []
    return [func(sequence[0])] + map(func, sequence[1:])

print map(lambda x: x*2, [1,2,3,4])

Die Funktion filter() wird dazu benutzt, die Elemente einer Liste nach einem gegebenen Kriterium zu filtern und nur aus den selektierten Elementen eine neue Liste zu erzeugen. Das gesuchte Kriterium wird als Prädikatsfunktion übergeben und bildet jedes Element der Liste auf einen booleschen Wert ab. filter() führt also die Aschenputteloperation aus, und wirft die Guten ins Töpfchen (Rückgabeliste) und die Schlechten ins Kröpfchen (continue). Die rekursive Definition von filter() sieht folgendermaßen aus:

def filter(predicate, sequence):
    if not sequence:
        return []

    head, tail = sequence[0], sequence[1:]
    if predicate(head):
        return [head] + filter(predicate, tail)
    else:
        return filter(predicate, tail)

print filter(lambda x: (x % 2) == 0, [1,2,3,4])

Die Funktion reduce() wird dazu verwendet, die Elemente einer Liste mittels einer Aggregierungsfunktion paarweise zu einem einzelnen Wert "zusammenzufalten". Dabei gibt es zwei grundlegende Spielarten von reduce(), je nachdem, ob die Listenelemente rechts-assoziativ oder links-assoziativ kombiniert werden. Zusätzlich gibt es die Unterscheidung, ob ein Initialwert angegeben wird oder nicht. Während die Assoziativität und der Anfangswert für Operationen wie + keine Rolle spielen, ist die Reihenfolge der Reduktionen für andere Aggregierungsfunktionen essenziell. Im folgenden Beispiel sehen wir sowohl die links-assoziative als auch die rechts-assoziative Variante, implementiert im imperativen Paradigma. Durch die Aggregierungsfunktion, welche zwei-elementige Tupel erzeugt, ist gut zu erkennen, wie sich die Auswertungsstrategien unterscheiden.

def reduce_left(func, sequence, initial):
    for elem in sequence:
        initial = func(initial, elem)
    return initial

def reduce_right(func, sequence, initial):
    for elem in reversed(sequence):
        initial = func(elem, initial)
    return initial

print reduce_left (lambda x,y: (x,y), [1,2,3,4,5], "init")
# => ((((('init', 1), 2), 3), 4), 5)
print reduce_right(lambda x,y: (x,y), [1,2,3,4,5], "init")
# => (1, (2, (3, (4, (5, 'init')))))

Neben diesen Listenmanipulatoren kann es ähnliche Operationen auch auf komplexeren Datenstrukturen wie Bäumen geben. So würde ein mapTree() einen Baum auf einen Baum gleicher Struktur abbilden, bei dem jeder Knoten durch eine gegebene Funktion transformiert wird. Im Grunde war unsere traverse()-Funktion aus der Vorlesung über die semantische AnalyseSiehe Traversierung von Bäumen. genau solch eine Funktion höherer Ordnung auf dem AST.

Graphiken und Animationen

PreviousNext

Aber ich habe Ihnen ja noch mehr Operationen auf Funktionsobjekten versprochen. Die sollen Sie in Form der Funktionskomposition und der partiellen Anwendung von Funktionen auch bekommen! So wie die Addition zwei Zahlen miteinander kombiniert, so können die genannten Operationen bereits existierende Funktionsobjekte manipulieren, ganz im Sinne von Funktionen zu Bürgern erster Klasse zu machen.

Die erste Operation ist die Funktionskomposition (compose()), die aus mehreren Funktionsobjekten ein neues Funktionsobjekt erzeugt, welches die gegebenen Funktionen hintereinander ausführen wird. Dazu füttert das neue Funktionsobjekt die eigenen Argumente an die erste übergebene Funktion, deren Ergebnis wird wiederum als Argument an die zweite Funktion gegeben, und so weiter bis das Ergebnis der letzten Funktion als endgültiger Rückgabewert an den Aufrufer der komponierten Funktion geht. Auf den Folien zeige ich Ihnen nur die Komposition zweier Funktionen, dies ist aber mit beliebig vielen hintereinander ausgeführten Funktionen möglich.

Besondere Wichtigkeit haben die Typsignaturen der komponierten Funktionen: Das neue Funktionsobjekt hat die gleiche Anzahl und Typisierung ihrer Parameter wie die erste übergebene Funktion. Den Rückgabetyp erbt sie von der letzten komponierten Funktion. Zudem ist es für die Komposition essenziell, dass die Rückgabewerte und Parametertypen der direkt hintereinander komponierten Funktionen kompatibel sind. Dies führt auch direkt dazu, dass ausschließlich die erste Funktion einer Funktionskomposition mehr als einen Parameter haben kann, alle anderen komponierten Funktionen dürfen nur einen Parameter besitzen. Die Einschränkungen in den Typen der komponierten Funktion ist auch recht einleuchtend, wenn man bedenkt, dass Funktionskomposition zu einer Art Pipeline-Auswertung führt. Klar müssen dann die Rückgabetypen einer Stufe kompatibel mit den Eingabetypen der nächsten Stufe sein.

Durch die Komposition lassen sich aus einfachen Funktionen komplexe Verarbeitungsstufen eines einzelnen Wertes komponieren. So lässt sich zum Beispiel die Verarbeitung von Bildern hervorragend und sehr klar als Komposition darstellen: convertToGrayscale . scaleDown . detectContour . scaleUp. Man kann bei dieser Komposition (ich habe die Haskell-Notation für Komposition mit . gewählt) sehen, wie ein Bild durch die Verarbeitungsstufen geschoben wird. Zuerst entfärben wir das Bild, bevor wir das Graustufenbild auf eine kleinere Größe skalieren, bevor wir eine Kantenerkennung durchführen und das Ergebnis wieder auf die Orginalgröße (unter Informationsverlust) hoch skalieren. An diesem Beispiel sehen wir auch gut, wie das funktionale Paradigma den Fokus auf die Verarbeitung von Daten legt, anstatt, wie das objektorientierte Paradigma, die Daten in den Vordergrund zu rücken.

Durch die Komposition und die strikte Verwendung von Ausdrücken lassen sich kompakt unterschiedliche Verarbeitungsstufen erzeugen. Die Funktion picturePipeline erzeugt eine Funktionskomposition, die anhand des booleschen Parameters fast das Bild für die Kantenerkennung herunterskaliert oder direkt auf dem orginalgroßen Bild arbeitet. Dabei hat der Ausdruck (scaleDown . detectContour . scaleUp) die gleiche Typsignatur wie detectContour. Das Beispiel ist dabei nur als eine Art funktionaler Pseudocode zu verstehen.

picturePipeline fast = loadFile 
		       . convertToGrayscale
		       . (if fast 
			  then (scaleDown . detectContour . scaleUp)
			  else detectContour)

main = (picturePipeline true) "testImage.png"

Übrigens kennen Sie bereits die Funktionskomposition aus dem Bereich der Unix-Systemprogrammierung. Die Komposition von einfachen Unix-Tools mit dem | Operator Ihrer Shell stellt ebenfalls eine Funktionskomposition auf gröberer Granularität dar. Auch dort müssen die Aus- und Eingabeformate der hintereinander ausgeführten Tools zueinander passen.

Bei der häufigen Verwendung der Komposition kommt man schnell zu dem Punkt, an dem man ständig einstellige Funktionen definiert, die ihr Argument an eine Funktion mit mehreren Argumenten weitergibt, wobei die restlichen Parameter mit einer Konstanten belegt werden. So könnte man auf die Idee kommen, die obige Bildverarbeitungsstufe dahingehend zu optimieren, das Bild auf unterschiedliche Größen herunter zu skalieren:

def scaleDown(width, height, picture):
    print "scaleDown(%s, %s, %s)" %(width, height, picture)

def scaleDown128(picture):
    return scaleDown(128, 128, picture)

def scaleDown256(picture):
    return scaleDown(256, 256, picture)

def scaleDown512(picture):
    return scaleDown(512, 512, picture)

Solche sich wiederholende Funktionsdefinitionen sind natürlich unangenehm und erzeugen eine ganze Menge Boilerplate Code, den wir wiederum funktional abstrahieren könnten, indem wir eine Funktion höherer Ordnung schreiben, die Skalierungsfunktionen mittels Lambda-Ausdruck zur Verwendung in Funktionskompositionen erzeugt:

def makeScaleDown(width, height):
    return lambda picture: scaleDown(width, height, picture)

pipeline = compose(makeScaleDown(256, 256), detectContour)

Mittels der Funktion makeScaleDown() können wir nun beliebige einstellige Funktionen zur Bildskalierung erzeugen, die wir in eine Verarbeitungskette einbauen können. Was wir hier auf manuellem Wege durchgeführt haben nennt man eine partielle Anwendung einer Funktion. Der partiellen Anwendung geht in etwa die folgende Überlegung voraus: Um eine mehrstellige Funktion aufzurufen benötigt man für jeden Parameter ein Argument. Durch die partielle Anwendung binden wir einen Teil der Parameter an bereits bekannte Argumente und erzeugen eine Funktion mit entsprechend weniger Parametern, die die restlichen Argumente vorher einsammelt, bevor die ursprüngliche Funktion gestartet wird.

Im Beispiel sieht diese Überlegung dann in etwa so aus: Die Funktion scaleDown() benötigt drei Parameter um ein Bild zu skalieren: Die Breite des Zielbildes, die Höhe des Zielbildes und das Quellbild. Beim Aufruf von makeScaleDown(width, height) kennen wir bereits zwei dieser drei formalen Parameter und können eine partielle Anwendung durchführen. Dazu erzeugen wir ein neues Funktionsobjekt, welches width und height in seinem Aufrufkontext gebunden hat und nur noch das letzte Argument (picture) einsammeln muss. Bei der Aktivierung der anonymen Funktion wird das übergebene Bild anhand der Breite und der Höhe aus dem lexikalisch gebundenen Aufrufkontext herunter skaliert.

Dieses Muster, welches wir hier einmal manuell für scaleDown durchexerziert haben, lässt sich hervorragend funktional abstrahieren, indem wir scaleDown nicht statisch in die Funktion makeScaleDown() codieren, sondern eine Funktion höherer Ordnung partial() definieren, die den ersten Parameter eine Funktion partiell bindet. Leider funktioniert das Beispiel im Browser nicht, weswegen Sie es in einer Python Shell ausprobieren müssen.

def scaleDown(width, height, picture):
    print "scaleDown(%s, %s, %s)" %(width, height, picture)

def partial(func, arg0):
    return lambda *args: func(arg0, *args)

scaleDown128 = partial(partial(scaleDown, 128), 128)
scaleDown128("foobar.png")

Auf den Folien sehen wir gut, wie die partielle Anwendung einer zweistelligen Funktion ein neues Funktionsobjekt mit nur noch einem Parameter erzeugt. Dabei wandert der partiell gebundene Parameter, der im neuen Objekt den Wert 23 hat, in den Ausführungskontext der neu erzeugten Funktion und wird bei endgültigem Aufruf an die ursprünglich zweistellige Funktion übergeben. In funktionalen Sprachen bzw. funktionalen Hilfsbibliothekensiehe Python 3.7: functools.partial, findet man auch Varianten von partial(), die nicht nur den ersten Parameter partiell binden können.

Das Konzept der partiellen Anwendung ist so wichtig, dass in der funktionalen Programmiersprache jede Funktion durch Currying partiell anwendbar ist, ohne dass man explizit eine partial() Funktion aufrufen muss. Dies funktioniert, indem bei Haskell alle Funktionen, die mehr als ein Argument benötigen, automatisch zu einer Sequenz von einstelligen Funktionen transformiert werden, die immer einen weiteren Parameter partiell binden. Konkret heißt das, dass keine Funktion in Haskell mehr als einen Parameter hat.

Machen wir das Ganze etwas konkreter an der Funktion add :: Int -> Int -> Int: Der Körper der Funktion benötigt zwei Ganzzahlen, um die Addition durchführen zu können. Ruft man die Funktion mit nur einem Argument auf ((add 3)), so erhält man ein Funktionsobjekt, dass noch einen Parameter bekommt, der dann zu drei addiert wird. Aufgerufen mit zwei Argumenten (add 1 2) wird die Addition direkt ausgeführt. Currying ist auch der Grund, wieso Funktionssignaturen in Haskell so "komisch" aussehen, denn eigentlich ist die Signatur von add() Int -> (Int -> Int), was bedeutet, dass hier eine Abbildung von einem Int auf eine Funktion "Int nach Int" durchgeführt wird, aus einer Ganzzahl wird eine Funktion. Daher sind in Haskell die Ausdrücke add 2 3, (add 2) 3 und add(2)(3) vollständig äquivalent.

Toll! Wir können jetzt also nicht nur komplexere Funktionen aus einfacheren komponieren, sondern die partielle Anwendung erlaubt es uns auch, aus einer hochgradig parametrisierbaren Funktion viele vorparametrisierte Funktionen abzuleiten. Lassen Sie uns das nun zur Anwendung bringen.

Graphiken und Animationen

PreviousNext

Auf den Folien sehen Sie, wie wir eine gegebene Aufgabenstellung, bei der es um die Verarbeitung einer Punktwolke geht, funktional lösen können. Dabei ist der erste Schritt, wie wir aus einer generischen Normierungsfunktion die 2-Norm durch partielle Anwendung ableiten und zu einer einstelligen Funktion machen, die einen Punkt in seine Distanz zum Ursprung transformiert. Durch map() wenden wir die 2-Norm auf jeden Punkt der Punktwolke an, um eine Liste der Distanzen zum Ursprung zu berechnen. Diese Liste filtern wir mittels filter() und einer anonymen Funktion, um nur noch die Distanzen von Punkten innerhalb des Einkeitskreises zu betrachten. Um nun die größte Distanz zum Ursprung innerhalb des Einheitskreises zu berechnen, reduzieren wir die Restliste mittels max(), wobei die Assoziativität keine Rolle spielt. Mittels partieller Anwendung ließe sich diese Verarbeitungskette in Haskell noch kompakter schreiben, indem man die Funktion nicht direkt auf points anwendet, sondern zuerst eine Verarbeitungsfunktion (maxDistance) erzeugt und im Anschluss anwendet:

maxDistance :: [Point] -> Float
maxDistance = (map (norm 2)) . (filter \x -> x < 1.0) . (reduce max)

maxD = maxDistance points

Bemerkenswert ist die Kombination von Funktionskomposition, partieller Anwendung und normalen Listenmanipulationsfunktionen. Dieses Muster von Abbildung, Ausfiltern und Reduzieren hat auch in der Verarbeitung großer Datenmengen Einzug gehalten. Das sogenannte MapReduceWikipedia: MapReduce Verfahren wurde jahrelang bei Google als zentrales Verarbeitungsmodell für große Datenmengen verwendet. Dabei wird zuerst eine große Menge von Dokumenten (Websites) unabhängig voneinander und parallel auf vielen Rechnern verarbeitet (map()) und die Ergebnisse im Anschluss kombiniert (reduce()). Der große Vorteil dieses Modells ist die Unabhängigkeit und leichte Parallelisierbarkeit des Abbildungsschrittes.

Dieser Vorteil lässt sich ebenfalls im Kleinen erreichen: Wenn wir uns zum Ausgangspunkt der Besprechung des funktionalen Paradigmas zurückerinnern, wissen wir, dass Funktionen keine Seiteneffekte haben. Daher lässt sich ein Aufruf map(func, sequence) trivialerweise, ohne sich groß synchronisieren zu müssen, auf viele Prozessoren verteilen. In Python bietet die multiprocessing Bibliothek eine map()-Variante, die alle Elemente einer Liste auf einem Pool von Workern parallel abarbeitet und so eine Maschine mit mehreren Kernen besser ausnutzt.

Graphiken und Animationen

PreviousNext

Jetzt habe ich Ihnen in vielen Worten die Welt des funktionalen Paradigmas näher gebracht. Aber es sollte bei Ihnen noch ein großes Fragezeichen offen sein. Gehen Sie kurz in sich und überlegen Sie, ob mit den genannten Konzepten, die das funktionale Paradigma beinhaltet, ein sinnvolles Programm erstellt werden kann. Nur zu, ich warte hier auf Sie, keine Eile… Denken Sie an alles, was wir hinzugefügt haben: Funktionen als Bürger erster Klasse, Komposition, partielle Anwendung von Funktionen, Listenmanipulationen. Das ist doch alles super schick, was könnte da fehlen? Ich verrate es Ihnen: Seiteneffekte. Denn Seiteneffekte beinhalten nicht nur das Wiederbeschreiben von Variablen, sondern auch jegliche Ein- und Ausgabe eines Programms. Das bedeutet, dass ein rein funktionales Programm hervorragend den ganzen Tag rechnen könnte, wir aber weder Daten hinein, noch wieder herausbekommen würden. Das ist jetzt eher anti-klimaktisch. Irgendwie müssen wir damit umgehen und eine Lösung finden.

Die erste Variante wäre nicht päpstlicher als der Papst zu sein und das mit der Freiheit von Seiteneffekten nicht ganz so eng zu nehmen und nur den Aspekt "Funktionen als Bürger erster Klasse" zu betonen, indem wir einen funktionalen Programmierstil pflegen. Dies ist der Weg, den die meisten Sprachen mit funktionalen Elementen gehen, da der vollständige Verzicht auf Seiteneffekte eine ziemlich große Einschränkung ist. Beim funktionalen Programmierstil behalten wir die Idee von Seiteneffekten, was Schleifen und Statements weiterhin zu nützlichen Konstrukten macht, und führen anonyme Funktionen, partielle Anwendung und Funktionskomposition ein.

Zum Beispiel ist es in Python möglich, einen funktionalen Programmierstil zu pflegen, etwas dass ich Ihnen schon die gesamte Vorlesung heimlich untergeschoben habe. Denken Sie an all die Funktionen höherer Ordnung zurück: traversal() zur Baumtraversierung oder fixpoint() zur Fixpunktiteration. An dieser Stelle haben interpretierte Skriptsprachen einen strategischen Vorteil für die Adoption eines funktionalen Programmierstils. Da der Interpreter während der Ausführung die Funktionen eh als Objekte im Speicher hat, kann man auch eben dem Benutzer die Möglichkeit einräumen, neue Funktionen zu erzeugen. Aber auch bei übersetzten Sprachen setzen sich zunehmend funktionale Sprachkonzepte durch. So haben sowohl C++ als auch Java in neuerer Zeit anonyme Funktionen mittels Lambda-Ausdrücke eingeführt.

Aber auch in rein-funktionalen Programmiersprachen kann man Ein- und Ausgabe einpflegen, ohne die Freiheit von Seiteneffekten gleich ganz über Bord zu werfen. Dabei ist die Idee, dass man I/O aus der Sprache entfernt und in der virtuellen Maschine der Sprache versteckt. Dazu verwendet man in Haskell die I/O-Monade. Monaden sind noch viel allgemeinere mathematische Objekte, die ich in diesem Rahmen leider nicht ausgiebig diskutieren kann. Daher werde ich die I/O-Monade nur, so gut es geht, phenomenologisch erklären.

Die Grundidee ist, dass das Programm ein monadisch komponiertes Funktionsobjekt definiert, welches die virtuelle Maschine verwendet, um das gesamte Universum in der I/O-Monade zu transformieren. Klingt erstmal etwas großspurig, das ganze Universum zu transformieren, aber ist genau das, was wir brauchen, um weiterhin Seiteneffektfreiheit zu haben. Wenn wir das Universum als Read-Only Kopie bekommen und ein neues Universumsobjekt in leichter Abwandlung erzeugen, so gibt es ja keine Seiteneffekte auf irgendeinen externen Zustand. Um diese Transformation der ganzen Welt etwas angenehmer zu gestalten, verwenden wir Monaden, die eine Art Meta-Auswertungsstrategie darstellen.

Wollen wir versuchen das ganze etwas plastischer zu machen: Ein Haskell Programm hat ein main Objekt vom Monaden-Typ IO (). Wenn der Haskell Prozess gestartet wird, nimmt die Haskell Laufzeitumgebung, der das Universum als Argument gegeben wurde, und führt das main-Objekt aus. Dabei kann der Code in main Daten aus dem Universum anfordern (Eingabe) und wieder zurückspielen (Ausgabe). Das Monadenobjekt hat also an den richtigen Stellen Ein- und Auslässe für den Weltzustand, die von der I/O-Monade bespielt werden. Auf diese Weise bleibt das Monadenobjekt selbst frei von Seiteneffekten.

Zusätzlich stellt Haskell über sein striktes und statisches Typsystem sicher, dass nur IO-Monadenobjekte Weltzustand anfordern und zurückspielen können. Daher hat ein reales Haskell-Programm auf der obersten Ebene der Aufrufhierarchie eine Reihe von monadisch komponierten Objekten, die wiederum vollständig seiteneffektfreie Funktionen aufrufen, um die tatsächliche Berechnung durchzuführen. Dem gesamten Monadenkonzept, welches noch andere spannende Anwendungen in der Welt der Programmiersprachen hat, liegt ein größerer kategorientheoretischer Hintergrund zu Grunde. Für Ihren 10.000 Meilenblick ist die Take-Away Message, dass man in Haskell an der Typsignatur direkt ablesen kann, ob eine Funktion Ein-/Ausgabe machen kann oder ob es eine seiteneffektfreie pure Funktion ist.

Für eine gut illustrierte Erklärung zu Monaden verweise ich Sie auf den hervorragenden Blogartikel Functors, Applicatives, And Monads in Pictures von Aditya Bhargava.