Wie werden Generika in einem modernen Compiler implementiert?

Ich meine hier, wie gehen wir von einer Vorlage T add(T a, T b) ...in den generierten Code? Ich habe mir ein paar Möglichkeiten überlegt, um dies zu erreichen. Wir speichern die generische Funktion in einem AST, Function_Nodeund jedes Mal, wenn wir ihn verwenden, speichern wir im ursprünglichen Funktionsknoten eine Kopie von sich selbst, wobei alle Typen Tdurch die Typen ersetzt werden, die es gibt verwendet werden. Zum Beispiel add<int>(5, 6)wird für eine Kopie der generischen Funktion speichern addund alle Arten ersetzen T in der Kopie mit int.

Also würde es ungefähr so ​​aussehen:

struct Function_Node {
    std::string name; // etc.
    Type return_type;
    std::vector<std::pair<Type, std::string>> arguments;
    std::vector<Function_Node> copies;
};

Dann könnten Sie Code für diese generieren, und wenn Sie ein Function_NodeVerzeichnis der Kopien besuchen copies.size() > 0, rufen Sie visitFunctionalle Kopien auf.

visitFunction(Function_Node& node) {
    if (node.copies.size() > 0) {
        for (auto& node : nodes.copies) {
            visitFunction(node);
        }
        // it's a generic function so we don't want
        // to emit code for this.
        return;
    }
}

Würde das gut gehen? Wie gehen moderne Compiler mit diesem Problem um? Ich denke, eine andere Möglichkeit wäre, die Kopien in den AST zu injizieren, so dass er alle semantischen Phasen durchläuft. Ich dachte auch, dass Sie sie vielleicht in einer unmittelbaren Form erzeugen könnten, wie zum Beispiel Rusts MIR oder Swifts SIL.

Mein Code ist in Java geschrieben, die Beispiele hier sind C ++, weil es für Beispiele etwas weniger ausführlich ist - aber das Prinzip ist im Grunde dasselbe. Es kann jedoch einige Fehler geben, da diese nur von Hand in das Fragenfeld geschrieben wurden.

Beachten Sie, dass ich modernen Compiler meine, wie man dieses Problem am besten angeht. Und wenn ich Generika sage, dann meine ich das nicht mit Java-Generika, bei denen Typlöschung verwendet wird.

Wie werden Generika in einem modernen Compiler implementiert?

Ich lade Sie ein, den Quellcode eines modernen Compilers zu lesen, wenn Sie wissen möchten, wie ein moderner Compiler funktioniert. Ich würde mit dem Roslyn-Projekt beginnen, das C # - und Visual Basic-Compiler implementiert.

Insbesondere mache ich Sie auf den Code im C # -Compiler aufmerksam, der Typensymbole implementiert:

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Symbols

und vielleicht möchten Sie auch den Code für die Konvertierbarkeitsregeln ansehen. Es gibt viel, was mit der algebraischen Manipulation von generischen Typen zu tun hat.

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Binder/Semantics/Conversions

Ich habe mich sehr bemüht, letzteres leicht lesbar zu machen.

Ich habe mir ein paar Möglichkeiten überlegt, um dies zu erreichen. Wir speichern die generische Funktion in einem AST als Function_Node und speichern dann jedes Mal, wenn wir sie verwenden, im ursprünglichen Funktionsknoten eine Kopie von sich selbst, wobei alle Typen T durch die Typen ersetzt werden die verwendet werden.

Sie beschreiben Vorlagen , keine Generika . C # und Visual Basic haben aktuelle Generika in ihren Typsystemen.

Kurz, sie arbeiten so.

• Wir beginnen damit, Regeln für das aufzustellen, was zur Kompilierungszeit formal einen Typ ausmacht. Beispiel: intist ein Typ, ein Typparameter Tist ein Typ, für jeden Typ Xist der Array-Typ X[]auch ein Typ und so weiter.

• Die Regeln für Generika beinhalten Substitution. Zum Beispiel class C with one type parameterist kein Typ. Es ist ein Muster zum Erstellen von Typen. class C with one type parameter called T, under substitution with int for T ist ein Typ.

• Regeln, die die Beziehungen zwischen Typen beschreiben - Kompatibilität bei Zuweisung, Bestimmung des Typs eines Ausdrucks usw. - werden im Compiler entworfen und implementiert.

• Eine Bytecodesprache, die generische Typen in ihrem Metadatensystem unterstützt, wird entworfen und implementiert.

• Zur Laufzeit wandelt der JIT-Compiler den Bytecode in Maschinencode um. Es ist für die Erstellung des entsprechenden Maschinencodes bei einer generischen Spezialisierung verantwortlich.

So zum Beispiel in C #, wenn Sie sagen

class C<T> { public void X(T t) { Console.WriteLine(t); } }
...
var c = new C<int>(); 
c.X(123);

Dann überprüft der Compiler, ob in C<int>das Argument inteine gültige Substitution für ist T, und generiert entsprechend Metadaten und Bytecode. Zur Laufzeit erkennt der Jitter, dass a C<int>zum ersten Mal erstellt wird, und generiert dynamisch den entsprechenden Maschinencode.

Die meisten Implementierungen von Generika (oder besser: parametrischer Polymorphismus) verwenden die Typlöschung. Dies vereinfacht das Problem des Kompilierens von generischem Code erheblich, funktioniert jedoch nur für Boxed-Typen: Da jedes Argument effektiv ein undurchsichtiger Zeiger ist, benötigen wir ein VTable oder einen ähnlichen Dispatch-Mechanismus, um Operationen an den Argumenten auszuführen. In Java:

<T extends Addable> T add(T a, T b) { … }

kann wie folgt kompiliert, typgeprüft und aufgerufen werden

Addable add(Addable a, Addable b) { … }

mit der Ausnahme, dass Generika der Typprüfung am Aufrufstandort weitaus mehr Informationen liefern. Diese zusätzlichen Informationen können mit Typvariablen verarbeitet werden , insbesondere wenn generische Typen abgeleitet werden. Während der Typprüfung kann jeder generische Typ durch eine Variable ersetzt werden. Nennen wir es $T1:

$T1 add($T1 a, $T1 b)

Die Typvariable wird dann mit weiteren bekannten Fakten aktualisiert, bis sie durch einen konkreten Typ ersetzt werden kann. Der Typprüfungsalgorithmus muss so geschrieben sein, dass diese Typvariablen berücksichtigt werden, auch wenn sie noch nicht in einen vollständigen Typ aufgelöst sind. In Java selbst ist dies normalerweise einfach möglich, da die Art der Argumente häufig bekannt ist, bevor die Art des Funktionsaufrufs bekannt sein muss. Eine bemerkenswerte Ausnahme ist ein Lambda-Ausdruck als Funktionsargument, der die Verwendung solcher Typvariablen erfordert.

Viel später, ein Optimierer kann spezialisierten Code für einen bestimmten Satz von Argumenten erzeugt, würde dies dann effektiv eine Art inlining.

Eine VTable für generische Argumente kann vermieden werden, wenn die generische Funktion keine Operationen für den Typ ausführt, sondern sie nur an eine andere Funktion übergibt. ZB call :: (a -> b) -> a -> b; call f x = f xmüsste die Haskell-Funktion das xArgument nicht boxen . Dies erfordert jedoch eine Aufrufkonvention, die Werte ohne Kenntnis ihrer Größe durchlaufen kann, wodurch sie im Wesentlichen ohnehin auf Zeiger beschränkt wird.

C ++ unterscheidet sich in dieser Hinsicht sehr von den meisten Sprachen. Eine Klasse oder Funktion mit Vorlagen (ich werde hier nur auf Funktionen mit Vorlagen eingehen) ist an sich nicht aufrufbar. Stattdessen sollten Vorlagen als Metafunktion zur Kompilierungszeit verstanden werden, die eine tatsächliche Funktion zurückgibt. Wenn Sie die Inferenz der Vorlagenargumente für einen Moment ignorieren, läuft der allgemeine Ansatz auf die folgenden Schritte hinaus:

1. Wenden Sie die Vorlage auf die angegebenen Vorlagenargumente an. Wenn Sie beispielsweise template<class T> T add(T a, T b) { … }as aufrufen add<int>(1, 2), erhalten Sie die eigentliche Funktion int __add__T_int(int a, int b)(oder wie auch immer der Name-Mangling-Ansatz lautet).

2. Wenn in der aktuellen Kompilierungseinheit bereits Code für diese Funktion generiert wurde, fahren Sie fort. Generieren Sie den Code ansonsten so, als ob eine Funktion int __add__T_int(int a, int b) { … }in den Quellcode geschrieben worden wäre. Dies beinhaltet das Ersetzen aller Vorkommen des Vorlagenarguments durch seine Werte. Dies ist wahrscheinlich eine AST → AST-Transformation. Führen Sie dann eine Typprüfung des generierten AST durch.

3. Kompilieren Sie den Aufruf, als ob der Quellcode gewesen wäre __add__T_int(1, 2).

Beachten Sie, dass C ++ - Vorlagen eine komplexe Interaktion mit dem Überladungsauflösungsmechanismus haben, den ich hier nicht beschreiben möchte. Beachten Sie auch, dass diese Codegenerierung es unmöglich macht, eine Vorlage zu haben, die auch virtuell ist - ein Ansatz auf der Basis von Typlöschung leidet nicht unter dieser wesentlichen Einschränkung.

Was bedeutet das für Ihren Compiler und / oder Ihre Sprache? Sie müssen sorgfältig überlegen, welche Arten von Generika Sie anbieten möchten. Die Typlöschung ohne Typinferenz ist der einfachste Ansatz, wenn Sie Boxed Types unterstützen. Die Template-Spezialisierung scheint recht einfach zu sein, beinhaltet jedoch in der Regel eine Namensverknüpfung und (bei mehreren Kompilierungseinheiten) eine erhebliche Verdoppelung der Ausgabe, da Templates am Aufrufstandort und nicht am Definitionsstandort instanziiert werden.

Der Ansatz, den Sie gezeigt haben, ist im Wesentlichen ein C ++ - ähnlicher Template-Ansatz. Sie speichern die spezialisierten / instanziierten Vorlagen jedoch als „Versionen“ der Hauptvorlage. Dies ist irreführend: Sie sind konzeptionell nicht identisch, und verschiedene Instanzen einer Funktion können sehr unterschiedliche Typen haben. Dies wird die Dinge auf lange Sicht komplizieren, wenn Sie auch eine Funktionsüberladung zulassen. Stattdessen benötigen Sie den Begriff eines Überladungssatzes, der alle möglichen Funktionen und Vorlagen enthält, die einen gemeinsamen Namen haben. Mit Ausnahme des Behebens von Überladungen können Sie verschiedene instanziierte Vorlagen als vollständig voneinander getrennt betrachten.