Begriff

Supercompilation

Computer Science Compiler S4

2 Quellen 0 Lernpfade 0 Backlinks enriched

Warum wichtig?

Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.

Partial Evaluation spezialisiert Code. Supercompilation geht noch weiter. Sie betrachtet den Programmablauf als Baum aller möglichen Zustände. Sie analysiert diesen Baum (Process Tree). Sie erkennt Schleifen und Muster ("Dieser Ast ist das gleiche wie der Start, nur mit x+1"). Sie "faltet" den Baum zusammen zu einem neuen, perfekten Graphen. Dabei verschwinden unnötige Variablen, Zwischenstrukturen und Funktionsaufrufe komplett. Das Ergebnis ist oft schneller, als ein Mensch es je schreiben könnte.

Merksatz: Eine umfassende Programmtransformationstechnik, die Programme durch Beobachtung ihres Verhaltens (Driving) und Restrukturierung (Folding) optimiert, oft mächtiger als partielle Auswertung.

Es ist der "Heilige Gral" der funktionalen Optimierung. Der GHC (Haskell Compiler) macht "Fusion" (Deforestation), was eine Light-Version von Supercompilation ist. map f . map g . filter p wird zu einer Schleife. Volle Supercompilation ist noch Forschung (Supero, Bolero), weil sie manchmal den Code explodieren lässt (Code Bloat).

1. Process Tree Construction

Das Herz der Supercompilation ist der Process Tree. Jeder Knoten im Baum ist ein Paar aus Expression und Umgebung. Der Supercompiler versucht, den Baum durch Driving zu expandieren. Wenn er eine Funktion aufruft, "drückt" er (Driving) die Auswertung so weit wie möglich in die Tiefe. Das Problem: Der Baum könnte unendlich tief werden (Rekursion). Hier kommt das Folding ins Spiel: Der Compiler prüft bei jedem Schritt: "Habe ich diesen Zustand schon mal gesehen (Homeomorphic Embedding)?" Wenn ja, wird der Pfad zu einem Loop geschlossen.

2. Positive vs. Negative Information Propagation

Positive Supercompilation: Der Compiler merkt sich: "Hier ist x = 5". Er nutzt das Wissen für alle Sub-Aufrufe.
Negative Information Propagation: Das ist die Stärke gegenüber Partial Evaluation. Wenn der Compiler in einem if (x == null) Zweig ist, weiß er im else Teil: "x ist DEFINITIV NICHT null". Er kann also alle Null-Prüfungen in der gesamten Folge-Historie dieses Zweiges löschen. Das führt zu massivem "Code Cleanup", besonders bei Parsern und Datenbank-Engines.

3. Turchin's Metasystem Transition

Valentin Turchin sah Supercompilation als Teil einer größeren Philosophie: Der Metasystem-Übergang. Ein System lernt, sich selbst zu beobachten und zu steuern. Supercompilation ist Metacomputation: Eine Berechnung, die eine andere Berechnung zum Frühstück isst. In der Sowjetunion wurde dies genutzt, um mathematische Beweise und Programmoptimierung als ein und dasselbe Ding zu behandeln. Heute sehen wir Ansätze davon im JIT-Compiling (wie PyPy), wo Statistiken über die Ausführung genutzt werden, um den Code "on-the-fly" zu supercompilieren.

Quick-Check

Unterschied zu Partial Evaluation?
PE spezialisiert auf Daten (static vs dynamic). Supercompilation spezialisiert auf Struktur (History). Supercompilation kann Dinge optimieren, wo alle Inputs unbekannt sind (z. B. append(append(x, y), z) -> append3(x, y, z) ohne Listen-Traversierung).
Schwierigkeit?
Termination. Zu wissen, wann man aufhören muss zu "driven".
Name?
Supervised Compilation. Der Compiler überwacht die Ausführung.