[C++] Générateurs

Démarré par Morwenn, 12 Juin 2012 à 23:21

0 Membres et 1 Invité sur ce sujet

12 Juin 2012 à 23:21 Dernière édition: 16 Juin 2012 à 00:35 par Morwenn
J'aime toujours autant présent des trucs sales quand il s'agit de programmation, donc aujourd'hui, je me suis dit que je ne pouvais que vous parler de ça, ne serait-ce que parce que je trouve ça drôle.

Générateurs

Pour ceux qui ne savent pas ce qu'est un générateur, il s'agit d'une "fonction" qui, au lieu de retourner une table de valeurs, retourne en calculant au fur et à mesure ces valeurs. Ainsi, si on s'arrête avant la fin de l'itération, ça nous évite de calculer toutes les valeurs inutilisées.

Le principe est très utilisé dans le langage Python, notamment dans sa bibliothèque standard. Si vous n'avez rien compris à l'explication plus haut, de un, ça veut sans doute dire que j'explique mal, et de deux, vous pourrez sûrement trouver plus de docs en cherchant des renseignements sur les générateurs en Python ailleurs sur internet.

En C++

En C/C++, le principe des générateurs n'est pas directement intégré au langage, même s'il est possible d'en créer, notamment via des variables statiques et en suivant le principe des coroutines. Mais c'est le bordel, soyons honnête, et limité. Andrew Fedoniouk nous propose une extension au C++ des générateurs, librement inspiré de l'article précédent. Les deux sont très intéressants. Aussi, il existe un essai d'implémentation des coroutines dans une extension de la bibliothèque C++ Boost.

La fonction range

Je ne vais pas tenter de trouver un moyen générique de faire des coroutines ou des générateurs en C++ de manière classe ; d'autres s'y cassent déjà les dents à ma place. Ce que je vais proposer dans ce sujet, c'est de tenter une implémentation de la fonction Python range (ou xrange dans Python 2.x) qui permet de créer générativement une suite d'entiers, de la manière suivante :

Code (Python 3) Sélectionner

>>> for i in range(10):
...     print i
...


Le résultat obtenu en ligne de commande est le suivant :
Citation
0
1
2
3
4
5
6
7
8
9

Afin d'obtenir le même résultat en C++, et le fait d'une manière assez "Python", nous pourrions utiliser la nouvelle boucle for du C++11 (la même qu'en Java) afin d'avoir la syntaxe suivante :

#include <iostream>

int main()
{
   for (int i: range(10))
   {
       std::cout << i << std::endl;
   }
   return 0;
}


Implémentation

La première chose qu'il faut savoir, c'est qu'afin d'être itérable, le générateur range doit être un objet. Nous devrons donc créer une classe range. Ensuite, jetons un œil à la façon dont est décomposé le morceau de code suivant en étendant la boucle for C++11 à une boucle for traditionnelle :

Code (Boucle étendue) Sélectionner

int main()
{
   for (auto it = range(10).begin() ; it != range(10).end() ; ++it)
   {
       int i = *it;
       std::cout << i << std::endl;
   }
   return 0;
}


Oui, tout de suite, c'est moins lisible. Mais ça donne au moins une idée des fonctions à implémenter à notre classe range. Dans notre cas, ce seront les fonctions suivantes :

  • range(int)
  • begin()
  • end()
  • operator!=(const range&)
  • operator++()
  • operator*()
Jusque-là, ça allait. Maintenant, après avoir un peu regardé le tout, on sent rend compte que ça va être sale. Très sale...
C'est par ailleurs ce qui m'a amusé dans ce petit jeu. Voici donc l'implémentation que je propose pour notre générateur range :

Code (Générateur range en C++) Sélectionner

class range
{
   private:

       int i;         // Compteur
       const int val; // Valeur à atteindre

   public:

       range& begin()
       {
           return *this;
       }

       range& end()
       {
           return *this;
       }

       bool operator!=(const range&)
       {
           return i < val;
       }

       void operator++()
       {
           ++i;
       }

       int operator*()
       {
           return i;
       }
};


Notons que notre condition d'arrêt n'a absolument rien à voir entre l'égalité de notre instance de range avec une autre instance de la classe. Par conséquent, la fonction end() ne sert à rien, d'où le fait qu'elle renvoie une valeur au pif tout le temps (elle est cependant obligatoire pour que la boucle fonctionne et doit renvoyer un range&), et que l'opérateur de différence prenne un paramètre inutile...

C'est sale... mais c'est beau !

Donc oui, n'importe quel manuel vous apprenant à coder des itérateurs de classes risque de piquer une crise à la vue d'un code pareil ; ce qui est compréhensible. Ce qui est particulier dans notre cas, c'est que la classe est l'itérateur en elle-même et utilise le concept pour calculer ses valeurs au fur et à mesure. L'implémentation et les trucs utilisés sont assez moches, j'en conviens.

D'ailleurs, quitte à aimer le code moche et Python (qui a dit que c'était incompatible ?), autant rajouter une petite macro pour une plus belle utilisation :
Code (Macro) Sélectionner

#define in :


Et alors, enfin, nous pourrons avoir l'ultime satisfaction d'écrire du code comme celui-ci, assez semblable à du Python, que ce soit du point de vue de l'écriture ou du comportement, mais en C++ tout à fait légal :


#include <iostream>

int main()
{
   for (int i in range(10))
   {
       std::cout << i << std::endl;
   }
   return 0;
}


J'aime toujours ce principe d'utiliser un code complètement immonde pour proposer une interface sympathique aux personnes qui auront à l'utiliser. Dans un cas comme celui-ci, le tout est un véritable cache-immondice, mais j'apprécie de pouvoir utiliser des générateurs à la manière de Python. Je conviens ceci dit que leur écriture en devient plus fastidieuse :P


EDIT : Pour ceux que ça intéresserait, voici la version complète du générateur range en C++11, à la différence près qu'il ne peut pas prendre de pas négatif (il choisit le signe du pas en fonction des paramètres begin et end) :)

EDIT² : Et pour ceux ça intéresse toujours (il y en a ?), voici la fonction reversed, toujours de Python, et toujours en générateur.

EDIT encore : Bon, techniquement, j'ai réussi à faire des trucs encore plus immondes depuis dans le même registre, qui sont cools, utiles, et qui marchent très bien. Par contre, je suis moi-même impressionnée de la complexité des structures que j'ai dû utiliser pour faire des fonctions pareilles .___.

Rha j'ai raté ce topic, c'est de ma faute pour cliquer sur "Voir toutes mes réponses non lues" plutôt que "Voir tous mes sujets non lus"

Si vous aimez la beauté intrinsèque du concept de générateur, alors vous n'avez pas grand chose à faire dans le monde du C/C++ — allez plutôt fouiner du côté de Erlang, Haskell et companie qui satisfairont plus votre esthétisme de mathématicien (python est une excellente drogue passerelle, comme le dit Morwenn).

Mais implémenter ce genre de choses est effectivement un exercice marrant, merci Morwenn pour ce topic ^^

24 Juin 2012 à 14:15 #2 Dernière édition: 17 Mars 2014 à 16:21 par Morwenn
En fait, techniquement, le C++ reste le langage qui m'amuse le plus, mais je regrette en effet parfois qu'on ne puisse pas utiliser facilement des concepts d'autres langages, parce qu'ils ne sont pas implémentés (ici les générateurs, avec le yield à la Python, ce serait tranquille) ou juste pas compatible (LISP a une certaine beauté si on parle d'esthétique mathématique mais c'est franchement pas toujours compatible avec C++ sur le principe...).
Du coup, j'essaye toujours d'importer des fonctions que j'ai bien aimées dans d'autres langages. La dernière norme a en plus apporté les templates variadiques (ou elliptiques) qui permettent de faire des trucs assez tarés. On peut grâce à eux avoir des trucs sympas à utiliser, mais parfaitement immondes à implémenter (ici, la fonction chain, en bas de page).

Bref. Pour revenir aux générateurs, c'est vrai que Haskell permet de faire des générateurs de manière élégante et c'est cool.

Yoshi: Lien corrigé