In einigen Bereichen der Programmierung ist es normal, eine Datenstruktur oder einen Algorithmus schreiben zu wollen, der mit Elementen unterschiedlicher Typen arbeiten kann. Zum Beispiel eine Liste von Generika oder ein Sortieralgorithmus, der nur eine Vergleichsfunktion benötigt. In verschiedenen Sprachen werden verschiedene Möglichkeiten zur Lösung dieses Problems vorgeschlagen: vom einfachen Aufzeigen der entsprechenden gemeinsamen Funktionen (C, Go) über Programmierer bis hin zu so leistungsfähigen generischen Systemen, dass sie vollständig werden (
Rust ,
C ++ ). In diesem Artikel werde ich über generische Systeme aus verschiedenen Sprachen und deren Implementierung sprechen. Ich werde zunächst das Problem in Sprachen ohne ein ähnliches System (wie C) lösen und dann zeigen, wie das schrittweise Hinzufügen von Erweiterungen zu Systemen aus anderen Sprachen führt.
Ich finde Generika eine interessante Option, da sie ein einfacher Spezialfall des allgemeinen Metaprogrammierungsproblems sind: Schreiben von Programmen, die Klassen anderer Programme generieren können. Als Beweis werde ich zeigen, wie drei verschiedene und vollständig allgemeine Metaprogrammierungsmethoden als multidirektionale Erweiterungen im Bereich generischer Systeme betrachtet werden können: dynamische Sprachen wie Python, prozedurale Makrosysteme wie
Template Haskel und schrittweise Kompilierung wie
Zig und
Terra .
Rückblick
Ich habe ein Blockdiagramm aller im Artikel beschriebenen Systeme gezeichnet, damit Sie deren Inhalt und die Art und Weise, wie diese Systeme miteinander verbunden sind, darstellen können:
Hauptideen
Angenommen, wir schreiben in einer Sprache ohne generische Systeme und möchten eine generische Stapeldatenstruktur erstellen, die mit Daten eines beliebigen Typs funktioniert. Das Problem ist, dass jede Funktions- und Typdefinition nur mit Daten derselben Größe funktioniert und auf eine Weise kopiert wird und im Allgemeinen ähnlich funktioniert.
Es gibt zwei Möglichkeiten, dies zu umgehen: Stellen Sie entweder sicher, dass alle Datentypen in unserer Struktur gleich funktionieren, oder erstellen Sie viele Kopien der Datenstruktur mit geringfügigen Änderungen, damit sie mit jedem Datentyp ordnungsgemäß funktionieren. Diese Ideen bildeten die Grundlage für zwei große Gruppen von Lösungen mit Generika: Boxen und Monomorphisierung.
Verpacken bedeutet, alles in einer Reihe in einheitliche „Kisten“ zu packen, die auf die gleiche Weise funktionieren. Dies geschieht normalerweise so: Die Daten werden in einen Heap gestellt und die Zeiger darauf werden in die Datenstruktur gestellt. Sie können Zeiger auf alle Typen erstellen, die auf die gleiche Weise funktionieren, sodass derselbe Code mit Daten aller Art funktioniert! Dies führt jedoch zu einem erhöhten Speicherverbrauch, dynamischer Suche und Cache-Fehlern. In C bedeutet dies, dass Ihre Datenstruktur
void* -Zeiger speichert und Daten einfach in und aus
void* (wenn sich die Daten nicht auf dem Heap befinden, werden sie dort abgelegt).
Monomorphisierung bedeutet, wiederholt Code für die verschiedenen Datentypen zu kopieren, die wir speichern möchten. Dann kann jede Codeinstanz direkt die Größen- und Datenmethoden verwenden, mit denen sie ohne dynamische Suche arbeitet. Bei diesem Ansatz wird der Code am schnellsten ausgeführt, aber seine Größe und Kompilierungszeit erhöhen sich, da wir denselben Code wiederholt mit geringfügigen Änderungen kompilieren. In C entspricht dies der
Definition der gesamten Datenstruktur als Makro , gefolgt von ihrem Aufruf für jeden Datentyp.
Im Allgemeinen wird der Code während der Kompilierung schneller kompiliert, aber seine Leistung kann sich während der Ausführung verschlechtern, während wir während der Monomorphisierung schnellen Code generieren, aber es dauert länger, alle Instanzen des Codes zu kompilieren und zu optimieren. Ein weiterer Unterschied besteht darin, dass Sie beim Packen von Erweiterungen ein dynamischeres Verhalten des ausführbaren Codes und durch Monomorphisierung verschiedene Instanzen des generischen Codes flexibler trennen können. Es ist auch erwähnenswert, dass in einigen großen Programmen die Vorteile der Monomorphisierung durch Fehler im Cache zusätzlicher Anweisungen aus dem generierten Code ausgeglichen werden können.
Jedes der beschriebenen Schemata für die Arbeit mit Generika kann in verschiedene Richtungen erweitert werden, wenn Sie mehr Funktionen oder Sicherheit benötigen, und die Autoren verschiedener Sprachen haben sehr interessante Lösungen gefunden. Zum Beispiel können beide Ansätze in Rust und C # verwendet werden!
Verpackung
Beginnen wir mit einem Beispiel für eine Basisverpackung in Go:
type Stack struct { values []interface{} } func (this *Stack) Push(value interface{}) { this.values = append(this.values, value) } func (this *Stack) Pop() interface{} { x := this.values[len(this.values)-1] this.values = this.values[:len(this.values)-1] return x }
Außerdem wird das Packen in C (
void* ), Go (
interface{} ), vorgenerischem Java (
Object ) und vorgenerischem Objective-C (
id ) verwendet.
Gepackte Generika mit Maischetypen
Die Hauptverpackungsmethode hat Nachteile:
- Abhängig von der Sprache müssen wir häufig bei jedem Lesen oder Schreiben in die Datenstruktur Werte in oder aus dem richtigen Typ umwandeln.
- Nichts hindert uns daran, Elemente unterschiedlichen Typs in die Struktur einzufügen, was zu Fehlern führen kann, die während der Codeausführung wie Abstürze aussehen.
Beide Probleme können gelöst werden, indem dem System von Funktionalitätstypen Generika hinzugefügt werden, während die Hauptverpackungsmethode auf die gleiche Weise wie zuvor während der Codeausführung verwendet wird. Dieser Ansatz wird häufig als Typlöschung bezeichnet, da Typen im generischen System überschrieben werden und zu einem Typ unter der Haube werden (wie
Object ).
Java und Objective-C begannen mit der üblichen Verpackung und erwarben später aus Kompatibilitätsgründen Sprachtools für Generika mit Typ-Mashing, wobei dieselben Sammlungstypen wie zuvor verwendet wurden, jedoch mit den optionalen Parametern generischer Typen. Betrachten Sie ein Beispiel aus einem Wikipedia-Artikel über
Generika in Java :
List v = new ArrayList(); v.add("test");
Abgeleitete verpackte Generika mit einheitlicher Leistung
OCaml entwickelt die Idee einer einheitlichen Sichtweise weiter. Es gibt keine primitiven Typen, die eine zusätzliche Paketplatzierung benötigen (da ein
int in eine
Integer , um in eine
ArrayList in Java zu gelangen), da alles bereits gepackt oder durch einen ganzzahligen Wert von der Größe eines Zeigers dargestellt ist, dh alles passt in ein Maschinenwort. Wenn der Garbage Collector jedoch die in generischen Strukturen gespeicherten Daten betrachtet, muss er Zeiger von Zahlen unterscheiden. Daher werden Zahlen mit einem einzelnen Bit markiert, das dort platziert wird, wo korrekt ausgerichtete Zeiger kein Bit haben, sodass nur Bereiche von 31 oder 63 Bit übrig bleiben.
OCaml verfügt auch über ein Typinferenzsystem, sodass Sie eine Funktion schreiben können und der Compiler den am besten geeigneten generischen Typ ausgibt, wenn Sie ihn nicht mit Anmerkungen versehen. Die Funktionen sehen also wie eine dynamisch typisierte Sprache aus:
let first (head :: tail) = head (* inferred type: 'a list -> 'a *)
Der angegebene Typ kann als "eine Funktion aus der Liste der Elemente vom Typ
'a in etwas mit dem Typ
'a " bezeichnet werden. Dies bedeutet, dass der Rückgabetyp mit dem Listentyp identisch ist und ein beliebiger Typ sein kann.
Schnittstellen
Eine weitere Einschränkung herkömmlicher Verpackungen besteht darin, dass verpackte Typen
vollständig undurchsichtig sind. Dies ist kein Problem für Datenstrukturen wie einen Stapel, aber Tools wie das Sortieren generischer Funktionen benötigen zusätzliche Funktionen, wie z. B. typspezifische Vergleichsfunktionen. Es gibt viele Möglichkeiten, dies zur Laufzeit zu implementieren und in der Sprache wiederzugeben. Technisch gesehen sind dies unterschiedliche Richtungen, und Sie können
dieselbe Sprache mit mehreren ähnlichen Ansätzen implementieren . Die Funktionen verschiedener Sprachen wirken sich jedoch auf ihre Implementierung aus, und erst dann verbessern Erweiterungen die Stärken der ausgewählten Implementierungen. Dies bedeutet, dass es zwei Sprachfamilien gibt, die auf unterschiedlichen Laufzeitansätzen basieren: virtuelle Methodentabellen (vtables) und Wörterbuchübertragung.
Tabellen für Schnittstellenmethoden
Wenn wir typspezifische Funktionen bereitstellen möchten, die sich an die Verpackungsstrategie halten, um eine einheitliche Arbeit mit allem zu ermöglichen, reicht es aus, eine einheitliche Methode zu haben, um ähnliche Funktionen zu finden, die wir vom Objekt erhalten müssen. Dieser Ansatz wird als "virtuelle Methodentabellen" (vtables, virtuelle Methodentabellen) bezeichnet, obwohl niemand den vollständigen Namen verwendet. Es wird wie folgt implementiert: Bei einem Nullpunktversatz in jedem generischen Strukturobjekt gibt es einen Zeiger auf eine Tabelle von Funktionszeigern mit einer konsistenten Schaltung. In diesen Tabellen sucht der generische Code nach Zeigern auf typspezifische Funktionen, indem bestimmte Zeiger mit festen Offsets indiziert werden.
Auf diese Weise werden
interface in Go- und
dyn trait Objekten in Rust implementiert. Wenn Sie einen Typ in einen Schnittstellentyp der Implementierung umwandeln, wird ein Wrapper für die Schnittstelle erstellt, der einen Zeiger auf das Quellobjekt und einen Zeiger auf die vtable typspezifischer Funktionen enthält. Dies erfordert jedoch eine zusätzliche Ebene der indirekten Adressierung von Zeigern und ein anderes Schema. Daher verwendet das Sortieren in Go die
Schnittstelle für den Container mit der Swap-Methode und verwendet nicht das Slice der Comparable-Schnittstelle, da hierfür ein völlig neues Slice von Schnittstellentypen im Speicher abgelegt werden müsste, das anstelle des ursprünglichen Slice sortiert würde!
Objektorientierte Programmierung
OOP ist eine Spracheigenschaft, die die Funktionen virtueller Typentabellen optimal nutzt. Anstelle von separaten Schnittstellenobjekten mit vtables fügen OOP-Sprachen wie Java einfach einen Zeiger auf eine Tabelle virtueller Typen am Anfang jedes Objekts ein. Java-ähnliche Sprachen verfügen über ein Vererbungssystem und Schnittstellen, die mithilfe dieser Objekttabellen vom virtuellen Typ vollständig implementiert werden können.
Durch das Einbetten von vtable in jedes Objekt werden nicht nur zusätzliche Funktionen bereitgestellt, sondern auch das Problem gelöst, dass neue Schnittstellentypen mit indirekter Adressierung (Indirektion) erstellt werden müssen. Im Gegensatz zu Go kann die
Comparable in Java
die Schnittstelle
Comparable auf die von ihr implementierten Typen anwenden.
Reflexion
Wenn Sie Tabellen mit virtuellen Typen haben, ist es für Sie nicht schwierig, den Compiler zu zwingen, Tabellen mit anderen Informationstypen zu generieren, z. B. Namen von Feldern, Typen und Speicherorten. Dies ermöglicht den Zugriff auf alle Daten dieses Typs mithilfe von Code, mit dem alle Daten anderer Typen angezeigt werden können. Dieses Verhalten kann verwendet werden, um der Sprache „Reflexion“ hinzuzufügen, was eine Serialisierung und eine schöne Anzeige beliebiger Typen ermöglicht. Reflexion als Erweiterung des Verpackungsparadigmas hat einen Nachteil: Dafür reicht nur eine Kopie des Codes aus, aber Sie müssen viele dynamische Suchvorgänge durchführen, wodurch die Serialisierungsgeschwindigkeit verringert wird.
Sprachen, die Reflection für die Serialisierung und andere Funktionen verwenden: Java, C # und Go.
Dynamisch getippte Sprachen
Reflection ist ein sehr leistungsfähiges Tool, mit dem Sie eine Reihe verschiedener Metaprogrammieraufgaben lösen können. Sie können jedoch keine neuen Typen erstellen oder Informationen zu den Typen vorhandener Werte bearbeiten. Wenn wir diese Funktion hinzufügen und Datenzugriffs- und Änderungssyntaxen standardmäßig Reflektion verwenden, erhalten wir dynamisch typisierte Sprachen! Die unglaubliche Flexibilität der Metaprogrammierung in Sprachen wie Python und Ruby ist dank der effektiven, leistungsstarken Reflexionssysteme entstanden, mit denen Probleme gelöst werden können.
Sie können sagen: "Aber dynamische Sprachen funktionieren nicht so, sie implementieren einfach alles mithilfe von Hash-Tabellen!" Hash-Tabellen sind nur eine gute Datenstruktur zum Erstellen bearbeitbarer Tabellen mit Typinformationen. Darüber hinaus arbeiten einige Interpreter wie CPython auf diese Weise. In einer Hochleistungs-JIT, beispielsweise V8,
gibt es viele virtuelle Typentabellen und Reflexionsinformationen. In V8 ähneln versteckte Klassen (vtables und Reflection-Informationen) und die Struktur von Objekten denen in Java VM, wobei Objekte zur Laufzeit durch neue virtuelle Typentabellen ersetzt werden können. Dies ist kein Zufall, da es keine Zufälle gibt: Der
Entwickler von V8 arbeitete früher
an Hochleistungs-Java-VMs .
Wörterbuchübertragung
Eine andere Möglichkeit, dynamische Schnittstellen zu implementieren, besteht darin, eine Tabelle mit den erforderlichen Funktionszeigern auf die generische Funktion zu übertragen, die sie benötigt. Dies ähnelt in gewisser Weise der Erstellung von Go-förmigen Schnittstellenobjekten am Aufrufort. In unserem Fall wird die Tabelle jedoch als verstecktes Argument übergeben und nicht als eines der vorhandenen Argumente in ein Bundle gepackt.
Dieser Ansatz wird in
Typklassen in Haskell verwendet , obwohl Sie mit GHC eine Art Monomorphisierung mithilfe von Inlining und Spezialisierung durchführen können. OCaml verwendet die Wörterbuchübertragung mit einem expliziten Argument in Form
erstklassiger Module. Es wurde jedoch bereits vorgeschlagen,
die Möglichkeit hinzuzufügen, den Parameter implizit zu machen .
Zeugen-Tische in Swift
Die Swift-Autoren verwendeten eine interessante Lösung: Durch das Übertragen des Wörterbuchs sowie das Einfügen von Daten zu den Schriftgrößen und zum Verschieben, Kopieren und Freigeben in die Tabelle können Sie alle erforderlichen Informationen für eine einheitliche Arbeit mit beliebigen Typen bereitstellen, ohne sie zu verpacken. Somit kann Swift Generika
ohne Monomorphisierung und Platzierung im Speicher in einer einheitlichen Darstellung aller Entitäten implementieren! Ja, Sie müssen für dynamische Suchvorgänge bezahlen, wie es für die gesamte Familie charakteristisch ist, die Verpackungen verwendet, aber es spart Ressourcen für die Speicherung, den Verbrauch und die Cache-Inkonsistenz. Mit den
als @inlinable gekennzeichneten Funktionen kann der Swift-Compiler auch Generika innerhalb des Moduls oder zwischen Modulen spezialisieren (monomorphisieren) und inline
generieren , um die genannten Kosten zu vermeiden. Wahrscheinlich wird eine heuristische Bewertung der Auswirkung auf die Codegröße verwendet.
Dies erklärt auch, wie Swift
die ABI-Stabilität implementieren kann, während Sie weiterhin Felder in der Struktur hinzufügen und neu verteilen können, obwohl die Autoren das Attribut
@frozen , um dynamische Suchen für eine bessere Leistung abzulehnen.
Intensive Typanalyse
Es gibt eine andere Möglichkeit, Schnittstellen für verpackte Typen zu implementieren. Wir fügen die Typkennung nach dem Beispiel des vtable-Zeigers einem bestimmten Teil des Objekts hinzu und generieren dann Funktionen für jede Schnittstellenmethode, die einen großen
switch für alle Typen hat, die diese Methode implementieren, und übergeben sie an die richtige typspezifische Methode.
Ich warne nicht davor, Sprachen zu verwenden, die diesen Ansatz verwenden, aber C ++ - Compiler und virtuelle Java-Maschinen verhalten sich ähnlich, wenn sie bei der Optimierung anhand von Profilen feststellen, dass ein bestimmter Ort zum Aufrufen von Generika hauptsächlich mit Objekten bestimmter Typen funktioniert. Compiler und VMs ersetzen Anrufpunkte durch Prüfungen für jeden normalen Typ und versenden diese Typen dann statisch als Fallback unter Verwendung des herkömmlichen dynamischen Versands. Daher kann der Verzweigungsvorhersagealgorithmus vorhersagen, auf welcher Verzweigung der Code weitergehen wird, und weiterhin Anweisungen unter Verwendung statischer Aufrufe senden.
Monomorphisierung
Dies ist eine Alternative zur Verpackung. Bei der Monomorphisierung müssen wir einen Weg finden, um für jeden Typ, den wir verwenden möchten, mehrere Versionen des Codes zu generieren. Compiler haben mehrere Präsentationsphasen, die der Code durchläuft, und können theoretisch in jede dieser Phasen kopiert werden.
Quellcode-Generierung
Der einfachste Weg zur Monomorphisierung ist das Kopieren in der ersten Präsentationsphase: Kopieren Sie den Quellcode! Dann muss der Compiler nicht einmal Generika unterstützen, und dies wird manchmal von Benutzern der Sprachen C und Go durchgeführt, deren Compiler diese Unterstützung nicht haben.
In C können Sie einen Präprozessor verwenden und die Datenstruktur in einem Makro oder Header definieren, indem Sie sie wiederholt mit einem anderen
#define einfügen. Go hat Skripte wie
Genny , die es einfach machen, Code zu generieren.
Der Nachteil des Duplizierens des Quellcodes besteht darin, dass es je nach Sprache erforderlich sein kann, sich mit zahlreichen Problemen und Randfällen zu befassen. Darüber hinaus analysiert und prüft der Compiler viele Male nach Typen, die tatsächlich denselben Code enthalten. Abhängig von der Sprache und den Werkzeugen kann es wiederum schwierig sein, diese generischen Methoden zu schreiben und zu verwenden, da in einem C-Makro jede Zeile mit einem Backslash endet und alle Arten und Namen von Funktionen manuell in ihre Bezeichner eingeklebt werden müssen, um Kollisionen zu vermeiden.
String-Mixins in D.
Die Codegenerierung hat jedoch ihre Vorteile, z. B. die Tatsache, dass Sie Code mit einer vollwertigen Programmiersprache generieren und eine den Benutzern vertraute Ansicht verwenden können.
In einigen Sprachen, in denen Generika unterschiedlich implementiert sind, können Sie auch Code für allgemeinere Metaprogrammierungsfälle generieren, die in ihren generischen Systemen nicht berücksichtigt werden, z. B. für die Serialisierung. Das verständlichste Beispiel sind
String-Mixins in D , mit denen D-Code in Form von String-Werten während der Kompilierung unter Verwendung aller Funktionen der Sprache kompiliert werden kann.
Rust-Verfahrensmakros
Ein ähnliches Beispiel, nur mit einer Darstellung im Compiler in nur einer Phase.
Rust-Prozedurmakros verwenden Token-Streams als Eingabe und Ausgabe und bieten Dienstprogramme zum Konvertieren dieser Streams in Zeichenfolgen und umgekehrt. Der Vorteil dieses Ansatzes besteht darin, dass Token-Streams Standortinformationen aus dem Quellcode speichern können. Der vom Benutzer geschriebene Code, das Makro, kann als Token direkt von der Eingabe bis zum Wochenende eingefügt werden. Und wenn dieser Code zu einem Kompilierungsfehler in der Ausgabe der Macos führt, zeigt der Compiler eine Meldung an und zeigt genau auf die Datei, Zeile und Spalte des fehlerhaften Teils des Codes. Wenn das Makro jedoch einen fehlerhaften Code generiert, zeigt eine Fehlermeldung einen Makroaufruf an. Wenn Sie beispielsweise ein
Makro verwenden, das eine Funktion beim Protokollieren von Aufrufen umschließt und beim Implementieren einer umschlossenen Funktion einen Fehler macht, verweist die Fehlermeldung direkt auf den Fehler in der Datei und nicht auf den vom Makro generierten Code.
Syntaxbaummakros
Einige Sprachen gehen sogar noch weiter und bieten Tools zum Verwenden und Erstellen verschiedener Arten von abstrakten Syntaxbäumen in Makros (Abstract Syntax Tree, AST). Beispiele hierfür sind
Template Haskell ,
Nim-Makros ,
OCaml PPX und fast alle
Lisp .
Der Nachteil von AST-Makros besteht darin, dass Sie Benutzer nicht zwingen möchten, eine Reihe von Funktionen zum Erstellen von AST-Typen sowie grundlegende Sprachen zu erlernen. In der Lisp-Sprachfamilie wird dies mithilfe einer starken Vereinfachung und maximalen Übereinstimmung zwischen Syntax und Struktur des AST gelöst. Das Erstellen von Strukturen ist jedoch nicht immer einfach.
Daher gibt es in allen Sprachen, die ich erwähnt habe, in der einen oder anderen Form ein "Zitat" -Primitiv, dem Sie einen Code in der Sprache geben und der einen Syntaxbaum zurückgibt. Diese Grundelemente können die Werte des Syntaxbaums mithilfe der Ähnlichkeit der Zeichenfolgeninterpolation zusammenführen. Hier ist ein Beispiel für Template Haskell:
, , , . . , PPX OCaml
/ , . Rust ,
parsing quotation , , . Rust
, , !
Muster
— . ++ D , « ». , , , , .
template <class T> T myMax(T a, T b) { return (a>b?a:b); } template <class T> struct Pair { T values[2]; }; int main() { myMax(5, 6); Pair<int> p { {5,6} };
, , . , , .
D , , : , , . D;
if (
! ):
C++20 «» , , .
D , (compile time function evaluation)
static if , , , , - runtime-. , , , ++ , .
, « ». , Zig:
fn Stack(comptime T: type) type { return struct { items: []T, len: usize, const Self = @This(); pub fn push(self: Self, item: T) { // ... } }; }
Zig , ,
comptime .
Terra , . Terra — Lua, - , Lua API , quoting splicing:
function MakeStack(T) local struct Stack { items : &T;
Terra
- (domain specific) ,
Java Go . Terra runtime , .
Rust
, . , , ++, . , , , , . , . Rust, — Swift Haskell.
Rust « » (trait bounds).
Trait — , , . Rust , - , , , . - Rust
. , -.
fn my_max<T: PartialOrd>(a: T, b: T) -> T { if a > b { a } else { b } } struct Pair<T> { values: [T; 2], } fn main() { my_max(5,6); let p: Pair<i32> = Pair { values: [5,6] };
, . Rust . Rust 2018 ,
v: &impl SomeTrait ,
v: &dyn SomeTrait . GHC Swift Haskell , .
— , . , (placeholders) -, , .
memcpy , ! , . . JIT, , .
, , , , , , ! , , , . , , .