Begriff
Partial Evaluation
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.
Du hast eine Funktion mit 2 Argumenten: pow(x, n).
Du rufst sie oft mit n=2 auf (Quadrieren).
Der Computer rechnet jedes Mal: "Loop von 1 bis n...".
Partial Evaluation sagt: "Ich kenne n schon vorher! Ich führe den Teil des Codes aus, der nur von n abhängt."
Aus pow(x, 2) generiert er eine neue Funktion pow2(x) = x * x.
Loops verschwinden. if(true) verschwindet.
Übrig bleibt hochoptimierter Code ("Residual Program").
Es ist ein "Pre-Compiler".
Merksatz: Eine Optimierungstechnik, bei der ein Computerprogramm unter Verwendung einiger bekannter Eingabewerte spezialisiert wird, indem statische Berechnungen vorab ausgeführt werden, um ein effizienteres Restprogramm zu erzeugen.
In GraalVM (Oracle). GraalVM nutzt Partial Evaluation, um Interpreter schnell zu machen. Du schreibst einen langsamen Interpreter (AST Walker) für Python. Graal nimmt "Dein Python-Script" (fester Input) + "Interpreter". Es "partiell evaluiert" den Interpreter gegen das Script. Ergebnis: Maschinencode, so schnell wie C. (Erste Futamura-Projektion).
1. Futamura Projections
Das Heiligtum der Metaprogrammierung.
PE(Interpreter, Code) -> Executable. (Compiler).PE(PE, Interpreter) -> Compiler. (Wir generieren einen Compiler aus dem Interpreter!).PE(PE, PE) -> Compiler-Compiler. (Generator für Compiler-Generatoren). Das funktioniert wirklich.
2. Binding-Time Analysis (BTA)
Der harte Teil. Der PE muss wissen: Welche Variablen sind "Statisch" (bekannt) und welche "Dynamisch" (unbekannt)? Wenn er sich irrt, läuft der Compiler ewig (versucht, eine Endlosschleife zur Compile-Zeit auszurollen).
1. Polyvariant Specialization
Was passiert, wenn eine Funktion mit verschiedenen statischen Werten aufgerufen wird?
Ein naiver PE würde nur eine Version bauen. Ein polyvarianter PE erkennt: "Oh, f(x, 1) und f(x, 2) brauchen unterschiedliche Optimierungen."
Er generiert für jede Wertekombination eine eigene spezialisierte Version. In der Produktion (z.B. bei der Optimierung von Datenbank-Abfragen) führt dies zu einem "Explosion"-Problem der Code-Größe (Code Bloat). Experten nutzen Heuristiken, um zu entscheiden, wann die Spezialisierung einen echten Performance-Gewinn bringt und wann sie nur den Instruction-Cache verstopft.
2. Online vs. Offline Partial Evaluation
Wie entscheidet man, was statisch ist?
- Offline PE: Es gibt eine separate Phase (Binding Time Analysis - BTA). Das Programm wird markiert (Static/Dynamic). Der Spezialisierer führt dann stur alles Statische aus. Das ist sicher und gut für klassische Compiler.
- Online PE: Der Spezialisierer entscheidet während der Auswertung: "Hey, dieser Wert ist gerade bekannt, also berechne ich ihn." Das ist mächtiger (findet mehr Optimierungen), ist aber viel schwerer zur Terminierung zu zwingen. GraalVM nutzt eine hochoptimierte Form der Hybrid-Evaluation.
3. Termination: Das "Partial" Problem
Ein Partial Evaluator kann sich in einer Endlosschleife verfangen, wenn er versucht, eine rekursive Funktion unendlich weit auszurollen.
Beispiel: f(n) = f(n+1). Wenn n statisch ist, versucht der PE ewig zu rechnen.
In der Forschung nutzt man Quasi-Termination-Analysen. Man sucht nach Mustern, bei denen der statische Teil "kleiner" wird (Well-founded ordering). Wenn der PE merkt, dass er eine Struktur zum zweiten Mal mit den gleichen (oder größeren) statischen Werten sieht, bricht er ab und erzeugt einen rekursiven Aufruf im Restprogramm (Fold).
Quick-Check
Unterschied zu Constant Folding?
Constant Folding optimiert3+4zu7. Partial Evaluation optimiert Kontrollfluss. Es rollt Loops aus, inlinet Funktionen, entfernt ganze Subsysteme.C++ Templates?
Ja, C++ Templates sind eine primitive Form von Partial Evaluation. Du spezialisierst Code zur Compile-Zeit.Warum "Partial"?
Weil wir nur einen Teil der Inputs haben. Hätten wir alle, wäre es einfach normale "Evaluation" (Ausführen).