Partielle Evaluierung: Wie ein Interpreter zum Compiler wird

The Magic of Partial Evaluation

Jimmy Miller zeigt, wie partielle Evaluierung aus einem Interpreter automatisch kompilierten Code macht. Am Beispiel eines Brainfuck-Interpreters führt er vor, wie sich Programme zu spezialisierten Funktionen reduzieren lassen – das ist die erste Futamura-Projektion. Auch wenn das Konzept oft als praxisfern gilt, kann es etwa bei Schema-Validierungen den Code erheblich beschleunigen. Miller veröffentlicht dazu eine eigene Bibliothek, nicht als Produkt, sondern als Spielwiese für eine der schönsten Ideen der Programmiersprachenwelt.

Was wir hier entdeckt haben, ist die erste von drei sogenannten Futamura-Projektionen.
  1. TuringTest

    > Für mich sind die schönsten Stücke Software diejenigen, die etwas über die Natur von Programmiersprachen offenbaren.

    Es gibt drei Momente, die den funktionalen Programmierer dazu bringen, sein Verständnis davon weiterzuentwickeln, wie eine Programmiersprache wirklich funktioniert – als symbolische Repräsentation menschlichen Denkens, jenseits der in der Schule gelehrten Metapher eines Computerprogramms als einer Mühle, die Eingabedaten zermahlt und Ergebnisse produziert.

    Der erste ist, wenn man Rekursion wirklich versteht und wie eine Funktion in Bezug auf sich selbst definiert werden kann (mit variierenden Parametern für jeden Aufruf).

    Der zweite ist, wenn man Prolog-Variablenunifikation oder Haskells Lazy Evaluation entdeckt und wie man unendliche Datenstrukturen darstellen kann, ohne dass das Programm in einer Endlosschleife hängt.

    Der dritte ist, wenn man lernt, dass das Verhalten jeder imperativen Sprache (bis hinunter zur Funktionsweise der Datenpfade eines Mikroprozessors) vollständig in einer rein funktionalen Rewrite-Sprache dargestellt werden kann (ohne destruktive Zuweisung / Zustandsänderungen von Zellen).

    Diese Einsichten lassen einen erkennen, dass alle Programmierparadigmen die Natur der Symbolverarbeitung gemeinsam haben und es keine „wahre Beschreibung“ der Laufzeitausführung eines Programms gibt – die imperative, funktionale und logische Sicht auf das laufende Programm sind alles äquivalente Darstellungen.

  2. artrax

    Wir bauen das als C++-Bibliothek, um Query-Compilation für unsere Stream-Processing-Engine durchzuführen.

    https://github.com/nebulastream/nautilus

    Dadurch können wir Operatoren oder Funktionen implementieren, ohne sie in Form einer LLVM-IR-DSL (oder ähnlichem) schreiben zu müssen. Stattdessen schreibt man seine Funktionen über einen Wrapper-Typ (und gibt einen zurück), für den es eine Überladung von allem gibt, was man in C++ überladen kann.

    Man kann einen Wrapper aus einem C++-Wert instanziieren, wobei der Wrapper dann einfach alles an diesen Wert weiterleitet, was sich in der präagentischen Ära als nützlich fürs Debugging erwies.

    Man kann einen solchen Wrapper aber auch als Tracer instanziieren, und das Ergebnis der Funktionsauswertung wird ein Trace sein.

    Für Kontrollfluss zeichnen wir auf, wann immer ein Wrapper-Typ als bool ausgewertet wird, geben zuerst true zurück, und wenn wir das Ende eines Zweigs erreichen, werfen wir eine Exception, um zum Anfang zurückzukehren und alles noch einmal zu starten, aber diesmal mit der Auswertung zu false.

    Den resultierenden Trace können wir in LLVM IR umwandeln und kompilieren oder zum Beispiel in wasm ausführen

  3. apignotti

    Wir haben ein ähnliches Konzept vor einigen Jahren in unserem C++-zu-JavaScript/WebAssembly-Compiler (Cheerp) implementiert. Es war eine schöne Herausforderung.

    https://labs.leaningtech.com/blog/reducing-webassembly-size-...

Mehr von diesem Tag

2026-11-18