Herzlich willkommen. Nach der Uhr bin ich so rechtzeitig. Gut, ich bin schon eine Minute hier.

Wie schon mal angekündigt, machen wir heute eine Kurzsitzung, die um sieben Minuten vor fünf bereits

endet, weil heute Nachmittag Professorium ist. Das gibt es nicht so oft, insofern bilde ich mir

ein, das nicht verpassen zu dürfen. Unser Thema heute, der Lambda-Kalkül. Es kommt gleich

noch so ein bisschen Motivation, die Sie auch im Skript nachlesen können, über das, was der

Lambda-Kalkül so in funktionalen Programmiersprachen so tut. Da stand mal ein längerer Text drin,

den ich in der ersten Ausgabe der Veranstaltung abgelassen hatte und den habe ich dann selber

wieder rauseditiert, weil er wirklich nicht für schriftliche Dokumente geeignet ist. Also,

der Text lautet der. Der Lambda-Kalkül steht in einer Reihe mit den großen Erfindungen der

Menschheit neben der Relativitätstheorie und der Currywurst. Ich motiviere gleich noch und der

Satz, den ich damals außerdem brachte, weil es gibt Dinge, die sind von Interesse unabhängig

davon, ob sie es mal als Feature in Java 8 schaffen oder nicht. Und ja, wie gesagt,

ein solches Ding ist der Lambda-Kalkül. Ja, Lambda-Kalkül ist im Wesentlichen ein

funktionales Programmieren und zwar, so ein bisschen haben wir es ja schon gesehen, als wir

uns im ersten Abschnitt der Veranstaltung mit Termersetzung beschäftigt haben. Was hier den

Lambda-Kalkül dann zusätzlich auch zeichnet, ist, dass hier zusätzlich mit höheren Funktionen

programmiert wird, das heißt also mit Funktionen, die wiederum andere Funktionen als Argumente

verarbeiten. Hier ist eine ganz einfache solche Funktion. Zum Beispiel eine Funktion, die einfach

eine Funktion desmaßen verdoppelt, also zweimal nacheinander anwendet. Gut, was da rauskommt,

dann ist es wieder eine Funktion. Also twice f ist die Verdoppelung von f und gut, um zu sagen,

was das für eine Funktion ist, muss ich sagen, was kommt raus, wenn ich das auf irgendein Argument

x anwende. Gut, da kommt eben raus f von x. Das können Sie so wörtlich abtippen, das schluckt

Haskell. Das ist eine Zeile Haskell, dann haben Sie damit eine Funktion, die Sie verwenden können.

Oder weiteres bekanntes Beispiel, etwas weniger sinnlos als diese twice-Funktion, ist die

Map-Funktion. Die Map-Funktion, was tut die? Die Map-Funktion nimmt sich eine Funktion und lässt

die anschließend auf jeden Eintrag einer gegebenen Liste los. Das heißt, das erste Argument, was die

kriegt, ist eine Funktion, sagen wir von einem Typ a in einen Typ b. Und dann kommt was raus,

das ist wieder eine Funktion, die erwartet eine Eingabe vom Typ list a und produziert dann eine

Ausgabe vom Typ b. Für die, die Haskell jetzt nicht so kennen, das ist so geklammert. Das heißt,

also ich habe eine Funktion, die nimmt sich eine Funktion als Argument und gibt eine weitere

Funktion wieder zurück. Einmal zur Übung fühle ich vor, wie man die also rekursiv programmiert.

Ich muss einmal sagen, was ist Map f von, wenn ich das so schreiben, ich schreibe es vielleicht so,

der Lesbarkeit halber, weil wir keine Listkonstruktoren eingeführt haben. Also

Listenfunktion programmieren, ich rekursiv typischerweise, indem ich einen Fall angebe für

die leere Liste und einen Fall für eine zusammengesetzte Liste. Wie viele Leute hier im Saal können

ein Funktional programmieren, in irgendeiner funktionalen Sprache? Ach, das sind ja tatsächlich

fast alle. Gut, dann verstehen Sie das ja, das ist ja gut. So, hier kommt also natürlich raus die

leere Liste und interessanterweise ist das hier die leere Liste vom Typ A und das hier die leere

Liste vom Typ B. Der andere Fall ist, dass meine Liste zusammengesetzt ist aus einem Element vorne

dran gehängt an eine Restliste. So, wie sieht die rekursive Definition aus? Ja, genau, also das erste

Element der Ergebnisliste ist f von x und das wird vorne dran gehängt an eine Restliste, die ich

bekomme, indem ich mapf wiederum anwende, jetzt eben auf die Restliste. Okay, das heißt, gut,

wer Funktional programmieren kann, der ist es eben sogar gewohnt mit höheren Funktionen zu programmieren.

So, das oben war, wie das Beispiel der mapfunktion zeigt, gedacht in einer getypten Welt,

wie eben in Haskell. Wir werden uns auch einen getypten Kalkül noch ansehen, fangen aber an,

der Historie folgenden mit dem ungetypten Kalkül, also der ungetypte Kalkül war zuerst da und die

Typen kamen später und genauso ist es mit den Programmiersprachen gelaufen. Der ungetypte

Lambda Kalkül ist schlicht und einfach Lisp, wenn man will. Lisp ist auch, wie Sie feststellen

werden, ungetypt. Lisp hat zwar so eine Vorstellung, dass also die Dinge, die es hat, alle so Bäume

sind, ja, aber gut, ich kann letztlich jedes Datenobjekt irgendwie als Baum darstellen,