Wikipedia · einfach zusammengefasst · Stand
Funktionale Programmierung
Funktionale Programmierung ist ein Programmierparadigma, in dem Funktionen nicht nur definiert und angewendet werden können, sondern auch wie Daten …
Inhalt5 Abschnitte
Grundidee und Bedeutung
Funktionale Programmierung ist ein Programmierparadigma: Programme werden als Funktionen verstanden, die zu einer Eingabe eine Ausgabe liefern, die nur von dieser Eingabe abhängt. Funktionen werden dabei nicht als Folge von Anweisungen, sondern als ineinander verschachtelte Funktionsaufrufe dargestellt.
Entscheidend ist, dass Funktionen gleichberechtigte Datenobjekte sind. Sie können als Argument an andere Funktionen übergeben, als Ergebnis zurückgegeben und zur Laufzeit erzeugt oder entfernt werden. Dadurch lassen sich neue Berechnungsvorschriften zur Laufzeit zusammensetzen und anwenden. Funktionen dürfen außerdem Variablen aus ihrem Entstehungskontext weiter verwenden. Verlässt eine solche Funktion ihren Kontext, bleiben die damaligen Variablenbelegungen eingefroren; die Funktion heißt Closure, die gespeicherten Belegungen heißen Closure-Variablen. Namenlose Funktionen, die direkt an der Stelle eines Funktionssymbols stehen, heißen anonyme Funktionen oder salopp „Lambdas“.
Die Grundlage liegt im von Alonzo Church in den 1930er Jahren entwickelten Lambda-Kalkül. Er ist ein Regelwerk für Funktionsanwendungen sowie freie und gebundene Variablen; jeder Ausdruck und jeder Wert kann darin als auswertbare Funktion betrachtet werden. Funktionale Programmierung kann auf Zustandsänderungen außerhalb eines Unterprogramms, also Seiteneffekte, verzichten. Das erleichtert die semantische Analyse, Programmverifikation, regelbasierte algebraische Programmtransformation und -synthese sowie die Überführung in parallel auswertbare Formen. Außerdem lassen sich Algorithmen häufig unabhängig von konkreten Datenobjekten und damit generisch beschreiben.
Sprachen, Typen und Wirkungen
Eine rein funktionale Sprache wäre mit minimalen Einschränkungen strikt isomorph zum Lambda-Kalkül; als Beispiel wird unlambda genannt. Wichtige funktionale Sprachen sind die Lisp-Familie und Haskell. Vornehmlich für funktionale Programmierung gedacht sind Clojure (2007), Elixir (2011), Erlang (1987), F# (2002), Haskell (1990), LISP (1958), ML (1973), OCaml (1996) und Scala (2004).
Viele neuere Sprachen unterstützen funktionale Programmierung zusätzlich zu anderen Paradigmen, etwa Perl, ECMAScript, Dylan, Ruby und Visual Basic.NET. Python schränkt die Formulierung anonymer Funktionen ein. C++ ab Version 11, Delphi ab Version 2009 und Java ab Version 8 wurden entsprechend erweitert; laut Artikel wird dabei aber nicht die Kompaktheit von LISP oder Haskell erreicht. C und VBA bieten keinerlei Möglichkeiten zur funktionalen Programmierung.
Lisp und Scheme sind dynamisch typisiert. Seit Standard ML (SML) sind statisch typisierte Sprachen wichtig, besonders mit dem Hindley-Milner-Typsystem. Es verbindet parametrischen Polymorphismus – Werte oder Funktionen können für verschiedene Typen verwendbar sein – mit Typinferenz: Der Übersetzer ermittelt Typen automatisch und kann Typfehler bereits beim Übersetzen melden. Dynamisch typisierte Sprachen wie Lisp und Python melden Typfehler dagegen erst zur Laufzeit, erlauben aber eine breitere Anwendung bereits definierter Funktionen auf später entstandene Einsatzgebiete. Hindley-Milner erlaubt nur Polymorphismus ersten Ranges; in GHC existieren Erweiterungen für den zweiten und allgemein k-ten Rang, die explizite Annotationen benötigen, weil Typinferenz ab dem zweiten Rang unentscheidbar ist.
Rein funktionale Sprachen kennen keine während der Berechnung veränderbaren Zustandsvariablen. Für Benutzerinteraktion und Ein-/Ausgabe sind besondere Vorkehrungen nötig. Standard ML, Caml und Scheme erlauben Wirkungen und sind daher nicht rein funktional. Haskell verwendet Monaden aus der Kategorientheorie, insbesondere nach Eugenio Moggi und Philip Wadler: Parametrische Typen kennzeichnen Wirkungen und zwingen das Typsystem zur Unterscheidung von Ausdrücken mit und ohne Wirkungen. Clean und Mercury verwenden dafür „Uniqueness“-Typen.
Listen, Faltungen und Erzeugung von Listen
Mathematische Konzepte der funktionalen Programmierung stammen vor allem aus Lambda-Kalkül und Kategorientheorie. Kategorientheoretisch sind Datentypen Objekte und Funktionen Morphismen zwischen ihnen. Funktionskomposition ist eine zweistellige assoziative Verknüpfung, die Identitäts-Abbildung ihr neutrales Element; die Funktionen bilden damit eine „Gruppe ohne das Gesetz vom inversen Element“.
Listen und Bäume passen gut zur funktionalen Programmierung, während Arrays wegen der Rekursion schwieriger verwendbar sind. Für einen beliebigen Datentyp A ist der Typ beliebig langer Listen gegeben durch A* = Nil | Cons(A,A*). Nil ist die leere Liste. Cons:A × A* → A* hängt einen Wert a vorne an eine Liste L an und erzeugt eine neue Liste M.
Ein Katamorphismus zerlegt eine Liste und berechnet dabei einen Wert. Für b ∈ B und ⊗:A × B → B gilt: h: A* → B, Nil ↦ b und Cons(a,L) ↦ a ⊗ h(L). In Bananenklammern lautet die Schreibweise h = (|b,⊗|). Diese rechtshändige Faltung entspricht einem Durchlauf vom Listenende zum Anfang; in Programmiersprachen heißen entsprechende Funktionen reduce oder fold. Beispiele sind (|0,+|) für die Summe einer Zahlenliste, (|ε,·|) zum Aneinanderhängen von Strings und (|0,Inc|) mit Inc:(n,k) ↦ k+1 für die Listenlänge. filter kann als Faltung konstruiert werden: Es fügt ein Element a nur dann wieder mit Cons(a,L) ein, wenn das Prädikat p(a) erfüllt ist. Ist eine Operation assoziativ und hat ein neutrales Element ∅, erweitert (|∅,h|) sie eindeutig auf beliebig viele Argumente. Die Komposition n Funktionen lässt sich daher als (|id,∘|) schreiben.
Anamorphismen sind dual zu Katamorphismen: Sie bauen aus einem Einzelwert eine Liste auf. Für p:B → {w,f} und g:B → A × B gilt h:b ↦ Nil bei p(b)=w, sonst h:b ↦ Cons(a,h(b')) mit [a,b']=g(b). Die Schreibweise ist h=[(p,g)]. Der Anamorphismus iota=[(i ↦ (i<1), i ↦ [i,i-1])] erzeugt aus n die umgedrehte Liste iota(n)=[n,n-1,n-2,..,1]. Ein Hylomorphismus verbindet beides: (|z,f|)∘[(p,g)] erzeugt zunächst eine Struktur und reduziert sie anschließend. Die Zwischenstruktur kann algebraisch entfernt werden, was Speicher spart. Der Hylomorphismus (!=(|1,×|)∘[(i ↦ (i<1),i ↦ [i,i-1])]) berechnet die Fakultät.
Abgrenzung, höhere Ordnung und Auswertung
Imperative Programme bestehen aus Rechenanweisungen und verändern häufig Werte durch Zuweisungen. Funktionale Programme sind dagegen Funktionsdefinitionen: mathematisch partielle Abbildungen von Eingabe- auf Ausgabedaten, die selbst aus Funktionsaufrufen bestehen. Bei der imperativen Fakultätsberechnung wird zunächst b := 1 gesetzt und dann in einer Schleife b := n · b sowie n := n − 1 ausgeführt. Zuweisungen sind hier charakteristisch; die Korrektheit des Rechenwegs ist nicht unmittelbar offensichtlich.
Funktional lässt sich dieselbe Berechnung rekursiv definieren: n! = f(n) = n · f(n−1) für n>0 und n! = 1 für n=0. Dadurch werden Schleifen und Zuweisungen durch Rekursion ersetzt.
Funktionen höherer Ordnung behandeln Funktionen selbst als Werte. Sie können also Funktionen entgegennehmen oder liefern. Ein klassisches Beispiel ist ein Ableitungsoperator: Er erhält eine differenzierbare Funktion und gibt ihre Ableitung zurück. map erhält eine Funktion f und eine Liste l und wendet f auf jedes Listenelement an. In Haskell gilt: map f [] = [] und map f (x:xs) = f x : map f xs.
Bei strikter Auswertung werden Funktionsargumente zuerst ausgewertet; bei nicht-strikter Auswertung werden Ausdrücke zunächst als Ganze übergeben. Für (3+5)^2 ergibt strikte Auswertung zuerst 8^2 und dann 64. Bei nicht-strikter Auswertung wird zunächst (3+5)·(3+5) gebildet und danach 8·8=64. Bedarfsauswertung (lazy evaluation) wertet einen Ausdruck erst aus, wenn sein Wert benötigt wird. Damit lassen sich etwa unendlich große Listen aller natürlichen Zahlen oder aller Primzahlen definieren. Je nach Berechnung kann eine Strategie effizienter sein. Terminiert die strikte Auswertung, terminiert auch die nicht-strikte; dies folgt aus der Konfluenz-Eigenschaft des Lambda-Kalküls, nach der das Ergebnis nicht von der Auswertungsreihenfolge abhängt.
Algorithmen, Datenstrukturen und Programmbeispiel
Ohne Zuweisungen lassen sich viele klassische Algorithmen und Datenstrukturen nicht unverändert übernehmen; dafür werden funktionale Lösungen benötigt. Funktionale Datenstrukturen sind oft persistent: Sie verwalten mehrere Versionen ihrer Daten. Übliche ephemere Datenstrukturen verwalten dagegen meist nur eine Version.
Ein typisches Beispiel ist ringarea, die Fläche zwischen zwei konzentrischen Kreisen mit Radien r1 und r2 berechnet, vorausgesetzt r1 ≥ r2. Die Formel lautet A = π · (r1² − r2²). Dazu wird eine Hilfsfunktion sq definiert, die x mit sich selbst multipliziert, und ringarea berechnet pi · (sq r1 − sq r2). Die Beispiele zeigen diese Struktur unter anderem in Common Lisp, F# und OCaml, Haskell, Joy, Julia, Python, Matlab, Scala, Kotlin, Java, Scheme, SML und Swift.
In Haskell ist ringArea mit dem Typ (Floating a) => a -> a -> a angegeben; sq und ringArea sind polymorph, pi ist vordefiniert und die Typangabe kann vom Compiler inferiert werden. Joy nutzt umgekehrte polnische Notation und behandelt auch pi als Funktion. In SML muss x als real typisiert werden, weil ein SML97-Übersetzer sonst int inferieren würde; Ursache ist die Überladung von Operatoren.
XSLT dient zur Transformation von XML, insbesondere in XHTML, und wird im Artikel als funktional beschrieben. Das Beispiel str:reverse kehrt die Wortreihenfolge einer Zeichenkette rekursiv um: Für „DOG BITES MAN“ wird jeweils der Teil nach dem ersten Leerzeichen rekursiv verarbeitet und anschließend das vorherige Wort angehängt.
