Code de grande personne – le truc de Barton-Nackman

Cet article sera court et inspiré d'une des stratégies typiques de la bibliothèque Boost. Des thématiques passionnantes et stimulantes pour l'esprit, mais définitivement du code de grande personne.

Notez que le truc Barton-Nackman est un cas particulier d'application de l'idiome CRTP.

Il y a, au moment d'écrire ces lignes, une forte mode autour des schémas de conception en informatique. Les schémas de conception, en gros, sont des (bonnes) façons de faire habituellement transférables d'un langage de programmation à l'autre, bien qu'il arrive souvent que l'exigence de base soit que le langage soit orienté objet (OO).

Parmi les schémas de conception, on trouve ce qu'on nomme des idiomes, qui sont de bonnes pratiques qui peuvent ne pas être transférables à d'autres langages (toute technique exploitant l'idée de constante et de destructeur déterministe dans un langage comme C++ est non transférable tel quel à Java ou à C#, par exemple). Voici donc un petit article sur un idiome de programmation générique en C++ qu'on nomme le truc de Barton-Nackman, du nom de ses auteurs.

À la demande d'un ami (allo Lamine!) qui lit occasionnellement les articles sur h-deb et a la gentillesse de me faire un rapport critique et de souligner les coquilles (ce que je vous invite toutes et tous à faire!), j'ai choisi de mieux mettre en contexte ce truc plutôt que d'arriver à froid dans le sujet, intéressant mais quand même un peu corsé.

À quoi sert le truc?

En programmation orientée objet (POO), une classe enfant spécifie la ou les classe(s) dont elle dérive dès sa déclaration. En ce sens, il est légitime de dire qu'en POO, un enfant connaît ses parents mais un parent ne connaît jamais ses enfants.

Cependant, la métaprogrammation que permet la programmation générique (et surtout les templates de C++, qui constituent un véritable langage complet au sens de Turing, contrairement aux generics de Java et aux Generics de C#) nous offre la latitude d'exprimer des programmes à plusieurs niveaux, de manière à informer, dans certaines circonstances, un parent de l'existence de son enfant.

Pour donner un exemple simple (bien que d'une utilité suspecte) du truc, supposons que la pratique d'une entreprise soit d'utiliser Afficher(x) pour projeter x, quel que soit son type, à la console. Le programme principal du programme proposé à droite en est un exemple.

Si projeter un objet à la console implique l'écrire sur std::cout, alors le travail fait par afficher est le même pour tout type affichable. Est affichable qui peut être projeté à la console, et est projetable à la console qui peut être écrit sur un flux en sortie tel que std::cout. Conséquemment, dans la programme à droite, un(e) informaticien(ne) consciencieuse/ consciencieux a écrit l'opérateur d'écriture sur un flux pour le type Entier. Ce qui manque, évidemment, est la fonction Afficher() pour un type donné qui projette une instance de ce type sur std::cout.

Il se peut qu'un programme ait des types pour lesquels l'opération de projection sur un flux n'a pas de sens. On voudrait restreindre l'opération Afficher() aux seuls types qui se disent Affichables.

Ce que l'exemple montre avec le truc Barton-Nackman, c'est qu'il est possible :

  • De définir un parent générique basé sur le type de l'un de ses enfants (ici, le parent est Affichable et l'enfant est, au sens générique, E). Le parent, en fait, ne sait pas que le type auquel il s'applique (E) est son enfant – c'est une particularité spécifique du truc qu'on nomme le Curiously Recurring Template Pattern, ou simplement l'idiome CRTP
  • Que le parent générique peut définir (en les spécifiant friend, ce qui indique au système que même si ces fonctions sont déclarées dans la classe, elles ne sont pas des méthodes mais bien des fonctions globales ajoutées à son interface!) des fonctions globales applicables au type de son enfant; et donc
  • Que l'enfant peut voir son interface étendue d'un certain nombre de fonctions globales de par la connaissance qu'a son parent de lui.

Pour que cela fonctionne, l'enfant injecte son propre nom dans la déclaration de son parent (ici: Entier dérive de manière privée – on ne veut pas que le lien serve à des fins généralistes ou polymorphiques, après tout – de Affichable<Entier>). Cela se tient du fait que le nom de l'enfant est connu du compilateur avant que le compilateur ne prenne conscience du nom du parent.

#include <iostream>
using namespace std;
template <class E>
   struct Affichable
   {
      friend void Afficher(const E &e)
         { cout << e; }
   };
class Entier
   : Affichable<Entier>
{
   int val;
public:
   Entier(int val) noexcept
      : val{val}
   {
   }
   int valeur() const noexcept
      { return val; }
};
ostream& operator<<(ostream &os, const Entier &e)
   { return os << e.valeur(); }
int main()
{
   Entier e = 3;
   Afficher(e);
}

Il n'y a aucun lien structurel entre Affichable<X> et Affichable<Y> si X et Y sont différents; l'idée de dériver de manière privée d'une classe servant aux fins du truc Barton-Nackman n'est pas liée à la généralisation ou aux similitudes structurelles mais bien à l'extension, sur une base générique, de l'interface de l'enfant.

Par cette technique, il est possible de construire plusieurs nouvelles opérations sur un type si certaines opérations sont déjà en place. De l'extension par réutilisation, en somme.

Exemple concret

Si vous souhaitez en savoir plus sur cette manière de définir les opérateurs relationnels, voir http://www.drdobbs.com/cpp/concrete-examples-of-orderings/240148718 par Andrew Koenig qui décrit l'ordonnancement sur des std::pair.

Présumons l'existence d'un type T sur lequel est défini un opérateur < duquel découle une relation d'ordre au sens faible (Strict Weak Ordering). On pourrait vouloir compléter le portrait à l'aide des opérateurs <=, > et >= (ce qui serait souhaitable pour fins de convivialité envers les utilisateurs de ce type), mais il est aussi possible de définir ces trois opérateurs à partir de la définition de l'opérateur < sans réelle perte d'efficacité.

L'écriture de ces opérateurs est d'ailleurs relativement simple :

Opérateur Définition à partir de l'opérateur <
Opérateur >
//
// a > b signifie b < a
//
bool operator>(const T &a, const T &b)
   { return b < a; }
Opérateur <=
//
// a <= b signifie !(b < a)
//
bool operator<=(const T &a, const T &b)
   { return !(b < a); }
Opérateur >=
//
// a >= b signifie !(a < b)
//
bool operator>=(const T &a, const T &b)
   { return !(a < b); }

Dans chaque cas, le coût supplémentaire est microscopique (dans la mesure où l'opérateur < est correctement écrit), se limitant dans le pire cas à une négation logique. Il existe des cas où il serait préférable de réécrire chacun de ces opérateurs sur une base individuelle, mais cette définition devrait suffire dans la majorité des cas.

Il est envisageable d'écrire ces opérateurs pour chaque classe (à la limite par copier/ coller), mais cela risquerait d'introduire des erreurs bêtes et difficiles à dépister. On voudrait plutôt dire, par exemple, qu'un type donné permet une relation d'équivalence dans la mesure où il expose un opérateur < correctement écrit.

La manière typique de catégoriser une classe est de la faire dériver d'une classe représentant la catégorie visée. Ici, si l'objectif est de définir une classe nombre (par exemple) comme permettant une relation d'équivalence (au sens exprimé plus haut) et si equivalence était une classe de l'espace nommé relation, alors on voudrait définir nombre comme dérivant de relation::ordonnancement.

Le problème est que la relation d'équivalence se définit sur un type et que, comme le dit la maxime OO bien connue, en situation d'héritage, chaque enfant connaît ses parents mais un parent ne connaît pas ses enfants. La question devient donc: comment construire correctement une classe définissant une relation d'équivalence pour ses éventuels enfants?

Le truc de Barton-Nackman

C'est ici qu'entre en scène le truc de Barton-Nackman, un cas particulier de l'idiome tout à fait charmant Curiously Recurring Template Pattern (CRTP).

Cette technique, à la fois simple et subtile, permet de définir dans un parent des opérations génériques (et pas seulement des opérateurs, même si c'est le cas classique par lequel le truc est décrit, ici comme ailleurs) à partir du type de ses enfants, ce qui constitue une forme de polymorphisme à la compilation. Nous examinerons cette technique en l'appliquant à notre problème bien concret.

La classe relation::ordonnancement est définie comme une classe générique applicable au type T et qui exprime, tel que promis, les opérateurs <=, > et >= sur deux opérandes constantes de type T en fonction de l'opérateur < applicable à T.

L'expression de ces opérateurs pour la classe relation::ordonnancement rejoint directement celle annoncée plus haut, et est aussi efficace que possible dans un cas général. Le critère d'efficacité est important: une implémentation générique mais inefficace restera le plus souvent inutilisée, parce qu'inutilisable en pratique.

Remarquez, et c'est important ici, que les opérateurs relationnels sont des opérateurs binaires (à deux opérandes) et sont exposés dans la classe relation::ordonnancement sous le forme de fonctions globales, et ce bien qu'elles soient définies à l'intérieur de la classe. La mention friend précédant chacune des définitions joue ce rôle et permet au compilateur de distinguer les opérateurs en tant que fonctions globales (avec deux opérandes explicitement indiqués) des mêmes opérateurs en tant que méthodes d'instance (avec opérande de gauche implicite).

La raison pour laquelle il est important que ces opérateurs soient des fonctions globales est que s'il s'agissait de méthodes d'instance, alors elles ne seraient pas définies sur des instances de T mais bien sur des instances de relation::ordonnancement<T> ce qui constituerait un glissement sémantique néfaste dans notre cas.

La classe nombre pour laquelle nous voudrons définir implicitement une relation d'équivalence (dans les termes de la classe relation::ordonnancement) se définira quant à celle comme suit :

namespace relation
{
   //
   // ordonnancement<T> définit une relation d'équivalence
   // pour T si T::operator< (const T&) const existe.
   //
   template <class T>
      struct ordonnancement
      {
         friend bool operator>(const T &a, const T &b)
            { return b < a; }
         friend bool operator<=(const T &a, const T &b)
            { return !(b < a); }
         friend bool operator>=(const T &a, const T &b)
            { return !(a < b); }
      };
}
class nombre
   : relation::ordonnancement<nombre>
{
   int valeur_;
public:
   nombre(int n = 0) noexcept
      : valeur_{n}
   {
   }
   //
   // La sainte-trinité (constructeur de copie,
   // affectation, destructeur) est Ok telle
   // quelle; on ne les réécrit pas.
   //
   int valeur() const noexcept
      { return valeur_; }
   friend bool operator<(const nombre &n0, const nombre &n1) noexcept
      { return n0.valeur() < n1.valeur(); }
};
#include <iosfwd>
// implémentation évidente; je vous laisse la faire
std::ostream & operator<<(std::ostream&, const nombre&);

Les éléments essentiels apparaissent en caractères gras. Notez que l'opérateur < est ici défini sous forme de fonction globale (suggestion du sympathique François-Xavier Bourlet), par souci d'homogénéité, mais dans ce cas une méthode d'instance aurait donné les mêmes résultats.

Notez tout d'abord que l'opérateur < est défini sur nombre, remplissant ainsi le contrat de cette classe (sa classe parent, relation::ordonnancement<nombre>, en dépend). L'implémentation de l'opérateur est très simple dans ce cas-ci mais toute implémentation sémantiquement correcte aurait fait l'affaire.

C'est d'ailleurs là l'un de ces cas un peu particuliers où l'héritage privé ne peut être remplacé par une stratégie de composition.

Ensuite, remarquez que nombre dérive de manière privée (et non pas publique) de relation::ordonnancement<nombre>. L'intention ici est de procéder à de l'héritage d'implémentation stricte, pas à une forme ou l'autre de design visant une éventuelle utilisation polymorphique.

Enfin, et c'est la nature de l'idiome CRTP, la classe parent (générique) se voit injecter à l'instanciation (au sens de la génération par le compilateur de la classe à laquelle s'applique le template) le type de son enfant. Cette technique est possible parce que le nom de l'enfant apparaît avant le nom du parent et existe donc au moment où le parent est généré par le compilateur.

Notez que la classe relation::ordonnancement<nombre> est une classe comme une autre; on aurait pu la nommer rel_ord_nb si notre objectif n'avait pas été de construire de manière générique des opérateurs sur le type de l'enfant. Il n'y a donc pas de circularité entre la définition du parent et de l'enfant, puisque le parent ne connaît toujours pas l'enfant (et ne le contient pas). L'enfant contient le parent, comme à l'habitude. Par contre, l'instanciation de la classe parent, qui la fait passer de générique à existante concrètement, entraîne la génération d'un ensemble de fonctions globales applicables à un autre type, qui (surprise!) se trouve à être l'une de ses classes dérivées.

Le petit programme ci-dessous montre comment il est possible de tester la classe nombre telle que définie à l'aide de cette stratégie.

#include <iostream>
using namespace std;
// ...
int main()
{
   nombre n0{4}, n1{4};
   if (n0 <  n1)
      cout << n0 << "< " << n1 << endl;
   if (n0 <= n1)
      cout << n0 << "<=" << n1 << endl;
   if (n0 >  n1)
      cout << n0 << "> " << n1 << endl;
   if (n0 >= n1)
      cout << n0 << ">=" << n1 << endl;
}

Vous pouvez bien sûr modifier les valeurs initiales de n0 et de n1 (3 et 4, disons, puis 4 et 3) pour tester tous les cas pertinents.

Lectures complémentaires

Article de 2001 sur l'injection de classes parents par voie de programmation générique, par Douglas Gregor, Sibylle Schupp et David Musser : http://www.osl.iu.edu/publications/prints/2001/GSM01a.pdf

En 2015, Arne Mertz décrit Boost.Operators, qui offrent essentiellement la fonctionnalité décrite ici : http://arne-mertz.de/2015/02/operator-overloading-introduction-to-boost-operators-part-1/


Valid XHTML 1.0 Transitional

CSS Valide !