Strukturierung: Der Lambda-Kalkül

Der Lambda-Kalkül

Der Lambda-Kalkül stellt ein formales System dar, das die Grundlagen der funktionalen Programmierung bildet. Das Kalkül wurde in den 1930er-Jahren vom Mathematiker Alonzo Church entworfen und in den nachfolgenden Jahren von verschiedenen Personen kontinuierlich weiterentwickelt. Dabei konnte nachgewiesen werden, dass durch das Kalkül alle berechenbaren Funktionen ausgedrückt werden können und es damit genau so mächtig wie eine Turingmaschine ist.

Der Lambda-Kalkül besteht aus nur drei Grundbausteinen:

1. Variablen:
   • Eine Variable dient im Lambda-Kalkül als ein ersetzbarer Platzhalter für einen Ausdruck.
   • Beispiele: $x$, $y$, $z$
     
     
2. Abstraktionen (Funktionen):
   • Eine Abstraktion hat immer die Form: $(\lambda v.\mathcal{L})$
     Dabei steht $v$ für eine beliebige Variable und $\mathcal{L}$ für einen beliebigen weiteren Lambda-Kalkül-Ausdruck.
   • Beispiele: $\ (\lambda y.y+1 )$,$\ \ \ $$(\lambda x.\lambda y. x +y)$
     
     
3. Applikationen (Funktionsanwendungen):
   • Eine Applikation hat immer die Form: $(\mathcal{L}_1\ \mathcal{L}_2)$
     Dabei stehen $\mathcal{L}_1$ und $\mathcal{L}_2$ für zwei beliebige Lambda-Kalkül-Ausdrücke. Der Ausdruck $\mathcal{L}_1$ wird dabei auf den Ausdruck $\mathcal{L}_2$ angewandt.
   • Beispiele: $\ ((\lambda y.y+1 )\ 6)$, $\ \ \ $ $((\lambda x.x )\ (\lambda z.z - 2 ))$

Der Lambda-Kalkül und Racket

Ein für die Informatik einflussreiche Verwendung des Kalküls war die Entwicklung der funktionalen Programmiersprache Lisp. Der Informatiker John McCarthy entwickelte diese in den späten 1950er-Jahren und nahm sich dabei das Lambda-Kalkül als Grundlage. Aus der Programmiersprache Lisp entstanden wiederum unzählige weitere funktionale Programmiersprachen - unter anderem die Programmiersprache Racket. In dieser sind auch heute noch die Nähe und die Bedeutung des Lambda-Kalküls zur Programmierung ersichtlich. Dies zeigt sich besonders im direkten Vergleich des Aufbaus von Funktionen und deren Anwendung:

Aufbau einer beispielhaften Racket-Funktion im Vergleich zu einer äquivalenten Abstraktion des Lambda-Kalküls:

Aufbau einer beispielhaften Racket-Funktionsanwendung im Vergleich zu einer äquivalenten Applikation des Lambda-Kalküls:

Gängige Schreibweisen

Um die Lesbarkeit der Lambda-Kalkül-Ausdrücke zu erhöhen, gibt es im Lambda-Kalkül einige Schreibkonventionen. Zwei der wichtigsten sind die folgenden:

1. Die äußersten Klammern dürfen weggelassen werden.
   • Beispiel: $\ $ $\lambda y.y+1$ $\ $ entspricht $\ $ $(\lambda y.y+1)$
   • Beispiel: $\ $ $(\lambda y.y+1)\ 17$ $\ $ entspricht $\ $ $((\lambda y.y+1)\ 17)$
     
     
2. Zwei aufeinanderfolgende Abstraktionen dürfen zu einer Abstraktion mit mehreren Parametern zusammengefasst werden.
   • Beispiel: $\ $ $\lambda xy.x+y$ $\ $ entspricht $\ $ $\lambda x.\lambda y.x+y$

Die Beta-Reduktion

Ausdrücke werden im Lambda-Kalkül schrittweise durch Anwendung der Beta-Reduktion ausgewertet. Die Beta-Reduktion lässt sich allgemein wie folgt zusammenfassen:

Wenn wir eine Funktion $\lambda v.\mathcal{L}$ mit dem Parameter $v$ und einem Lambda-Ausdruck $\mathcal{L}$ als Funktionskörper auf einen Ausdruck $\mathcal{A}$ anwenden: $(\lambda v.\mathcal{L})\ \mathcal{A}$, dann ersetzen wir jedes Vorkommen von $v$ in $\mathcal{L}$ durch den Ausdruck $\mathcal{A}$.

Durch $\rightarrow_{\beta}$ geben wir bei der schrittweisen Auswertung an, dass wir wie beschrieben eine Beta-Reduktion durchgeführt haben:

• Beispiel: $\ $ $(\lambda x.x)\ 4 \ \ \rightarrow_{\beta}\ \ 4$
• Beispiel: $\ $ $(\lambda x.x)\ (\lambda z.z*z) \ \ \rightarrow_{\beta}\ \ (\lambda z.z*z)$
• Beispiel: $\ $ $((\lambda ab.a+b)\ 17) \ 3 \ \ \rightarrow_{\beta}\ \ (\lambda b.17+b) \ 3 \ \ \rightarrow_{\beta}\ \ 17+3$
• Beispiel: $\ $ $((\lambda xy.(y\ x))\ 6)\ (\lambda a.a*a) \ \ \rightarrow_{\beta}\ \ (\lambda y.(y\ 6))\ (\lambda a.a*a) \ \ \rightarrow_{\beta}\ \ (\lambda a.a*a)\ 6 \ \ \rightarrow_{\beta}\ \ 6*6$

Aufgabe 1: Arithmetik im Lambda-Kalkül

In unseren bisherigen Lambda-Kalkül-Ausdrücken haben wir sowohl Zahlen als auch gängige mathematische Operatoren genutzt. So zum Beispiel den Operator $+$ und die Zahlen $1$ und $2$ im Ausdruck: $$(\lambda x.x+1)\ 2$$ Genau genommen gibt es im Lambda-Kalkül allerdings weder Zahlen noch mathematische Operatoren, wie wir sie kennen. Das Kalkül besteht tatsächlich nur aus exakt den drei oben beschriebenen Grundbausteinen: Variablen, Abstraktionen und Applikationen. Komplexere Konzepte wie Zahlen oder Operationen müssen daher selbst durch die drei Grundbausteine dargestellt und codiert werden können.

Church-Numerale:

Eine Möglichkeit, die natürlichen Zahlen mit dem Lambda-Kalkül darzustellen, bilden die Church-Numerale. Um diese Darstellung zu verstehen, schauen wir uns zuerst eine Möglichkeit an, die natürlichen Zahlen rekursiv zu definieren:

• Jede natürliche Zahl entsteht aus $0$ durch endlich oft Anwenden einer Nachfolgerfunktion.
• Eine Nachfolgerfunktion $S$ ordnet jeder natürlichen Zahl ihre unmittelbar folgende natürliche Zahl zu.

Die natürlichen Zahlen $0$ bis $3$ lassen sich entsprechend wie folgt darstellen:

• $ 0 = 0$
• $1 = S(0)$
• $2 = S(S(0))$
• $3 = S(S(S(0)))$
• usw.

Die Church-Numerale nehmen diese Idee auf und definieren die natürlichen Zahlen als Abstraktionen, die die obige Definition analog abbilden. Eine Zahl $n$ wird im Lambda-Kalkül durch eine Abstraktion codiert, die eine Funktion $f$ erhält und diese $n$-mal auf eine Variable $x$ anwendet.

Die Zahl $0$ entspricht damit analog zur obigen Definition der $0$-fachen Anwendung der Funktion $f$ auf $x$.
Die Zahl $1$ entspricht analog der $1$-fachen Anwendung der Funktion $f$ auf $x$.

Die natürlichen Zahlen $0$ bis $3$ lassen sich entsprechend wie folgt als Church-Numerale darstellen:

• $ 0 = \lambda fx. x$
• $1 = \lambda fx.(f\ x)$
• $2 = \lambda fx. (f (f\ x))$
• $3 = \lambda fx. (f (f (f\ x)))$
• usw.

(a) Welche Zahlen werden durch die folgenden Church-Numerale dargestellt?

1. $\ \lambda fx.x$
2. $\ \lambda fx. (f (f (f (f (f\ x)))))$
3. $\ \lambda fx. (f (f (f (f (f (f (f\ x)))))))$

(b) Stelle die folgenden Zahlen als Church-Numerale dar

• $\ 2$
• $\ 4$
• $\ 8$

Die Addition:

Mithilfe der Church-Numerale lässt sich ebenfalls rechnen. Hierfür benötigen wir Abstraktionen, die die mathematischen Operatoren codieren. Diese Abstraktionen können wir dann auf die Church-Numerale anwenden. Wir betrachten dafür exemplarisch die Codierung der Addition: $$\lambda m n f x.((m\ f)\ ((n\ f)\ x))$$ Wendet man diese Abstraktion nun auf die Zahlen $1$ und $2$ an, so erhält man die Applikation: $$((\lambda m n f x.((m\ f)\ ((n\ f)\ x)))\ 1\ )\ 2$$

(Die nachfolgenden Beta-Reduktionsschritte sind für eine bessere Übersicht farblich markiert. Dabei ist die anzuwendende Abstraktion orange markiert und der Ausdruck, auf den die Abstraktion angewandt wird jeweils blau.)

Für unsere Rechnung ergibt sich die folgende Auswertung: $$(({\color{orange}\lambda m} n f x.((m\ f)\ ((n\ f)\ x)))\ {\color{blue}1}\ )\ 2$$ $$\rightarrow_{\beta}\ \ ({\color{orange}\lambda n} f x.((1\ f)\ ((n\ f)\ x)))\ {\color{blue}2}$$ $$\rightarrow_{\beta}\ \ \lambda f x.((1\ f)\ ((2\ f)\ x))$$ Ersetzt man nun die Zahl ${\color{green}2}$ durch das entsprechende Church-Numeral, so erhält man: $$\lambda f x.((1\ f)\ (({\color{green}(\lambda fx. (f (f\ x)))}\ f)\ x))$$ Reduziert man dies weiter, ergibt sich: $$\lambda f x.((1\ f)\ ((({\color{orange}\lambda f}x. (f (f\ x)))\ {\color{blue}f})\ x))$$ $$\rightarrow_{\beta}\ \ \lambda f x.((1\ f)\ (({\color{orange}\lambda x}. (f (f\ x)))\ {\color{blue}x}))$$ $$\rightarrow_{\beta}\ \ \lambda f x.((1\ f)\ (f (f\ x)))$$ Ersetzt man nun die Zahl ${\color{green}1}$ durch das entsprechende Church-Numeral, so erhält man: $$\lambda f x.(({\color{green}(\lambda fx.(f\ x))}\ f)\ (f (f\ x)))$$ Reduziert man dies weiter, ergibt sich: $$\lambda f x.((({\color{orange}\lambda f}x.(f\ x))\ {\color{blue}f})\ (f (f\ x)))$$ $$\rightarrow_{\beta}\ \ \lambda f x.(({\color{orange}\lambda x}.(f\ x))\ {\color{blue}(f (f\ x))})$$ $$\rightarrow_{\beta}\ \ \lambda f x.(f(f(f\ x)))$$ Das Ergebnis entspricht damit genau unserer Definition des Church-Numerals für die Zahl $3$.

(c) Führe analog zum obigen Beispiel die folgenden beiden Rechnungen aus:

• Rechnung 1: $\ 0 + 2$
• Rechnung 2: $\ 2 + 3$

Arithmetik-Schreibweise im Lambda-Kalkül

Da wir wissen, dass wir die notwendige Arithmetik im Lambda-Kalkül abbilden können und Ausdrücke wie... $$ (( \lambda y z. (((\lambda m n f x.((m\ f)\ ((n\ f)\ x)))\ y)\ z)) \ (\lambda f.\lambda x. f (f x))) \ (\lambda f.\lambda x. f (f (f x))) $$ ... doch etwas schwerfällig zu lesen sind, nutzen wir die Schreibweise mit gängigen Zahlen und Operatoren. Wenn nötig, ersetzen wir diese durch die entsprechenden Lambda-Kalkül-Ausdrücke. So entspricht der obige Ausdruck beispielsweise: $$ ((\lambda yz.y+z)\ 2)\ 3$$