Während sich die meisten Besucher der Uphill Conf 2019 bereits auf das Apéro einstimmten, betrat Anjana Vakil die Gurtenbühne. Und das ausgerechnet mit dem „definitv nutzlosesten Talk“ der Konferenz. Ausgehend vom Lamdba-Kalkül zeigte sie, wie man nur mit Funktionen Zahlen, Kontroll- und Datenstrukturen entwickeln kann. Das sollte man eigentlich nicht tun, es macht aber ziemlich viel Spass. Und ich denke, dass es Sinn macht, sich auf die Grundlagen der funktionalen Programmierung zurück zu besinnen…
Das Lamdba-Kalkül ist ein mathematischer Formalismus, welcher einzig auf Abstraktionen (Funktionen) und deren Applikation beruht [1]. Er wurde in den 1930er Jahren von Alonzo Church entwickelt. Interessanterweise war Church der Doktorvator von Alan Turing und sie haben gemeinsam die Church-Turing-These entwickelt, welche ungefähr folgendes besagt:
Jedes berechenbare Problem kann sowohl mit einer Turing Maschine als auch mit dem Lambda-Kalkül gelöst werden.
Dabei besteht das Lambda-Kalkül nur aus folgenden drei Bausteinen:
| Syntax | Name | Beschreibung |
| x | Variable | Ein Bezeichner für einen Parameter oder einen mathematischen Wert. |
| (ƛx.M) | Abstraktion | Eine Funktionsdefinition. Die Variable x wird gebunden. |
| (M N) | Applikation | Applikation eines Argumentes auf eine Funktion. |
Möchte man eine Funktion zum inkrementieren eines Wertes x definieren, sieht das wie folgt aus:
(ƛx.x+1)
Eine Funktionsdefinition beginnt mit dem griechischen Buchstaben
ƛ gefolgt von genau einem Argument, hier x (dies kann aber ein beliebiger Bezeichner sein). Nach dem Argument trennt ein Punkt . den Funktionsrumpf ab, in diesem Fall x+1.Wenn man auf diese Funktion einen Wert anwenden will (Applikation), schreibt man das Argument mit oder ohne Klammer hinter die Funktion, welche selbst wieder in Klammer geschrieben wird – als anonyme Funktion (1). Anschliessend wird
x durch den Wert des Arguments ersetzt (2). Wenn dies für alle Argumente durchgespielt wurde, kann der Funktionsrumpf evaluiert werden (3) und wir erhalten das Resultat (4).(ƛx.x+1) (ƛx.x+1) 5 (1) (ƛ5.5+1) (2) (ƛ5.6) (3) 6 (4)
Für uns Entwickler ist das alltägliches Brot – darum kann man sich Fragen, was das eigentlich alles bezwecken soll.
Darauf gibt es verschiedene Antworten:
1. Jedes mögliche Programm kann mittels Lambda-Kalkül abgebildet werden. Das kann sehr ineffizient sein, bedeutet aber, dass das Lambda-Kalkül eigentlich eine komplette Programmiersprache ist.
2. Das Lambda-Kalkül macht das Wesen von funktionalen Programmiersprachen aus. Eigenschaften funktionaler Programmiersprachen wie „immutability“, „higher order functions“, „partial application“ und „pure“ etc. ergeben sich konsequenterweise aus dem Lambda-Kalkül.
3. Funktionale Ansätze sind mittlerweile in allen wichtigen Programmiersprachen erkennbar – das war vor einigen Jahren noch nicht der Fall.
ƛ == =>
In Javascript steht uns das Symbol
ƛ nicht zur Verfügung, stattdessen können wir mit ES6 auf Arrow Functions zurück greifen. Folgende Tabelle zeigt einige Beispiele von Funktionsdefinitionen in Lambda-Kalkül, ES6 und ES5:| Name | Lambda | ES6 | ES5 |
|
Identity |
ƛx.x |
x => x |
function(x) {return x}
|
|
Increment |
ƛx.x+1 |
x => x + 1 |
function(x) {return x + 1}
|
|
Add |
ƛx.ƛy.x+y |
x => y => x + y |
function(x) {
return function(y) {
return x + y
}
}
|
Bemerkenswert ist, dass hier nicht Funktionen mit zwei Argumenten definiert werden, sondern immer nur Funktionen mit einem einzigen Argument. Den Prozess, aus einer Funktion mit mehreren Argumenten mehrere Funktionen mit jeweils einem Argument zu machen, nennt man Currying – dazu aber mehr an anderer Stelle.
Ausgehend von diesen Bausteinen hat uns Anjana Vakil in die Welt der Church numerals und Church encodings entführt. Exemplarisch dafür hier nur die Herleitung von Booleans aus reinen Funktionen.
Functional Booleans
Im Lambda-Kalkül gibt es kein „If Else“, kein „True“ oder „False“ – es gibt nur Funktionen – sonst nichts. Wie können wir also diese Dinge nur mit Hilfe von Funktionen abbilden? Beginnen wir zunächst mit
if-else. Ausgehend vom „Ternary Operator“ können wir eine Signatur einer Funktion ifThenElse einfach ableiten, wobei jedes Element, also auch ifThenElse wird:<bool> ? <then do this> : <else do this>
Wird zu:
const ifThenElse => bool => thendothis => elsedothat => // ????
Dabei wissen wir noch nicht, wie die Implementation aussehen soll. Das Argument
bool kann nur eine Funktion oder ein Wert sein. Da wir aber keine Booleans zur Verfügung haben, müssen wir uns dies zuerst verdienen und True und False als Funktionen (troo und faals, da true und false reservierte Wörter sind) definieren. In obiger Definition von ifThenElse können wir boolals Funktion betrachten, welche entscheidet, ob wir das erste Argument (thn) oder das zweite (els) anwenden sollen. Dementsprechend können wir eine „boolsche Funktion“ als Auswahl aus zwei Argumenten definieren, wobei eine Funktion troo das erste Argument zurück geben soll und faals das zweite:const troo = thn => els => thn; // return the first argument, drop the second const faals = thn => els => els; // return the second argument, drop the first
Unsere boolschen Funktionen machen genau das, was wir wollen. Daraus ergibt sich folgende Implementation von
ifThenElse: Wähle aus zwischen dem ersten oder dem zweiten Argument. Und weil ifThenElse eine derartige Funktion und zwei weitere Werte erhält, können wir einfach diese Funktion auf diese zwei Werte anwenden:const ifThenElse = bool => thn => els => bool(thn)(els); // bool is a function! not a value!
Damit haben wir schon das Terrain von „higher order functions“ betreten – dazu mehr in einem meiner nächsten Beiträge.
Ein komplettes kleines Programm inklusive aller Definitionen ist hier zu finden.
Wie man nun weiter zu den logischen Operationen
not,and und or kommt, kann man mit Hilfe der Slides bzw. der Aufzeichnung des Talks von Anjana Vakil nachvollziehen.Fazit
Obwohl dieser Talk ein sehr abstraktes Thema behandelt hat und ausser der Tatsache, dass Anjana die Javascripts Arrow Functions verwendet, eigentlich nichts mit „Frontend“ zu tun hatte, war es für mich der spannendste Talk der diesjährigen Konferenz. Ich werde mich sicherlich weiter mit funktionaler Programmierung auseinandersetzen und vielleicht auch ab und zu mal mit den theoretischen Grundlagen.
Kommentare sind geschlossen.