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:
- Re-Implementierung des Cross-Compilers für Ninja-2 in Ninja-2
- Realisierung von Modulen mit getrennter Übersetzung
- Spezifikation und Implementierung von erweiterbaren Records
- Re-Targeting des Compilers für RISC5 anstelle der Ninja-VM
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
- Wir haben ein GitLab-Projekt für unseren Kurs:
"Compiler-Bootstrap".
- Es gibt auf connect.thm.de einen Raum für uns:
"Compiler-Bootstrap".
Einladungen zu beiden Einrichtungen gibt's zu Beginn des Kurses.
Wie fangen wir an?
Ich plane, zu Beginn des Kurses folgende Themen zu besprechen:
- Konzepte und Konstrukte der Quellsprache Ninja-2
- Implementierungssprache des Cross-Compilers?
- Organisation des Cross-Compilers
- Zielsprache und Toolchain
- Beispiel einer Spracherweiterung: bedingte Ausdrücke
- Organisation des Native-Compilers?
- Wie bitte, kein Flex und kein Bison verfügbar?
- Vorläufige Festlegung der Ziele und Aufgaben
- Voraussichtliche Teilnehmer?
- Wer möchte an welchen Thema arbeiten?
Ressourcen