Compiling with Consumers
Marius Müller · 2026
In unserer hochgradig digitalisierten Welt sind Computerprogramme allgegenwärtig. Es gibt eine Vielzahl von Hochsprachen mit komplexen Sprachmerkmalen, die das strukturierte Schreiben von Code erleichtern. Letztlich muss dieser Code jedoch auf realer Hardware ausgeführt werden, die weitaus weniger strukturiert ist und komplexe hochsprachliche Merkmale nicht direkt ausdrücken kann. Ein Programm aus einer Ausgangssprache, in der Programmierer ihre Programme schreiben, in Befehle zu kompilieren, die eine reale Maschine versteht, ist daher eine komplexe Aufgabe. Ein Compiler sollte nicht nur Maschinencode erzeugen, der das beabsichtigte Verhalten des Programms korrekt umsetzt, sondern der erzeugte Code sollte auch effizient ausgeführt werden. Diese anspruchsvolle Aufgabe wird durch den Einsatz einer Zwischenrepräsentation im Compiler ermöglicht, die die Lücke zwischen hochsprachlichen Annehmlichkeiten und maschinennahen Anforderungen überbrückt. Moderne funktionale Programmiersprachen zeichnen sich oft durch ein besonders hohes Abstraktionsniveau aus. Dies ermöglicht es Programmierern zwar häufig Programme auf eine prägnante und elegante Weise auszudrücken, macht jedoch zugleich die Kompilierung solcher Sprachen besonders herausfordernd. Erschwerend kommt hinzu, dass moderne Programme oft kontinuierlich mit externen Komponenten interagieren, was asynchron erfolgen muss, um die Ausführung nicht zu blockieren, während auf das Ergebnis der externen Komponente gewartet wird. Asynchrone Kommunikation erfordert die Fähigkeit, nicht-lokale Kontrollflüsse auszudrücken. Compiler gehen damit typischerweise auf zwei Arten um: Entweder sie fügen dem Laufzeitsystem Unterstützung für eine Art von Kontrolloperator hinzu, oder sie wenden eine Übersetzung an, die nicht-lokale Kontrolleffekte durch andere Konstrukte ausdrückt, die in der Zwischenrepräsentation des Compilers bereits vorhanden sind. Eine Möglichkeit, nicht-lokalen Kontrollfluss auszudrücken, ist die Verwendung einer Zwischenrepräsentation mit expliziten Konsumenten (consumers). Ein gut untersuchtes Beispiel hierfür sind Zwischenrepräsentationen im Continuation-Passing Style (CPS). Im Continuation-Passing Style ist die Continuation, d.h. der Rest der Berechnung, explizit als Term in der Sprache vorhanden. Sprachen im Continuation-Passing Style sind seit langem als Option für Zwischenrepräsentationen in Compilern etabliert. Eine andere, bisher deutlich weniger beachtete Möglichkeit sind Sprachen, die auf dem Sequenzenkalkül basieren. Der Sequenzenkalkül ist das Gegenstück zum natürlichen Schließen, bekannt aus der Logik. Während das natürliche Schließen durch seine Entsprechung mit dem Lambda-Kalkül via des Curry-Howard-Isomorphismus seit langem als Grundlage funktionaler Programmiersprachen dient, wurde erst vergleichsweise kürzlich ein zufriedenstellendes Termzuweisungssystem für den klassischen Sequenzenkalkül gefunden. Im Gegensatz zum natürlichen Schließen und dem Lambda-Kalkül, die auf Beweise, welche zu Produzenten (producers) korrespondieren, ausgerichtet sind, behandeln der klassische Sequenzenkalkül und darauf basierende Sprachen Beweise und Widerlegungen, welche zu Konsumenten korrespondieren, auf symmetrische Weise. Dies macht solche Sprachen zu einer interessanten Alternative zum Continuation-Passing Style für Zwischenrepräsentationen. In dieser Dissertation untersuchen wir zwei verschiedene Möglichkeiten, wie explizite Konsumenten bei der Kompilierung funktionaler Programmiersprachen eingesetzt werden können. Zunächst betrachten wir Zwischenrepräsentationen im Continuation-Passing Style sowie Übersetzungen in diese. Eine naheliegende Frage in diesem Zusammenhang ist, ob es möglich ist, Programme aus dem Continuation-Passing Style wieder zurück in den Direktstil (direct style) zu übersetzen, in dem Programme üblicherweise geschrieben werden. Dies ist nicht nur theoretisch von Interesse, sondern hat auch praktische Relevanz. Zwar bringt der Continuation-Passing Style viele Vorteile für Zwischenrepräsentationen mit sich, jedoch auch einige Nachteile im Vergleich zum Direktstil. Insbesondere stellen viele Plattformen einen Aufrufstapel (call stack) bereit, der von Programmen im Continuation-Passing Style nicht genutzt wird. Eine geeignete Rückübersetzung in den Direktstil könnte es einem Compiler ermöglichen, die Vorteile beider Stile zu nutzen. Im ersten Teil dieser Arbeit stellen wir daher das Design einer Rückübersetzung in den Direktstil vor, die viele Eigenschaften besitzt, die im Compiler-Kontext wichtig sind, und legen damit die Grundlage für eine praktische Anwendbarkeit einer solchen Übersetzung. Im zweiten Teil dieser Arbeit gehen wir in die andere Richtung: Wir kompilieren bis hinunter zu Maschinencode. Dabei verwenden wir jedoch nicht den Continuation-Passing Style, sondern untersuchen Zwischenrepräsentationen auf Basis des klassischen Sequenzenkalküls. Wir präsentieren eine vollständige Kompilationskette, beginnend mit einer funktionalen Ausgangssprache mit interessanten Eigenschaften, bis hin zur Erzeugung von Maschinencode, der auf einem realen Computer ausgeführt werden kann. Wir identifizieren eine Normalform unserer sequenzenkalkülbasierten Zwischenrepräsentation, die sich für eine überraschend direkte Möglichkeit der Codegenerierung eignet. Die symmetrische Struktur von Sprachen, die auf dem klassischen Sequenzenkalkül basieren, macht sie, auch im Hinblick auf Optimierungen, zu einem vielversprechenden Ziel, und unsere Kompilationskette bildet die Grundlage für zukünftige Untersuchungen.