lambda.tex

\section{Lambda calculus}
Der Lambda calculus ist ein Datenverarbeitungskonzept erfunden von Alonzo Church, dem Professor von Alan Turing. Turing studierte unter Church einige Zeit an der Princeton Universität bevor er dann wieder zurück nach England ging. Im folgenden Abschnitt wird kurz auf Church eingegangen, danach wird Churches Werk, der Lambda calculus und dessen Gesetze, Notation und Beispiele behandelt. Hier wird ein Einblick in die Welt der funktionellen Programmiersprachen und ihrer Geschichte gegeben.
\subsection{Alonzo Church}
Alonzo Church wurde am 14 Juni 1903 in Washington DC geboren. \cite{lifechurch}
Nach 1920 ging er nach Princeton. In den 1930gern ging es in Princeton rund. Es waren viele Spezialisten der Logik dort, darunter auch John von Neumann und Kurt Gödel. Gegen 1936 kam auch Alan Turing als Gaststudent an die Universität. Dort kreuzten sich ihre Wege und so entstand die Church-Turing Thesis. Diese wird im nächsten Kapitel beschrieben.
\subsection{Gesetze des Lambda calculus}
Der Lambda calculus besteht aus 3 Grundgesetzen.
\begin{itemize}
\item Funktionen können definiert werden.
\item diese können/müssen Daten ein und ausgeben.
\item Funktionen können angewendet werden.
\end{itemize}
Ausführlicher: Es muss ein Weg vorhanden sein eine Funktion zu definieren, dafür gibt es eine mathematische Definition. Die Erzeugung einer Funktion ist aber nicht auf die mathematische Notation beschränkt, ganz im Gegenteil, die Notationen im modernen Lambda weichen, nicht zuletzt aus technischen Gründen, stark von der mathematischen Notation ab. Dabei müssen im originalen Lambda Ein- und Ausgaben definiert werden. Dies weicht im modernen Lambda ebenfalls von der originalen Definition ab. Hier können Ein- und Ausgaben definiert werden, müssen es aber nicht. Dies führt zu mehr Flexibilität, so können die Lambda Funktionen auch an Stellen eingesetzt werden, wo nicht direkt Daten verarbeitet werden, sondern zum Beispiel Signale. Des weiteren kennt man beim Ausführen der Funktion den Inhalt der Funktion nicht. Um nun damit Daten verarbeiten zu können, kann man nun Eingaben auf Funktionen anwenden.\cite{lambdacalculus}

\subsection{Mathematische Notation}
Für den ursprünglichen Lambda calculus definiert von Alonzo Church gibt es auch eine mathematische Notation die wie folgt durch das Zeichen Lambda eingeleitet wird.
\begin{equation}
\lambda x. x + 1
\end{equation}
Diese Funktion erhöht die Eingabe um eins. Dabei ist es wichtig anzumerken, dass wir nicht wissen was die Funktion wirklich tut. Wir können nur sagen was in die Funktion herein gegeben wird und was beim anwenden der Funktion heraus kommt. Wobei die Inputs mit dem $\lambda$ (lambda) Symbol gekennzeichnet sind und mit einem Punkt enden. Am Schluss folgt die Ausgabe. Die Funktion könnte beim ausführen $x + 2 - 1$ rechnen oder $x + 4 - 3$ das kann man in diesem Model nicht beschreiben, klar ist nur es kommt immer $x + 1$ heraus.
Die ursprüngliche Notation ist weit aus mathematischer als die in derzeitigen Programmiersprachen. Dennoch lassen sich damit beliebig Daten durch das sogenannte Kodieren, wie im folgenden Beispiel, verarbeiten. Gegeben sind zwei Funktionen.
\begin{equation}
TRUE = \lambda x. \lambda y. x
\end{equation}
In der originalen Notation wird der Punkt und das zweite Lambda bei den Inputs weggelassen. Wir bleiben aber bei der heutig genutzten Version der Übersichtlichkeit halber. \cite{churchcalculi}
\begin{equation}
TRUE = \lambda xy. x
\end{equation}
\begin{equation}
FALSE = \lambda x. \lambda y. y
\end{equation}
Diese zwei Funktionen sollen nun zu einem logischen Und-Gatter zusammen gefügt werden. Dabei entsteht folgende Funktion.
\begin{equation}
AND = \lambda x. \lambda y. x y x
\end{equation}
Nun wird auf die Und-Funktion als Beispiel die Funktionen TRUE und FALSE angewendet. Dazu werden einfach die variablen mit den als Eingabe verwendeten Funktionen ausgetauscht. In diesem konkreten Beispiel wird TRUE und TRUE auf die Funktion AND angewendet
\begin{equation}
AND\:\:TRUE\:\:TRUE = (\lambda x. \lambda y. x y x) TRUE\:\:TRUE 
\end{equation}
Hier wird detailliert aufgeschrieben wie man die Funktionen auflöst. Man nimmt immer die Funktion die am weitesten links steht und schreibt auf wie sie aufgebaut ist. Die nachfolgenden Methoden beziehungsweise Daten werden nun als Input verwendet, in diesem Fall natürlich die kodierten Funktionen. In diesem Fall ist die Funktion AND definiert als $x y x$
und gegeben sind die Inputs $x = TRUE$ und $y = TRUE$. Dies wird nun ebenfalls hingeschrieben und es wird weiter aufgelöst. 
\begin{equation}
TRUE\:\:TRUE\:\:TRUE = (\lambda x. \lambda y. x) TRUE\:\:TRUE = TRUE
\end{equation}
Nun wird auf die ganz links stehende Funktion TRUE die Inputs $x = TRUE$ und $y = TRUE$ angewendet. Da sich TRUE immer zu x auflöst ist das Ergebnis also AND TRUE TRUE = TRUE. Dies bestätigt die Annahme. Um ein Gegenbeispiel zu bringen wird im nächsten Beispiel FALSE und TRUE übergeben.
\begin{equation}
AND\:\:FALSE\:\:TRUE = FALSE\:\:TRUE\:\:FALSE = FALSE
\end{equation}
Und auch hier funktioniert die Und-Funktion wie gedacht. So kann man alle möglichen Arten von Datentransformation in Lambda Funktionen darstellen. 
\cite{lambdacalculus}

\subsection{Lambda in Programmiersprachen}
Schauen wir uns nun zur weiteren Erläuterung ein Beispiel aus Java an. Diese Beispiele sind weit aus moderner und weichen in Teilen von der originalen Definition ab, beziehungsweise fügen neue Regeln hinzu. Es gibt eine Funktionsdeklaration die der Implementation vorgibt, welche Ein und Ausgänge eine gewisse Lambda Funktion hat, sowie ihren Namen.
\begin{minted}{java}
@FunctionalInterface
public interface TestFunctionalInterface {
	public int test(double d);
}
\end{minted}
Die Funktion wird nun als Interface übergeben und von einer ausführenden Funktion genutzt. Was hier auffällt ist das die ausführende Funktion nicht weiß, was die Funktion eigentlich tut.
\begin{minted}{java}
public void runTest(TestFunctionalInterface interf) {
	int testres = interf.test(89.1);
	// Mache etwas mit dem resultat
}
\end{minted}
Normalerweise müsste man dieses Interface überschreiben und dort dann implementieren was die Funktion tun würde. Hier gibt es allerdings eine separate Schreibweise um eine Funktion zu definieren. Die wie folgt durch die Zeichenkombination $->$ eingeleitet wird. Rechts von dem sog. Lambda-Operator stehen die Inputs, rechts die Operationen bzw. Outputs. Im folgenden Beispiel wird die gerade erzeugte Funktion auf \emph{runTest} angewendet.
\begin{minted}{java}
public void main() {
	runTest(input -> (int)(input + 1));
}
\end{minted}
Und nicht nur Java hat diese Art Paradigma übernommen, auch C++ zum Beispiel, hat zusätzlich zu den bereits vorhandenen Funktionspointern, Lambda Funktionen eingeführt.
In C++ haben die Lambda Funktionen eine leicht veränderte Anwendungsstruktur.
\begin{minted}{c++}
playercontroller = [](Input* input) { 
topdown.positiony += input->y1; 
topdown.positionx -= input->x1;
setTopDownCamera(&topdown); 
};
\end{minted}
Hier wird eine Player-Controller-Funktion in meiner Engine definiert. Der Player-Controller bekommt die letzten Inputs des Players in die Funktion und verarbeitet diese dann weiter.