01-einleitung.org

01 - Einleitung

  \subtitle{{{{title()}}}}

  \maketitleframe

\begin{frame}{Der Dozent}
  \PutAt{(10cm,1.6cm)}{
    \includegraphics[width=2cm]{fig/01-dietrich}\scriptsize
    \\\mbox{Christian Dietrich}
  }
  \bi
  \ii Wer ist der Dozent da? (30. Semester)\\{
    \bi
    \ii Informatikstudium in Erlangen (ab 2009)
    \ii Promotion in Hannover (2019)
    \ii Juniorprofessor an der TUHH (2021-2023)
    \ii Betriebssysteme, \textbf{Programmiersprachen}, \\Low-Level Gefrickel, Emacs User
    \ei
  }\medskip
  \ii Ich mag Programmiersprachen! {
    \bi
    \ii Sie erleichtern mir Lösungen klar und deutlich aufzuschreiben.
    \ii Sowohl eleganter als auch zu komplexer Code ist Kunst.
    \ei
  }\qquad\qquad
  \ii<2-> Programmiersprachen und Übersetzer erstmals an der TU-BS  {
    \bi
    \ii Wir müssen das jetzt gemeinsam durchstehen.
    \ii Ich werde mein Bestes geben ihnen nur Sinnvolles zu vermitteln.
    \ii Melden Sie sich mit Fehlern, Kritik und Anregungen.
    \ei
  }
  \ei
\end{frame}

Gedanken zu dieser Vorlesung

Mit der ersten Vorlesung, soll der Studierende für die Vorlesung motiviert werden. Es soll verstehen, welcher ganz konkreten Erkenntnisgewinn aus der Veranstaltung gezogen werden kann sich mit Programmiersprachen und deren Implementierungen zu beschäftigen. Ihm muss klar werden, dass er hier zukunftssicheres Wissen erlangt.

• Was muss der Studierende wissen um eine neue Programmiersprache effektiv und effizient ein zu setzen?
  • Welche Abstraktion bietet eine Programmiersprache an und was hat dies mit dem Ebenenmodell zu tun?
  • Was ist der Unterschied zwischen einem Interpreter und einem Übersetzer?
  • Was darf ein Übersetzer und was darf dieser nicht?

Einleitung

In diesem Skript sind die Themen der Vorlesung “Programmiersprachen und Übersetzer” noch einmal schriftlich erörtert. Dabei erhebt das Skript **keinen** Anspruch auf Vollständigkeit und es ersetzt auch nicht die Lektüre von Lehr- und Fachbüchern. Im Verlaufe der Veranstaltung werden Sie entsprechende Literaturhinweise, sowohl Bücher als auch Links zu entsprechenden Fachartikeln und Blogeinträgen, finden. Sollten Sie weitere interessante Artikel zur Veranstaltung finden, scheuen Sie sich nicht, mir diese zuzusenden.

Um unnötige Dopplungen mit den Folien zu vermeiden, haben wir die einzelnen Vorlesungsfolien in dieses Dokument mit eingebunden. Zu den jeweiligen Abschnitten finden Sie die Erläuterungen, Ergänzungen und Informationen, die während der Vorlesung auf der “Tonspur” erzählt werden. In den jeweiligen Folienblöcken können Sie mittels Mausklick vorwärts, und bei gedrückter Shifttaste rückwärts, navigieren.

\begin{frame}{Was soll diese Veranstaltung leisten?}
  \btUseExtraItemSep
\bi
\ii<+-> Informatiker werden fortwährend mit neuen Sprachen konfrontiert. {
  \bi
  \ii The next 700 programming languages, P. J. Landin\only<+->{, \citeyear{landin:66:cacm}\hfill\cite{landin:66:cacm}}
  \ii<+-> Hype Train (z.B. Rust), Evolution (C++20), Legacy (COBOL)
  \ii<.-> Sprachen allerorten: HTML5, LaTeX/TikZ, SQL, QT5/QML
  \ei
}
\ii<+-> \Structure{Anforderung an Sie}: Schnell \alert{effektiv} und \alert{effizient} entwickeln können. {
  \bi
  \ii Effektiv:  In der Lage sein, ein komplexes Programm zu schreiben.
  \ii Effizient: Das Programm soll schnell und ressourcenschonend sein.
  \ii Häufig gibt es eine Abwägung zwischen beiden Zielen (siehe Skriptsprachen).
  \ei
}
\ii<.-> \Structure{Mein Ziel}: Vermittlung von Handwerkszeug und Denkweisen. {
  \bi
  \ii Welche Fragen muss ich an eine neue Programmiersprache stellen?
  \ii Welche Konstrukte müssen prinzipbedingt teuer sein?
  \ii Demystifizierung der Black Box \enquote{Übersetzer}
  \ei
}
\ei
\end{frame}

\begin{frame}[fragile,t]{Wieso ist das überhaupt möglich?}
  \btUseExtraItemSep
  \bi
  \ii Sprachen wurden von Ingenieuren erdacht. Man baut, was man kennt.  {
    \bi
    \ii Jede neue Sprache bringt nur eine Hand voll neuer Konzepte.
    \ii Der Rest ist eine Rekombination von bereits Bekanntem.
    \ei
  }
  \ii<+-> Beispiel: Über einen Zahlenvektor iterieren. {

  \begin{code}<1|handout:1>[tag=C]
    \begin{C}[]
      int sum = 0;
      int *it;
      for (it  = &vec[0];    // Initialisierung
           it != &vec[10];   // Abbruchbedingung
           ++it) {           // Nächstes Element
        sum += (*it);
      }
    \end{C}
  \end{code}%
  \begin{code}<2|handout:2>[tag=C++03]
    \begin{CPP}[]
      int sum = 0;
      std::vector<int>::iterator it;
      for (it = vec.begin();  // Initialisierung
           it != vec.end();   // Abbruchbedingung
           ++it) {            // Nächstes Element
        sum += (*it);
      }
    \end{CPP}
  \end{code}%
  \begin{code}<3|handout:3>[tag=Python]
    \begin{py}[]
      sum = 0
      for x in vec:
          sum += x
    \end{py}
  \end{code}%
  \begin{code}<4-|handout:4->[tag=C++11]
    \begin{CPP}[]
      int sum = 0;
      for (int x : vec) { // foreach Schleife
        sum += x;
      }
    \end{CPP}
  \end{code}
}
  \ii<5-> Gemeinsame Konzepte von verschiedenen Programmiersprachen {
    \bi
    \ii Datentypen, Objekte, Benennung von Objekten, Operationen auf Objekten
    \ii Gemeinsamkeiten erleichtern erfahrenen Programmierern den Einstieg.
    \ii Unendliche Mannigfaltigkeit in unendlicher Kombination! (Spock)
    \ei
  }
  \ei

\end{frame}

Zunächst stellt sich die Frage, wieso es für einen Informatiker sinnvoll ist, sich im Detail mit Programmiersprachen, ihren Konzepten und ihrer Übersetzung in Maschinencode zu beschäftigen. Schließlich gibt es all diese Werkzeuge bereits und wir können sie einfach verwenden. Außerdem haben Sie vielleicht das Gefühl, dass Übersetzer und deren Konstruktion ein schwierig zu durchdringendes Thema sind und eher an schwarze Magie denn an normale Programmierung erinnern. Aus eigener Erfahrung kann ich Ihnen sagen: Dem ist nicht so und sowohl Programmiersprachen, als auch Übersetzer, sind ein spannendes Feld der Informatik, in dem eine beständige Entwicklung stattfindet.

Diese beständige Entwicklung stellt allerdings auch eine Herausforderung für Sie, als Informatiker oder Informatik-geneigter Ingenieur, dar. Mit den Programmiersprachen, die Sie im Laufe Ihres Studiums konfrontiert sind, werden Sie nicht über die nächsten 40 Jahre kommen. Um zukunftssicher zu werden, brauchen Sie nicht nur rein technisches Wissen über eine oder zwei Sprachen, sondern systematisches und konzeptionelles Wissen, das nicht so schnell altert, wie der Hype-Train vom **Java** Bahnhof, über die **C#** Hochebene, zur **Rust**-Mine braucht.

Aber nicht nur die fortschreitende Entwicklung einzelner Programmiersprachen oder das Aufkommen von ganz neuen Sprachen bringt dauerhafte Relevanz für das Thema, sondern auch die schiere Prävalenz und die Vielfalt an Sprachen, die von Computern mechanisch verarbeitet werden. Sprachen werden nicht nur für die Kodifikation von ausführbaren Programmen verwendet, sondern, unter anderem, auch zur Aufbereitung von Informationen (z.B. HTML5 oder TiKZ) oder zur Beschreibung von Datenabfragen (z.B. SQL oder Overpass).

Im Laufe Ihres Lebens wird, nachdem in ihrem Projekt entschieden wurde die Programmiersprache R++ in Version 2034 zu verwenden, die Anforderung an Sie gestellt werden, möglichst schnell **effektiv** darin zu werden ein möglichst **effizientes** Programm zu schreiben. Die von Ihnen erwartete Effektivität besteht darin, dass Sie die Fähigkeit erarbeiten, überhaupt ein Programm zu schreiben. Die erwartete Effizienz besteht darin, dass das erstellte Programm nicht unrealistisch lange für eine einfache Aufgabe braucht. Aber auch, wenn Sie selbst in die Lage kommen, die Wahl der Programmiersprache für ein neues Projekt zu treffen, brauchen Sie das nötige Wissen, um eine informierte Entscheidung treffen zu können. Beispielsweise muss die Abwägung zwischen der performanten Ausführung einer übersetzten Sprache und der schnellen Entwicklung in einer Skriptsprache, je nach Anwendungsfall, Unternehmenstruktur und Verfügbarkeit von Entwicklern, anders getroffen werden. Ein Startup, welches seine Webanwendung in COBOL entwickelt, wird es schwer haben die nötige Entwicklungsgeschwindigkeit zu erreichen.

Da Sie das Erlernen neuer Sprachen also nicht vermeiden können, können Sie es sich auch gleich möglichst einfach machen und wiederverwendbare Konzepte lernen anstatt 20 Ausprägungen von selbem Konzept. Dies ist auch das angepeilte Vorgehen dieser Veranstaltung: Wir werden uns Sprachkonzepte anschauen, die immer wieder auftauchen, und wir werden versuchen ihre Essenz herauszudestillieren. Dabei werden wir uns Beispiele aus verschiedensten Sprachen anschauen, um unterschiedliche Ausprägungen dieser Konzepte kennenzulernen. Nur so können wir der großen Vielfalt an Sprachen adäquat begegnen, ohne in einer Flut technischer Details unterzugehen.

Zu Gute kommt uns dabei, dass Ingenieure, auch bei der Entwicklung einer neuen Sprache, nicht jedes mal auf der grünen Wiese anfangen, sondern gerne auf altbewährte Konzepte zurückgreifen. Diese evolutionäre Entwicklung ist allerdings nicht reiner Phantasielosigkeit geschuldet, sondern hat den sozialen Faktor, dass andere Ingenieure einfacher in die neue Sprache hineinfinden; die Einstiegshürde ist deutlich geringer. Ein Beispiel für das evolutionäre einschleichen eines Sprachkonzepts in den Kanon allgemein bekannter Konzepte ist die Iteration über eine Sequenz von Elementen. Wo in C noch umständlich mit Zeigern hantiert wird, und die ursprüngliche C++-Variante beinahe genauso aussieht, hat die aktuelle Version von C++ die Möglichkeit, mittels einer Kurzschreibweise, über Sequenzen zu iterieren.

sequence = [1, 1, 2, 3, 5, 8, 13]
idx = 0
while idx < len(sequence):
    print(sequence[idx])
    idx += 1

print("---")
for element in sequence:
    print(element)

Im Verlaufe des Skriptes gibt es Quellcodebeispiele, die direkt im Browser ausgeführt werden können. Um die Ladezeit der Seite zu verringern, haben wir darauf verzichtet diese Funktionalität standardmäßig zu aktivieren. Durch einen Klick auf den “Load Interpreter” Button, wird Klipse nachgeladen und die Beispiele erwachen zum Leben und können auch direkt im Browser editiert werden. Allerdings erfolgt das Nachladen von Klipse von Drittseiten, auf deren Einstellung zu Ihrer Privatsphäre wir keinen Einfluss haben. Falls Sie Browserplugins zur digitalen Selbstverteidigung, wie uMatrix, nutzen, müssen Sie Ihre Einstellungen entsprechend anpassen. Ansonsten können Sie den Codeschnipsel auch herauskopieren und als Python (leider nur Version 2) Programm ausführen

Inhalt der Veranstaltung

\begin{frame}{Welchen Inhalt hat diese Veranstaltung?}
  \bi
  \ii \STRUCTURE{Programmiersprachen}: Abstrahiert von der echten Maschine {
    \bi
    \ii Kernkonzepte, die sich in vielen Sprachen wiederfinden
    \ii High-Level Paradigmen (funktional, OO), die sich daraus zusammensetzen
    \ii Wir werden uns verschiedenste Programmiersprachen anschauen.
    \ei
    }
  \ei

  \begin{center}
    \Large {\Huge $\downarrow$} Programmiersprachen und Übersetzer {\Huge $\uparrow$}
  \end{center}

  \bi
  \ii \STRUCTURE{Übersetzer}: Bringt die Abstraktionen auf die Maschine {
    \bi
    \ii Zwischenschritte vom Zeichenstrom zum Assemblerprogramm
    \ii Nötige Datenstrukturen und Algorithmen
    \ii Praktische Arbeit an einem einfachen Übersetzer
    \ei
  }
  \ei
\end{frame}

\begin{frame}{Literaturhinweise}\small
  \begin{columns}
    \begin{column}{2cm}
      \includegraphics[width=\linewidth]{fig/01-pragmatics}%
    \end{column}
    \begin{column}{9cm}
      \emph{Programming Language Pragmatics, Fourth Edition.\\Michael L. Scott, 2015.}\\[1ex]
      Folgt einer ähnlichen Herangehensweise wie die Vorlesung. Deckt sowohl den Sprach- als auch den Übersetzerteil ab.
    \end{column}
  \end{columns}
  \bigskip
  \begin{columns}
    \begin{column}{2cm}
      \includegraphics[width=\linewidth]{fig/01-aho}%
    \end{column}

    \begin{column}{8cm}
      \emph{Compiler: Prinzipien, Techniken und Werkzeuge.\\Ullmann, Lam, Sethi, Aho, 2008.}\\[1ex]
       \textbf{Das} klassische Buch zum Übersetzerbau (Drachenbuch). Auch bereits in der alten Auflage von unschätzbarem Wissen.
     \end{column}
     \begin{column}{2cm}
       \includegraphics[width=\linewidth]{fig/01-aho-old}%
     \end{column}
   \end{columns}
\end{frame}

Diese Veranstaltung trägt den Namen “Programmiersprachen und Übersetzer” und ist dementsprechend auch entlang dieser beiden Begriffe in zwei Teile getrennt, die allerdings eng miteinander interagieren. Die Programmiersprachen geben vor, welche Konstrukte bei der effektiven Kodierung von Programmen verwendet werden können. Auf der Gegenseite entscheidet der Übersetzer, wie diese Konstrukte auf die darunterliegende Maschine abgebildet werden und bestimmt damit maßgeblich die Effizienz der Programmausführung.

Im Bereich der Sprachen werden wir uns mit Kernkonzepten beschäftigen, die in vielen unterschiedlichen Sprachen auftauchen. Dazu gehört die Frage nach Typannotationen (z.B. int, struct element), genauso wie die Menge der verwendbaren Kontrollstrukturen (z.B. if, while, do-while). Hierbei werden wir einen Fokus auf jene Konzepte werfen, die in Sprachen verwendet werden, die dem funktionalen bzw. dem objektorientierten Paradigma zugeordnet werden können. Man kann davon sprechen, dass ein **Programmierparadigma** aus diesen Konzepten zusammengesetzt wird, um einen bestimmen Stil oder eine “Philosophie” von Implementierungen zu ermöglichen. Jedoch kann heute kaum noch eine Programmiersprache nur einem dieser Paradigmen zugeordnet werden.

Auf Seite der Übersetzer wollen wir uns jene Zwischenschritte anschauen, die notwendig sind, um Programme einer Hochsprache in die eigentliche Sprache der Maschine zu übersetzen. Durch diese mechanische Übersetzung, bei der die Abstraktionen der Sprache schrittweise abgebaut werden, können wir nicht nur feststellen, ob bei der Kodierung Fehler passiert sind (der Übersetzung schlägt fehl), sondern es können auch diverse Optimierungen durchgeführt werden, auf die wir ebenfalls einen kurzen Blick werfen wollen. Dabei können die Vorlesungseinheiten zum Übersetzerbau kein vollständiges Bild liefern, dazu ist die Vielfalt an möglichen Sprachkonstrukten zu groß. Das Ziel dieser Termine ist es, Ihnen einen Überblick über die kanonischen Zwischenschritte der Übersetzung von imperativen Sprachen zu geben. Dabei ist es ebenfalls mein Ziel, Ihnen eine Intuition zu vermitteln, welche Konstrukte einer Sprache inhärent weniger effizient sind als andere.

Als Literatur zu dieser Vorlesung empfehle ich ihnen “Programming Language Pragmatics” von Michael L. Scott, welches eine ähnliche Mischung von Sprachkonzepten und Übersetzerbau wie diese Vorlesung hat. Dabei deckt dieses Buch viel mehr ab als wir in dieser Veranstaltung machen können, und ist daher nicht nur eine gute Grundlage zur Vor- und Nachbereitung, sondern auch ein Startpunkt für alle Studierenden, die sich noch tiefer mit dem Thema auseinandersetzen wollen. Daneben muss man auch **das** klassische Buch zum Übersetzerbau von Ullmann, Lam, Sethi und Aho empfehlen, welches den Übersetzerbau noch intensiver diskutiert. Im Laufe der Veranstaltung werde ich, wo sinnvoll, einzelne Unterkapitel aus diesen Büchern referenzieren.

\begin{frame}{Übersicht}
  \includegraphics[width=\textwidth,page=3]{fig/01-overview-small}
\end{frame}

\begin{frame}{Programmiersprachen}
  \centering
  \includegraphics[height=\textheight-2cm,page=1]{fig/01-overview-small}
\end{frame}

\begin{frame}{Übersetzer}
  \includegraphics[width=\textwidth,page=2]{fig/01-overview-small}
\end{frame}

\begin{frame}[fragile]{Kurzübersicht: Syntaktische Analyse}
  \framesubtitle{\lecturetag{compiler}{2}}
  \begin{center}
    \includegraphics[page=1,width=0.6\linewidth]{fig/01-overview-example}
  \end{center}
  \bi
  \ii Von der Zeichenkette zum Abstrakten Syntaxbaum {
    \bi
    \ii Strukturierte Daten lassen sich einfacher verarbeiten als Strings.
    \ii Formale Grammatiken und effiziente Parsertechniken
    \ii Parser prüft einen Teil der Sprachregeln: Syntaktische Korrektheit
    \ei
  }
  \ei
\end{frame}

\begin{frame}{Kurzübersicht: Semantische Analyse}
  \framesubtitle{\lecturetag{compiler}{5}}
  \begin{center}
    \includegraphics[page=2,width=0.6\linewidth]{fig/01-overview-example}
  \end{center}
  \bi
  \ii Von Typprüfung und Namensauflösung {
    \bi
    \ii Ist das Programm wirklich Teil der Sprache?
    \ii Namensauflösung findet zu jedem Bezeichner das jeweilige Objekt.
    \ii Typprüfung stellt sicher, dass die deklarierten und inferrierten Typen stimmen.
    \ei
  }
  \ei
\end{frame}

\begin{frame}{Kurzübersicht: Zwischencodeerzeugung}
  \framesubtitle{\lecturetag{compiler}{8}}
  \begin{center}
    \includegraphics[page=3,width=\linewidth]{fig/01-overview-example}
  \end{center}
  \bi
  \ii Vom Syntaxbaum zum Kontrollflussgraphen {
    \bi
    \ii Zwischencode ist eine ausdrucksmächtige virtuelle Maschine.
    \ii Bereits nahe an realer Maschine, aber gut für Analysen und Optimierungen
    \ii Alle Sprachkonstrukte müssen linearisiert werden.
    \ei
  }
  \ei
\end{frame}

\begin{frame}[fragile]{Kurzübersicht: Maschinencode}
  \framesubtitle{\lecturetag{compiler}{10}}
  \begin{columns}
    \begin{column}{0.4\textwidth}
      \includegraphics[page=4,width=\linewidth]{fig/01-overview-example}
    \end{column}\hfill
    \begin{column}{0.4\textwidth}
      \begin{code}[tag=RV32I]
      \lstinputlisting[style=ASM]{lst/01-example-if.S}
    \end{code}
  \end{column}
\end{columns}
\bigskip

\bi
\ii Vom Zwischencode zur realen Maschine {
  \bi
  \ii Auswahl von passenden Befehlen der realen Maschine
  \ii Bestimmung des Stacklayouts für jede Funktion
  \ii Entscheidung, welcher Wert zu welchem Zeitpunkt in einem Register \enquote{lebt}.
  \ei
}
\ei

\end{frame}

Die drei Themenbereiche Übersetzertechniken, Sprachkonzepte und Paradigmen von Programmiersprachen werden in den nächsten 12 Vorlesungen vermischt und aufeinander aufbauend behandelt. Dabei werden wir in der ersten Hälfte des Semesters die notwendigen Grundlagen an Sprachkonzepten schaffen, um diese dann direkt in der entsprechenden Phase der Übersetzung verwenden zu können. Zum Beispiel führt die semantische Analyse sowohl die Typprüfung als auch die Namensauflösung durch, wodurch Vorlesung 2 und 3 direkt in die Semantische Analyse im Übersetzer übergehen.

In der zweiten Hälfte des Semesters wird der Fokus der Veranstaltung sich in beide Richtungen erweitern: Zum einen lernen wir die weiteren technischen Schritte kennen, um vom abstrakten Syntaxbaum zum fertigen Maschinenprogramm zu kommen. Zum anderen schauen wir uns die Philosophie hinter dem objektorientierten und dem funktionalen Programmierparadigma an, welche aus den grundlegenden Sprachkonzepten komponiert sind. Hier geht es nur noch teilweise um konkrete Techniken und Sprachkonstrukte, sondern mehr um jene Designentscheidungen und Prinzipien, die man anwenden muss, um objektorientiert bzw. funktional zu programmieren. Denn nur weil eine Sprache Abstraktionen für Klassen und Objekte anbietet, heißt es noch lange nicht, dass alle Programme, die in jener Sprache verfasst sind, automatisch auch objektorientiert sind. Man kann jede Turing-vollständige Sprache gegen den Strich bürsten; man sollte es nur nicht tun.

Die einzelnen Schritte der Übersetzung können wir in mindestens vier Abschnitte einteilen, die von weiteren, optionalen, Abschnitten begleitet werden können. Jeder dieser Abschnitte wird in einer Vorlesung behandelt und soll einen Überblick über das jeweilige Thema bieten.

Syntaktische Analyse

Die Übersetzung startet in der syntaktischen Analyse mit dem Einlesen des Programms als Zeichenkette (z.B. von der Festplatte). Dabei haben die einzelnen Zeichen noch keinerlei Bedeutung (oder Semantik) für den Übersetzer, sondern es ist nur ein Array von Bytes. Zu diesem Zeitpunkt ist der Quellcode noch nach dem jeweiligen Gusto des Programmierers (z.B. überflüssige Leerzeichen) formatiert. Durch die syntaktische Analyse überführen wir diese Sequenz von Bytes in einen **abstrakten Syntaxbaum** (AST), der die hierarchische Programmstruktur widerspiegelt. In dem gezeigten Beispiel, ist die Bedingung a > b als erstes Kind der Bedingung im Baum eingeordnet. Um diesen Schritt der Strukturextraktion zu machen, werden wir uns die Lexing (Abtastung) und Parsing (Zerteilung) anschauen. Nachdem wir ein Programm syntaktisch analysiert haben, wissen wir, ob es einen Syntaxfehler enthält. Allerdings ist noch nicht klar, ob es wirklich ein valides Programm der gewünschten Sprache ist, denn es könnte zum Beispiel noch Typfehler enthalten.

Semantische Analyse

Den zweiten notwendigen Schritt der Programmanalyse führen wir auf dem AST durch. Dabei analysieren wir den AST auf seine semantische Bedeutung. Zum einen bedeutet das den Schritt vom Bezeichner zum Namen (was ist die Bedeutung eines Variablennamens) zu machen und für jede Verwendung einer Variable die gültige Definition zu finden. Im Beispiel sieht man dem AST erst nach der semantischen Analyse an, dass a eine lokale und b eine globale Variable ist. Weiterhin wird das Programm auf Typkorrektheit hin untersucht: Passen die von den Blättern des Baumes (unten) zur Wurzel (oben) hin propagierten Datentypen zu den verwendeten Operationen? Würde man im Beispiel schreiben 23 > "hallo", wäre dies zwar syntaktisch Korrekt, jedoch nicht semantisch, da man Zahlen nicht mit Zeichenketten vergleichen darf. Nach der semantischen Analyse wissen wir endgültig, ob das Programm ein valides Programm ist. Tritt bis hier kein Fehler bei der Übersetzung auf, darf auch in den nachfolgenden Schritten kein Fehler mehr auftreten.

Erzeugung des Zwischencodes

Mit dem Übergang vom AST zum Zwischencode (engl. intermediate representation, IR) klopfen wir die hierarchische Baumstruktur einzelner Operationen platt und machen einen großen Schritt hin zur realen Maschine. Der Zwischencode moderner Übersetzer ist an Assemblerbefehle angelehnt, enthält aber noch genug Informationen, um weitreichende Programmoptimierungen durchzuführen. Der Zwischencode enthält keine sprachspezifischen Konstrukte mehr und kann daher für Sprachfrontends verwendet werden. Zum Beispiel wird sowohl die Programmiersprache Rust als auch C++ (bei Verwendung von clang) in LLVM-IR[fn::Einen kurzen Überblick über LLVM-IR bietet der folgende Blogeintrag: https://idea.popcount.org/2013-07-24-ir-is-better-than-assembly/] übersetzt, bevor es an die Optimierung und Erzeugung der Binärdatei geht.

Maschinencode

Für den letzten Schritt zur Binärdatei muss der Zwischencode zu Assemblerinstruktionen übersetzt werden. Dabei müssen semantisch äquivalente Befehle oder Befehlssequenzen der realen Maschine ausgewählt werden. Weiterhin verwendet der Zwischencode noch (unendlich viele) Variablen, wo die reale Maschine nur eine endliche Anzahl an Registern anbietet. Daher müssen die Werte an diese realen Register gebunden werden (Registerallokation).

\begin{frame}[fragile]{Was passiert in den Übungen?}
  \Alert{Ziel:} Vertiefung von theoretischem Wissen und praktische Erfahrungen.
  \medskip
  \bi
  \ii Theorieaufgaben zur Durchdringung des Vorlesungsinhalts
  \ii Praktische Programmieraufgaben {
    \bi
    \ii Erweiterung eines kleinen Beispielübersetzers (in Python)
    \ii Arbeiten am Parser, der Typprüfung, Codeerzeugung, und am Optimierer
    \ii Übersetzer macht selbst rege Gebrauch von Python Sprachfeatures
    \ei
  }\medskip
  \ii Die Programmiersprache L0 - Basis unseres Übersetzers{
    \begin{columns}
      \begin{column}{0.49\textwidth}
        \begin{code}[tag=L0]
          \begin{lzero}[]
            var fib_calls : int;

            func fib(n : int) : int {
              fib_calls = fib_calls + 1;
              if (n <= 1) {
                return n;
              }
              return fib(n-1) + fib(n-2);
            }

          \end{lzero}
        \end{code}
      \end{column}
      \hfill
      \begin{column}{0.47\textwidth}
        \btUseExtraItemSep[-\smallskipamount]
        \bi
        \ii Globale und lokale Variablen
        \ii Funktionen mit mehreren Argumenten
        \ii Nur Ganzzahlen und Pointer
        \ii Keine Sicherheitsnetze
        \ei

      \end{column}
    \end{columns}
  }
  \ei
\end{frame}

Während wir in der Vorlesung die theoretischen Grundlagen kennenlernen, soll Ihr Wissen in der Übung weiter vertieft werden. Dies wird zum einen dadurch geschehen, dass wir Ihnen passende theoretische Aufgaben zur Bearbeitung stellen. Zum anderen sollen Sie auch praktische Übungen an einem Beispielübersetzer, der von uns bereitgestellt wird, durchführen. Dieser Übersetzer verarbeitet bereits die rudimentäre L0-Sprache und wird von Ihnen um diverse Fähigkeiten erweitert werden. Durch diese Arbeit an einem existierenden Übersetzer lernen Sie den Aufbau eines solchen Softwareprojekts kennen und können die Arbeit eines Übersetzers “live und in Farbe” erleben.

Organisation der Veranstaltung

  \begin{frame}[t]{Organisatorisches: Vorlesung}
  \PutAt{(10.5cm,1cm)}{
    \includegraphics[width=2cm]{fig/01-dietrich}
  }
  \bi
  \ii Vorlesung: 12 Termine {
    \bi
    \ii Mittwochs 9:45-11:15 Uhr, IZ160 und BBB (Hybrid)
    \ii Terminplan und Vorlesungsaufzeichnung im Stud.IP
    \ii Vorlesungsskript auf der IBR Seite
    \ii Sourcen sind auf Github (CC-BY 4.0), PR welcome.
    \ei
  }\medskip
  \ii Besonderheiten in diesem Semester {
    \bi
    \ii Vorlesung und Übung aus einer Hand.
    \ii Ihre Mithilfe ist essentiell (Beteiligung, Rückmeldungen, Solidarität)
    \ei
  }
  \ei
  \pause
  \vspace{1em}
  \Large
   \STRUCTURE{Universität}:\\\hspace{1cm} Sprechen Sie \btSetTab mit den interessantesten Menschen\\\btUseTab über die abwegigsten Themen
\end{frame}

\begin{frame}[t]{Organisatorisches: Übungen}
  \PutAt{(10.5cm,1cm)}{
    \includegraphics[width=2cm]{fig/01-dietrich}\\
  }
  \bi
  \ii \structure{Tafelübungen}: 6 Termine {
    \bi
    \ii Verantwortlicher: \textbf{Auch ich…}
    \ii Donnerstag 15:00-16:30, IZ 161 und BBB (Hybrid)
    \ii Übungsaufzeichnung im Stud.IP
    \ii Vertiefung der Vorlesung, Erörterung der Übungsaufgaben
    \ei
  }\medskip
  \ii \structure{Fragestunden}: Freie TÜ Slots {
    \bi
    \ii Donnerstag 15:00-16:30, IZ 161
    \ii Beantwortung von Fragen, Hilfe bei den Übungen
    \ii Bringen Sie ihr Notebook mit!
    \ei
  }\medskip
  \ii \structure{Aufgaben}: 6 Aufgaben mit theoretischem und praktischen Anteil {
    \bi
    \ii Bearbeitung in \textbf{Zweierteams}, Abgabe im Gitlab
    \ii Korrektur durch studentische Tutoren
    \ei
  }
  \ei
\end{frame}

\begin{frame}{Das Modul: Programmiersprachen und Übersetzer}
  \btUseExtraItemSep
  \begin{itemize}
  \item Schriftliche Klausur\hfill\ALERT{rechtzeitig anmelden} {
      \begin{itemize}
      \item Dauer: \btSetTab[8ex] 90 Minuten, schriftlich
      \item Termin: \btUseTab Unbekannt
      \item \ALERT<2>{Benotete Prüfungsleistung}
      \end{itemize}
    }
  \item Arbeitsblätter  \hfill\ALERT{rechtzeitig abgeben!} {
      \begin{itemize}
      \item 6 Arbeitsblätter, werden nur bei rechtzeitiger Abgabe gewertet
      \item Mindestens 50\% der erreichbaren Punkte
      \item \ALERT<2>{Unbenotete Studienleistung}
      \end{itemize}
    }
  \item<2-> Verwendbar für folgende Studiengänge {
      \bi
      \ii Informatik Bachelor
      \ei
    }
  \end{itemize}
\end{frame}


\begin{frame}{Wo bekomme ich Hilfe?}
  \begin{enumerate}
    \ii ÜbungspartnerInnen
    \ii KommilitonInnen\hfill\raisebox{0pt}[0pt]{\OrangeBox[align=left, scale content=0.85]{Reihenfolge beachten!}\vspace{2cm}}
    \ii \STRUCTURE{Stud.IP-Forum}
    \ii Übungstutoren
    \ii Chris
  \end{enumerate}

  \btUseExtraItemSep

  \begin{itemize}
    \ii Schriftliche Fragen zum Inhalt werden \textbf{nur im Forum} bentwortet
    \begin{itemize}
      \ii Studentische Antworten sind hier \STRUCTURE{sehr gerne gesehen}
      \ii Es gibt keine falschen Fragen -- und keine Nachteile durch Antworten
      \ii Trauen Sie sich auch zu antworten -- man lernt eine Menge dabei!
    \end{itemize}
    \ii Wir moderieren, korrigieren und ergänzen nach Bedarf. \textbf{Nur Mut!}
  \end{itemize}
\end{frame}

Ebenenmodell und Virtuelle Maschinen

\dividerframe{Ebenenmodell\\und\\ Virtuelle Maschinen}

\begin{frame}{Systemnahe Informatik}\framesubtitle{Der Blick aus 10000 Meilen}
    \begin{columns}
      \begin{column}{0.35\textwidth}
        \begin{center}\small
          \includegraphics[width=1.5cm]{fig/01-problem}\\\relax
          [Problem]\\[1ex]
          \fbox{\parbox{0.8\textwidth}{\centering
            Hochsprache\\
            $\Uparrow$\\
            \structure{Semantische Lücke}\\
            $\Downarrow$\\
            CPU-Steuersignale
          }}\\[1ex]\relax
        [Ausführung]\\\relax
        \includegraphics[width=1.5cm]{fig/01-cpu}
        \end{center}
      \end{column}\hfill
      \begin{column}{0.6\textwidth}
        \bi
        \ii {Informatisches Urproblem:\\ Schließen der Semantischen Lücke}\bigskip
        \ii Komplexitätsreduktion durch Abstraktion {
          \bi
          \ii Hierarchisch angeordnete \structure{virtuelle Maschinen}
          \ii Definierte Schnittstellen nach oben
          \ii Schrittweise Vereinfachungen nach unten
          \ei
        }\bigskip
        \ii PSÜ: Zwei Sichtweisen {
          \bi
          \ii Top-Down: Was bieten Sprachen an?
          \ii Bottom-Up: Wie bildet ein Compiler das ab?
          \ei
        }
        \ei
      \end{column}
    \end{columns}
  \end{frame}


  \newcommand{\down}[2][1em]{\tikzmark{#2}\tikz[remember picture,overlay]\draw[>=latex',->,thick,srared] (pic cs:#2)--++(down:#1);}
  \begin{frame}[label=vm-hierarchie]
    \frametitle{Hierarchie virtueller Maschinen\,\cite[S.\,3]{tanenbaum:06:sco}}

    \begin{columns}
      \begin{column}{0.7\textwidth}
        \bi
        \ii Schrittweises Schließen der semantischen Lücke\\[2ex]{
          \begin{tabular}{cllc}
            Ebene & Abstraktion & \\\hline
            $n$ & virtuelle Maschine $M_n$ & Sprache $L_n$ & \down{a} \\ \hline
            $\vdots$ & \multicolumn{1}{c}{$\vdots$}  & \multicolumn{1}{c}{$\vdots$}&\down{x}\\[0.5ex] \hline
            $2$ & virtuelle Maschine $M_2$ & Sprache $L_2$ &\down{b}\\ \hline
            $1$ & virtuelle Maschine $M_1$ & Sprache $L_1$ &\down{c}\\ \hline
            $0$ & reale Maschine $M_0$ & Sprache $L_0$\\\hline
          \end{tabular}
        }\bigskip
        \ii {$L_x$-Programm wird auf Maschine $M_{x-1}$ abgebildet
          \bi
          \ii \STRUCTURE{Dynamisch}: Interpreter als $L_{x-1}$-Programm
          \ii \STRUCTURE{Statisch}: Compiler erzeugt $L_{x-1}$-Programm\\
              Spätere Abbildung von $L_{x-1}$ auf $M_{x-2}$
          \ei
        }
        \ei
      \end{column}\hfill
      \begin{column}{0.2\textwidth}
        \begin{tikzpicture}
          \foreach \x/\s in {0/0.7,1/0.8,2/0.9,3/1} {
            \node at (\x*1mm,-\x * 8mm) {
              \includegraphics[width=\s\textwidth]{fig/01-matroschka}
            };
          }
        \end{tikzpicture}
        \legalcode[commons=Dedoushka-no_bg.jpg]{CC BY-SA 3.0}{Dedoushka}
      \end{column}
    \end{columns}
  \end{frame}

  \begin{frame}[t,label=vm-hierarchie-beispiel]{Beispiel: Arbeitsplatzrechner}
    \animation[trim={\btLeftMargin} 0pt 0pt 0pt, width=\textwidth]{1/1,2/2}{fig/01-layers}
  \end{frame}

Nach der vorangegangenen Motivation, wieso es sich lohnt sich mit Übersetzern und Programmiersprachen zu beschäftigen, wollen wir nun diese beiden Themen in den Kanon der Informatik, genauer gesagt der **systemnahen** Informatik, einordnen. Hierbei sind Programmiersprachen ein ganz essenzieller Teil bei einem der grundlegendsten Problemen der Informatik: Dem Zwiespalt zwischen dem Wunsch seine Problemlösung möglichst abstrakt und nahe am Problem zu formulieren, und der Realität der real existierenden Maschinen. Diesen Zwiespalt nennen wir auch **semantische Lücke**, da zwischen einer mathematischen Formulierung und dem existierenden Silizium eine große Lücke klafft. Dank Alan Turing und Alonzo Church wissen wir, dass sehr einfache Turingmaschinen bereits alles berechnen können, was berechnet werden kann; aber bequem geht es dabei keinesfalls zu.

Daher ist es ein Ziel der Informatik, die man auch als die Wissenschaft von der Abstraktion bezeichnen kann, diese semantische Lücke durch möglichst gute und effiziente Abstraktionen zu schließen. Da der Abstand zwischen beiden Seiten, mathematisches Problem und reale Hardware, sehr groß ist, sind sogar mehrere Abstraktionsstufen notwendig, die als Hierarchie von virtuellen Maschinen übereinander angeordnet werden. In dieser Veranstaltung werden wir uns einer dieser Schichten, der Hochsprachenebene, von zwei Seiten, einmal von unten nach oben (Bottom-Up), und einmal von oben nach unten (Top-Down) nähern.

Durch die Hierarchie der virtuellen Maschinen, wie sie von Tanenbaum beschrieben wird, abstrahieren wir von der realen Maschine, die ganz unten liegt, schrittweise, indem wir immer abstraktere virtuelle Maschinen darüber legen. Jede dieser virtuellen Maschinen kommt mit ihrer eigenen Sprache, in der sie programmiert wird: Wo die reale Maschine mittels Binärcode programmiert wird, können wir die weiter oben liegenden Maschinen bereits in textuell erfassbarem Assemblercode oder in einer Hochsprache wie C programmieren. Die Abbildung von den oben liegenden Maschinen, die ja nicht real existieren, sondern nur rein virtuelle Konzepte sind, auf die unteren Schichten erfolgt ebenso schrittweise, wie wir die Abstraktionen aufeinander aufgetürmt haben. Dabei kann die Abbildung auf die darunterliegende Maschine entweder statisch durch eine Übersetzung oder dynamisch durch Interpretation erfolgen.[fn::Die Unterscheidung zwischen statisch (vor der Laufzeit) und dynamisch (zur Laufzeit) wird uns durch das ganze Semester hindurch begleiten. Es ist das erste Kernkonzept von Programmiersprachen, dem wir begegnen; man kann es als die Frage “Was passiert in einer Sprache statisch und was passiert dynamisch?” formulieren.]

Im konkreten Falle eines Arbeitsplatzrechners ordnet sich die Hochsprachenebene direkt über der Ebene der Assemblersprache ein. Das in den Folien gezeigte Bild kennen Sie bereits aus der Veranstaltung ”Grundlagen der Betriebssysteme”, in der Sie sich mit der Maschinenprogramm- und Befehlssatzebene auseinandergesetzt haben. Zur Erinnerung: Das Betriebssystem nimmt eine Teilinterpretation des Anwenderprogamms vor, indem es jeden Systemaufruf (int 0x80, sysenter) aus dem Maschinenprogramm interpretiert; alle anderen Befehle (mov, add) werden direkt auf der Befehlssatzebene ausgeführt. In PSÜ werden wir uns nicht mit (Teil)Interpretation auseinandersetzen, sondern mit der Übersetzung von Hochsprachenprogrammen in Assemblersprachenprogrammen. Dabei werfen wir auch noch kurzen Blick auf den nachgelagerten Schritt der Linkens, der neben dem Assemblieren, die letzten Schritte zum ausführbaren Binärprogramm fehlt.

\begin{frame}[t]{"Virtuelle Maschinen"}
  \alert{Wichtig:} Wir meinen nicht VMWare, VirtualBox oder KVM.\bigskip

  \bi
  \ii Maschinenmodell der virtuellen Maschine {
    \bi
    \ii \structure{Speicher/Objekte}: Wie kann man Daten ablegen und wieder abrufen?
    \ii \structure{Befehle/Operationen}: Wie kann man Daten miteinander kombinieren?
    \ii Ein "\structure{Prozessor}" kann dieses Modell implementieren.
    \ei
  }\medskip
  \ii Maschinenprogramme {
    \bi
    \ii Eine Menge Befehlen, die gegen das Maschinenmodell geschrieben wurden.
    \ii Wird von einem Prozessor verarbeitet, um ein Ergebnis zu berechnen.
    \ei
  }\medskip
  \ii Sprache der virtuellen Maschine {
    \bi
    \ii Nicht jede Zeichenkette ist ein für jedes Maschinenmodell valides Programm.
    \ii Syntaktische und Semantische Regeln, um valide Programme zu schreiben.
    \ei
  }
  \ei
\end{frame}

\begin{frame}[fragile,t]{Beispiel: Die (virtuelle) RISC-V Maschine}
  RISC-V ist eine Rechnerarchitektur, die an industrieller Relevanz gewinnt.\bigskip

  \bi
  \ii Maschinenmodell (RV32I) {
    \bi
    \ii \structure{Speicher}: 32 CPU Register + frei adressierbarer Speicher
    \ii \structure{Befehle}: 47 Instruktionen mit arithmetischen, binären und Sprungbefehlen
    \ii Der SweRV von Western Digital ist \alert{ein} Prozessor für dieses Modell.
    \ei
  }\medskip
  \ii Beispiel eines Maschinenprogramms: 02 b5 05 3b 80 82 \pause{
    \\{\scriptsize (Wir tun mal so als wäre Assembler und Binärcode das gleiche)}\smallskip
    \begin{code}[tag=RV32I]
      \begin{asm}[]
        multiply: # int multiply(int a, int b) { return a*b; }
            mul a0, a0, a1
            ret
      \end{asm}
    \end{code}
  }\medskip
  \ii Die RV32I Assemblersprache {
    \bi
    \ii Welche Mnemonics gibt es? Anzahl und Art der Argumente.
    \ii \texttt{add}: 1 Ziel- und 2 Quellregister; \texttt{addi}: 1 Zielregister und 12-Bit Ganzzahl
    \ii \enquote{\texttt{addi a0, a2, $\gamma_i$}} -- wäre nicht valide in der RV32I Sprache.
    \ei
  }
  \ei
\end{frame}

\begin{frame}[fragile,t]{Beispiel: Die virtuelle C Maschine}
  \bi
  \ii Maschinenmodell {
    \bi
    \ii \structure{Speicher}: Definierte Variablen und über Pointer erreichbarer Speicher
    \ii \structure{Befehle}: z.B.: \lstinline{if (a < 3) return b * (c + d);}
    \ii Sowohl GCC als auch Clang sind \enquote{Prozessoren} für dieses Modell.
    \ii Es gibt auch C-Interpreter, die als Prozessoren agieren.
    \ei
  }\medskip
  \ii Beispielprogramm : Der Obfuscated Tiny C Compiler (2048 Zeichen)\footnote{\url{https://bellard.org/otcc/}}{
    \begin{code}[tag=C90]
      \lstinputlisting[basicstyle=\ttfamily\tiny, breaklines=true, postbreak=\mbox{}]{lst/01-otcc.c}
    \end{code}
  }\medskip
  \ii Die C-Sprache (eigentlich eine ganze Familie von Sprachen) {
    \bi
    \ii Variablen und Funktionen müssen deklariert sein, um sie zu nutzen.
    \ii Eine Ganzzahl ist kein valider Funktionsname.
    \ii \enquote{\texttt{12345(b, c)}} -- ist kein valides C-Programm.
    \ei
  }
  \ei
\end{frame}

\begin{frame}<1-2>{Definitionen}
  \btUseExtraItemSep \setbeamercovered{transparent}
  \begin{description}
  \item[Programmiersprache] Regelwerk zur Erstellung von Zeichenketten, die valide Programme für ein bestimmtes
    Maschinenmodell sind. Verletzt eine Zeichenkette auch nur eine dieser Regeln, ist es kein entsprechendes Programm.
  \item<1>[Interpreter] Ein Programm, das Sprachprozessor für ein bestimmtes Maschinenmodell ist und andere Programme direkt ausführt.
  \item[Übersetzer] Ebenfalls ein Sprachprozessor, der das gegebene Programm allerdings nicht ausführt, sondern in ein valides
    Maschinenprogramm für eine andere Sprache übersetzt.
  \end{description}
\end{frame}

Zunächst wollen wir uns mit dem Konzept der “virtuellen Maschinen”, welche wir im Ebenenmodell aufeinander stapeln, genauer beschäftigen und die Frage beantworten, was diese virtuellen Maschinen sind. Dabei beschäftigen wir uns nicht mit der Virtualisierung von echter Hardware, wie bei VMWare, bei der es darum geht eine existierende Maschinenschnittstelle (der IBM PC) so zu virtualisieren, dass man mehrere Instanzen davon nebeneinander laufen lassen kann. Unsere virtuellen Maschinen haben Schnittstellen, die unterschiedlich von den Maschinen auf denen sie implementiert werden, sind.

Grundlegend besteht eine virtuelle Maschine aus zwei Komponenten: dem Speicher und den angebotenen Befehlen. Dabei können Befehle Daten aus dem Speicher lesen, sie verarbeiten, und die Ergebnisse wieder zurückschreiben. Die Gesamtheit des Speichers zu einem Zeitpunkt ist der Zustand der virtuellen Maschine. Reihen wir mehrere (valide) Befehle hintereinander, so erhalten haben wir ein Programm der Maschine. Um dieses sehr abstrakte Konzept zu verdeutlichen, wollen wir einen Prozessor für das Modell einer kleinen virtuellen Maschine in Python implementieren.

def prozessor(memory, program, maximal_steps=10):
    """Prozessor fuer eine virtuelle Maschine mit 2 Befehlen: inc und print"""
    # Der Programmzaehler zeigt den naechsten Befehl an
    pc = 0
    steps = 0

    while steps < maximal_steps and pc < len(program):
        steps += 1
        # Der Array Zugriff: Holen der Instruktion
        (operation, operand) = program[pc]

        # Das if: Dekodierung der Instruktion
        if operation == "inc":
            # Das Ausführen der Operation
            memory[operand] += 1
        elif operation == 'print':
            print(memory[operand])
        else:
            raise RuntimeError("Invalid Opcode")

        # Gebe den Zustand nach jedem Befehl aus
        # print("Zustand nach %s: %s" %(program[pc], memory))

        # Inkrementieren des Programmzählers
        pc += 1

program = [
    # (Operation, Speicherzelle)
    ("inc",   0),
    ("inc",   0),
    ("inc",   1),
    ("print", 0)
]

memory = [0] * 5 # 5 Worte an genulltem Speicher

prozessor(memory, program)

Die gezeigte virtuelle Maschine beinhaltet beinahe alle Elemente, die zu unserem Verständnis von virtuellen Maschinen gehören. Zum ersten haben wir den Prozessor (prozessor()), der die Semantik des Maschinenmodells als Interpreter implementiert; ein übergebenes Programm wird also direkt ausgeführt, anstatt ein Programm einer tieferen Ebene zu erzeugen. Dieser Prozessor ist mit Hilfe der virtuellen Python-Maschine implementiert, die ihrerseits interpretiert wird.

Weiterhin hält program das auszuführende Programm und die Variable memory den Speicher der virtuellen Maschine. Beides übergeben wir dem Prozessor, der die Befehlsfolge sequentiell ausführt[fn::Nicht jede virtuelle Maschine hat eine solch sequentielle Ausführungsreihenfolge. Für manche Maschinenmodelle darf der Prozessor eine gute Reihenfolge, in gewissen Grenzen, selbst auswählen]. Spielen Sie mit der virtuellen Maschine herum: (1) Lassen Sie sich den Zustand nach jedem Befehl ausgeben. (2) Fügen Sie einen neuen Befehl mul10 ein, der eine Speicherzelle mit 10 multipliziert. (3) Was passiert, wenn Sie einen Befehl in das Programm einfügen, der nicht vom Prozessor unterstützt wird? (4) Was passiert, wenn Sie die adressierte Speicherzelle beim print auf 100 setzen?

Das einzige, was in dem Beispiel fehlt, ist die Sprache der virtuellen Maschine, denn diese ist nur im Skript, und hoffentlich jetzt auch in Ihren Köpfen, zu finden. Kurz könnte man sagen: Ein Programm unserer Beispielsprache ist eine Liste von Befehlen, die jeweils aus Operation und Operand bestehen; dabei muss die Operation eine der Zeichenketten "inc" oder "print" sein. Der Operand ist die Adresse einer Speicherzelle, von denen wir 5 haben, kodiert als Ganzzahl.

Mithilfe dieser Sprachdefinition können Sie nun noch einmal an die Aufgaben 3 und 4 herangehen und werden sehen, dass das Einfügen eines invaliden Befehls zwar Vordergründig zu einem RuntimeError geführt hat, aber der Prozessor eigentlich richtig gehandelt hat. Denn das übergebene Programm war leider kein Program, welches gegen unser Maschinenmodell programmiert wurde, es hatte nur Ähnlichkeit mit einem validen Programm. Ähnlich verhält es sich mit der zu großen Speicheradresse (4); auch dort war das übergebene Programm nicht von unserer Sprachdefinition abgedeckt.

Die Sprache eines Maschinenmodells beschreibt also wie valide Programme für dieses Modell aussehen müssen, damit sie von einem Prozessor der Sprache verarbeitet werden können. Dabei kann eine Sprache alle validen Programme exemplarisch aufzählen, aber einfacher ist es, ein Regelwerk aufzustellen, gegen das man Programme prüfen kann. Um eine möglichst präzise Prüfung vornehmen zu können, ist es sinnvoll, diese Regel formal aufzuschreiben. Zum Beispiel, indem man ein weiteres Programm schreibt, welches die Regel kodiert. Im Folgenden führen wir genau das für unsere kleine Sprache durch. Führen Sie das Beispiel aus, und korrigieren Sie alle Fehler im Programm.

def sprache(program):
    for (operation, operand) in program:
        if operation not in ("inc", "print"):
            raise RuntimeError("Invalide Operation: " + str(operation))
        if operand < 0 or operand > 5:
            raise RuntimeError("Invalider Operand: " + str(operand))
    print("Valides Programm")

programm = [
    ("inc", 10),
    ("prnt", 3)
]
sprache(programm)

Der hier gezeigte Code ist eine formale Beschreibung unserer Sprache, die gleichzeitig als Validierer arbeitet: Wirft die Funktion eine Exception, so ist das übergebene Programm nicht Teil unserer Sprache. Die Funktion sprache() könnte so wie sie hier steht auch Teil eines Übersetzers sein. Dieser wird auch zuerst prüfen, ob das übergebene Programm von den Sprachregeln abgedeckt ist, bevor das Programm in die Sprache einer anderen virtuellen oder realen Maschine übersetzt wird.

Auf den Folien finden Sie weitere Beispiele für reale bzw. virtuelle Maschinenmodelle (RISC-V und C).

\begin{frame}{Beobachtbare Zustände und Zustandsfolgen}
  \structure{Frage:} Wann ist eine Übersetzung eigentlich korrekt?\\
  \structure{Informelle Antwort:} Das erzeugte Programm soll sich "gleich" verhalten.
  \bigskip
  \pause

  \bi
  \ii Das Maschinenmodell bestimmt den beobachtbaren Zustand ($q_n$). {
    \bi
    \ii Bei RISC-V: Zustand ist der Registersatz nach jeder Instruktion.
    \ii Wir werden keine halb ausgeführten Instruktionen sehen.
    \ii Definition des beobachtbaren Zustands ist bei komplexeren Sprachen schwierig.
    \ei
  }\medskip
  \ii Programmausführung durch einen Prozessor ergibt eine Zustandsfolge: \\
  $q = (q_1, q_2, \ldots, q_n)$ {
    \bi
    \ii Die Zustände sind vom Speicher der Maschine abgeleitet.
    \ii Die Übergänge sind Folge von ausgeführten Operationen: $q_t\rightarrow q_{t+1}$.
    \ei
  }
  \ei
  \medskip
  \includegraphics[page=1]{fig/01-zustand}
\end{frame}


\begin{frame}[fragile]{Beispiel einer Zustandsfolge}
  \bi
  \ii Berechnung des größten gemeinsamen Teilers {
    \bi
    \ii Wiederholte Subtraktion {
    \begin{columns}
      \begin{column}{0.4\textwidth}
        \begin{code}[tag=Py]
          \lstinputlisting[style=py,linerange=sub0-sub1]{lst/ggt.py}
        \end{code}
      \end{column}
      \hfill
      \begin{column}{0.4\textwidth}\ttfamily
        \begin{codetext}
        (i,j) = (7, 35)
                (7, 28)
                (7, 21)
                (7, 14)
                (7, 7)
        \end{codetext}
      \end{column}
    \end{columns}
     }\pause
  \ii Wiederholtes Modulo {
    \begin{columns}
      \begin{column}{0.4\textwidth}
        \begin{code}[tag=Py]
          \lstinputlisting[style=py,linerange=mod0-mod1]{lst/ggt.py}
        \end{code}
      \end{column}
      \hfill
      \begin{column}{0.4\textwidth}
        \begin{codetext}
        (i,j) = (7, 35)
                (0, 7)
        \end{codetext}
      \end{column}
    \end{columns}
  }
  \ei }\medskip
  \ii Beide Programme berechnen das gleiche Ergebnis: $ggT(7, 35)=7$.\\
      Sie zeigen aber unterschiedliche Zustandsfolgen.
      \ei
  \medskip
  \pause
  \structure{Frage:} Darf ein Übersetzer einen Algorithmus tauschen?
\end{frame}

\begin{frame}{Korrektheit einer Übersetzung}
  \bi
  \ii Die Programmiersprache definiert die \alert{beobachtbaren} Zustände. {
    \bi
    \ii Ein- und Ausgabe ist immer beobachtbar, oft aber auch Teile des Speichers
    \ii Bei C: Nur das Schreiben von globalen Variablen, nicht aber von lokalen.
    \ei
  }\bigskip
  \ii Ein \advantage{korrekter} Übersetzer erhält alle beobachtbaren Zustände.{
    \bi
    \ii Es kann eine allerdings Abbildungsfunktion geben:\\[2ex]{
      \includegraphics[page=2,width=0.9\textwidth]{fig/01-zustand}
    }
    \ii Eine sehr absurder Übersetzer könnte alle beobachtbaren Bits invertieren.
    \ei
  }\bigskip
  \ii Grundlage optimierender Übersetzer! {
    \bi
    \ii Ein optimierender Übersetzer erhält nur den beobachtbaren Zustand.
    \ii Der nicht-beobachtbare Zustand kann sich beliebig ändern.
    \ei
  }
  \ei
\end{frame}

\begin{frame}[fragile,t]{Beispiele korrekter Übersetzung von C nach \only<1|handout:1>{C}\only<2|handout:2>{RISC-V}\only<3|handout:3>{Kobold}}
  \begin{code}[tag=C]
    \begin{C}[]
      int foo() {
        int x = 0;
        x += 1; x += 1; x += 1;
        return x;
      }
    \end{C}
  \end{code}
  \begin{center}
    \Huge$\Downarrow$
  \end{center}
  \begin{code}<1|handout:1>[tag=C]
    \begin{C}[]
      int foo() {
        return 3;
      }
    \end{C}
  \end{code}%
  \begin{code}<2|handout:2>[tag={RV32I}]
    \begin{asm}[]
      foo:
        lui a0, 3
        ret
    \end{asm}
  \end{code}%
  \begin{code}<3|handout:3>[tag={Kobold}]
    \begin{columns}
      \begin{column}{0.25\textwidth}
        \centering
        \includegraphics[height=3cm]{fig/01-cobold}
        \legalcode[commons=Kobold_artlibre_jnl.jpg]{Free Art License}{Jean-no}
      \end{column}\hfill
      \begin{column}{0.6\textwidth}
        \centering
        Dies ist ein besonders gut geschulter Kobold. Immer wenn man ihn irgendetwas fragt, wird er mit \ALERT{3} antworten.
      \end{column}
    \end{columns}
  \end{code}
\end{frame}

Wir haben gelernt, dass ein Übersetzer von der Sprache eines Maschinenmodells in die Sprache eines anderen Maschinenmodells übersetzt. Zum Beispiel übersetzt gcc von der C-Sprache in die RISC-V-Sprache. Dabei ist es zwar klassisch, dass die Richtung der Übersetzung immer von den oberen Schichten des Ebenenmodells zu den weiter unten liegenden geht, aber es ist nicht zwingend. Genauso ist es möglich, dass ein Übersetzer von RISC-V-Assembler nach C (umgekehrte Richtung) übersetzt oder von C nach JavaScript (quer zum Ebenenmodell).

Jedoch stellt sich die Frage, wann wir von einem korrekten Übersetzer bzw. einer korrekten Übersetzung eines Programms sprechen können. Es ist natürlich notwendig, dass ein Übersetzer für jedes valide Quellprogramm, die er durch seine Validierungsfunktion vorher überprüft, ein ebenfalls valides Zielprogramm erzeugt. Diese notwendige Bedingung ist allerdings ganz sicher nicht hinreichend, da ein Übersetzer, der immer dasselbe Programm ausgibt, egal mit was wir ihm füttern, ganz sicher nicht nützlich ist.

Daher müssen wir noch einmal zu unserem Maschinenmodell zurückkehren und schauen, was wir vom Übersetzer erwarten. Wir möchten, dass ein Übersetzer ein Zielprogramm erzeugt, das sich so verhält, wie das Quellprogramm es getan hätte. Im einfachsten Fall bedeutet das, dass beide Programme die gleiche Ausgabe erzeugen, wenn sie mit den gleichen Eingabedaten ausgeführt werden. Meistens stellt das Maschinenmodell aber noch weitere Regeln für eine korrekte Übersetzung auf.

Bei dieser erweiterten Definition von korrekter Übersetzung erwarten wir nicht nur, dass das Zielprogramm das gleiche Ergebnis berechnet und uns mitteilt, sondern auch, dass es dies auf die gleiche Weise tut. Das Zielprogramm soll, im Grunde, die gleichen Schritte durchführen wie das Quellprogramm, nur auf einer anderen virtuellen Maschine. Um dies formaler zu fassen, führen wir auf den Folien den Begriff des beobachtbaren Zustands ein.

Wichtig beim Begriff des beobachtbaren Zustands ist, dass es vom Maschinenmodell bestimmt wird und es nicht zwingend den gesamten Speicher der virtuellen Maschine umfassen muss. Im Grunde legt das Maschinenmodell fest, welcher Teil des Zustandes wichtig ist und als beobachtbar gilt. Zum Beispiel legt die Programmiersprache C fest, dass die Werte von globalen Variablen beobachtbar sind. Der Hintergrund dieser Entscheidung ist, dass andere Threads die geschriebenen Werte von globalen Variablen sehen, wenn die Zuweisung ausgeführt wurde und nicht erst am Ende der Funktion, oder gar noch später.

Eine andere wichtige Erkenntnis aus der Definition der korrekter Übersetzungen ist das nur der beobachtbare Zustand erhalten werden muss. Alles was die Sprache als nicht beobachtbar deklariert, kann vom Übersetzer beliebig verändert werden. Zum Beispiel entfernen C-Übersetzer lokale Variablen aus Funktionen, wenn diese niemals verwendet werden. Dies ist laut C-Standard eine legale Optimierung, da die Werte von lokalen Variablen nicht beobachtbar sind. Umso mehr ein Maschinenmodell als nicht beobachtbar deklariert, umso leichter fällt es einem optimierenden Übersetzer ein effizientes Zielprogramm zu erzeugen. Auf den Folien ist das Beispiel mit dem Kobold gezeigt, um genau dies zu verdeutlichen. Für die Funktion foo() ist es unerheblich, wie die Funktionalität implementiert ist, da nur ihre Ausgabe von uns beobachtbar ist. Wir können sie also ebenso mittels eines Kobolds implementieren anstatt mit einer Maschine aus Silizium und Strom.

Bootstrapping und Portierung

\dividerframe{Bootstrapping\\und\\Portierung}

\begin{frame}{Wer übersetzt den Übersetzer?}
  \bi
  \ii Wo läuft eigentlich der Übersetzer und wie kommen wir zu ihm? {
    \bi
    \ii Die allerersten Übersetzer von Programmen waren Menschen.
    \ii Wo sie herkommen: Evolution. Worauf sie laufen: Physik (wie der Kobold).
    \ei
  }\pause
  \ii Wir brauchen einen Übersetzer von L nach M der auf M läuft.\\[2ex] {
    \begin{center}
      \includegraphics[page=1,width=0.7\textwidth]{fig/01-t-diagram}
    \end{center}
  }
  \ei
  \bii
  \ii \Alert{Aber:} Es ist zu aufwendig einen Übersetzer in M (z.B. Assembler) zu schreiben.
  \ii Wir wollen den Übersetzer lieber in L schreiben und irgendwie nach M bringen.
  \ii Dieser Prozess heißt Bootstrapping ($=$ sich selbst aus dem Sumpf ziehen).
  \eii
\end{frame}

\begin{frame}[t]{T-Diagramme (oder Tombstone Diagramme)}
  \bi
  \ii T-Diagramme dienen zur Visualisierung des Bootstrapping Problems. \\[2ex] {
    \begin{center}
      \includegraphics[page=1,width=0.7\textwidth]{fig/01-t-diagram}
    \end{center}
  }
  \ei
  \begin{columns}
    \begin{column}{0.49\textwidth}
      \bi
      \ii Interpreter (für M auf m)\\[2ex]{
        \begin{center}
          \includegraphics[page=2,height=3cm]{fig/01-t-diagram}
        \end{center}
      }
      \ei
    \end{column}
    \begin{column}{0.49\textwidth}
      \bi
      \ii Echte Maschinen (führen m aus)\\[2ex]{
        \begin{center}
          \includegraphics[page=3,height=2cm]{fig/01-t-diagram}
          \vspace{1cm}
        \end{center}
      }
      \ei
    \end{column}
  \end{columns}

\end{frame}

\begin{frame}{1. Möglichkeit: Selbstübersetzung mittels Interpreter}
  \bi
  \ii Schreibe einen Interpreter \dn2 für L. Führe \dn1 auf \dn2 aus, um \dn[fill=badbee!40]{1} in \dn[fill=badbee!40]{1'} zu übersetzen.\\[2ex] {
    \begin{center}
      \only<1>{\includegraphics[height=4cm, page=4]{fig/01-t-diagram}}%
      \only<2>{\includegraphics[height=4cm, page=5]{fig/01-t-diagram}}
    \end{center}
  }
  \iiad (Langsame) Interpreter schreiben ist meist einfacher als Übersetzer.
  \iida Doppelter Aufwand und der Interpreter ist Wegwerfware
  \iida Verhält die \dn1 und \dn2 wirklich gleich?
  \ei
\end{frame}

\begin{frame}{2. Möglichkeit: Vereinfachter Übersetzer}
  \bi
  \ii Ableitung eines einfacheren Übersetzers \dn2 aus \dn1.\\[2ex] {
    \begin{center}
      \includegraphics[height=2cm, page=6]{fig/01-t-diagram}
    \end{center}
    \bi
    \ii Das Subset L' (von L) enthält nur die unbedingt notwendigen Sprachelemente.
    \ii Das Subset M' (von M) enthält nur einfache Maschinenbefehle.
    \ii \dn{2} darf langsam sein und langsamen Code erzeugen.
    \ei
  }
  \ii<2-> Manuelle oder semiautomatische Übersetzung von \dn{2} in \dn{3}.\\[2ex] {
    \begin{center}
      \includegraphics[height=2cm, page=7]{fig/01-t-diagram}
    \end{center}
    \bi
    \ii Teilweise mit einem existierenden Übersetzer einer anderen Sprache möglich.
    \ei
  }
  \ei
\end{frame}

\begin{frame}{2. Möglichkeit: Vereinfachter Übersetzer}
  \begin{center}
    \animation[width=0.8\textwidth]{8/1,9/2,10/3,11/4}{fig/01-t-diagram}
  \end{center}
  \begin{enumerate}
  \item Übersetze \dn{2} mit \dn{3}: \dn{2a} ist langsam und erzeugt langsamen Code.
  \item<3-> Übersetze \dn{1} zu einem langsamen, aber optimierenden, Übersetzer (1a).
  \item<4-> Übersetze \dn{1} erneut mit sich selbst (1b).
  \end{enumerate}
\end{frame}

Wir haben bereits gesehen, dass Übersetzer Programme von einer Sprache, unter Beibehaltung der beobachtbaren Zustände, in eine andere Sprache transformieren. Bisher haben wir allerdings noch nicht darüber gesprochen, auf welcher Maschine dieser Übersetzer ausgeführt werden soll und wer das Übersetzerprogramm erstellt.

Aus Anwendersicht möchten wir einen Übersetzer für unsere Programmiersprache L haben, der auf der selben Maschine M läuft, auf der wir später auch das Zielprogramm ausführen wollen. Allerdings ist es sehr aufwendig einen Übersetzer direkt in M zu schreiben, denn M hat traditionellerweise weniger nützliche Abstraktionen als L (Ebenenmodell). Einen Übersetzer in Assembler zu schreiben macht einfach keine Freude. Außerdem wäre dann unser mühsam erstellter Übersetzer spezifisch für unsere Zielplattform und wir müssten mit jeder neuen Prozessorarchitektur einen neuen Übersetzer erstellen. Daher wollen wir lieber den Übersetzer in der Sprache L schreiben.

Dies hat auch den Vorteil, dass wir, als neue Sprachentwickler, gleich die Vor- und Nachteile unserer neuen Sprache kennenlernen und vielleicht noch Anpassungen an der Sprache vornehmen. Außerdem ist ein Übersetzer ein hinreichend komplexes Softwareprojekt, um herauszufinden, ob der Übersetzer korrekt arbeitet, wenn man ihn mit sich selbst füttert. Weil man sich in diesem Prozess quasi selbst an den Haaren aus dem Sumpf zieht, heißt dieser Prozess Bootstrapping (im Englischen zieht sich Münchhausen an den Schnürsenkeln, und nicht an den Haaren, aus dem Sumpf). Außerdem gehört es quasi zum guten Ton eines Sprachentwicklers, wenn sein Übersetzer in der eigenen Sprache geschrieben ist und sich selbst übersetzen kann[fn::Wikipedia: Self-Hosting Compiler].

Prinzipiell haben wir zwei Möglichkeiten, die beide ihre Vor- und Nachteile haben. Zum einen können wir, neben dem Übersetzer für L, der in L geschrieben ist, auch einen Interpreter für L in M schreiben. Da ein Interpreter, zumindest wenn man erlaubt, dass er langsam sein darf, weniger Komplex ist als ein Übersetzer, spart man bei der Entwicklung und der Portierung auf neue Plattformen Zeit. Nachteil an dieser Variante ist, dass der Interpreter, wenn wir ihn nicht an anderer Stelle noch einmal verwenden können, Wegwerfware ist. Viel schwerwiegender ist allerdings das Problem der Konsistenz. Denn woher wissen wir, dass Interpreter und Übersetzer wirklich die gleiche Sprache implementieren oder ob sich doch in einem von beiden ein Fehler eingeschlichen hat.

Die andere Möglichkeit verwendet einen iterativen Prozess der Selbstübersetzung einer vereinfachten Variante des Übersetzers. Nachdem man den Übersetzer (L->M) in L geschrieben hat, definiert man die Untermengen L’ und M’, die gerade noch so mächtig sind, um einen vollständigen Übersetzer zu schreiben. Dies kann passieren, indem man exotische Sprachfeatures aus L weglässt bzw. die komplexeren Maschinenbefehle, die M eigentlich bietet, ignoriert.

Mit diesen Untermengen leitet man aus dem eigentlichen Übersetzer einen vereinfachten Übersetzer her, der in L’ implementiert ist und nur ineffizienten Code für M’ erzeugt. Da M’ eine Untermenge von M ist, läuft auch jedes Zielprogramm des vereinfachten Übersetzers auf unser eigentlichen Zielarchitektur. Häufig kann die Ableitung des vereinfachten Übersetzers dadurch geschehen, dass man die komplizierteren Phasen des Übersetzungsvorgangs, wie Optimierung, einfach weglässt (z.B. mit #ifdef).

In einem zweiten Schritt müssen wir diesen vereinfachten Übersetzer per Hand, oder mit Hilfe eines anderen Übersetzers, für die Maschine M’ implementieren. Und obwohl unser vereinfachter Übersetzer eigentlich L übersetzen kann, können wir bei diesem manuellen Schritt sogar noch mehr Aspekte weg lassen, sodass am Ende nur ein Übersetzer für L'->M' entsteht. Damit haben wir zum ersten Mal ein Programm, das auf der Maschine M läuft und so etwas ähnliches wie L übersetzen kann.

Im Folgenden übersetzen wir zuerst den vereinfachten Übersetzer mit seiner Implementierung. Damit bekommen wir eine volle Version des vereinfachten Übersetzers, der nun wirklich den gesamten Umfang von L versteht und verarbeiten kann. Als nächstes stecken wir den originalen Übersetzer in diesen vereinfachten Übersetzer und bekommen eine langsame Variante des originalen Übersetzers, der auf M’ läuft, aber schon Code für M erzeugt. Eine weitere Iteration der Selbstübersetzung, liefert nun endlich das gewünschte Ergebnis: einen schnellen Übersetzer, der unsere Sprache L verarbeitet und Programme für M erzeugt. Zum Schluss wiederholt man den Vorgang ein weiteres Mal und vergleicht die Binärdateien der beiden letzten Übersetzer. Wenn alles geklappt hat, sind beide Dateien bis aufs letzte Bit gleich, was weiteres Vertrauen in die Übersetzungsleistung des entwickelten Übersetzers bringt[fn::Ein interessantes Beispiel eines absichtlichen Fehlers beim Bootstrapping ist das klassische Paper von Ken Thompson, einem der Erfinder von C, Reflections on trusting trust. Dort hat Thompson einen Übersetzer geschrieben, der eine Hintertür beim Übersetzungsvorgang einbaut, wenn der Übersetzer selbst übersetzt wird.].

\begin{frame}{Portierung auf neue Plattform und Cross-Compiler}
  \begin{center}
    \animation[width=0.7\textwidth]{12/1,13/2,14/3-}{fig/01-t-diagram}
  \end{center}
  \bi
  \ii Ähnliches Problem, wenn man auf eine neue Plattform N wechselt. {
    \bi
    \ii<2-> Mit der vorhandenen Werkzeugkette: Erzeuge den \alert{Cross-Compiler} \dn{Z'}.
    \ii<3-> Übersetze \dn{Z} mit seinem Cross-Compiler zu \dn{Z''}.
    \ei
  }
  \ii<4> Zunehmend kein Problem mehr, da viele Übersetzer Multitarget bieten. {
    \bi
    \ii Das Übersetzerbackend  bietet, über Optionen, sowohl M als auch N an.
    \ii LLVM: \texttt{llc -version} \hfill(\texttt{llc} ist das Backend von LLVM)
    \ei
  }
  \ei
\end{frame}

Ein ähnliches Problem wie beim Bootstrappen tritt bei der Portierung eines Übersetzers auf eine neue Hardwarearchitektur auf. Allerdings ist hier der Vorgang deutlich vereinfacht, da wir bereits einen Übersetzer für L haben, der auf der alten Hardware läuft. Wir erweitern unseren Übersetzer dahingehend, dass er die neue Architektur N als Ausgabeformat unterstützt und übersetzen ihn für M. Eine zweite Iteration der Selbstübersetzung, liefert nun einen Übersetzer der auf N läuft und Code für N erzeugt.

Früher war die Portierung von Übersetzern ein größeres Problem, da ein Übersetzerprogramm meist nur ein einziges Ausgabeformat unterstützt hat. Also entweder konnte er Code für M erzeugen oder für N. Ein Beispiel für solch einen Übersetzer ist gcc; dort benötigt man für jede Zielplattform ein eigenes Übersetzerbinary. Modernere Übersetzer sind Multi-Targetfähig und sind von Anfang an darauf vorbereitet, Code für unterschiedliche Architekturen zu erzeugen (siehe LLVM-Grafik weiter oben).

Zusammenfassung

\begin{frame}{Zusammenfassung}
  \bi
  \ii \structure{Virtuelle Maschinen} führen Programme aus, haben Speicher und Befehle{%
    \bi
    \ii Ihre Maschinensprache umfasst alle valide Programme.
    \ii Korrekter Übersetzer erhält die Sprachsemantik und beobachtbare Zustände.
    \ei
  }\bigskip
  \ii \structure{Ebenenmodell}: Schrittweise Abstraktion von der echten Hardware {
    \bi
    \ii Obere Schichten bieten ausdrucksstärkere Sprachen.
    \ii Untere Schichten sind direkt implementierbar.
    \ii Übergang zu den unteren Schichten durch Übersetzung (oder Interpretation)
    \ei
  }\bigskip
  \ii \structure{Bootstrapping}: Der erste Übersetzer übersetzt sich selbst. {
    \bi
    \ii Reduktion auf manuelle Übersetzung eines abgespeckten Übersetzers
    \ii Bei der Portierung auf neue Plattform braucht es einen Cross-Compiler
    \ei
  }
  \ei
\end{frame}

\begin{frame}{Quellenverzeichnis}
  \nocite{scott:15:book}
  \nocite{aho:07}
  \printbibliography
\end{frame}