Compilerbau: Spracherweiterungen und Bootstrapping WS 23/24

Überblick

In diesem Kurs wollen wir die (möglicherweise aus KSP bekannte) kleine Programmiersprache Ninja "self-hosting" machen. Das bedeutet, dass der Compiler für Ninja in Ninja selbst geschrieben wird und sich dann selber übersetzen kann. Das dabei offensichtlich bestehende Henne-Ei-Problem (wie können wir das erste Mal überhaupt ein Ninja-Programm übersetzen?) ist bereits gelöst: es gibt einen Cross-Compiler, der ja in KSP die ganze Zeit benutzt wird. Den kann man einsetzen, um den in Ninja geschriebenen Ninja-Compiler das erste Mal zu übersetzen. Nachfolgende Übersetzungen, auch nach Spracherweiterungen, können dann mit dem in Ninja geschriebenen Compiler ausgeführt werden ("Compiler-Bootstrap").

Leider ist der Sprachumfang unserer Programmiersprache wirklich recht klein. Die Liste der wünschenswerten Erweiterungen umfasst sowohl eher einfache Dinge (z.B. Dateizugriffe, mehr Operatoren, bedingte Ausdrücke, Funktionspointer), als auch tiefergehende Änderungen (z.B. Module, variante bzw. erweiterbare Records, Klassen und Methoden).

Ich habe bereits eine Reihe einfacher Erweiterungen definiert und im Cross-Compiler realisiert. Die für das Erreichen unseres Ziels unbedingt notwendigen komplizierteren Erweiterungen müssen wir im Kurs diskutieren und implementieren. Auch ich weiß nicht genau, was wir alles brauchen werden und wie wir das in die bestehende Software integrieren können. Lassen Sie uns das herausfinden!

Damit komme ich zur Organisation des Kurses und den Anforderungen an die Teilnehmerinnen und Teilnehmer: wir werden (in Gruppen) zusammen an unserem gemeinsamen Ziel arbeiten müssen, damit wir in der kurzen Zeit eines Semesters etwas Substantielles auf die Beine stellen können. Gefragt sind deshalb solide Vorkenntnisse im Compilerbau und systemnaher Programmierung sowie engagierte Mitarbeit an einem nicht-trivialen Projekt. Im Gegenzug gibt's eine Menge interessanter Erkenntnisse und - so hoffe ich zumindest - viel Spaß.

Umfeld

Die Aufgabenstellung unseres Kurses ist eingebettet in ein etwas umfangreicheres Vorhaben, das ich kurz schildern möchte. Der bekannte Informatiker Niklaus Wirth hat (zusammen mit Kollegen) in den späten 80er-Jahren die Sprache Oberon entwickelt und sie dazu benutzt, ein kleines Betriebssystem für Mikrocomputer zu schreiben ("Project Oberon"). Die letzte Version der Sprache (Oberon-07) stammt aus dem Jahr 2016. Er hat dann auch ein einfaches RISC-Prozessorsystem für FPGAs entwickelt (RISC5 - bitte nicht verwechseln mit RISC-V), das in der Lage ist, mit minimalen Ressourcen das Oberon-System auszuführen. Die letzten Änderungen am Gesamtsystem stammen aus dem Jahr 2018; das System ist im industriellen Einsatz.

Wenn man aus heutiger Sicht das "Project Oberon" anschaut, scheinen manche Designentscheidungen reif für eine Neubewertung zu sein. Das bezieht sich auf die Sprache (dort sind es allerdings hauptsächlich kosmetische Dinge, Beispiele: Schlüsselworte in Großbuchstaben, umständliche Formulierungen bei Typvereinbarungen), als auch auf das Betriebssystem (Beispiel: keine hierarchischen Dateiverzeichnisse). Wichtig wäre auch eine Modernisierung des RISC5-Prozessors, besonders im Hinblick auf eine vernünftige Speicherankopplung mittels Caches.

Ein möglicher Startpunkt für eine grundlegend erneuerte Version des Oberon-Systems ist sicherlich die Spezifikation und Implementierung der Sprache, in der es geschrieben wird. Unser Kurs untersucht die Eignung einer erweiterten Version von Ninja für diesen Zweck ("Ninja-2"). Exemplarisch dient der Compiler selber als ein erstes Ziel für die Anwendung der neuen Sprache.

Aufgaben und Arbeitsgruppen

Hier ist eine grobe (und vielleicht unvollständige) Liste von Teilaufgaben: Der erste Punkt auf der Liste ist das eigentliche Kursziel. Das lässt sich seinerseits in Teilaufgaben zerlegen, die Sie aus dem Compilerbau kennen: lexikalische Analyse, syntaktische Analyse, AST, Symboltabelle, semantische Analyse, Codeerzeugung). Damit dieser Teil handhabbar wird, ist eine Sprachunterstützung von Modulen mit getrennter Übersetzung praktisch unabdingbar. Das hat Auswirkungen auf das Frontend des Compilers: Anpassen der syntaktischen und der semantischen Analyse, dazu Übermittlung von Typinformation über Modulgrenzen hinweg. Aber auch das Backend und die Toolchain sind betroffen, denn die getrennt übersetzten Module müssen vor dem Laden und Ausführen gebunden werden.

Die erweiterbaren Records würden helfen, die Abstrakte Syntax zu vereinfachen (und stellen zusammen mit den Funktionspointern eine Art "Klassen für Arme" dar), sind aber nicht unbedingt notwendig.

Das Re-Targeting für RISC5 sollten wir nur bei ausreichend guter personeller Besetzung des Kurses in Angriff nehmen.

Infrastruktur

Einladungen zu beiden Einrichtungen gibt's zu Beginn des Kurses.

Wie fangen wir an?

Ich plane, zu Beginn des Kurses folgende Themen zu besprechen:

Ressourcen