Was ist funktionale Programmierung?
Was ist funktionale Programmierung und was macht eine funktionale Sprache aus? Diese Fragen sind gar nicht so einfach oder eindeutig zu beantworten.
Wie der Name schon sagt, wird in der funktionalen Programmierung viel mit Funktionen gearbeitet. Insbesondere sollte es möglich sein, Funktionen als ganz normale Werte zu benutzen. Funktionen dürfen also Rückgabe oder Übergabeparameter in anderen Funktionen zu sein. Diese nennt man dann Funktionen höherer Ordnung.
Aber was ist eigentlich eine Funktion? Programmierer haben hier durchaus unterschiedliche Vorstellungen von diesem Begriff. Ist eine Methode eine Funktion? Was ist mit Seiteneffekten – darf eine "Funktion" also beispielsweise eine Datei schreiben oder lesen? Wenn das nicht erlaubt ist, ist eine Sprache, die das nicht erlaubt, dann nicht ein wenig "nutzlos" im Alltag?
Viele der modernen funktionalen Sprachen scheinen großen Wert auf ein "mächtiges" Typsystem zu legen. Ist eine Sprache jetzt funktionaler, je besser ihr Typsystem ist? Um das gleich vorwegzunehmen: Nein, eine funktionale Sprache muss nicht "rein" – also ohne Seiteneffekte sein – und ein Typsystem muss sie auch nicht mitbringen – aber helfen kann beides.
Wo kommen die Ideen her?
Die Geschichte der funktionalen Programmierung reicht, wie vieles in der Informatik, vor die Zeit von Computern zurück. In den 1920er Jahren waren viele Mathematiker der Meinung, dass in naher Zukunft Methoden gefunden werden könnten, die Antworten auf praktisch alle mathematischen Fragen geben würden. Einige – darunter auch Alan Turing und Alonzo Church – haben sich dabei mit dem Problem befasst, was es eigentlich heißt, dass "etwas berechenbar" ist. Aus diesen Arbeiten und Ideen sind unsere Computer und Programmiersprachen entstanden.
Church führte sein "Lambda-Kalkül" ein, das später sehr direkt Lisp inspiriert hat und das man durchaus die erste "funktionale Sprache" betrachten kann [1]. Sein Student Turing befasste sich mit abstrakter Maschine, die wir heute "Turingmaschine" nennen und die man durchaus als geistigen Vorgänger unser heutigen Computer sehen kann.
Beide Ideen stellten sich als äquivalent heraus [2]. In der Praxis hat sich allerdings der deklarative – wir würden heute sagen "funktionale" – Ansatz von Church zunächst nicht durchsetzen können. In den letzten Jahrzehnten hat sich das aber dann etwas relativiert.
Aber zurück zu diesem seltsamen Kalkül. Es würde diesen Artikel sprengen, hier eine tatsächliche Einführung zu geben. Aber ein kleiner Einblick sei erlaubt.
Im Lambda-Kalkül sind Ausdrücke aus 3 Bausteinen zusammengesetzt:
- Symbole (a,b,..),
- Abstraktionen (λ x. B – x ist hier ein Symbol und b ein anderer Ausdruck im Kalkül) und
- Applikationen (F X – F und X sind hier andere Ausdrücke im Kalkül).
Ein Programmierer würde eine Abstraktion heute sicher als anonyme Funktion oder eben als Lambda-Funktion erkennen. Im modernen JavaScript wäre eine Übersetzung etwa x => ...B... Eine Applikation entspricht einfach dem Aufrufen einer Funktion mit einem Wert oder besser: dem Anwenden von einer Funktion auf einen Wert f(x). Dann gibt es noch eine Hand voll Regeln wann Ausdrücke im Kalkül "gleich" sind und wie Ausdrücke "umgeformt" werden können.
Die hier interessante Regel beschreibt die Applikation einer Abstraktion mit einem Term. Im wesentlichen wird hier jedes Vorkommen der Variablen im "Körper" der Funktion mit dem eingesetzten Term ersetzt.
Hier ein Beispiel:
(λf.f 1) (λx.x)
ersetze f mit λx.x:
= (λx.x) 1
ersetze x mit 1:
= 1
Was in JavaScript (f => f(1))(x=>x) entsprechen würde und natürlich auch 1 ergibt.
Was hier auffällt ist, dass es in diesem Kalkül tatsächlich nicht mehr als Funktionen und Symbole gibt. Es gibt zunächst keine Darstellung von Zahlen oder anderen Werten und es gibt auch keinen Konstruktor zur Programmsteuerung wie etwa if. Trotzdem ist das Lambda-Kalkül "Turing-Komplett"!
Hier ein kleiner Ausblick. wie das sein kann: Die Repräsentation der booleschen Konstanten true und false im Lambda-Kalkül sind λx.λy.x für true und λx.λy.y für false. In JavaScript wäre das wieder x => (y => x) und x => (y => y). Das Faszinierende ist, dass in dieser sogenannten "Church-Kodierung" von true und false das if praktisch schon eingebaut ist:
true t f
Definition von `true`:
= ((λx.λy.x) t) f
Applikation
= (λy.t) f
Applikation
= t
oder vielleicht leichter zu lesen in JavaScript:
(x => y => x)('then-Branch')('else-Branch') // => "then-Branch"
(x => y => y)('then-Branch')('else-Branch') // => "else-Branch"Versuchen Sie es doch mal – Sehen Sie, wie das ein if impliziert? Keine Sorge, es ist für das Verständnis des Artikels nicht notwendig, wenn Sie es nicht gleich sehen.
Der if-Ausdruck bzw. die if-Funktion würde dann einfach so aussehen:
const ifExp =
bedingung => thenBranch => elseBranch => bedingung(thenBranch)(elseBranch)Ähnliche Kodierungen gibt es für natürliche Zahlen (die implizieren eine Art for-Schleife), Listen (die implizieren eine fold/reduce-Operation) usw. Damit aber genug der Geschichtsstunde – begeben wir uns zurück in die Gegenwart.
Was sind "reine" Funktionen?
Funktionen sind in der funktionalen Programmierung also überall. Aber eigentlich sind hier ganz bestimmte Funktionen gemeint und zwar solche, wie sie die Mathematik definiert. Für jeden möglichen Eingabewert sollte eine Funktion insbesondere immer genau einen Rückgabewert liefern. Das klingt zunächst harmlos, aber vieles von dem, was wir als Entwickler tun, widerspricht diesem Prinzip.
Fragen wir beispielsweise die Systemzeit ab, liefert diese Funktion nach einem Augenblick einen anderen Wert:
const currentTime = () => new Date().toLocaleString()
>> currentTime()
'5/1/2021, 8:00:00 AM'
>> currentTime()
'6/1/2021, 8:00:01 AM'currentTime kann also keine "Funktion" in dem hier verwendeten Sinn sein, weil offensichtlich currentTime () nicht immer den gleichen Wert liefert. Gleiches gilt natürlich auch für Datenbankabfragen und Ähnliches.
Ein weiterer Vorteil von mathematischen oder "reinen" Funktionen ist es, dass sie mit ihrem Graph identifiziert werden können. Oder, bei den für uns Entwickler üblichen diskreten Wertebereichen, auch mit ihrer Wertetabelle.
Damit können wir einen Funktionsaufruf f(x) einfach mit dem Wert der Berechnung y = f(x) im Programm ersetzen, ohne dass sich das Programm dadurch im Verhalten verändern kann. Diese Eigenschaft wird auch Referenzielle Transparenz genannt [3].
Das steckt auch hinter den Ableitungen, die wir oben im Lambda-Kalkül berechnet haben. Funktionale Programmierer nutzen diese Technik – auch equational Reasoning genannt [4] – gerne, um zu "beweisen", dass eine Funktion tut, was sie soll oder um eine alternative Repräsentation herzuleiten.
Streng genommen ist es dabei nicht mal nötig, alle Seiteneffekte zu verbieten. Diese dürfen nur nicht von außen beobachtbar sein. In F# ist es beispielsweise nicht unüblich, innerhalb einer Funktion Variablen zu ändern, um die Funktion performanter zu machen. Und natürlich geschieht das zur Laufzeit in unseren Rechnern sowieso. Register werden geändert und die CPU wird warm – alles Seiteneffekte.
Was heißt das aber für Variablen? Das Verändern von Variablen-Werten führt fast immer zu einem beobachtbaren Effekt (Ausnahmen sind etwa lokale Variablen in Funktionen). Es macht also Sinn, dass Variable nach dem Initialisieren nicht mehr verändert werden sollten. Sie sind in funktionalen Sprachen oft standardmäßig unveränderlich. Deswegen wird in der funktionalen Programmierung lieber von Werten als von Variablen gesprochen.
Programmiersprachen (wie etwa Haskell), die diese reinen Funktionen und unveränderlichen Daten wirklich durchsetzen, können alle diese Eigenschaften nutzen, um weitgehende Optimierungen am Programmcode durchzuführen, die sonst nicht möglich wären. Selbst die Reihenfolge von Aufrufen kann so sicher geändert werden.
Wie kann dann aber zum Beispiel in Haskell die System-Zeit abgefragt werden? Haskell verwendet für Seiteneffekte einen speziellen Typ IO. Die getCurrentTime-Funktion von oben kann in Haskell dann in etwa so geschrieben werden:
getCurrentTime :: () -> IO String
getCurrentTime () =
show <$> Time.getZonedTimeBemerkung: Natürlich würde ein "Haskeller" das nicht so schreiben – () ist hier überflüssig (schon wegen der referentiellen Transparenz) – aber sonst wäre es keine Funktion mehr und der Vergleich zu oben ist dann vielleicht nicht ganz so offensichtlich.
Der "Trick" ist jetzt, dass getCurrentTime sehr wohl bei jedem Aufruf das Gleiche zurückgibt. Denn die Rückgabe enthält noch nicht den String mit der Systemzeit, sondern eine Art "Rezept" oder "Anweisung", wie die Runtime diese Zeichenkette berechnen kann.
Das Ausführen übernimmt dann die Runtime über den Einstiegspunkt main :: IO (). Alternativ führt die REPL (Read-Eval-Print-Loop) die IO-Berechnungen ebenfalls automatisch aus, um das Ergebnis anzuzeigen.
Folgende REPL-Sitzung verdeutlicht das etwas:
> getCurrentTime ()
"2021-05-01 08:30:28.843711694 CEST"
> getCurrentTime ()
"2021-05-01 08:30:32.367012759 CEST"Wie erwartet liefert jeder Aufruf von getCurrentTime() eine andere Ausgabe. Aber tatsächlich nur, weil die REPL hier den IO String ausführt und anzeigt. Was passiert, wenn wir den Rückgabewert selber mehrfach ausführen lassen?
> timeIO = getCurrentTime ()
> :t timeIO
timeIO :: IO String
> timeIO
"2021-05-01 08:40:59.670154962 CEST"
> timeIO
"2021-05-01 08:41:00.777721733 CEST"Der gleiche "Seiteneffekt" tritt auf – eben weil der IO String-Wert selber nur das "Rezept" darstellt, um die lokale Systemzeit als Zeichenkette abzufragen.
Etwas philosophischer ist noch eine andere Erklärung: Konzeptionell erhält IO String noch eine weitere Eingabe: "Den Zustand der ganzen Welt" und liefert noch eine weitere Ausgabe: "Den neuen Zustand der ganzen Welt". Somit sind auch diese Werte als eigene Funktion tatsächlich auch wieder mathematisch korrekte Funktionen.
Currying und Partial Applikation
Wenn Sie sich die Definition von const lcTrue = x => y => x von oben noch einmal ansehen, fragen Sie sich vielleicht, warum die Funktion hier nicht einfach als (x,y) => y definiert wurde.
Im Lambda-Kalkül gibt es hier direkt zunächst keine Möglichkeit, eine Funktion mit mehr als einem Argument zu definieren. Deswegen wird diese zunächst ungewohnte Variante genutzt, in der eine Funktion eine andere zurückgibt. Diese Art, eine Funktion mit mehreren Argumenten zu definieren, nennt man "Currying" – nach dem Mathematiker Haskell Curry [5].
Die meisten funktionalen Sprachen bevorzugen es, Funktionen in dieser Weise zu definieren. In dieser Variante ist es nämlich besonders einfach, die ersten Parameter anzugeben um eine "spezialisierte" Variante der Funktion zu erhalten. Diese Technik wird "partial application" (partielle/teilweise Anwendung) genannt.
Hier ein kleines Beispiel: Eine Funktion const addition = a => b => a+b kann mit 10 aufgerufen werden, um eine neue Funktion const add10 = addition(10) zu erhalten. Diese Funktion addiert dann eben 10: add10(1) = 11.
Funktionale Programmierer nutzen das überall – besonders oft zusammen mit dem "Pipe-Operator" |>, der ja demnächst vielleicht sogar in JavaScript verfügbar sein wird [6].
Hier ein kleine F#-Funktion, die die Summe der ersten n natürlichen Zahlen berechnet:
let sumSquares n =
[1..n]
|> List.map (fun x -> x*x)
|> List.sum;;In der Zeile |> List.map (fun x -> x*x) wird die Funktion List.map : ('a -> 'b) -> 'a list -> 'b list partiell mit der anonymen Funktion fun x -> x*x, die eine Zahl quadriert, aufgerufen. um eine Funktion zu erhalten, die in einer Liste von Zahlen jedes Element quadriert.
Currying und partielle Anwendungen von Argumenten sind oft schwierig oder umständlich in nicht funktional-orientierten Sprachen einzusetzen, was vielleicht ein Grund ist, warum funktionale Programmierung in Mainstream-Sprachen manchmal frustrierend und komplex wirkt.
Datentypen
Bei den Datentypen bieten funktionale Sprachen meist Tupel und Records, die mehrere verschiedene Werte zusammenfassen und die es in irgendeiner Form eigentlich in jeder Sprache gibt (Klassen etwa) an. In der funktionalen Sprechweise werden diese häufig "Produkt-Typen" genannt. Der Begriff kann veranschaulicht werden, indem die einzelnen Möglichen Werte eines Typs gezählt werden.
Ein Bool-Typ etwa hat zwei Werte: true und false. Ein Record { a : bool; b : bool; c : bool } hat acht (2*2*2).
Zusätzlich haben die meisten funktional orientierten Sprachen noch einen "Summen-Datentyp" dessen Werte sich addieren. Dieser ist für die meisten Entwickler etwas ungewohnter, kann sich aber als mit Daten erweiterter Enum-Typ vorgestellt werden.
In F# könnte man zum Beispiel die Bezahlmethode eines Shops darstellen als
type Zahlmethode =
| Barzahlung
| Überweisung of Kontonummer
| Kreditkartenzahlung of Kartennummer * DateTimeHier hätte die Zahlungsmethode Barzahlung keine weiteren assoziierten Werte, Überweisung eine (die Kontonummer) und Kreditkartenzahlung zwei (die Kartennummer und das Gültigkeitsdatum).
Da in einem solchen Summen-Typ in der Regel auch ein Tupel mit angegeben werden kann – wie auch hier in Kreditkartenzahlung geschehen – werden diese Typen oft auch "algebraische Datentypen" genannt. Diese Typen sind mit wenig Zeilen Code oft so expressiv wie eine komplexe Klassenhierarchie und deswegen entsprechend beliebt unter funktionalen Programmierern.
Es ist noch anzumerken, dass anders als Klassenhierachien, diese Typen "abgeschlossen" sind – das heißt, in der Regel können diese Typen nicht an anderer Stelle oder später noch "Fälle" erhalten. In der funktionalen Programmierung ist es deswegen oft einfacher, Verhalten (Funktionen) hinzuzufügen, als in der Objektorientierung, dafür aber schwerer, Fälle hinzuzufügen. Beides zu ermöglichen ist als das Expression-Problem [7] bekannt. Es sei bemerkt, dass es sowohl in OO als auch FP Lösungen dieses Problems gibt.
Pattern-Matching
Eng mit den algebraischen Datentypen ist das sogenannte "Pattern Matching" verwandt. Damit kann eine Fallunterscheidung programmiert werden.
Hier ein einfaches Beispiel mit F#:
let zahlungsMethodeText methode =
match methode with
| Barzahlung ->
"Der Kunde hat Bar gezahlt"
| Überweisung konto ->
sprintf "Der Kunde hat per Überweisung vom Konto %O bezahlt" konto
| Kreditkartenzahlung (karteNummer, _) ->
sprintf "Der Kunde hat per Kreditkarte [%O] bezahlt" karteNummerDadurch, dass die Typen abgeschlossen sind, bieten die meisten funktionalen Sprachen hier erweiterte Unterstützung. So ist es oft eine Warnung oder gar ein Fehler, wenn nicht alle Möglichkeiten behandelt werden, wobei auch geschachteltes Pattern-Matching und Konstanten in den Patterns erlaubt sind.
Fazit
Funktionale Elemente bieten heute praktisch alle Sprachen – Funktionen als Werte zu verwenden geht eigentlich immer. Somit bieten praktisch alle beliebten Sprachen funktionale Features. Auch an funktionalen Bibliotheken mangelt es nicht. Sie dürften keine Probleme haben, funktional in JavaScript oder C# zu programmieren.
Im Detail haben die funktional orientierte Sprachen wie F#, Haskell und Co aber immer noch deutlich die Nase vorn, wenn es um Unterstützung von Currying, algebraischen Datentypen und Pattern-Matching geht, auf das viele funktionale Entwickler nicht verzichten möchten.
Und natürlich ist das noch nicht das Ende der Fahnenstange. Fortgeschrittene Features wie Typ-Klassen, Abstraktionen wie Funktoren, Monaden, etc. oder gar Dependent Types [8] sind im Moment noch nicht in den Mainstream-Sprachen angekommen.
Es lohnt sich also nach wie vor, eine "echte" funktionale Sprache zu erlernen und sei es nur, um einen Ausblick auf die Zukunft vielleicht auch im Mainstream zu bekommen.
- Wikipedia: Lambda-Kalkül
- Wikipedia: Church-Turing-These
- Wikipedia: Referenzielle Transparenz
- Wikipedia: Equational Reasoning examples
- Wikipedia: Haskell Brooks Curry
- Pipeline operator (|>)
- Wikipedia: Expression-Problem
- Wikipedia: Dependent Types
Wolfgang
am 07.06.2024