Retour à l'accueil
Accueil Aide Rechercher Calendrier Identifiez-vous Inscrivez-vous
Bienvenue, Invité. Veuillez vous connecter ou vous inscrire.
Avez-vous perdu votre courriel d'activation?
24 Juin 2019 à 20:18

Connexion avec identifiant, mot de passe et durée de la session
Règlement | Grades du forum | L'équipe de modération | Album photo | Chat
Rechercher:     avancée
Forums Zelda Solarus  |  Jeux amateurs  |  Programmation  |  Topic: [C++] Générateurs 0 Membres et 1 Invité sur ce sujet.
Pages: [1] Imprimer
Auteur Sujet: [C++] Générateurs  (Lu 1575 fois)
Morwenn
Sheikah
*
Offline Offline

Messages: 3 266


And so what?


WWW Courriel
« le: 12 Juin 2012 à 22:21 »

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) [Select]
>>> for i in range(10):
...     print i
...

Le résultat obtenu en ligne de commande est le suivant :
Quote
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 :
Code: (C++) [Select]
#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) [Select]
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++) [Select]
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) [Select]
#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 :

Code: (C++) [Select]
#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 .___.
« Dernière édition: 15 Juin 2012 à 23:35 par Morwenn » Journalisée

Noxneo
Guest


Courriel
« Répondre #1 le: 23 Juin 2012 à 20:08 »

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 ^^
Journalisée
Morwenn
Sheikah
*
Offline Offline

Messages: 3 266


And so what?


WWW Courriel
« Répondre #2 le: 24 Juin 2012 à 13:15 »

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é
« Dernière édition: 17 Mars 2014 à 16:21 par Morwenn » Journalisée

Pages: [1] Imprimer 
Forums Zelda Solarus  |  Jeux amateurs  |  Programmation  |  Topic: [C++] Générateurs
Aller à:  

Propulsé par MySQL Propulsé par PHP Powered by SMF 2.0.15 | SMF © 2006, Simple Machines LLC XHTML 1.0 Transitionnel valide ! CSS valide !
Zelda Solarus 2009Skin par Eidarloy
Solarus-Games