Funktionale Programmierung

Was ist funktionale Programmierung? Und was können wir von funktionalen Sprachen für unseren Engineering-Alltag lernen? ZHAW-Dozent Dandolo Flumini und Nicolas Gagliani, Senior Software Engineer bei Atpoint, haben uns in einem zweitägigen Event die spannende Welt der funktionalen Programmierung anhand der Sprache Elm näher gebracht.

Einleitung in die Funktionale Programmierung

Um ein Gefühl für funktionale Programmierung zu bekommen, schauen wir uns an, wie die Summe eines Arrays in C# (imperativ) und in Elm (funktional) berechnet wird:

int ArraySum(int[] arr)
{
  int sum = 0;
  for (int i = 0; i < arr.Length; ++i)
  {
    sum += arr[i];
  }
  return sum;
}

sum : List Int -> Int
sum xs = case xs of
    [] -> 0
    (x :: r) -> x + sum r

In Elm wird die Summe aller Elemente einer Liste durch eine rekursive Definition berechnet, die mathematischer anmutet. Der Ausdruck case xs of ist ein Pattern-Matching-Konstrukt, das die Liste in ihre Bestandteile zerlegt. Wenn die Liste leer ist, ist die Summe 0. Andernfalls wird das erste Element x der Liste zur Summe der restlichen Elemente r addiert.

Ein zentrales Merkmal der funktionalen Programmierung ist die rekursive Definition, bei der Rekursion anstelle von Schleifen verwendet wird. Dies ermöglicht eine mathematischere und elegantere Ausdrucksweise. Ein weiteres wichtiges Merkmal ist das Fehlen von Mutation. In der funktionalen Programmierung gibt es keine veränderlichen Zustände oder Variablen; stattdessen werden neue Werte aus bestehenden Werten abgeleitet.

Zudem ist die funktionale Programmierung deklarativ statt imperativ. Das bedeutet, dass der Fokus auf dem "Was" und nicht auf dem "Wie" liegt. Entwickler beschreiben, was das Programm tun soll, anstatt wie es das tun soll.

Funktionale Programmierung kann pragmatisch als eine Sammlung von Patterns betrachtet werden, die bestimmte Prinzipien betonen. Dazu gehört die Vermeidung von Seiteneffekten. Seiteneffekte, wie das Ändern von globalen Variablen oder das Schreiben in Dateien, werden vermieden, um die Vorhersagbarkeit und Testbarkeit des Codes zu erhöhen.

Ein weiteres Prinzip ist die Wiederverwendbarkeit durch Komponierbarkeit. Funktionen werden so gestaltet, dass sie leicht wiederverwendbar sind und sich zu komplexeren Funktionen zusammensetzen lassen.

In den folgenden Abschnitten wollen wir nun die fünf folgenden funktionalen Patterns genauer anschauen.

• Pure Funktionen
• Partielle Applikation
• Higher-Order Functions
• Algebraische Datentypen
• Maybe und Either

Funktionale Patterns

Pure Funktionen

Eine pure Funktion hat keine observierbaren Seiteneffekte und gibt für die gleichen Inputs immer dieselben Outputs zurück. Das heisst eine pure Funktion kann keinen State verändern.

Seiteneffekte und Veränderung von State sind transitiv, das bedeutet um zu verifizieren, dass eine Funktion pur ist muss jede von ihr gecallte Funktion überprüft werden! Deshalb kann es von Vorteil sein wenn das Typensystem pure von nicht puren Funktionen unterscheiden kann.

Pure Funktionen sind eine essentielle Basis für weitere funktionale Patterns. Durch ihre Eigenschaften können sie bedenkenlos wiederverwendet und komponiert werden, und das mit Hilfe von sogenannten Higher-Order Functions.

Partielle Applikation

Funktionale Sprachen bieten die Möglichkeit, eine Funktion partiell anzuwenden. Dabei werden einer mehrstelligen Funktion nicht alle ihre Argumente gegeben. Das Resultat einer partiellen Applikation ist wieder eine Funktion, nun aber mit weniger Argumenten. Als Beispiel können wir uns eine Inkrement-Funktion bauen indem wir die Plus-Funktion partiell anwenden.

-- Plus is just a function:
-- (+) : Int -> Int -> Int

increment : Int -> Int
increment = (+) 1

increment 5 -- 6 

Manchmal wird partielle Applikation auch 'currying' genannt, nach dem Mathematiker Haskell Curry . Partielle Applikation erlaubt es uns, generelle Funktionen schrittweise zu spezialisieren.

Higher-Order Functions

Eine Higher-Order Function ('Funktion höherer Ordnung') ist eine Funktion, die Funktionen als Argumente erhält oder Funktionen als Ergebnis liefert. Die Möglichkeit, Funktionen als Werte ('first-class citizens') zu behandeln ermöglicht weitere Abstraktionen.

Ein klassisches Beispiel einer Higher-Order Function ist map, welche eine Funktion nimmt, diese auf jedes Element einer Liste anwendet und eine Liste mit den Resultaten zurückgibt. Eine Implementation könnte folgendermassen aussehen.

map : (a -> b) -> List a -> List b
map f list = case list of
    [] -> []
    (x :: xs) -> f x :: map f xs

Wieder nutzen wir eine rekursive Formulierung, und unterscheiden die Fälle einer leeren Liste und einer Liste mit mindestens einem Element.

Eine weitere Higher-Order Function offenbart sich sobald wir bei der 'sum'⁻Funktion von oben die Rekusion von der tatsächlichen Operation trennen.

foldr : (a -> b -> b) -> b -> List a -> b
foldr op start vals = case vals of
  [] -> start
  (v :: vs) -> op v (foldr op start vs)
sumF : List Int -> Int
sumF = foldr (+) 0

Die Signatur von foldr (von "fold right", "von rechts falten") sagt uns dass sie eine andere Funktion op, einen Startwert mit generischem Typ b und eine Liste mit Elementen des generischen Typs a nimmt, und uns einen Wert vom Typ b zurückgibt.

Die Signatur der Funktion op ist ebenfalls vorgegeben, sie nimmt einen Wert vom Typ a und einen Wert vom Typ b und gibt uns ein Wert mit Typ b zurück.
Wenden wir foldr nun auf die Funktion "plus" (Präfix-Notation: (+) 1 2 == 3) mit Startwert 0 an erhalten wir eine Funktion die sich genau gleich verhält wie sum.
Bei der Definition von sumF haben wir uns die partielle Applikation von Funktionen zunutzen gemacht; indem wir foldr erst zwei der drei erwarteten Argumente geben erhalten wir eine Funktion die eine Liste von Zahlen erwartet und uns eine Zahl zurück gibt.

Ausgerüstet mit dieser Funktion höherer Ordnung können wir eine ganze Familie von Funktionen aufschreiben, die alle eine Liste von Dingen in ein einzelnes Ding 'falten'.

product = foldr (*) 1
maxElement = foldr max 0

Dem aufmerksamen Leser ist vielleicht schon aufgefallen dass sich die Struktur von sum (in der ursprünglichen Implementation), map und foldr stark ähnlich sind. Tatsächlich kann foldr benutzt werden um map zu implementieren.

map : (a -> b) -> List a -> List b
map f = foldr ((::) << f) []

Was hier geschieht ist vielleicht nicht auf den ersten Blick klar. Der Schlüssel ist der Ausdruck (::) << f, vor allem der Operator << den wir bis jetzt noch nicht angetroffen haben. f << g bildet die Komposition zweier Funktionen, also (f << g) x = f (g x). Das heisst in Worten ausgedrückt bedeutet (::) << f soviel wie 'wende zuerst die Funktion f an, und dann wende auf das Resultat (::) an'. Zur Erinnerung, (::) ist die Präfix-Version des Prepend-Operators. Da dieser Operator zwei Werte erwartet (das voranzustellende Element und die Liste), ist (::) << f eine Funktion mit Signatur (a -> List b -> List b). Diese Signatur wiederum passt genau ins erste Argument von foldr. Dass map angewendet auf eine leere Liste als Resultat auch eine leere Liste hat erklärt das zweite Argument von foldl.

Puh, das war ganz schön kompliziert. Aber mit dem Ergebnis können wir zufrieden sein, wir haben einen sehr spannenden Zusammenhang in einem einzigen Ausdruck aufschreiben können. Diese Expressivität ist eine grosse Stärke funktionaler Sprachen.
Beim Entwickeln des Ausdrucks hat uns das Typensystem (also der Compiler) stark unter die Arme greifen können, was typisch ist in funktionalen Sprachen.

Algebraische Datentypen

Produkt- und Summentypen werden als algebraische Datentypen bezeichnet. Mit Produkttypen sind wir in der Regel vertraut, da sie von vielen Sprachen unterstützt werden. Tupel oder structs sind zum Beispiel Produkttypen. Die Signatur einer Funktion die das Minimum und Maximum einer Sequenz findet sieht in C#, C++, respektive Elm so aus:

(int Min, int Max) FindMinMax(int[] nums) {...}

struct MinMax {int min; int max;};
MinMax FindMinMax(std::vector<int> nums) {...}

findMinMax : List Int -> (Int, Int)

An diesen Beispielen sehen wir dass die Felder von Produkttypen benannt sein können oder nicht. Dies hat keinen Einfluss darauf ob ein Typ ein Produkttyp ist oder nicht. Weiter unten werden wir ein Elm-Beispiel einen Produkttyps mit benannten Feldern sehen.

Produkttypen heissen so, weil sich die Anzahl möglicher Werte aus dem Produkt der möglichen Werte seiner Felder ergibt (von kartesisches Produkt).

Summentypen hingegen sind seltener ausserhalb von funktionalen Sprachen anzutreffen. Eine andere Bezeichnung ist ‘tagged union', also ein Typ einen Wert seiner verschiedenen Varianten annehmen kann. 'Tagged' bedeutet dass die Sprache 'sich merkt' zu welcher Typenvariante der aktuelle Wert gehört, und uns daran hindert den Wert falsch zu interpretieren. Im Gegensatz dazu stehen 'untagged unions', bei denen diese Information nicht unbedingt vorhanden ist. Ein Typ der entweder einen Zahl- oder einen String-Wert hat sieht in TypeScript, C++, respektive Elm so aus:

MyType = number | string

using MyType = std::variant<int, std::string>

type alias MyType = Int | String

Summentypen heissen so weil die Anzahl möglicher Werte eines Summentyps sich aus der Summe der möglichen Werte seiner Varianten ergibt.

Pattern-Matching haben wir in den vorherigen Beispielen schon oft angetroffen. Es macht das Arbeiten mit Summentypen sehr viel angehmer.

Algebraische Datentypen erleichtern oft das Formalisieren von Domänenwissen, indem sie es erlauben eine DSL (Domain Specific Language) zu formulieren. Beispielsweise kann man eine Zahlung folgendermassen formalisieren (adaptiert von fsharpforfunandprofit.com ).

-- A type alias helps gives a 'new name' for an existing type,
-- thus allowing the compiler to catch logic errors
type alias CardNumber = String
type alias Email = String

-- CardType is a Sum-Type, consisting of three singleton types
type CardType = Visa | Amex | Master

-- CardInfo is a Produt-Type, more specifically a record (its fields are named)
type alias CardInfo =
    { cardType : CardType
    , cardNumber : CardNumber
    }

type PaymentMethod = Cash | Card CardInfo | Paypal Email

type Currency = EUR | USD | CHFR

type alias Payment =
    { amount : number
    , currency : Currency
    , paymentMethod : PaymentMethod
    }

Diese Typenhierarchie ist auch für Domänenexperten leserlich, ohne einen Programmierbackground mitbringen zu müssen.

Maybe und Either

Mit Hilfe von Summentypen können wir zwei sehr hilfreiche Types definieren: Maybe und Either. Sie erlauben es, Funktionen zu schreiben die schiefgehen können und trotzdem ihren Caller einen return-value zurückgeben. Dies erlaubt es, Fehler ohne Exceptions zu kommunizieren. Dies kann den Control-Flow eines Programms vereinfachen.

Als Beispiel schreiben wir eine Funktion die zwei Zahlen dividiert. Ist der Dividend 0 ist das Resultat mathematisch nicht definiert. Üblicherweise wird in diesem Fall eine DivideByZeroException geworfen. Mit Maybe können wir die Funktion so schreiben: Du gibst mir zwei Zahlen, ich gebe dir vielleicht eine Zahl zurück.

type Maybe a = Nothing | Just a

divide : Int -> Int -> Maybe Int
divide x y =
    case y of
        0 -> Nothing
        _ -> Just (x // y)

Durch die Rückgabe eines Maybe zwingen wir unseren Caller, den Fall von divide-by-zero explizit zu handhaben.

Oft muss dies aber nicht unmittelbar geschehen. Wenn wir eine Abfolge von Operationen abhandeln wollen macht es den Control-Flow sehr umständlich, nach jeder Operation zu checken ob wir tatsächlich einen Wert zurück erhalten haben. Besser wäre es, die Abfolge der Operationen so zu verketten, dass uns dies erspart bleibt.

Tatsächlich, wir können Higher-Order Functions schreiben die uns das ermöglichen

map : (a -> b) -> Maybe a -> Maybe b
map f x =
  case x of
    Nothing -> Nothing
    Just v -> Just (f v)

andThen : (a -> Maybe b) -> Maybe a -> Maybe b
andThen f x =
  case x of
    Nothing -> Nothing
    Just v -> f v

-- Beispiel
"2.4"
  |> toFloat            -- Just 2.4
  |> map round          -- Just 2
  |> andThen (divide 6) -- Just 3

Pattern Matching erlaubt es uns, das erwartete Verhalten von map und andThen einfach zu deklarieren: Falls kein Input vorhanden ist (das zweite Argument ist Nothing), reichen wir es einfach weiter, ansonsten wenden wir die Funktion auf den 'ausgepackten' Input an.
Am Beispiel sehen wir wie eine Abfolge von Operationen konzise formulieren können (die Definition des Pipeline-Operators ist x |> f = f x ).

Wenn wir unserem Caller im Falle eines Errors mehr Informationen zurückgeben wollen als nur Nothing, dann können wir den Typ Either brauchen. Either verhält sich analog zu Maybe, aber anstatt von nur Nothing enthält es einen Wert eines Error-Typs.

Either e a = Left e | Right a

divideE : Int -> Int -> Either String Int
divideE x y =
  case y of
    0 -> Left "Cannot divide by zero"
    _ -> Right (x // y)

Per konvention wird der Left-Konstruktor für den Error-Pfad verwendet. Wir sehen dass die Definition der Divisions-Funktion analog zur Maybe-Version funktioniert. Dasselbe gilt für map and andThen, sowie deren Anwendung.

Maybe und Either, zusammen mit map und andThen, erlaubt es uns Programme zu schreiben die Error-Handling ohne Verwendung von Exceptions betreiben.

Funktionale Einflüsse

Viele moderne Sprachen haben Ideen und Patterns aus funktionalen Sprachen übernommen. 

Lambdas

Anonyme Funktionen (Lambdas) sind heutzutage üblich und aus vielen Mainstream-Sprachen nicht mehr wegzudenken. Ihr Name kommt aber aus dem Lambda-Kalkü, der mathematischen Foundation der funktionalen Programmierung.

map und fold

Higher-Order Functions, im spezifischen map und fold, haben auch in vielen Sprachen Einzug gehalten. Obwohl sie nicht immer unter dem gleichen Namen auftauchen ist das Pattern doch oft anzutreffen. Vor allem in Kombination mit Lambdas können Operationen auf Sequenzen prägnant formuliert werden.

Algebraische Datentypen

Wie schon erwähnt sind Produkttypen sehr weit verbreitet. Explizit erwähnenswert sind records aus C#, da sie immutable sind eine spezielle Update-Syntax haben, was sie sehr ähnlich zu records in funktionalen Sprachen wie Elm macht.

Generelle Summentypen sind seltener. Typescript zum Beispiel hat zwar Union-Types mit einer sehr angenehmen Syntax, jedoch sind Typescript-Unions 'untagged', d.h. der Typ 'merkt sich nicht mit welchem Wert er konstruiert wurde'. Es ist aber möglich diesen 'Tag' selbst einzufügen. Zum Beispiel ist das Analogon von Either a b in Typescript type Either<err, ok> = { tag: "left", error: err} | { type: "right", ok: ok}.

Für C# gibt es ein Proposal um Summentypen in die Sprache aufzunehmen.

Null safety

Typen wie Maybe sind ein elegantes Tool zur Verhinderung von NullPointer-Exceptions. Viele Sprachen bauen ähnliche Typen ein oder werden von Anfang an damit designed. Beispiele sind Nullable Value Tyes (C#), Strict Null Checking (Typescript), optional (C++) oder Option (Rust).

Fazit

Während des sehr intensiven zweitägigen Workshops haben wir weitere spannende Themen wie zum Beispiel Tail-Recursion, das Bauen einer Webapp in Elm, Parsen und vieles mehr behandelt. Um den Umfang dieses Posts nicht zu sprengen, wollen wir es bei den bis jetzt besprochenen Sachen belassen.

Wer sich weiter mit funktionaler Programmierung beschäftigen möchte findet in den exzellenten Elm-Docs einen guten Startpunkt. Auch der schon erwähnte Blog F# for fun and profit bietet interessante Gedankenanstösse. Und im Allgemeinen sind, wie schon erwähnt, viele moderne Patterns in der Software-Entwicklung funktional inspiriert, es wird also immer schwieriger sich nicht mit funktionaler Programmierung auseinanderzusetzen.

Auf jeden Fall hat sich der Horizont aller Workshop-Teilnehmer merklich erweitert, und wir freuen uns das neu gelernte in unserem Arbeitsalltag umzusetzen.

Titelbild: freepik