Dans certains domaines de la programmation, il est normal de vouloir écrire une structure de données ou un algorithme pouvant fonctionner avec des éléments de différents types. Par exemple, une liste de génériques ou un algorithme de tri qui n'a besoin que d'une fonction de comparaison. Dans divers langages, différentes manières de résoudre ce problème sont proposées: du simple fait de signaler les fonctions communes appropriées (C, Go) aux programmeurs à des systèmes génériques si puissants qu'ils deviennent Turing complet (
Rust ,
C ++ ). Dans cet article, je parlerai des systèmes génériques de différentes langues et de leur implémentation. Je commencerai par résoudre le problème dans les langues sans un tel système (comme C), puis je montrerai comment l'ajout progressif d'extensions conduit à des systèmes d'autres langues.
Je trouve que les génériques sont une option intéressante, car ils sont un cas spécial simple du problème général de métaprogrammation: écrire des programmes qui peuvent générer des classes d'autres programmes. Pour preuve, je montrerai comment trois méthodes de métaprogrammation différentes et complètement générales peuvent être considérées comme des extensions multidirectionnelles dans l'espace des systèmes génériques: les langages dynamiques comme Python, les macro-systèmes procéduraux comme
Template Haskel et la compilation par phases comme
Zig et
Terra .
Revue
J'ai dessiné un schéma de principe de tous les systèmes décrits dans l'article afin que vous puissiez présenter son contenu et comment ces systèmes sont interconnectés:
Idées principales
Supposons que nous écrivons dans un langage sans systèmes génériques et que nous voulons créer une structure de données de structure de données de pile générique qui fonctionne avec des données de tout type. Le problème est que chaque définition de fonction et de type ne fonctionnera qu'avec des données de même taille et copiées dans un sens, et fonctionnera généralement de la même manière.
Il existe deux façons de contourner ce problème: soit assurez-vous que tous les types de données agissent de la même manière dans notre structure, soit faites de nombreuses copies de la structure de données avec des modifications mineures pour fonctionner correctement avec chaque type de données. Ces idées ont formé la base de deux grands groupes de solutions génériques: la boxe et la monomorphisation.
L'emballage signifie mettre tout de suite dans des «boîtes» unifiées qui fonctionnent de la même manière. Cela se fait généralement comme ceci: les données sont placées dans un tas et les pointeurs vers celles-ci sont placés dans la structure de données. Vous pouvez créer des pointeurs vers tous les types qui fonctionneront de la même manière, donc le même code fonctionnera avec des données de tout type! Cependant, cela entraîne une consommation de mémoire accrue, une recherche dynamique et des échecs de cache. En C, cela signifie que votre structure de données stocke des pointeurs
void* et met simplement en cache les données vers et depuis
void* (si les données ne sont pas sur le tas, elles les placent là).
La monomorphisation signifie la copie répétée de code pour les différents types de données que nous voulons stocker. Ensuite, chaque instance de code peut utiliser directement la taille et les méthodes de données avec lesquelles elle fonctionne sans recherche dynamique. Avec cette approche, le code s'exécute le plus rapidement, mais sa taille et son temps de compilation augmentent, car nous compilons à plusieurs reprises le même code avec des modifications mineures. En C, cela correspond à la
définition de la structure de données entière en tant que macro , suivie de son invocation pour chaque type de données.
En général, lors de la compilation, le code se compile plus rapidement, mais ses performances peuvent se détériorer pendant l'exécution, tandis que pendant la monomorphisation, nous générons du code rapide, mais il faut plus de temps pour compiler et optimiser toutes les instances du code. Une autre différence est que lorsque les extensions d'empaquetage vous permettent de faire un comportement plus dynamique du code exécutable, et la monomorphisation vous permet de séparer de manière plus flexible différentes instances du code générique. Il convient également de noter que dans certains grands programmes, les avantages de la monomorphisation peuvent être compensés par des échecs dans le cache d'instructions supplémentaires du code généré.
Chacun des schémas décrits pour travailler avec des génériques peut être développé dans différentes directions, si vous avez besoin de plus de fonctionnalités ou de sécurité, et les auteurs de différentes langues ont trouvé des solutions très intéressantes. Par exemple, les deux approches peuvent être utilisées dans Rust et C #!
Emballage
Commençons par un exemple d'emballage de base dans 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 }
De plus, le packaging est utilisé en C (
void* ), Go (
interface{} ), Java pré-générique (
Object ) et Objective-C pré-générique (
id ).
Génériques emballés avec types de purée
La principale méthode d'emballage présente des inconvénients:
- Selon la langue, nous devons souvent convertir des valeurs vers ou à partir du type correct chaque fois que nous lisons ou écrivons dans la structure de données.
- Rien ne nous empêche de mettre des éléments de différents types dans la structure, ce qui peut provoquer des bugs qui ressemblent à des plantages lors de l'exécution du code.
Les deux problèmes peuvent être résolus en ajoutant des génériques au système de types de fonctionnalités, tout en utilisant la méthode d'empaquetage principale de la même manière qu'auparavant lors de l'exécution du code. Cette approche est souvent appelée effacement de type, car les types du système générique sont écrasés et deviennent un type sous le capot (comme
Object ).
Java et Objective-C ont commencé avec le packaging habituel, et ont ensuite acquis des outils de langage pour les génériques avec le mashing de type, par souci de compatibilité, en utilisant les mêmes types de collection qu'auparavant, mais avec les paramètres facultatifs des types génériques. Prenons un exemple tiré d'un article de Wikipedia sur les
génériques en Java :
List v = new ArrayList(); v.add("test");
Génériques packagés dérivés avec performances unifiées
OCaml développe encore l'idée d'une vision unifiée. Il n'y a pas de types primitifs qui nécessitent un placement d'empaquetage supplémentaire (car un
Integer doit se transformer en
Integer pour entrer dans une liste de
ArrayList en Java), car tout est déjà compressé ou représenté par une valeur entière de la taille d'un pointeur, c'est-à-dire que tout tient dans un seul mot machine. Mais lorsque le garbage collector examine les données stockées dans des structures génériques, il doit distinguer les pointeurs des nombres, de sorte que les nombres sont marqués avec un bit, placés là où les pointeurs correctement alignés n'ont pas un bit, laissant des plages de seulement 31 ou 63 bits.
OCaml dispose également d'un système d'inférence de type, vous pouvez donc écrire une fonction et le compilateur affichera le type générique le plus approprié si vous ne l'annotez pas, et donc les fonctions ressembleront à un langage typé dynamiquement:
let first (head :: tail) = head (* inferred type: 'a list -> 'a *)
Le type donné peut être appelé «une fonction de la liste des éléments de type
'a vers quelque chose de type
'a ». Cela signifie que le type de retour sera le même que le type de liste, et il peut être de n'importe quel type.
Interfaces
Une autre limitation de l'emballage conventionnel est que les types emballés sont
complètement opaques. Ce n'est pas un problème pour les structures de données comme une pile, mais des outils comme le tri des fonctions génériques nécessitent des fonctionnalités supplémentaires, telles que des fonctions de comparaison spécifiques au type. Il existe de nombreuses façons de l'implémenter lors de l'exécution et de refléter dans le langage, techniquement, ce sont des directions différentes, et vous pouvez
implémenter le même langage avec plusieurs approches similaires . Cependant, les fonctionnalités de différents langages affectent leur implémentation et ce n'est qu'alors que les extensions améliorent les points forts des implémentations sélectionnées. Cela signifie qu'il existe deux familles de langages basées sur des approches différentes de l'exécution: les tables de méthodes virtuelles (vtables) et le transfert de dictionnaire.
Tableaux de méthodes d'interface
Si nous voulons fournir des fonctions spécifiques au type, en adhérant à la stratégie d'emballage pour le travail unifié avec tout, alors il suffit d'avoir un moyen unifié de trouver des fonctions similaires que nous devons obtenir de l'objet. Cette approche est appelée «tables de méthodes virtuelles» (vtables, tables de méthodes virtuelles), bien que personne n'utilise le nom complet. Il est implémenté comme suit: à un décalage nul dans chaque objet de structure générique, il y a un pointeur vers une table de pointeurs de fonction avec un circuit cohérent. Dans ces tableaux, le code générique recherche des pointeurs vers des fonctions spécifiques au type en indexant des pointeurs spécifiques à des décalages fixes.
C'est ainsi que
interface types d'
interface sont implémentés dans les objets
dyn trait Go et
dyn trait dans Rust. Lorsque vous convertissez un type en un type d'interface de ce qu'il implémente, un wrapper est créé pour l'interface qui contient un pointeur sur l'objet source et un pointeur sur la table des fonctions spécifiques au type. Mais cela nécessite un niveau supplémentaire d'adressage indirect des pointeurs et un autre schéma. Par conséquent, le tri dans Go utilise l'
interface du conteneur avec la méthode Swap et ne prend pas la tranche de l'interface comparable, car cela nécessiterait de placer en mémoire une toute nouvelle tranche de types d'interface qui serait triée à la place de la tranche d'origine!
Programmation orientée objet
La POO est une propriété de langage qui fait bon usage des capacités des tables de types virtuels. Au lieu d'objets d'interface séparés avec vtables, les langages OOP comme Java insèrent simplement un pointeur vers une table de types virtuels au début de chaque objet. Les langages de type Java ont un système d'héritage et des interfaces qui peuvent être entièrement implémentées à l'aide de ces tables d'objets de type virtuel.
En plus de fournir des fonctionnalités supplémentaires, l'intégration de vtable dans chaque objet résout le problème de la nécessité de construire de nouveaux types d'interface avec un adressage indirect (indirection). Contrairement à Go, en Java
, la fonction de tri peut appliquer l'interface
Comparable aux types qu'elle implémente.
La réflexion
Si vous avez des tables de types virtuels, il ne vous sera pas difficile de forcer le compilateur à générer des tables d'autres types d'informations, par exemple, des noms de champs, des types et des emplacements. Cela permettra d'accéder à toutes les données de ce type à l'aide d'un code qui peut afficher toutes les données de tout autre type. Ce comportement peut être utilisé pour ajouter de la «réflexion» au langage, ce qui permet la sérialisation et un bel affichage de types arbitraires. La réflexion, en tant qu'extension du paradigme de l'empaquetage, a un inconvénient: pour cela, une seule copie du code suffit, mais vous devez effectuer de nombreuses recherches dynamiques, ce qui réduit la vitesse de sérialisation.
Langages qui utilisent la réflexion pour la sérialisation et d'autres fonctions: Java, C # et Go.
Langues typées dynamiquement
La réflexion est un outil très puissant qui vous permet de résoudre un tas de tâches de métaprogrammation différentes. Mais cela ne vous permet pas de créer de nouveaux types ou de modifier des informations sur les types de valeurs existantes. Si nous ajoutons cette fonctionnalité et que les syntaxes d'accès aux données et de modification utilisent la réflexion par défaut, nous obtenons des langages typés dynamiquement! L'incroyable flexibilité de la métaprogrammation dans des langages comme Python et Ruby est née grâce aux systèmes de réflexion efficaces et puissants qui sont utilisés pour résoudre tous les problèmes.
Vous pouvez dire: "Mais les langages dynamiques ne fonctionnent pas comme ça, ils implémentent simplement tout en utilisant des tables de hachage!" Les tables de hachage ne sont qu'une bonne structure de données pour créer des tables modifiables avec des informations de type. De plus, certains interprètes, tels que CPython, fonctionnent de cette façon. Dans un JIT hautes performances, par exemple V8,
il y a beaucoup de tables de types virtuels et d' informations de réflexion. Dans la V8, les classes cachées (vtables et informations de réflexion) et la structure des objets sont similaires à ce que vous pouvez voir dans Java VM, avec la possibilité de remplacer des objets par de nouvelles tables de types virtuels lors de l'exécution. Ce n'est pas une coïncidence, car il n'y a pas de coïncidences: le
créateur de V8 travaillait sur une machine virtuelle Java haute performance .
Transfert de dictionnaire
Une autre façon d'implémenter des interfaces dynamiques consiste à transférer une table avec les pointeurs de fonction requis vers la fonction générique qui en a besoin. Ceci est quelque peu similaire à la construction d'objets d'interface en forme de Go sur le lieu de l'appel, seulement dans notre cas, la table est passée comme argument caché, et non empaquetée dans un bundle comme l'un des arguments existants.
Cette approche est utilisée dans
les classes de types dans Haskell , bien que GHC vous permette d'effectuer une sorte de monomorphisation en utilisant l'inline et la spécialisation. OCaml utilise le transfert de dictionnaire avec un argument explicite sous la forme
de modules de première classe , mais il a déjà été proposé d'
ajouter la possibilité de rendre le paramètre implicite .
Tables de témoins dans Swift
Les auteurs de Swift ont utilisé une solution intéressante: le transfert du dictionnaire, ainsi que la mise en place de données sur les tailles de caractères et comment les déplacer, les copier et les publier dans le tableau, vous permet de fournir toutes les informations nécessaires pour un travail unifié avec tous les types sans les emballer. Ainsi, Swift peut implémenter des génériques
sans monomorphisation et placement en mémoire dans une représentation unifiée de toutes les entités! Oui, vous devez payer pour les recherches dynamiques, comme c'est la caractéristique de toute la famille qui utilise le packaging, mais cela économise des ressources pour le placement en mémoire, sa consommation et l'incohérence du cache. En utilisant les fonctions
annotées comme @inlinable , le compilateur Swift est également capable de spécialiser (monomorphiser) et de générer des génériques à l'intérieur du module ou entre les modules pour éviter les dépenses mentionnées. Une évaluation heuristique de l'effet sur la taille du code est probablement utilisée.
Cela explique également comment Swift peut
implémenter la stabilité ABI , tout en vous permettant d'ajouter et de redistribuer des champs dans la structure, bien que les auteurs fournissent l'attribut
@frozen pour refuser les recherches dynamiques pour de meilleures performances.
Analyse de type intensionnelle
Il existe une autre façon d'implémenter des interfaces pour les types packagés. Nous ajoutons l'identificateur de type à une certaine partie de l'objet, en suivant l'exemple du pointeur vtable, puis générons des fonctions pour chaque méthode d'interface qui a une grande expression de
switch pour tous les types qui implémentent cette méthode et la transmettons à la méthode spécifique au type correcte.
Je ne mets pas en garde contre l'utilisation de langages qui utilisent cette approche, mais les compilateurs C ++ et les machines virtuelles Java agissent de la même manière, lorsqu'ils utilisent l'optimisation basée sur des profils, ils découvrent qu'un certain endroit de l'appel des génériques fonctionne principalement avec des objets de certains types. Les compilateurs et les machines virtuelles remplacent les points d'appel par des vérifications pour chaque type ordinaire, puis répartissent statiquement ces types, comme solution de rechange en utilisant la répartition dynamique conventionnelle. Par conséquent, l'algorithme de prédiction de branche peut prédire quelle branche le code continuera et continuera à envoyer des instructions à l'aide d'appels statiques.
Monomorphisation
Il s'agit d'une alternative à l'emballage. Avec la monomorphisation, nous devons trouver un moyen de générer plusieurs versions du code pour chaque type que nous voulons utiliser. Les compilateurs ont plusieurs phases de présentation que le code traverse et, théoriquement, peuvent être copiés à n'importe laquelle de ces étapes.
Génération de code source
La façon la plus simple de monomorphiser est de copier au premier stade de la présentation: copiez le code source! Ensuite, le compilateur n'a même pas à prendre en charge les génériques, et cela est parfois fait par les utilisateurs des langages C et Go, dont les compilateurs ne disposent pas d'un tel support.
En C, vous pouvez utiliser un préprocesseur et définir la structure de données dans une macro ou un en-tête en l'insérant à plusieurs reprises avec différents
#define . Go a des scripts comme
genny qui facilitent la génération de code.
L'inconvénient de la duplication du code source est que, selon la langue, il peut être nécessaire de traiter de nombreux problèmes et cas marginaux.En outre, le compilateur analyse et vérifie plusieurs fois les types réellement pour le même code. Encore une fois, selon le langage et les outils, ces génériques de méthodes peuvent être difficiles à écrire et à utiliser, comme si à l'intérieur d'une macro C chaque ligne se termine par une barre oblique inverse et tous les types et noms de fonctions doivent être collés manuellement dans leurs identifiants pour éviter les collisions.
Mixins à cordes en ré
Cependant, la génération de code a ses avantages, comme le fait que vous pouvez générer du code en utilisant un langage de programmation à part entière, ainsi que d'utiliser une vue familière aux utilisateurs.
Certains langages dans lesquels les génériques sont implémentés différemment vous permettent également de générer du code pour des cas de métaprogrammation plus généraux qui ne sont pas pris en compte dans leurs systèmes génériques, par exemple pour la sérialisation. L'exemple le plus compréhensible est
le mixage de chaînes en D , qui permet de compiler du code D sous forme de valeurs de chaîne au milieu de la compilation, en utilisant toutes les fonctionnalités du langage.
Macros procédurales de rouille
Un exemple similaire, uniquement avec une représentation dans le compilateur à une seule étape.
Les macros procédurales de Rust utilisent des flux de jetons comme entrée et sortie, fournissant des utilitaires pour convertir ces flux en chaîne et vice versa. L'avantage de cette approche est que les flux de jetons peuvent stocker des informations de localisation à partir du code source. Le code écrit par l'utilisateur, la macro peut être insérée en tant que jetons directement de l'entrée au week-end. Et si ce code conduit à une erreur de compilation dans la sortie des macos, le compilateur affichera un message et pointera avec précision vers le fichier, la ligne et la colonne de la partie cassée du code. Mais si la macro génère un code cassé, un message d'erreur indiquera un appel de macro. Par exemple, si vous utilisez une
macro qui encapsule une fonction dans la journalisation des appels et commet une erreur lors de l'implémentation d'une fonction encapsulée, le message d'erreur pointera directement vers l'erreur dans le fichier et non vers le code généré par la macro.
Macros d'arborescence de syntaxe
Certaines langues vont encore plus loin et proposent des outils pour utiliser et créer différents types d'arbres de syntaxe abstraite dans les macros (Abstract Syntax Tree, AST). Les exemples incluent
Template Haskell , les
macros Nim ,
OCaml PPX et presque tous
Lisp .
L'inconvénient des macros AST est que vous ne voulez pas forcer les utilisateurs à apprendre un tas de fonctions pour créer des types AST, ainsi que des langages de base. Dans la famille de langages Lisp, cela est résolu à l'aide d'une forte simplification et d'une correspondance maximale entre la syntaxe et la structure d'AST, cependant, la création de structures n'est pas toujours facile.
Ainsi, dans toutes les langues que j'ai mentionnées, sous une forme ou une autre, il existe une primitive «quote» à laquelle vous donnez un morceau de code dans la langue, et qui renvoie un arbre de syntaxe. Ces primitives peuvent fusionner les valeurs de l'arbre de syntaxe en utilisant la similitude de l'interpolation de chaînes. Voici un exemple sur Template Haskell:
, , , . . , PPX OCaml
/ , . Rust ,
parsing quotation , , . Rust
, , !
Patterns
— . ++ 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, , .
, , , , , , ! , , , . , , .