Article original : [History of C++] Templates: from C-style macros to concepts | Belay the C++ (belaycpp.com)
Traductrice : Chloé Lourseyre
Introduction : les types paramétrés
Template est, en C++, le nom donné à la fonctionnalité (ou plutôt au groupe de fonctionnalités, puisque le mot est utilisé dans plusieurs contextes) qui implémente les types paramétrés.
La notion de types paramétrés (ou parametrized types dans sa dénomination originale) est très importante dans la programmation moderne. Elle consiste à utiliser un type en tant que paramètre d’une fonctionnalité, de manière à ce que cette fonctionnalité puisse être utilisée avec plusieurs types différents, et ce de la même manière qu’on utilise une fonctionnalité avec différentes valeurs.
L’exemple le plus simple est avec std::vector. Quand vous déclarez un vecteur comme ceci : std::vector<int> foo;, le type int est paramétré. Vous auriez tout aussi bien pu mettre un autre type, comme double, void* ou une classe définie par vous.
C’est une manière de faire de la métaprogrammation, c’est-à-dire écrire un programme dont le but est de modifier les données d’un autre programme (ou d’une autre partie de son programme).
Pour le reste de l’article (y compris la partie 2), j’utiliserai le mot « template » pour renvoyer à la fois au concept de types paramétrés et à son implémentation en C++ (sauf dans les cas où je voudrais faire explicitement la distinction).
Avant les templates
Avant la création des templates, au début du C++, on devait écrire des macros de style C pour les émuler.
Une manière de faire était la suivante :
foobar.h
void foobar(FOOBAR_TYPE my_val);
foobar.cpp
void foobar(FOOBAR_TYPE my_val)
{
// do stuff
}
main.cpp
#define FOOBAR_TYPE int
#include "foobar.h"
#include "foobar.cpp" // Only do this in a source file
#undef FOOBAR_TYPE
#define FOOBAR_TYPE double
#include "foobar.h"
#include "foobar.cpp" // Only do this in a source file
#undef FOOBAR_TYPE
int main()
{
int toto = 42;
double tata = 84;
foobar(toto);
foobar(tata);
}
Mais ne faites pas ça chez vous ! Ce n’est pas quelque chose qu’on veut faire de nos jours (surtout la partie #include <foobar.cpp>). Aussi, notez que ce code utilise la fonctionnalité des surcharges de fonctions, propre au C++, et que donc ce code ne compile pas en C.
De notre point de vue moderne, cela peut sembler très limité et sujet à erreurs. Mais la chose intéressante à retenir est que puisque les templates étaient utilisés avec des macros avant même le C++, elles pouvaient être utilisées au début du C++ et donc permettre à l’équipe de design du langage de gagner de l’expérience avant son implémentation réelle.
Timing
Les templates ont été introduits avec la version 3.0 du langage, en octobre 1991. Dans The Design and Evolution of C++, Stroustrup révèle que c’était une erreur de les introduire aussi tard, et qu’en rétrospective il aurait été préférable de l’introduire dans la version 2.0 (juin 1989) quitte à mettre de côté d’autres fonctionnalités moins importantes, comme l’héritage multiple :
Aussi, ajouter l’héritage multiple dans la Version 2.0 était une erreur. L’héritage multiple a sa place en C++, mais est beaucoup moins importante que les types paramétrés — et pour certaines personnes, les types paramétrés le sont encore moins que les exceptions.
— Bjarne Stroustrup, The Design and Evolution of C++, chapitre 12: Multiple Inheritance, §1 – Introduction
Avec le recul d’aujourd’hui, il est clair que Stroustrup avait raison et que les template ont impacté le paysage du C++ beaucoup, beaucoup plus que l’héritage multiple.
Cet ajout est arrivé tard car il était très chronophage pour les concepteurs d’explorer les designs et les soucis potentiels d’implémentation.
Besoins et objectifs
Le besoin originel pour les templates était de paramétrer les classes de conteneurs. Pour ce travail, les macros étaient trop limitées. Elles ne respectaient pas les périmètres de nommage et interagissaient très mal avec les outils (en particulier les debuggers). Avant les templates C++, il était très difficile de maintenir du code qui utilisait des type paramétrés, nécessitait de code dans un niveau d’abstraction très bas et on devait ajouter chaque instance de type paramétré à la main.
Les premières inquiétudes concernant les templates étaient les suivantes : est-ce que les templates seraient aussi faciles à utiliser que les objets codés à la main ? Est-ce que les temps de compilation et de link seraient significativement impactés ? Et est-ce que ce serait facilement portable ?
Le processus de développement des templates
La dernière fois nous avions vu l’origine des templates, l’idée de départ et la note d’intention. Cette semaine nous allons voir comment les template ont été construit et comment ils évoluent encore aujourd’hui.
Syntaxe
Les chevrons
Concevoir la syntaxe d’une fonctionnalité n’est pas aisé et nécessite beaucoup de questionnement.
Le choix des chevrons <...> pour les paramètres de template a été fait parce que même si les parenthèses auraient été plus pratique pour les analyseurs, elles sont très utilisées en C++, et les chevrons sont plus plaisants à lire dans ce contexte.
Ceci dit, cela pose des problèmes pour les chevrons imbriqués, comme ceci :
List<List<int>> a;
Dans ce petit bout de code, au début du C++, vous auriez eu une erreur de compilation car les chevrons fermant >> auraient été perçu comme l’opérateur de flux operator>>() et non comme deux chevrons fermants.
Depuis le C++141, une motion lexicale a été ajoutée pour prendre cela en compte et ne plus le considérer comme une erreur de compilation.
L’argument de template
Au départ, l’argument de template aurait été placé juste après l’objet qu’on template :
class Foo<class T>
{
// ...
};
Mais cela posait deux problèmes :
- C’est assez dur à lire pour les analyseurs automatiques et pour les humains. Comme l’indication qu’il s’agit d’un template est imbriqué dans la définition de l’objet, c’est un peu difficile à détecter.
- Dans le cas des fonctions templatées, le type templaté peut être utilisé avant d’être déclaré, comme ceci:
T at<class T>(const std::vector<T>& v, size_t index) { return v[index]; }. CommeTest le type de retour il est vu (par les analyseurs automatiques) avant même qu’on sache qu’il s’agit d’un type templaté.
Ces deux problèmes sont réglés si on déclare le template avant l’objet, comme ceci :
template<class T> class Foo
{
// ...
};
template<class T> T at(const std::vector<T>& v, size_t index) { return v[index]; }
Et c’est ce qui a été retenu.
Les contraintes sur les paramètres de template
En C++, les contraintes sur les paramètres des templates sont implicites2
Le dilemme suivant est apparu à la création des templates : est-ce qu’on doit rendre les contraintes explicites ou pas ?
Un exemple de contrainte explicite a été proposé comme ceci :
template < class T {
int operator==(const T&, const T&);
T& operator=(const T&);
bool operator<(const T&, int);
};
>
class Foo {
// ...
};
Mais cela a été jugé trop verbeux et il aurait fallu écrire plus de templates pour le même nombre de features au final. De plus, cela limite un peu trop fort les possibilités des classes qu’on implémente, excluant des implémentations qui auraient été tout à fait correcte sans elles3.
Cependant, l’idée d’avoir des contraintes explicites n’a pas été abandonnée, c’est juste que les exprimer ainsi n’était pas la bonne manière de faire.
Une autre manière de faire (qui a été envisagée) a été via des classes dérivées. En spécifiant que tel template doit dériver de telle classe, on obtient un moyen explicite d’ajouter des contraintes :
template <class T>
class TBase {
int operator==(const T&, const T&);
T& operator=(const T&);
bool operator<(const T&, int);
};
template <class T : TBase>
class Foo {
// ...
};
Cependant cette méthode créé plus de problèmes que cela n’en règle. Les développeurs sont, avec cette méthode, encouragés à exprimer les contraintes en tant que classes, menant à une sur-utilisation de l’héritage. Il y a une perte d’expressivité et de sens sémantique, parce que « T doit être comparable à une int » devient « T doit hériter de TBase ». De plus, vous ne pouvez pas exprimer des contraintes sur des types qui ne peuvent pas avoir de classe mère, comme int ou double.
Ce sont les raisons pour lesquelles nous n’avons pas eu de moyen d’exprimer des contraintes sur les paramètres de template pendant très longtemps4.
Mais tout vient à point à qui sait attendre, et le débat a été ranimé à la fin des années 2010, ce qui a mené à la création des Concepts en C++20 (c.f. Évolutions modernes – Concepts plus bas).
La génération d’objets templatés
La manière dont les templates sont compilés est assez simple : pour chaque jeu de paramètres de templates (pour un objet templaté donné), le compilateur va généré autant d’implémentations de cet objet en utilisant explicitement ce jeu de paramètres.
Donc, écrire ceci :
template <class T> class Foo { /* ... do things with T ... */ };
template <class T, class U> class Bar { /* ... do things with T and U... */ };
Foo<int> foo1;
Foo<double> foo2;
Bar<int, int> bar1;
Bar<int, double> bar2;
Bar<double, double> bar3;
Bar< Foo<int>, Foo<long> > bar4;
Est la même chose qu’écrire cela :
class Foo_int { /* ... do things with int ... */ };
class Foo_double { /* ... do things with double ... */ };
class Foo_long { /* ... do things with long ... */ };
class Bar_int_int { /* ... do things with int and int... */ };
class Bar_int_double { /* ... do things with int and double... */ };
class Bar_double_double { /* ... do things with double and double... */ };
class Bar_Foo_int_Foo_long { /* ... do things with Foo_int and Foo_long... */ };
Foo_int foo1;
Foo_double foo2;
Bar_int_int bar1;
Bar_int_double bar2;
Bar_double_double bar3;
Bar_Foo_int_Foo_long bar4;
… sauf que c’est plus verbeux et moins générique.
Classes templatées
À la base, les templates ont été imaginés pour les classes, en particulier pour l’implémentation de conteneurs standards. Ils ont été pensés pour être aussi simples à utiliser que les classes standardes et aussi performantes que les macros. Ces deux faits ont été décidés pour que les tableaux bas niveaux puissent être abandonnés quand ils n’étaient pas spécifiquement utiles (comme en programmation très bas niveau) et que les conteneurs templatés soient préférés pour les plus hauts niveaux.
En plus des paramètres typés, les templates peuvent avoir des paramètres non-typés, comme suit :
template <class T, int Size>
class MyContainer {
T m_collection[Size];
int m_size;
public:
MyContainer(): m_size(Size) {}
// ...
};
Cela a été conçu pour permettre d’utiliser des conteneurs de taille statique. Avoir la taille directement dans le type du conteneur permet d’avoir une implémentation plus performante.
class Foo;
int main()
{
Foo[700] fooTable; // low-level container
MyContainer<Foo, 700> fooCnt; // high-level container, as efficient as the previous one
}
Fonctions templatées
L’idée des fonctions templatées est venue directement du besoin d’avoir des méthodes de classe templatées et de l’idée selon laquelle les fonctions templatées sont dans la continuité logique des classes templatées.
Aujourd’hui, l’exemple le plus classique de fonction templaté auquel on peut penser sont les algorithmes de la STL (std::find(), std::find_first_of(), std::merge(), etc.). Même à sa création, les algorithmes de la STL n’existaient pas, c’était ce genre de fonctions qui a inspiré les fonctions templatées (la plus symbolique étant sort()).
La principale problématique a été de savoir comment déduire les paramètres du template à partir des arguments et du type de retour sans avoir à les spécifier à chaque appel.
Dans ce contexte, il a été décidé que les arguments de templates pouvaient à la fois être déduits (quand cela est possible) et spécifiés (quand c’est nécessaire). C’est extrêmement utile pour spécifier une valeur de retour, car celle-ci ne peut pas toujours être déduite, comme dans l’exemple suivant :
template <class TTo, class TFrom>
TTo convert(TFrom val)
{
return val;
}
int main()
{
int val = 4;
convert(val); // Error: TTo is ambiguous
convert<double, int>(val) // Correct: TTo is double; TFrom is int
convert<double>(val) // Correct: TTo is double; TFrom is int;
}
Comme vous pouvez le voir ligne 12, les arguments de template peuvent être en partie (ou en intégralité) ignorés, en partant du dernier.
La manière dont les templates sont générés (confère à la section La génération d’objets templatés ci-avant) fait qu’ils fonctionnent parfaitement bien avec la surcharge de fonctions. La seule subtilité intervient quand on a à la fois des surcharges templatées et des surcharges non-templatées. Dans ce cas, les surcharges non-templatées sont prioritaires sur celles qui sont templatées, s’il y a une correspondance parfaite. Sinon, on prend la version templatée s’il est possible d’avoir une correspondance parfaite. Sinon, on résout la surcharge comme une surcharge ordinaire.
Instanciation de templates
Au tout début, l’instanciation explicite de templates n’était pas vraiment envisagée. C’était parce que cela pouvait créer des problèmes complexes à résoudre dans certaines circonstances spécifiques. Par exemple : si deux parties (sans lien) d’un code indiquent chacune qu’elles veulent la même instanciation d’un objet templaté, ce qui aurait besoin d’être fait sans réplication de code et sans gêner le link dynamique. C’est pourquoi au début, il semblait préférable de n’avoir que des instanciations implicites.
La première instanciation automatique de template s’est déroulée ainsi : quand le linkeur est lancé, il cherche les instanciations de template manquantes. Il rappelle alors le compilateur pour qu’il les génère. On relance alors le linkeur, qui cherche alors de nouveau les instanciations manquantes, et ainsi de suite jusqu’à ce qu’on ait toutes les instanciations de template dont on a besoin.
Cependant, cette manière de faire avait plusieurs soucis, notamment celui d’être très peu performante (puisqu’on fait beaucoup de va-et-viens entre le compilateur et le linkeur).
C’est pour mitiger ce problème que les instanciations de template explicite ont finalement été introduites.
Le développement des instanciations de templates a eu beaucoup d’autres soucis et écueils, comme le point d’instanciation (aussi appelé « le problème des noms », c’est-à-dire localiser précisément à quelle déclaration les noms invoqués dans un template font référence), les problèmes de dépendance, la résolution d’ambiguïtés, etc. Les évoquer tous dans le détail requerrait un article dédié.
Évolutions modernes
Les templates sont une fonctionnalité qui a continué d’évoluer alors même qu’on entrait dans l’ère moderne du C++ (qui commença avec le C++11).
Templates variadiques
Les templates variadiques sont des templates qui ont au moins un paquet de paramètres. Un paquet de paramètre (parameter pack en VO) est une manière d’indiquer qu’une fonction ou un template a un nombre variable de paramètres.
Par exemple, la fonction suivante utiliser un paquet de paramètres :
void foobar(int args...);
Et peut être appelée avec n’importe quel nombre d’argument (mais toujours au moins 1) :
foobar(1);
foobar(42, 666);
foobar(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16);
Les templates variadiques permettent la même chose, mais avec des types différents pour chaque paramètre.
Avec cela, on peut écrire des fonctions beaucoup plus génériques. Par exemple :
#include <iostream>
struct MyLogger
{
static int log_counter;
template<typename THead>
static void log(const THead& h)
{
std::cout << "[" << (log_counter++) << "] " << h << std::endl;
}
template<typename THead, typename ...TTail>
static void log(const THead& h, const TTail& ...t)
{
log(h);
log(t...);
}
};
int MyLogger::log_counter = 0;
int main()
{
MyLogger::log(1,2,3,"FOO");
MyLogger::log('f', 4.2);
}
Ce code génère la sortie suivante :
[0] 1
[1] 2
[2] 3
[3] FOO
[4] f
[5] 4.2On peut aisément supposer que la motivation derrière les templates variadiques (et les paquets de paramètres) est de pouvoir implémenter des fonctions encore plus genériques, au détriment parfois du volume de code généré (en l’occurrence, dans l’exemple précédent, la classe MyLogger a 8 surcharges de la fonction log5).
Vous trouverez plus de détails sur cette page : Parameter pack (since C++11) – cppreference.com.
Concepts
Les concepts sont une fonctionnalité introduite en C++20 qui vise à donner au développeur une manière de déclarer des contraintes sur les paramètres d’un template. Cela mène à du code plus clair (avec un plus haut niveau d’abstraction) et des messages d’erreur moins abscons.
Par exemple, voici une déclaration de concept :
template<typename T_>
concept Addable = requires(T_ a, T_ b)
{
a + b;
};
Et un exemple de son utilisation :
template<typename T_>
requires Addable<T_>
T_ foo(T_ a, T_ b);
template<typename T_>
T_ bar(T_ a, T_ b) requires Addable<T_>;
auto l = []<typename T_> requires Addable<T_> (T_ a, T_ b) {};
Avant cela, les erreurs de compilations liées à des templates était à peine lisible. Les concepts sont devenus (au cours des années précédant le C++20) une fonctionnalité très attendue.
Un bon aperçu des concept est trouvable sur le blog d’Oleksandr Koval : All C++20 core language features with examples | Oleksandr Koval’s blog (oleksandrkvl.github.io).
Guides de déduction
Les guides de déduction de templates sont une fonctionnalité du C++17 et sont des motifs qui, associés à un objet templaté qui indiquent au compilateur comment interpréter les paramètres (et leur type).
Par exemple :
template<typename T_>
struct Foo
{
T_ t;
};
Foo(const char *) -> Foo<std::string>;
Foo foo{"A String"};
Dans ce code, l’objet foo est un Foo<std::string> et non un Foo<const char*> comme on pourrait éventuellement le penser. De ce fait, foo.t est une std::string. C’est grâce à l’indication qu’on laisse sous la forme d’un guide de déduction, indiquant au compilateur que quand on utilise le type const char* on veut utiliser l’instanciation std::string du template.
C’est particulièrement utile pour des objets comme les vecteurs, qui peuvent ainsi avoir ce genre de constructeur :
template<typename Iterator> vector(Iterator b, Iterator e) -> vector<typename std::iterator_traits<Iterator>::value_type>;
De ce fait, si on appelle le constructeur du vecteur avec un itérateur, le compilateur comprendra qu’on veut non pas un vecteur d’itérateurs, mais un vecteur contenant des objets de même type que celui pointe par l’itérateur.
Substitution Failure Is Not An Error
L’échec de substitution n’est pas une erreur (Substitution Failure Is Not An Error, ou SFINAE parce que c’est un nom beaucoup trop long) est une règle qui s’applique pendant la résolution d’une fonction templatée qui possède plusieurs surcharges.
Elle signifie que si la résolution du type (déduit ou spécifié) du template d’un paramètre échoue, alors la spécialisation est mise de côté sans générer d’erreur (et on continue d’essayer de résoudre le template normalement).
Par exemple, prenons le code suivant :
struct Foo {};
struct Bar { Bar(Foo){} }; // Bar can be created from Foo
template <class T>
auto f(T a, T b) -> decltype(a+b); // 1st overload
Foo f(Bar, Bar); // 2nd overload
Foo a, b;
Foo x3 = f(a, b);
Instinctivement, on pourrait se dire que c’est la première surcharge qui est appelée ligne 10 (parce que l’instanciation qui utilise Foo en tant que T est une surcharge plus adéquate que l’autre, qui nécessite une conversion).
Cependant, l’expression (a+b) n’est pas solvable pour le type Foo. Mais à la place de générer une erreur de compilation (du type « pas d’opérateur ‘+’ n’a été trouvé pour Foo ») cette surcharge est mise de côté. Il ne reste plus que l’autre surcharge, qui fonctionne parce qu’on peut convertir implicitement un Foo en Bar.
Ce genre de substitution se produit pour tous les types utilisés dans les types de fonction et pour tous les types utilisés dans les déclarations de paramètres templatés. Depuis le C++11, cela se produit également pour toutes les expressions utilisées dans le type d’une fonction et toutes les expressions utilisées dans les déclarations de paramètres templatés. Depuis le C++20, cela se produit aussi pour toutes les expressions utilisées dans les spécifieurs explicites.
La documentation complète du SFINAE se trouve là : SFINAE – cppreference.com.
Autres features en C++20
Les templates continuent toujours d’évoluer aujourd’hui. Voici une petite liste des fonctionnalités concernant les templates qui sont apparue en C++20 et auxquelles je n’ai pas pu faire une place dans cet article :
- Les listes de paramètres templatés pour les lambdas génériques. Parfois les lambdas génériques sont trop génériques. Le C++20 permet d’utiliser la syntaxe familière de fonctions templatées pour introduire directement des noms de type.
- La déduction d’argument de template de classe pour les agrégats. En C++17 on avait besoin d’expliciter des guides de déduction pour la déduction d’argument de template avec les agrégats. Plus maintenant.
- Les classes dans des paramètres de template non-typés. Les paramètres de template non-typés peuvent maintenant être des classes littérales.
- Les paramètres des template non-typé généralisés. Les paramètres des template non-typé sont généralisés aux soi-disants type structuraux.
Exceptions et templates : les deux revers d’une même médaille
Je n’ai pas parlé d’exceptions dans cet article, mais pour Stroustrup, les exceptions et les templates sont des fonctionnalités complémentaires :
Dans ma tête, les templates et les exceptions sont deux revers d’une même médaille : les templates permettent de réduire le nombre d’erreurs d’exécution en étendant le panel de problèmes que la vérification statique de type peut résoudre ; les exceptions fournissent un mécanisme pour traiter les erreurs d’exécution restantes. Les templates font que le traitement des exceptions est faisable en réduisant le besoin de gérer des erreurs à l’exécution, ne laissant que les cas essentiels. Les exceptions font que les librairies générales basées sur des templates sont gérables en donnant à ces librairies une manière de remonter des erreurs.
— Bjarne Stroustrup, The Design And Evolution Of C++, Chapitre 15 : Templates, §1 – Introduction
Donc, par construction, les templates et les exceptions sont liées, en plus d’élever le niveau d’abstraction du code où elles sont employées.
Cependant, les exceptions et les templates (surtout les templates) ont évolué depuis, donc je pense que cela n’est plus trop vrai aujourd’hui.
Conclusion
D’après moi, les templates sont le plus gros poisson dans le lac métaphorique qu’est le C++. On n’en parlera jamais assez, et je pense qu’ils continueront d’évoluer pour des décénnies encore.
Il en est ainsi car, dans le C++ moderne, une des idées-clés est qu’on souhaite écrire des intentions plutôt que des actions. Nous voulons un niveau d’abstraction toujours plus élevé et plus de métaprogrammation. Ainsi, il est normal que les templates soient au coeur des évolutions actuelles.
Merci de votre attention et à la semaine prochaine !
Article original : [History of C++] Templates: from C-style macros to concepts | Belay the C++ (belaycpp.com)
Traductrice : Chloé Lourseyre
Addenda
Notes
1 – J’ai réussi à isoler le changement dans le compilateur de GCC à la version 6 ([https://godbolt.org/z/vndGdd7Wh][11]), suggérant que ça a effectivement été pris en compte lors du passage au C++14. J’ai réussi à observer la même chose auprès de clang, à la version 6 ([https://godbolt.org/z/ssfxvb4cM][12]), ce qui confirme cette hypothèse.
2 – On appelle ça le duck-typing (le typage-canard). Si ça ressemble à un canard, que ça nage comme un canard et que ça cancane comme un canard, alors c’est probablement un canard.
3 – Je n’ai cependant pas d’exemple concret a présenter pour illustrer cette assertion et je ne fais que plus ou moins paraphraser Stroustrup sur le sujet. Cependant, l’idée d’avoir des contraintes implémentées par l’utilisateur ferme des portes dont vous ne saviez pas qu’elles existaient et qui pourraient tout à fait être exploitées.
4 – Il y a eu d’autres essais pour exprimer des contraintes, mais sans succès. Vous pouvez avoir plus de détails sur ces essais au paragraphe §15.4 de Stroustrup: The Design and Evolution of C++.
5 – Ces instanciations sont (d’après le code assembleur – Compiler Explorer (godbolt.org)):
– log(int);
– log(char[4]);
– log(char);
– log(double);
– log(int,int,int,char[4]);
– log(int,int,char[4]);
– log(int,char[4]);
– log(char,double);
Sources
Par ordre d’apparition :