Funktionale Programmierung

Funktionale Programmierung ist ein Programmierparadigma, in dem Funktionen nicht nur definiert und angewendet werden können, sondern auch wie Daten miteinander verknüpft, als Parameter verwendet und als Funktionsergebnisse auftreten können. Dadurch kann ein funktionales Programm sehr weitreichend neue Berechnungsvorschriften zur Laufzeit zusammensetzen und anwenden. Programmiersprachen, die funktionale Programmierung ermöglichen, werden als funktionale Programmiersprachen bezeichnet.

Die funktionale Programmierung entspringt der mathematischen Grundlagenforschung. In den 1930er Jahren entwickelte Alonzo Church den Lambda-Kalkül als Instrument, um das Entscheidungsproblem zu bearbeiten und dazu den Begriff der berechenbaren Funktion zu definieren. Der Lambda-Kalkül selbst beschäftigt sich nicht mit bestimmten Funktionen, sondern ist nur ein Regelwerk dafür, wie die Anwendung von Funktionen auf ihre Argumente erfolgt und wie dabei mit freien und gebundenen Variablen verfahren wird.

Die besonderen Eigenschaften der funktionalen Programmierung ermöglichen es, auf die in der prozeduralen Programmierung benötigten Zustandsänderungen außerhalb eines Unterprogrammes, die auch Seiteneffekte genannt werden, zu verzichten, falls sie überhaupt möglich sind. Der Verzicht auf die Seiteneffekte vereinfacht auf der einen Seite die semantische Analyse eines Computerprogramms erheblich und eröffnet auf der anderen Seite weitreichende Möglichkeiten zur regelbasierten, algebraischen Programmtransformation und -synthese. Daraus ergibt sich die erhebliche praktische Bedeutung der funktionalen Programmierung für die Informatik.

Eine weitere Konsequenz ist, dass es in funktionaler Programmierung besonders einfach ist, Algorithmen ohne Berücksichtigung der Beschaffenheit der bearbeiteten Datenobjekte zu beschreiben und dadurch generischen Programmcode zu erstellen. Viele funktionale Verfahren sind so generisch, dass sie seit den 1950er Jahren keiner Anpassung unterworfen werden mussten.

Die erste bedeutende, in funktionaler Programmierung erstellte Software ist der von John McCarthy im Jahr 1958 erstellte, metazirkuläre Lisp-Interpreter mit Namen eval, der die Semantik von LISP aus fünf einfachen Funktionen zusammengesetzt darstellt. Er findet auf einer DIN-A4-Seite Platz und ist bis heute konzeptionelle Grundlage für die Implementierung der meisten Programmiersprachen.

Definition Die funktionale Programmierung ist durch folgende Eigenschaften gekennzeichnet:

Computerprogramme werden als Funktionen verstanden, die für eine Eingabe eine Ausgabe liefern, die nur von dieser abhängig ist. Funktionen werden nicht als Abfolge von Anweisungen dargestellt, sondern als ineinander verschachtelte Funktionsaufrufe. Funktionen sind gegenüber allen anderen Datenobjekten gleichberechtigt. Das bedeutet, dass sie als Parameter in Funktionen eingehen dürfen und ebenso als Berechnungsergebnisse aus Funktionen hervorgehen können. Insbesondere können Funktionen wie andere Datenobjekte zur Laufzeit erstellt werden oder entfallen. Eine Funktion kann auf Variablen Bezug nehmen, die dem Kontext angehören, in dem ihre Erstellung erfolgt ist. Dies kann sie auch dann noch tun, wenn sie den Kontext verlassen hat. Die Belegung der Variablen zum Zeitpunkt des Verlassens dieses Kontextes wird dann innerhalb dieser Funktion eingefroren. Eine so entstandene Funktion heißt Closure und die eingefrorenen Variablenbelegungen heißen Closure-Variablen. Funktionsdefinitionen können insbesondere bei Funktionsanwendungen ohne explizite Namensgebung literal in der Stellung des Funktionssymbols stehen. Solche Funktionen heißen anonym und werden oft salopp „Lambdas“ genannt.

Funktionale Programmiersprachen Eine rein funktionale Programmiersprache wäre strikt isomorph zum Lambda-Kalkül. Das gilt mit minimalen Einschränkungen beispielsweise für die esoterische Programmiersprache unlambda.

Wichtige Vertreter funktionaler Programmiersprachen sind die Lisp-Programmiersprachenfamilie und die rein funktionale Programmiersprache Haskell. Vornehmlich zur funktionalen Programmierung gedachte Sprachen sind: Clojure (2007) Elixir (2011) Erlang (1987) F# (2002) Haskell (1990) LISP (1958) ML (1973) OCaml (1996) Scala (2004).

Fast alle in jüngster Zeit entstandenen Programmiersprachen gestatten funktionale Programmierung. Sprachen, die funktionale Programmierung neben anderen Paradigmen ermöglichen, sind zum Beispiel Perl, ECMAScript, Dylan, Ruby und Visual Basic.NET. Python hat Einschränkungen bei der Formulierung von anonymen Funktionen. Viele eigentlich objektorientierte Sprachen wurden in jüngsten Versionen aufgerüstet wie C++ (ab Version 11), Delphi (ab Version 2009) oder Java (ab Version 8). Allerdings leidet darunter die Syntax, sodass die Kompaktheit von LISP oder Haskell nicht erreicht wird.

Populäre Programmiersprachen, die keinerlei Möglichkeiten zur funktionalen Programmierung bieten, sind zum Beispiel C und VBA.

Mathematische Konzepte Die allgemeingültigen Konzepte der funktionalen Programmierung entstammen der Mathematik der 1930er und 1940er Jahre. Von besonderer Bedeutung sind der Lambda-Kalkül und die Kategorientheorie. Der Lambda-Kalkül ist ein operatives Regelwerk, mit dessen Hilfe die Bedeutung von symbolischen Ausdrücken bestimmt werden kann. Kategorientheoretisch (Kategorientheorie) sind Datentypen Objekte und Funktionen Morphismen, die zwischen diesen abbilden und für die die gewöhnliche Funktionskomposition als zweistellige, assoziative Verknüpfung und die Identitäts-Abbildung als neutrales Element definiert ist. Damit bilden die Funktionen eine „Gruppe ohne das Gesetz vom inversen Element“.

Listen In der imperativen Programmierung übliche Datenstrukturen wie Arrays sind in der funktionalen Programmierung schwierig im Gebrauch, da sie durch Rekursion nur schwierig darstellbar sind, auch wenn es Ansätze wie das Functional Programming System gibt, die explizit mit solchen Strukturen arbeiten. Listen und Bäume sind hingegen sehr gut mit der Funktionalen Programmierung verträglich.

Sei ein beliebiger Datentyp. Dann ist der Typ der beliebig langen Listen mit mindestens 0 Elementen des Typs gegeben durch die Rekursion . Dabei ist die leere Liste und eine zweistellige Operation, die aus einem Wert und einer Liste eine neue Liste konstruiert, indem sie vorne an anhängt.

Man kann diesen rekursiven Aufbau benutzen, um Funktionen zu schreiben, die eine Liste zerlegen und dabei einen Wert ermitteln. Eine solche Funktion heißt Katamorphismus.

Katamorphismen Sei ein Datentyp, ein Wert und eine Abbildung. Dann ist durch

der Katamorphismus (zu griech. κατά = entlang, herab) mit Initialwert und Verknüpfung gegeben. In der üblichen Notation mit Bananenklammern wird er als geschrieben. Im Sinne der funktionalen Programmierung ist die Zirkumfix-Operation eine Funktion höherer Ordnung. In funktionalen Programmiersprachen gibt es zur Berechnung von Katamorphismen die Funktion reduce oder fold. Ein Katamorphismus, der obiger Definition folgt, ist rechtshändig. Er entspricht der folgenden Programmschleife, die eine Liste von ihrem Ende her traversiert:

Ein linkshändiger Katamorphismus würde beim Index 1 beginnen.

Viele grundlegende Verfahren der Programmierung sind Katamorphismen. So berechnet die Summe einer Zahlenliste, hängt Strings aneinander und mit berechnet die Länge einer Liste. Eine Funktion, die eine Liste nach Elementen filtert, die die Eigenschaft erfüllen, kann mit der Funktion aus errechnet werden, die wie folgt definiert ist: mit falls und sonst.

Ist die Operation assoziativ mit dem neutralen Element , dann ist der Katamorphismus die eindeutige Erweiterung der Operation auf beliebig viele Argumente. Das ist eine nützliche Eigenschaft, die viel Arbeit in der praktischen Programmierung einsparen kann. Ist zum Beispiel eine zweistellige Funktions-Komposition bereits implementiert, so lässt sich die Komposition von Funktionen als darstellen (dabei ist die identische Abbildung).

Anamorphismen Während Katamorphismen Listen zu Einzelwerten reduzieren, bauen Anamorphismen Listen aus Einzelwerten auf. Die Begriffe sind dual zueinander.

Es sei ein Prädikat und eine Abbildung. Ein Anamorphismus ist dann so definiert:

Der Anamorphismus mit Generator und Prädikat wird mit Linsenklammern notiert: . Ein Beispiel für einen einfachen Anamorphismus ist die Funktion . Sie errechnet aus einer natürlichen Zahl die (umgedrehte) Liste der ersten natürlichen Zahlen .

Hylomorphismen Sei ein Katamorphismus und ein Anamorphismus. Dann ist die Abbildung ein sogenannter Hylomorphismus (). Hylomorphismen sind in der Lage, einen ganzen Verarbeitungsprozess darzustellen, innerhalb dessen eine Struktur durch einen Anamorphismus entwickelt und durch einen Katamorphismus wieder eingedampft wird. Diese Darstellung ermöglicht es, die durch den Anamorphismus erzeugte Zwischenstruktur algebraisch zu entfernen.Patrick M. Krusenotto: Funktionale Programmierung und Metaprogrammierung. Springer, Wiesbaden 2016, S. 217ff, S. 244 ff. Die daraus resultierende, eigenständige Darstellung des Hylomorphismus ohne Zwischenstruktur führt in der Praxis zu einer erheblichen Reduktion des benötigten Speicherplatzes.

Es ist problemlos möglich, einen komplexeren Algorithmus wie den Minimax-Algorithmus, der den besten Zug in einem Zweipersonenspiel wie Schach findet, als Hylomorphismus darzustellen. Der Hylomorphismus , der den Katamorphismus zur Berechnung eines Zahlenprodukts mit dem oben genannten Anamorphismus kombiniert, berechnet die Fakultät einer Zahl.

Abgrenzung von imperativer Programmierung Im Gegensatz zu imperativen Programmen, die aus Rechenanweisungen bestehen, sind funktionale Programme eine Menge von (Funktions)-Definitionen, die mathematisch eine partielle Abbildung von Eingabedaten auf Ausgabedaten sind und gleichzeitig selbst aus Funktionsaufrufen zusammengesetzt sind.

Ein typisches Beispiel ist die Berechnung der Fakultät n! einer Zahl n (n! = 1 · 2 · 3 · … · n), hier eine imperative Lösung: Eingabe: Zahl n Ausgabe: Zahl b (= 1 · 2 · 3 · … · n) Algorithmus: b := 1 (Zuweisung)

solange n > 0 führe aus b := n · b n := n − 1

Ausgabe: b

Charakteristisch für die imperative Programmierung sind hier die Zuweisungen (Änderung von Werten, durch das Symbol := im Pseudocode repräsentiert). Zwar berechnet der Algorithmus die Fakultät der Zahl n, aber die Korrektheit dieses Rechenweges ist nicht offensichtlich.

Nun kann man die Fakultät jedoch auch mithilfe von rekursiven Funktionen definieren, was zur funktionalen Lösung führt.

Funktion f(n): wenn n > 0 dann: Ausgabe: n · f(n - 1) sonst wenn n = 0 dann: Ausgabe: 1

Die funktionale Programmierung kommt also ohne Schleifen und Zuweisungen aus, benötigt dafür aber Rekursion.

Lambda-Kalkül Die theoretische Grundlage der funktionalen Programmierung ist der λ-Kalkül (Lambda-Kalkül) von Alonzo Church. Jeder Ausdruck und jeder Wert wird dabei als auswertbare Funktion betrachtet, so dass die ganze Programmierung auf der Übergabe von Funktionen als Parameter an Funktionen fußt.

Der Lambda-Kalkül erlaubt es, vollständige Teilausdrücke separat auszuwerten. Dies ist der wichtigste Vorteil gegenüber der imperativen Programmierung. Dieses Konzept vereinfacht die Programmverifikation und Programmoptimierung, beispielsweise die Überführung der Programme in eine parallel auswertbare Form.

Typsystem