Die WHILE-Sprache

Hier lernst du eine Formalisierung von Pseudocode kennen: die WHILE-Sprache. Während Pseudocode dazu dient, allgemeine algorithmische Ideen zu präsentieren, ist die WHILE-Sprache ein formales Berechnungsmodell, welches bestimmte Operationen erlaubt. Zu einem gegebenen WHILE-Programm lässt sich dann auch eindeutig eine Funktion zuordnen, welche natürliche Zahlen auf natürliche Zahlen abbildet (also \(\mathbb{N} \rightarrow \mathbb{N}\)). Diese zugeordnete Funktion ist dann die durch das Programm berechnete Funktion. Den Programmcode nennt man dann auch die Syntax, die durch das Programm berechnete Funktion die Semantik des Programms.

Wir lernen die WHILE-Sprache in den folgenden Schritten kennen.

1. Syntax von WHILE-Programmen;
2. Formale Definition der Semantik von WHILE-Programmen;
3. Laufzeit von WHILE-Programmen;
4. Andere Berechnungsmodelle;
5. LOOP-Berechenbarkeit;
6. Bonus: Geschichte der Berechnungsmodelle.

Syntax

Anmerkung zum Video: Es wäre besser, das Ungleichheitszeichen \(\neq\) auch noch als Symbol aufzunehmen.

Wir halten fest: WHILE-Programme sind rekursiv definiert. Die folgenden beiden Zeichenketten sind atomare WHILE-Programme für beliebige natürliche Zahlen \(i\), \(j\) und \(c\):

Für die Subtraktion zweier natürlicher Zahlen \(a\) und \(b\) gilt dabei, dass \(a - b = 0\), falls \(b \geq a\).

Wenn \(P_1\) und \(P_2\) WHILE-Programme sind und \(v\) ein Variablensymbol, dann sind auch die folgenden beiden Zeichenketten WHILE-Programme:

Wichtig hierbei ist, dass die WHILE-Schleife stets nur auf Ungleichheit zur \(0\) prüft.

In dieser sehr simplen Programmiersprache können wir jetzt kompliziertere Funktionen bauen, zum Beispiel die Addition:

Zuweisungen von Konstanten, also \(x_i := c\), sind auch nicht direkt möglich. Stattdessen kann man zum Beispiel das folgende Programmschema nehmen:

Dieser Code beschreibt nicht direkt ein WHILE-Programm, da die Indizes der Variablen keine konkreten Werte haben. Er steht allerdings stellvertretend für das Programm, das man erhält, wenn man einen konkreten Wert für \(i\) angibt.

Ebenso können andere, auch komplizierte aritmetische Operationen eingeführt werden, inklusive Relationen wie \(\leq\) und \(\geq\) (wobei wir eine Ausgabe von \(0\) als false interpretieren und alle anderen Werte als true). Auch können wir andere Konstrukte erstellen, zum Beispiel IF-Verzweigungen. Wenn wir \(\textbf{IF } v \neq 0 \textbf{ THEN } P \textbf{ END}\) implementieren wollen, können wir zum Beispiel das folgende Schema bentzen:

Dabei bezeichnen \(z\) und \(v\) wieder Platzhalter, die in einem konkreten Programm mit richtigen Variablen belegt werden müssten.

Wir erlauben uns, IF-Verzweigungen und andere komplexe Operationen im WHILE-Code zu benutzen, und verstehen das als verkürzte Darstellung des (etwas länglichen) tatsächlichen WHILE-Codes (mit entsprechend vorsichtiger Wahl der zusätzlich benötigten Variablen). Man spricht dann auch von Syntactic Sugar.

Wir halten fest: Gegeben ein WHILE-Programm \(P\), bezeichnen wir mit \(\textbf{WHILE}_P^k\) die partielle Funktion \(\mathbb{N}^k \rightarrow \mathbb{N}\), welche durch \(P\) berechnet wird. Dabei legen wir fest, dass die Eingabe am Anfang der Ausführung in \(x_1, x_2, \ldots, x_k\) steht (bei \(k\) Eingaben) und dass am Ende der Ausführung die Ausgabe in \(x_0\) steht. Wir nennen die Zeichenkette \(P\) die Syntax und die Funktion \(\textbf{WHILE}_P^k\) die Semantik. Insbesondere ist \(\textbf{WHILE}^k_P(a_1,\ldots,a_k)\) die Ausgabe von \(P\) bei Eingaben \(a_1,\ldots,a_k \in \mathbb{N}\) (undefiniert, falls \(P\) auf \(a_1,\ldots,a_k\) nicht terminiert).

Anmerkung zum Video: Bei den Laufzeitanalysen wurde stets das Überprüfen der Schleifenbedingung für den Fall, dass die Schleife nicht weiter ausgeführt wird, vergessen. So hat die Addition beispielsweise eigentlich eine Laufzeit von \(2 + 3a_2\) und nicht nur von \(1 + 3a_2\), da beim Terminieren der Schleife noch ein letztes Mal die Schleifenvariable geprüft werden muss.

Wir halten fest: Gegeben ein WHILE-Programm \(P\), bezeichnen wir mit \(\textbf{TIME}_P^k\) die partielle Funktion \(\mathbb{N}^k \rightarrow \mathbb{N}\), welche die Ausführungszeit von \(P\) auf der Eingabe beschreibt. Dabei kostet jede Zuweisung einen Schritt, ebenso die Evaluierung der \(\textbf{WHILE}\)-Bedingung. \(\textbf{TIME}^k_P(a_1,\ldots,a_k)\) ist also die Anzahl der Ausführungsschritte von \(P\) bei Eingaben \(a_1,\ldots,a_k \in \mathbb{N}\) (undefiniert, falls \(P\) auf \(a_1,\ldots,a_k\) nicht terminiert).

Andere Berechnungsmodelle

Es gibt eine Vielzahl von Berechnungsmodellen, die ähnlich formal wie die WHILE-Sprache definiert sind; die folgende Liste ist eine Auswahl:

• GOTO-Programme sind sehr ähnlich zu WHILE-Programmen, erlauben aber anstelle von Schleifen GOTO-Anweisungen.
• Turingmaschinen; das wohl bekannteste und historisch wichtigste Modell.
• Der Lambda-Kalkül; eine sehr mathematische Formalisierung von Berechenbarkeit.
• \(\mu\)-Rekursion; eine wiederum mathematische Formalisierung, die mit Abschlusseigenschaften arbeitet.

Interessanterweise sind alle diese Berechnungsmodelle äquivalent, das heißt, dieselben Funktionen sind berechenbar in jedem Modell. Außerdem sind diese Modelle auch äquivalent zur Mächtigkeit moderner Programmiersprachen. Diese Eigenschaft der Programmiersprachen nennt man Turing-Vollständigkeit.

LOOP-Berechenbarkeit

Wir führen jetzt eine Schleife ein, bei der die Anzahl der Schleifendurchläufe bei Schleifeineintritt schon feststeht. Dazu verwenden wir \(\textbf{LOOP }x_i\textbf{ DO }P\textbf{ END}\) mit der Semantik, dass \(P\) genau so oft ausgeführt wird, wie \(x_i\) zum Zeitpunkt des Schleifeneintritts festlegt. Wenn wir keine unbeschränkten Schleifen (WHILE-Schleifen) zulassen, sondern nur LOOP-Schleifen, dann terminiert das Programm immer; solche Programme nennt man LOOP-berechenbar (oder auch primitiv rekursiv). Es gibt allerdings Funktionen, die zwar WHILE-berechenbar sind, jedoch nicht LOOP-berechenbar, zum Beispiel die Ackermannfunktion. Somit hat die LOOP-Sprache (ohne WHILE) einige Vorteile (weil die berechneten Funktionen immer total sind), andereseits aber auch Nachteile (weil einige WHILE-berechenbare Funktionen nicht LOOP-berechenbar sind).

Was haben wir gelernt?

1. WHILE-Programme sind eine Möglichkeit der Formalisierung von Berechnung. Viele andere Formalisierungen sind möglich und äquivalent.
2. Ohne Syntactic Sugar will man nicht in WHILE programmieren.
3. Die Laufzeit von WHILE-Programmen kann man unabhängig von Hardware als Anzahl der ausgeführten Befehle definieren.
4. Restriktivere Berechnungsmodelle sind selten, ermöglichen aber teilweise andere interessante Eigenschaften (zum Beispiel, dass alle Programme terminieren).

Bonus: Geschichte der Berechnungsmodelle