RustAst/docs/Optimizing.md

Optimierung: Closure-Cracking und Upvalue-Inlining

• Datum: 21.02.2026
• Status: Entwurf / Motivation

1. Motivation

Die aktuelle Monomorphisierung (Specializer) ist auf zustandslose Funktionen (Funktionen ohne Upvalues) beschränkt. Sobald eine Funktion Variablen aus ihrem äußeren Scope einfängt (Closures), wird sie für den Specializer zur "Blackbox". Dies verhindert die Optimierung von Higher-Order Functions (HOFs) und Currying, was in einer funktional orientierten DSL essenziell für die Performance ist.

2. Die Garantie

Zwei Faktoren in MyC erlauben eine aggressive Optimierung von Closures, die in anderen Sprachen (wie JavaScript oder Python) aufgrund von Mutabilität schwierig ist:

1. Immutability von Globals: Nach der Bootstrap-Phase sind Address::Global-Werte unveränderlich.
2. Partial Evaluation: Der Specializer nutzt die VM, um konstante Teilausdrücke bereits zur Compile-Zeit zu evaluieren. Das Ergebnis sind oft Constant(Value::Object(Closure))-Knoten.

3. Das Konzept

3.1 Closure-Cracking

Wenn der Specializer einen Funktionsaufruf sieht, dessen Callee eine Constant(Closure) ist (z. B. das Ergebnis einer Partial Application), kann er die Closure "knacken":

1. Extraktion: Der AST-Body der Closure und das dazugehörige upvalues-Array (die konkreten Daten) werden extrahiert.
2. Substitution: Jeder Zugriff auf einen Upvalue (Get(UpValue(i))) im AST-Body wird durch einen Constant(Value)-Knoten mit dem echten Wert aus dem upvalues-Array ersetzt.
3. Rekursive Spezialisierung: Der nun "flache" (upvalue-freie) AST wird erneut durch den Specializer geschickt.

3.2 Upvalue-Inlining (Global-Propagation)

Wenn eine Closure Upvalues besitzt, die auf Address::Global verweisen, können diese ebenfalls inlined werden:

• Da Globals unveränderlich sind, kann der Specializer den Wert des Globals zum Zeitpunkt der Spezialisierung aus dem Environment lesen und direkt als Constant in den AST einbauen.
• Dies eliminiert den Indirektions-Overhead über das Upvalue-Array und den Global-Lookup zur Laufzeit.

4. Beispiel-Analyse

Betrachte den Ausdruck: (((fn [x] (fn [] x)) 5))

1. Innerer Call: ((fn [x] (fn [] x)) 5)

   • Der Specializer erkennt das Lambda und das Argument 5.
   • Die VM evaluiert dies zu einer Closure-Instanz mit upvalues: [Value::Int(5)].
   • Der Knoten wird zu Constant(Value::Object(Closure)).

2. Äußerer Call: ( <Constant(Closure)> )

   • Ohne Optimierung: Dynamischer Dispatch der Closure zur Laufzeit.
   • Mit Closure-Cracking:
     • Der Specializer sieht die Constant(Closure).
     • Er extrahiert den Body (Get x (UpValue 0)).
     • Er ersetzt Get x durch Constant(5).
     • Der gesamte Call wird zu Constant(5) reduziert.

5. Vorteile

• Zero-Cost Abstractions: HOFs und Currying haben keinen Laufzeit-Overhead mehr, wenn die Argumente statisch auflösbar sind.
• Flattening: Komplexe, verschachtelte Funktionshierarchien kollabieren zu flachen, effizienten Operationen.
• JIT-Vorbereitung: Ein upvalue-freier, spezialisierter AST ist die ideale Eingabe für einen späteren LLVM- oder Cranelift-Backend.

6. Implementation-Plan

1. specializer.rs: Erweiterung der specialize_call_logic, um neben BoundKind::Get auch BoundKind::Constant (mit Typ-Check auf Closure) als Callee zu akzeptieren.
2. environment.rs: Der compiler-Closure innerhalb von specialize_node muss Zugriff auf das upvalues-Array der aktuellen Closure-Instanz erhalten, um die Substitution durchzuführen.
3. Substitution-Visitor: Implementierung eines einfachen AST-Transformers, der Get(UpValue(i)) gegen Constant(values[i]) austauscht.