… & Kontext: Currying

Babel-Bulletin  –  0 Kommentare

"Konsole & Kontext" ist eine gemeinsame Serie von Golo Roden und Michael Wiedeking, in der sich die beiden regelmäßig mit Konzepten der (funktionalen) Programmierung beschäftigen. Während "Konsole & …" die praktische Anwendung dieser Konzepte in JavaScript und Node.js zeigt, erläutert "... & Kontext" deren jeweiligen eher theoretischen Hintergrund.

Eine Funktion ist eine Abbildungsvorschrift, bei der die Parameter einer Funktion auf ein (häufig nur einelementiges) Tupel von Werten abgebildet werden. Bei einer Addition etwa werden zwei Zahlen auf ihre Summe abgebildet.

add : (ℕ, ℕ) ⟶ ℕ
(x, y) ⟼ x + y

Mit dieser Funktion kann man nun nach Belieben die Summe zweier Zahlen berechnen, beispielsweise

add(3, 1)
add(3, 2)
add(3, 3)

Schaut man sich nun die "zufällig" gewählten Additionen an, haben diese eine Gemeinsamkeit, nämlich den ersten Parameter. Wüsste man, dass der erste Parameter immer 3 ist, hätte man die Funktion vielleicht auch gleich add3 nennen können, die wie folgt definiert ist

add3 : (ℕ) ⟶ ℕ
(y) ⟼ add(3, y)

Ein Herr Schönfinkel ist nun – lange bevor es Rechner gab – auf die Idee gekommen, dass man in diesem Fall dasselbe Ergebnis erzielen kann, wenn man die Funktion add nur teilweise anwendet:

add(3)

Eine solche "partielle Anwendung" einer Funktion liefert dann also eine neue Funktion, die sozusagen einen Parameter weniger hat, aber dafür eine Funktion mit einem Parameter liefert. Wenn man das nun konsequent anwendet, dann könnte man die Signatur der add-Funktion wie folgt verstehen:

add : (ℕ) ⟶ (ℕ ⟶ ℕ)

Um also die Summe von 3 und 2 auszurechnen, schreibt kann man dann also auch

add(3)(2)

schreiben. Allerdings mit dem unglaublichen Vorteil, dass man eben Parameter "weglassen" kann, um die partiell angewandte Funktion anderweitig einsetzen zu können. Also kann man obige add3-Funktion recht einfach definieren

add3 :⟵ add(3)

Sollen beispielsweise ganzzahlige Werte um 1 inkrementiert werden, muss man dazu nicht eine neue Funktion definieren, sondern kann ganz einfach die vorhandene add-Funktion partiell auswerten

inc :⟵ add(1)

inc(7) etwa liefert dann wunschgemäß 8. Dies funktioniert natürlich nicht nur mit Zahlen, sondern beispielsweise auch mit Zeichenketten. Gibt es eine zweistellige Funktion concat, die zwei Strings zusammenfügt, dann liefert

greet :⟵ concat("Hello, ")

eine Funktion, mit der sich die Welt und andere Zeichenketten angemessen grüßen lassen:

greet("world") = "Hello, world".

Diese "Umwandlung" einer beliebigen Funktion

f : (T1, T2, … , Tn-1, Tn) ⟶ T

in eine, die man partiell auswerten kann,

f : (T1) ⟶ (T2 ⟶ (… ⟶ (Tn-1 ⟶ (Tn ⟶ T))…))

nennt man nach Herrn Schönfinkel auch Schönfinkeln. Unabhängig von dem hat sich aber auch ein Herr Curry mit dem Thema der partiell angewandten Funktionen beschäftigt. Dem zu Ehren hat man der funktionalen Programmiersprache Haskell seinen Vornamen gegeben. Und nachdem sich in Haskell jede Funktion partiell auswerten lässt, nennt man in diesen Kreisen das Schönfinkeln auch Currying, was sich in der IT wohl eher durchgesetzt hat.

Während einige Programmiersprachen die "Curryfizierung" für jede Funktion erlauben, benötigen andere dazu Funktionen, die eine Funktion explizit "curryierbar" macht. So wandelt etwa die Funktion curry eine "normale" Funktion in eine um, die sich auch nur dann partiell auswerten lässt; derweil die Funktion uncurry eine solche Funktion wieder in eine normale umwandelt. Wieder andere Sprachen müssen eine Funktion, die partiell ausgewertet werden sollen, auf Wunsch explizit als solche definieren.

Um den unglaublichen Nutzen dieser Methode besser als mit dem banalen Inkrement demonstrieren zu können, muss man allerdings ein bisschen weiter ausholen. Angenommen, es gibt einen Datencontainer C[T], der Elemente vom Typ T enthält. Des Weiteren definiert man eine Funktion reduce, die alle Werte eines solchen Containers irgendwie zu einem zusammenfasst. Das könnte beispielsweise die Summe, das Produkt oder der Mittelwert aller Zahlen eines Zahlencontainers sein. Die reduce-Funktion hat dann eine Form wie

reduce(f : T ⟶ T, c : C[T]) ⟶ T

wobei der erste Parameter eine Funktion f ist, die der Reihe nach auf die Elemente der Collection c angewandt, die als zweiter Parameter übergeben wird. Allerdings ergibt sich hier noch ein kleines Anfangsproblem. Hat man es etwa mit einem Container mit den Zahlen 1, 2 und 3 zu tun, dann könnte man ja recht einfach die Summe s mit

s ⟵ ???
ss + 1
ss + 2
ss + 3

berechnen. Allerdings stellt sich die Frage, wie s initialisiert werden soll, um dann elementweise die Addition anwenden zu können. 0 wäre hier ein geeigneter Wert, der allerdings im Falle des Produkts völlig unbrauchbar ist. Der Anfangswert muss also im Zusammenhang mit der Funktion definiert werden.

Die reduce-Funktion braucht also zusätzlich den Initialwert für den kumulierten Wert, der aber auch als Wert für eine leere Collection geliefert wird, und hat die Form

reduce(z : T, f : T ⟶ T, c : C[T]) ⟶ T

Mit einer partiellen Auswertung kann man nun sehr einfach und elegant die Summe oder das Produkt definieren.

sum :⟵ reduce(0, add)
product :⟵ reduce(1, mul)

Dann ist sum({1, 2, 3, 4, 5}) = 15 und product({1, 2, 3, 4, 5}) = 120. So etwas funktioniert natürlich auch für Dinge, die keine Zahlen sind. So liefert etwa

cat :⟵ reduce("", concat)

eine Funktion, die sämtliche Zeichenketten einer Collection aneinander hängt.

Das Currying ist also ein weiteres mächtiges Mittel, das das funktionale Paradigma beschert. Nicht, dass man dies nicht auch anders bewerkstelligen könnten, aber wenn so etwas durch die Sprache selbst unterstützt wird, wird es halt doch eleganter und viel einfacher.