Appliquer, rincer et recommencer
— Notice d’utilisation de mon shampoing
Après les espaces de noms, l’autre « coup de génie » de Python a été les itérateurs et les générateurs. Depuis leur introduction dans Python 2.2, ils ont envahi et unifié le langage. Ils favorisent un style de programmation à faible couplage, simple à écrire, facile à lire, souple et extensible.
Pour résumer, le protocole d’itéraction implique deux parties : un producteur et un consommateur. Un objet itérable dit « je sais comment fournir des données élément par élément » et le consommateur dit « donne-moi les données élément par élément en m’indiquant quand tu auras fini ».
La connexion producteur/consommateur peut prendre différentes formes. Dans le cas le plus simple, une fonction ou un constructeur enveloppe un objet itérable. Dans sorted(set(‘simsalabim’)), par exemple, le constructeur d’ensemble parcourt tous les éléments de la chaîne itérable et la fonction sorted entoure l’objet ensemble itérable ainsi obtenu.
Outre les fonctions et les constructeurs, les instructions classiques de Python peuvent utiliser l’opérateur in pour parcourir les objets itérables. for ligne in mon_fichier: print ligne, par exemple, parcourt toutes les lignes d’un objet file itérable. De même, if element in sequence parcourt tous les éléments d’une séquence jusqu’à trouver une correspondance (ou atteindre la fin de cette séquence).
Ces deux formes de consommation du protocole d’itération utilisent implicitement le protocole, mais il existe également une forme explicite, plus souple mais moins souvent utilisée : on sauvegarde d’abord l’objet itérateur dans une variable, it = iter(ma_chaine), puis on utilise sa méthode next pour obtenir un élément, elem = it.next( ). Ces appels sont généralement enveloppés dans des instructions try/ except pour pouvoir capturer l’exception StopIteration lancée par l’itérateur lorsqu’il a fini de parcourir le flux de données.
Toutes ces approches ont tous les avantages des itérateurs, notamment un couplage et une consommation mémoire faibles. Le couplage faible apparaît clairement dans le premier exemple, où la fonction sorted, le type set et l’objet string se combinent alors qu’ils sont totalement indépendants les uns des autres. La faible consommation mémoire, quant à elle, est due à la structure du protocole d’itération, qui ne récupère qu’un élément à la fois. Les programmes qui utilisent des itérateurs consomment moins de ressources et s’adaptent mieux à un accroissement de charge que ceux qui utilisent des list.
Un objet voulant être itérable devrait implémenter une méthode __iter__ renvoyant un objet itérateur. Dans l’idéal, cet itérateur devrait être un autre objet que l’itérable, car cela permet de parcourir ce dernier avec plusieurs itérateurs. Il y a, cependant, des exceptions à cette règle générale : un objet file ne se prête pas à plusieurs itérations ; en ce cas, il est préférable que l’objet fichier soit son propre itérateur — quelle que soit l’instance f de file, iter(f) est f.
Un objet itérateur doit implémenter les méthodes next et __iter__. La première devrait lever l’exception StopIteration à la fin de l’itération ; ses appels suivants continueront à lever StopIteration (une fois terminée, elle reste terminée). La seconde devrait toujours renvoyer l’itérateur lui-même (__iter__ est une opération idempotente pour les itérateurs). Cela simplifie le code client en lui permettant de traiter les itérateurs et les itérables de la même façon (car tous les deux renvoient un itérateur en réponse à l’appel à iter).
La plupart des itérateurs ont un état interne leur permettant de renvoyer un nouvel élément à chaque appel. Les responsabilités que nous venons de décrire et ce besoin d’état interne semblent suggérer que la meilleure façon de créer des objets itérables consiste à utiliser des classes. Cette approche est évidente et explicite, mais elle est rarement utilisée (seules deux recettes de ce chapitre utilisent les classes).
Deux autres approches dominent. En partant de la constation que beaucoup de fonctions et de types attendent des paramètres itérables et renvoient des valeurs itérables, une approche évidente consiste à les relier comme des tubes et des filtres pour former de nouveaux outils. def uniq(seq): return sorted(set(seq)), par exemple, permet de créer directement un nouvel outil à partir de fonctions et de types existants. Comme en programmation fonctionnelle, le code ainsi produit est bref, lisible, très facile à déboguer et va souvent aussi vite qu’un programme compilé. Ce sont les avantages de cette approche qui ont motivé la création de itertools, un module complet pour la création d’itérateurs, qui est utilisé dans de nombreuses recettes de ce chapitre.
Si le problème ne peut pas être résolu en combinant des briques de base, l’autre approche consiste à écrire un générateur ; la recette 11.1 montre la facilité avec laquelle on peut en construire un. Le mot-clé yield permet de créer automatiquement un itérateur. Les objets itérateurs obtenus en appelant un générateur sont tous distincts, mémorisent leur état, disposent d’une méthode __iter__ idempotente et d’une méthode next qui lève StopIteration lorsqu’elle a fini et continue de le faire ensuite. En interne, Python s’occupe de tous ces détails. D’ailleurs, la plupart des recettes de ce chapitre utilisent ces générateurs si fascinants.
À partir de la version 2.4, l’omniprésence des itérateurs a encore franchi un pas supplémentaire avec l’introduction des expressions génératrices (les genexps dans le jargon Python). Une genexp peut être considérée comme une forme de liste en intension plus souple et moins consommatrice de mémoire. Il suffit de remplacer les crochets par des parenthèses pour qu’une expression produise un seul élément à la fois au lieu de les stocker tous en mémoire. Utilisées correctement (c’est-à-dire dans un contexte où elles sont consommées immédiatement, élément par élément), les genexps offre une clarté et une économie de mémoire remarquables : sum(x*x for x in xrange(10)), par exemple, est un excellent moyen d’exprimer la somme des carrés des dix premiers entiers naturels.
Paradoxalement, plus une idée est simple et générale, plus on peut l’utiliser de façon inattendue. Voici quelques exemples dans lesquels les itérateurs et les générateurs ont été poussés dans leurs derniers retranchements.
Comme l’opérateur yield a la propriété unique de stopper l’exécution, de mémoriser l’état et de reprendre ensuite, il n’est pas surprenant que l’on ait trouvé des techniques pour utiliser les générateurs comme des co-routines et des continuations. Le principe consiste à implémenter chaque routine comme un générateur et à utiliser une fonction répartiteur pour lancer les routines dans l’ordre. À chaque fois qu’il faut effectuer un basculement de tâche, les routines reviennent au répartiteur qui lance ou relance la routine suivante en appelant sa méthode next. Il y a quelques petites complications pour le lancement et la fin des routines, ainsi que pour le partage des données, mais elles peuvent toutes être résolues assez facilement, en tous cas plus simplement que les solutions à base de threads.
Lorsque certains outils peuvent être à la fois producteurs et consommateurs, il est naturel de vouloir les empiler comme des tubes ou des filtres. Bien que cette analogie puisse donner un découplage commode, il ne faut pas oublier que les modèles sous-jacents sont différents. Les itérateurs ne s’exécutent pas de façon autonome du début à la fin ; ils sont toujours sous le contrôle d’une couche plus externe qui leur demande des éléments un par un : rien ne se passe tant que cette couche n’a pas commencé à demander les éléments.
Lorsque l’on empile des outils (comme on l’a fait dans le premier exemple avec sorted, set et une chaîne), le code ressemble à ce que l’on obtient avec un langage de programmation fonctionnelle. Cette ressemblance n’est pas qu’apparente : les itérateurs réalisent certaines promesses des langages à évaluation paresseuse. Il est donc naturel d’emprunter certaines des techniques les plus intéressantes de ces langages, notamment de Haskell et SML.
L’une de ces techniques consiste à écrire des itérateurs qui produisent des flux infinis et à concentrer le code de contrôle dans une fonction externe. En programmation numérique, par exemple, on écrira un générateur produisant successivement de meilleures approximations d’un résultat attendu et on l’appellera à partir d’une fonction qui s’arrêtera lorsque deux approximations successives ont un écart correspondant à une certaine tolérance. Séparer le contrôle du calcul découple ces deux opérations, ce qui facilite leur écriture, leurs tests, leur débogage et leur réutilisation dans d’autres contextes.
Voici quelques extraits de code instructifs. Étudiez-les tous soigneusement, leur fonctionnement vous permettra de mieux comprendre comment relier des itérateurs pour résoudre des problèmes pratiques. Toutes ces lignes sont indépendantes les unes des autres :
La notion d’itérateurs réinitialisables revient très souvent à la surface puis s’enlise dans les sables mouvants. sys. stdin est un exemple typique d’itérable qui ne peut pas être redémarré, sauf si la session entière a été sauvegardée en mémoire. Lorsqu’un besoin maladif de réinitialisation apparaît, c’est sûrement l’indice qu’une list serait une structure de données plus appropriée.
Ce n’est pas parce que les itérateurs ne peuvent pas être réinitialisés qu’ils doivent être abandonnés au milieu du gué. Tirez parti de leur production paresseuse, à la demande, qui est l’une de leurs fonctionnalités essentielles. Après tout, c’est la raison pour laquelle l’instruction for autorise le mot-clé break.
itertools et ses dérivés (étudiez les recettes fournies avec sa documentation dans la Library Reference) s’exécutent quasiment à la vitesse d’un code compilé. Lorsque Python 2.4 a introduit le type de données natif set, j’ai comparé sa vitesse à la version en Python pur, sets.py, ce qui m’a permis de constater que certaines opérations ensemblistes (l’intersection, l’union, etc.) ne s’exécutaient que deux fois plus vite. Cela est dû au fait que sets.py utilise itertools, dont les performances sont exceptionnelles. Par conséquent, si vous voulez améliorer la vitesse d’exécution d’un programme Python, pensez à utiliser itertools avant de vous tourner vers des optimisations laborieuses ou des extensions écrites dans un langage compilé.
Vous avez besoin d’une progression arithmétique comme celle que fournit la fonction xrange prédéfinie, mais avec des valeurs flottantes (xrange ne fonctionne qu’avec des entiers).
Bien qu’aucune fonction prédéfinie ne propose des progressions arithmétiques avec les flottants, on peut facilement coder un générateur pour obtenir le même résultat :