Was ist überhaupt „Funktionale Programmierung?“ Zur Beantwortung dieser Frage dürften sich viele Neueinsteiger in das Thema an Wikipedia wenden. Die entsprechende Seite in deutscher Sprache lässt aber einiges zu Wünschen übrig, was mich dazu veranlasst hat den Titel dieses Blogs einmal grundlegend zu erklären.

Der Begriff funktionale Programmierung ist nicht eindeutig definiert, aber man kann sich ihm aus drei verschiedenen Richtungen nähern. Der Begriff kann für das sogenannte Funktionale Paradigma stehen, was soetwas wie eine Minimalanforderung ist. Oder er steht für das Programmieren in funktionalen Sprachen, was schon eine sehr viel restriktivere Definition darstellt. Schließlich kann er auch als Oberbegriff für „typisch funktionale“ Programmierkonzepte stehen, die auch in anderen Sprachen Verbreitung finden. Zunächst zum Begriff des Funktionalen Paradigmas.

Das Funktionale Paradigma

Computerprogramme sind im Grunde nichts anderes als die strukturierte Form einer Berechnung. Die genaue Art dieser Formalisierung ist dabei immer von der verwendeten Programmiersprache abhängig, und in der Regel auch von Programmierer zu Programmierer unterschiedlich, aber es lassen sich einige grundlegende Kategorieren ausmachen - die sogenannten Programmierparadigmen.

Die zwei wichtigsten Paradigmen sind das imperative Paradigma, und das deklarative Paradigma. Nach dem imperativen Paradigma beschreibt man eine Berechnung als Folge von Anweisungen, die einen Programmzustand modifizieren, der am Ende das Ergebnis der Berechnung enthält. Man beschreibung also wie man zu dem Ergebnis gelangt.

Nach dem deklarativen Paradigma beschreibt man eine Berechnung als einen Ausdruck, der zu einem Ergebnis ausgewertet werden kann, und damit angibt, was das Ergebnis der Berechnung sein soll. Dabei gibt es grundlegende, primitive Ausdrücke, und zusammengesetze, komplexe Ausdrücke.

Das Paradigma der funktionalen Programmierung ist nun eine Verfeinerung des deklarativen Paradigmas, bei dem die grundlegenden Ausdrücke die Erzeugung von Funktionen (die Abstraktion) und die Anwendung von Funktionen (die Applikation) sind.

Der Ausdruck zur Erzeugung von Funktionen wird meist als „Lambda-Ausdruck“ bezeichnet, und als Beispiel oft die Programmiersprache Scheme gewählt, vielleicht weil hier das Wort Lambda direkt vorkommt. Hier eine Funktion die zu einer Zahl 2 addiert:

(lambda (x) (+ x 2))

Die nächste Version von Java, Java 8, wird aber zum Beispiel auch Lambda-Ausdrücke enthalten. Die gleiche Funktion kann dann dort so notiert werden:

(x) -> x + 2

In der breitesten Auslegung ist funktionales Programmieren ist also das Programmieren im funktionalen Paradigma, oder das Programmieren mit Lambda-Ausdrücken.

Funktionale Sprachen

Die meisten Programmiersprachen lassen sich nicht einem einzelnen Paradigma zuordnen, sondern erlauben oder erfordern das Programmieren nach unterschiedlichen Paradigmen. Das nennt man dann Multi-Paradigmen-Sprachen.

Wann eine Programmiersprache als „Funktionale Sprache“ bezeichnet werden kann, ist daher weniger gut definiert als der Begriff des funktionalen Paradigmas. Die FAQ der Newsgroup ‚comp.lang.functional‘ definiert den Begriff aber recht passend als Bezeichnung für Sprachen, die das Programmieren im funktionalen Paradigma unterstützen und befördern.

Funktionale Konzepte

Es gibt eine Reihe von Konzepten die typisch für funktionale Sprachen sind, beziehungsweise das relativ grobe Konzept des funktionalen Paradigmas in verschiedene Richtungen weiter untergliedern. Hier kann nur eine kleine Auswahl aufgelistet werden:

Funktionen höherer Ordnung

Als Funktion höherer Ordnung wird eine Funktionen bezeichnet, die ihrerseits Funktionen als Argument erwartet, oder eine Funktion zurück gibt. Eng damit verknüpft ist das Konzept, dass Funktionen sogenannte „First-class citizens“ sind. Das bedeutet, dass Funktionen in einem Programm überall dort auftauchen können wo auch andere primitive Werte wie Zahlen oder Strings auftauchen können.

Beispiel in Scala:

def twice(f: Int => Int): Int => Int = { x => f(f(x)) }

Die Funktion twice nimmer eine Funktion f und gibt eine neue Funktion zurück, die f auf einen Wert x zweimal hintereinander anwendet.

Reinheit, Pure functions

Eine Funktion, bzw. ein Ausdruck ist rein, wenn seine Auswertung keine Wirkung hinterlässt (auch Seiteneffekt genannt).

Die Gruppe der rein-funktionalen Programmiersprachen erlaubt ausschließlich das Programmieren mit reinen Ausdrücke, bzw. erschwert die Verwendung von unreinen Ausdrücken in besonderem Maß. Aber auch in anderen Sprachen empfielt es sich die unreinen Ausdrücke auf ein Minimum zu redizieren und besonders kenntlich zu machen.

Beispiel in D:

pure int square(int x) {
  return x * x;
}

Der D-Compiler stellt hier sicher, dass die Funktion square auf keine globalen Variablen zugreift und nur andere reine Funktionen aufruft.

Rekursion

Als grundlegendes Element zur Wiederholung von Ausdrücken dient in Funktionalen Sprachen häufig die Rekursion, d.h. dass eine Funktion sich selbst aufrufen kann, oder auch zwei Funktionen die sich gegenseitig aufrufen können. Rekursion ist notwendig um eine größere Klasse von Berechnungen durchführen zu können.

Häufig wird dabei die sogenannte Endrekursion, das sind rekursive Aufrufe an Stellen ohne Kontext, ohne Nutzung von zusätzlichen Resourcen ausgewertet. Eine „endlose“ Rekursion kann dann genauso verwendet werden wie eine Endlos-Schleife in imperativen Sprachen.

Beispiel in Scheme:

(letrec ((ping (lambda (ball) (pong ball)))
         (pong (lambda (ball) (ping ball))))
  (ping 42))

Hier rufen sich zwei Funktionen, ping und pong bis in alle Ewigkeit gegenseitig auf (ohne dass dem Programm irgendwann der Speicher ausgehen würde).

Lazy evaluation, oder nicht-strikte Auswertung

Bei einer strikten Auswertung werden für eine Funktionsanwendung zunächst die Argumente ausgewertet, bevor die Funktion aufgerufen, d.h. mit der Auswertung des Funktionsrumpfes forgefahren wird.

Dies ist aber insbesondere dann nicht notwendig, wenn es nur reine Ausdrücke gibt. Dann kann man die Auswertung der Argumente an die Stelle verschieben, an der deren Wert benötigt wird, ohne dass sich das Ergebnis dadurch ändern könnte. Außerdem kann auf die Auswertung auch komplett verzichtet werden, wenn der Wert überhaupt nicht gebraucht wird.

Die meisten funktionalen Sprachen verfolgen dennoch eine strikte Auswertungsstrategie von Funktionsaufrufen, aber z.B. fast immer eine nicht-strikte Auswertung bei Operatoren wie dem logisches Oder, oder bei bedingten Ausdrücken.

Ein Beispiel in Haskell, einer Sprache mit nicht-strikter Auswertung ist folgendes. Angenommen wir haben schon eine Funktion die Quick-Sort implementiert, also einen Sortieralgorithmus, bei dem das erste Element einer Liste genommen wird, dann rekursiv die beiden Listen aller Elemente die kleiner bzw. größer sind sortiert werden, und diese drei Teile dann wieder passend aneinander gehängt werden:

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

Möchten wir nun eine Funktion definieren, die das kleinste Elemente einer Liste zurückgibt, dann können wir einfach schreiben, dass wir das erste Element der sortierten Liste haben wollen:

minimum xs = head (quickSort xs)

Die Funktion quickSort wird dabei dann automatisch nur so weit ausgewertet, wie es notwendig ist, um zu ermitteln welches das erste Element ist.

Typinferenz

Ein statisches Typsystem, bei dem jedoch die Typen aller (oder der meisten) Ausdrücke inferiert, d.h. automatisch hergeleitet werden können, ist seit den 1970er Jahren in vielen funktionalen Sprachen vorhanden.

An dem Beispiel von gerade eben, der Funktionen miminum und quickSort kann man das schon gut erkennen:

minimum xs = head (quickSort xs)

Es ist nicht nötig hier die Typen der Parameter oder des Rückgabewerts zu deklarieren. Der Compiler inferiert den allgemeinsten Typ für die Funktion minimum und würde eine Fehlermeldung ausgeben, wenn man sie beispielsweise mit einer Zahl aufrufen wollte.

Zusammenfassung

Funktionale Programmierung ist also im Kern einfach nur das Programmieren mit Lambda-Ausdrücken, hat aber in seiner langen Geschichte viele ausgereifte Konzepte hervorgebracht, die nicht nur in diesem Blog jede Woche erläutert werden, sondern auch in der Industrie immer größere Verwendung finden.

Hier noch ein paar Links auf frühere Blog-Artikel, die diese und weitere Konzepte besonders beleuchten: