Der Lambda-Kalkül

Warum eigentlich lambda?

Eines der wichtigsten Schlüsselworte in Racket ist lambda. Erst das Erstellen eines lambda-Ausdrucks ermöglicht es uns, neue Funktionen zu implementieren und diesen auch Übergabedaten zur Verarbeitung zu übergeben. Doch woher stammt eigentlich die Bezeichnung lambda und was hat diese mit funktionaler Programmierung zu tun?

Um diese Fragen zu beantworten, werfen wir einen Blick in die Mathematik und schauen uns die formale Grundlage funktionaler Programmierung an: den Lambda-Kalkül. (Häufig auch als $\lambda$-Kalkül geschrieben.)

Kurz gefasst stellt der Lambda-Kalkül ein formales System dar, mit dem man beschreiben kann, wie Funktionen funktionieren. Dabei besteht er aus nur wenigen Grundbausteinen, die in Kombination jedoch so mächtig sind, dass sich mit ihnen alle berechenbaren Funktionen ausdrücken lassen. Der Lambda-Kalkül ist damit genau so mächtig wie eine Turingmaschine.

Aufgabe 1: Die Grundbausteine des Lambda-Kalküls

Betrachten wir einmal einen lambda-Ausdruck in Racket, der eine Zahl um eins erhöht:

(lambda (x) (+ x 1))

Möchten wir die Funktion nun auf Daten anwenden, zum Beispiel auf die Zahl 2, so schreiben wir:

((lambda (x) (+ x 1)) 2)

Möchten wir dieselbe Funktion im Lambda-Kalkül darstellen, so nutzen wir eine ähnliche Schreibweise.

Die Funktion schreiben wir als: $$( \lambda x.x+1 )$$ Die Anwendung der Funktion auf die Zahl 2 als: $$(( \lambda x.x+1 )\ 2)$$

(a) Vergleiche die Schreibweise von Racket und vom Lambda-Kalkül, welche Parallelen fallen dir auf?
(Hinweis: $\lambda$ ist der Kleinbuchstabe des griechischen Buchstaben Lambda).

Die Grundbausteine:

Mit diesem Beispiel haben wir tatsächlich schon alle Grundbausteine des Lambda-Kalküls abgedeckt. Zur Erzeugung von korrekten Lambda-Kalkül-Ausdrücken gibt es genau drei Bausteine:

1. Variablen:
   • Eine Variable dient im Lambda-Kalkül als ein ersetzbarer Platzhalter für einen Ausdruck. So wie die Definitionen und Parameter in Racket.
   • 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 x.x )$$\ \ $[entspricht: (lambda (x) x)]
     - $(\lambda y.y+1 )$$\ \ $[entspricht: (lambda (y) (+ y 1))]
     - $(\lambda x.\lambda y. x +y)$ $\ \ $[entspricht: (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 x.x )\ 2)$ $\ \ $[entspricht: ((lambda (x) x) 2)]
     - $((\lambda y.y+1 )\ 6)$ $\ \ $[entspricht: ((lambda (y) (+ y 1)) 6)]
     - $((\lambda x.x )\ (\lambda z.z - 2 ))$ $\ \ $[entspricht: ((lambda (x) x) (lambda (z) (- z 2)))]
     
     

(b) Formuliere die nachfolgenden drei Racket-Ausdrücke in Lambda-Kalkül-Ausdrücke um.

;Ausdruck 1  
(lambda (x) (* x x))

;Ausdruck 2
((lambda (y) (+ y 1)) 17)

;Ausdruck 3  
(lambda (z)
 (lambda (y) (- y z)))

(c) Formuliere die nachfolgenden drei Lambda-Kalkül-Ausdrücke in Racket-Ausdrücke um.

• Ausdruck 1: $\ (\lambda x.x*3 )$
  
  
• Ausdruck 2: $\ ((\lambda a.a+a )\ 10)$
  
  
• Ausdruck 3: $\ (((\lambda f.f)\ (\lambda x.x*3 ))\ 3)$

Gängige Schreibweisen

Um die Lesbarkeit der Lambda-Kalkül-Ausdrücke zu erhöhen, wurde sich auf einige Schreibkonventionen geeinigt. Zwei der wichtigsten sind die folgenden:

1. Die äußersten Klammern dürfen weggelassen werden.
   • Der Ausdruck $(\lambda y.y+1)$ kann beispielsweise auch als $\lambda y.y+1$ geschrieben werden.
   • Der Ausdruck $((\lambda y.y+1)\ 17)$ auch als $(\lambda y.y+1)\ 17$.
     
     
2. Zwei aufeinanderfolgende Abstraktionen dürfen zu einer Abstraktion mit mehreren Parametern zusammengefasst werden.
   • Der Ausdruck $(\lambda x.\lambda y.x+y)$ kann beispielsweise auch als $(\lambda xy.x+y)$ bzw. als $\lambda xy.x+y$ geschrieben werden.

Aufgabe 2: Auswertung von Ausdrücken: Die Beta-Reduktion

Wie in Racket lassen sich auf die Ausdrücke im Lambda-Kalkül schrittweise auswerten:

Schritt	Auswertung in Racket	Auswertung im Lambda-Kalkül
0	(((lambda (x) (lambda (y) (+ x y))) 3) 4)	$((\lambda xy.x+y)\ 3)\ 4$
1	((lambda (y) (+ 3 y)) 4)	$(\lambda y.3+y)\ 4$
2	(+ 3 4)	$3+4$
3	7	7

(a) Vergleiche die beiden Auswertungen von Racket und vom Lambda-Kalkül, welche Parallelen fallen dir auf?

Bei der Auswertung von Applikationen (bzw. Funktionsanwendungen) kommt eine grundlegende Operation aller Funktionsanwendungen zum Einsatz: Das Ersetzen von Parametern durch den Ausdruck, auf den die Abstraktion (bzw. Funktion) angewandt wird. In der oberen Tabelle also die Schritte 0 zu 1 sowie 1 zu 2. Diese Operation nennt sich im Lambda-Kalkül Beta-Reduktion. (Häufig auch als $\beta$-Reduktion geschrieben.)

Ein Beta-Reduktionsschritt wird mit $\rightarrow_{\beta}$ angegeben. So schreibt man beispielsweise: $$(\lambda x.x)\ 2\ \ \rightarrow_{\beta} \ \ 2$$ Sprachlich lässt sich die obige Reduktion wie folgt zusammenfassen: Wir wenden die Funktion $(\lambda x.x)$ auf den Ausdruck $2$ an. Hierfür ersetzen wir alle Vorkommen von $x$ im Funktionskörper der Funktion durch den Ausdruck $2$.

Weitere Beispiele sind: $$(\lambda x.x+1)\ 2\ \ \rightarrow_{\beta} \ \ 2+1$$ $$(\lambda x.x)\ (\lambda z.z+3)\ \ \rightarrow_{\beta} \ \ (\lambda z.z+3)$$ $$(\lambda yz.z*y)\ 17\ \ \rightarrow_{\beta} \ \ (\lambda z.z*17)$$

Sowie unser in der Tabelle ausgewertete Ausdruck: $$ ((\lambda xy.x+y)\ 3)\ 4 \ \ \rightarrow_{\beta}\ \ (\lambda y.3+y)\ 4 \ \ \rightarrow_{\beta}\ \ 3+4 = 7$$

(b) Reduziere die folgenden sechs Lambda-Kalkül-Ausdrücke durch die Beta-Reduktion.

• Ausdruck 1: $\ (\lambda y.y+1)\ 17$
  
  
• Ausdruck 2: $\ (\lambda x. x * 2)\ 3$
  
  
• Ausdruck 3: $\ ((\lambda xy. y - x)\ 6)\ 4$
  
  
• Ausdruck 4: $\ ((\lambda x.x )\ (\lambda z.z - 2 ))\ 2$
  
  
• Ausdruck 5: $\ (\lambda f. (f\ 3))\ (\lambda x. x + 1)$
  
  
• Ausdruck 6: $\ ((\lambda fa. (f\ 3) + a)\ (\lambda x. x + 1))\ ((\lambda z.z*3)\ 3)$