Générateurs

Nous étudierons dans ce chapitre les générateurs, un nouveau type d’itérables.

Dessine-moi un générateur

Les générateurs sont donc des itérables, mais aussi des itérateurs, ce qui implique qu’ils se consomment quand on les parcourt (et que nous ne pouvons donc les parcourir qu’une seule fois).

Ils sont généralement créés par des fonctions construites à l’aide du mot clef yield. Par abus de langage ces fonctions génératrices sont parfois elles-mêmes appelées générateurs.

Le mot-clef yield

Un générateur est donc construit à partir d’une fonction. Pour être génératrice, une fonction doit contenir un ou plusieurs yield.

Lors de l’appel, la fonction retournera un générateur, et à chaque appel à la fonction builtin next sur ce générateur, le code jusqu’au prochain yield sera exécuté. Comme pour tout itérateur, la fonction next appelle la méthode spéciale __next__ du générateur.

yield peut-être ou non suivi d’une expression. La valeur retournée par next sera celle apposée au yield, ou None dans le cas où aucune valeur n’est spécifiée.

Un exemple pour mieux comprendre cela :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
>>> def function():
...     yield 4
...     yield
...     yield 'hej'
...
>>> gen = function()
>>> next(gen)
4
>>> next(gen)
None
>>> next(gen)
'hej'
>>> next(gen)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> list(gen) # Tout le générateur a été parcouru
[]

Ou avec un for :

1
2
3
4
5
6
>>> for i in function():
...     print(i)
...
4
None
hej

Il est aussi possible pour une fonction génératrice d’utiliser return, qui aura pour effet de le stopper (StopIteration). La valeur passée au return sera contenue dans l’exception levée.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
>>> def function():
...     yield 4
...     yield
...     return 2
...     yield 'hej'
...
>>> gen = function()
>>> next(gen)
4
>>> next(gen)
None
>>> next(gen)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration: 2

Le générateur en lui-même ne retourne rien (il n’est pas callable), il produit des valeurs à l’aide de yield. Pour bien faire la différence entre notre générateur et sa fonction génératrice, on peut regarder ce qu’en dit Python.

1
2
3
4
>>> gen
<generator object function at 0x7f008dfb0570>
>>> function
<function function at 0x7f008dce2ea0>

Bien sûr, notre générateur est très simpliste dans l’exemple, mais toutes les structures de contrôle du Python peuvent y être utilisées. De plus, le générateur peut aussi être paramétré via les arguments passés à la fonction. Voici un exemple un peu plus poussé avec un générateur produisant les n premiers termes d’une suite de Fibonacci débutant par a et b.

1
2
3
4
5
6
7
8
9
>>> def fibonacci(n, a=0, b=1):
...     for _ in range(n):
...         yield a
...         a, b = b, a + b
...
>>> list(fibonacci(10))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>> list(fibonacci(5, 6, 7))
[6, 7, 13, 20, 33]

Altérer un générateur avec send

Maintenant que nous savons créer des générateurs, nous allons voir qu’il est possible de communiquer avec eux après leur création.

Pour cela, les générateurs sont dotés d’une méthode send. Le paramètre reçu par cette méthode sera transmis au générateur. Mais comment le reçoit-il ?

Au moment où il arrive sur une instruction yield, le générateur se met en pause. Lors de l’itération suivante, l’exécution reprend au niveau de ce même yield. Quand ensuite vous appelez la méthode send du générateur, en lui précisant un argument, l’exécution reprend ; et yield retourne la valeur passée à send.

Attention donc, un appel à send produit une itération supplémentaire dans le générateur. send retourne alors la valeur de la prochaine itération comme le ferait next.

1
2
3
4
5
6
7
8
9
>>> gen = fibonacci(10)
>>> next(gen)
0
>>> next(gen)
1
>>> gen.send('test') # Le send consomme une itération
1
>>> next(gen)
2

Comme je le disais, une valeur peut-être retournée par l’instruction yield, c’est-à-dire dans le corps même de la fonction génératrice. Modifions quelque peu notre générateur fibonacci pour nous en apercevoir.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
>>> def fibonacci(n, a=0, b=1):
...     for _ in range(n):
...         ret = yield a
...         print('retour:', ret)
...         a, b = b, a + b
...
>>> gen = fibonacci(10)
>>> next(gen)
0
>>> next(gen)
retour: None
1
>>> gen.send('test')
retour: test
1
>>> next(gen)
retour: None
2

Nous pouvons voir que lors de notre premier next, aucun retour n’est imprimé : c’est normal, le générateur n’étant encore jamais passé dans un yield, nous ne sommes pas encore arrivés jusqu’au premier appel à print (qui se trouve après le premier yield).

Cela signifie aussi qu’il est impossible d’utiliser send avant le premier yield (puisqu’il n’existe aucun précédent yield qui retournerait la valeur).

1
2
3
4
5
>>> gen = fibonacci(10)
>>> gen.send('test')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can´t send non-None value to a just-started generator

Pour comprendre un peu mieux l’intérêt de send, nous allons implémenter une file (queue) par l’intermédiaire d’un générateur. Celle-ci sera construite à l’aide des arguments donnés à l’appel, retournera le premier élément à chaque itération (en le retirant de la file). On pourra aussi ajouter de nouveaux éléments à cette queue via send.

1
2
3
4
5
6
def queue(*args):
    elems = list(args)
    while elems:
        new = yield elems.pop(0)
        if new is not None:
            elems.append(new)

Testons un peu pour voir.

1
2
3
4
5
6
7
8
9
>>> q = queue('a', 'b', 'c')
>>> next(q)
'a'
>>> q.send('d')
'b'
>>> next(q)
'c'
>>> next(q)
'd'

Et si nous souhaitons itérer sur notre file :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
>>> q = queue('a', 'b', 'c')
>>> for letter in q:
...     if letter == 'a':
...         q.send('d')
...     print(letter)
...
'b'
a
c
d

Que se passe-t-il ? En fait, send consommant une itération, le b n’est pas obtenu via le for, mais en retour de send, et directement imprimé sur la sortie de l’interpréteur (avant même le print de a puisque le send est fait avant).

Nous pouvons assigner le retour de q.send afin d’éviter que l’interpréteur n’en imprime le résultat, mais cela ne changerait pas tellement le problème : nous ne tomberons jamais sur 'b' dans nos itérations du for.

Pour obtenir le comportement attendu, nous pourrions avancer dans les itérations uniquement si le dernier yield a renvoyé None (un yield renvoyant None étant considéré comme un next). Comment faire cela ? Par une boucle qui exécute yield jusqu’à ce qu’il retourne None. Ce yield n’aura pas de paramètre spécifique, cette valeur étant celle retournée ensuite par send, elle ne nous intéresse pas ici.

Ainsi, les send ne consommeront qu’une itération de la sous-boucle, tandis que les « vraies » itérations seront réservées aux next.

1
2
3
4
5
6
7
def queue(*args):
    elems = list(args)
    while elems:
        new = yield elems.pop(0)
        while new is not None:
            elems.append(new)
            new = yield

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
>>> q = queue('a', 'b', 'c')
>>> for letter in q:
...     if letter == 'a':
...         q.send('d')
...     print(letter)
...
a
b
c
d

Méthodes des générateurs

Nous avons vu que les générateurs possédaient des méthodes __next__ et send. Nous allons maintenant nous intéresser aux deux autres méthodes de ces objets : throw et close.

throw

La méthode throw permet de lever une exception depuis le générateur, à l’endroit où ce dernier s’est arrêté. Elle a pour effet de réveiller le générateur pour lui faire lever une exception du type indiqué.

Il s’agit alors d’une autre manière d’influer sur l’exécution d’un générateur, par des événements qui lui sont extérieurs.

throw possède 3 paramètres dont deux facultatifs :

  • Le premier, type, est le type d’exception à lever ;
  • Le second, value, est la valeur à passer en instanciant cette exception ;
  • Et le troisième, traceback, permet de passer un pile d’appel (traceback object) particulière à l’exception.

L’exception survient donc au niveau du yield, et peut tout à fait être attrapée par le générateur. Si c’est le cas, throw retournera la prochaine valeur produite par le générateur, ou lèvera une exception StopIteration indiquant que le générateur a été entièrement parcouru, à la manière de next.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
>>> def generator_function():
...     for i in range(5):
...         try:
...             yield i
...         except ValueError:
...             print('Something goes wrong')
...
>>> gen = generator_function()
>>> next(gen)
0
>>> next(gen)
1
>>> gen.throw(ValueError)
Something goes wrong
2
>>> next(gen)
3
>>> next(gen)
4
>>> gen.throw(ValueError)
Something goes wrong
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Si l’exception n’est pas attrapée par le générateur, elle provoque alors sa fermeture, et remonte logiquement jusqu’à l’objet ayant fait appel à lui.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
>>> def generator_function():
...     for i in range(5):
...         yield i
...
>>> gen = generator_function()
>>> next(gen)
0
>>> next(gen)
1
>>> gen.throw(ValueError)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in generator_function
ValueError
>>> next(gen)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

close

Un cas particulier d’appel à la méthode throw est de demander au généraeur de s’arrêter en lui faisant lever une exception GeneratorExit.

À la réception de cette dernière, il est attendu que le générateur se termine (StopIteration) ou lève à son tour une GeneratorExit (par exemple en n’attrapant pas l’exception survenue).

La méthode close du générateur permet de réaliser cet appel et d’attraper les StopIteration/GeneratorExit en retour.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
>>> def generator_function():
...     for i in range(5):
...         yield i
...
>>> gen = generator_function()
>>> next(gen)
0
>>> next(gen)
1
>>> gen.close()
>>> next(gen)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
>>> def generator_function():
...     for i in range(5):
...         try:
...             yield i
...         except GeneratorExit:
...             break
...
>>> gen = generator_function()
>>> next(gen)
0
>>> next(gen)
1
>>> gen.close()
>>> next(gen)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Puisqu’elle attrape les StopIteration, il est possible d’appeler plusieurs fois la méthode close sur un même générateur.

1
2
>>> gen.close()
>>> gen.close()

close s’occupe aussi de lever une RuntimeError dans le cas où le générateur ne s’arrêterait pas et continuerait à produire des valeurs.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
>>> def generator_function():
...     for i in range(5):
...         try:
...             yield i
...         except GeneratorExit:
...             print('Ignoring')
...
>>> gen = generator_function()
>>> next(gen)
0
>>> next(gen)
1
>>> gen.close()
Ignoring
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: generator ignored GeneratorExit
>>> next(gen)
3

Déléguer à un autre générateur avec yield from

Nous savons produire les valeurs d’un générateur à l’aide du mot clef yield. Voyons maintenant quelque chose d’un peu plus complexe avec yield from. Ce nouveau mot clef permet de déléguer l’itération à un sous-générateur pris en paramètre. La rencontre du yield from provoque une interruption du générateur courant, le temps d’itérer et produire les valeurs du générateur délégué.

1
2
3
4
def big_queue():
    yield 0
    yield from queue(1, 2, 3)
    yield 4

Celui-ci agit comme si nous itérions sur queue(1, 2, 3) depuis big_queue, tout en yieldant toutes ses valeurs.

1
2
3
4
5
def big_queue():
    yield 0
    for value in queue(1, 2, 3):
        yield value
    yield 4

À la différence près qu’avec yield from, les paramètres passés lors d’un send sont aussi relégués aux sous-générateurs. Tout comme sont relayés aux sous-générateurs les appels aux méthodes throw et close.

Dans notre première version, nous pouvons nous permettre ceci :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
>>> q = big_queue()
>>> next(q)
0
>>> next(q)
1
>>> q.send('foo')
>>> next(q)
2
>>> next(q)
3
>>> next(q)
'foo'
>>> next(q)
4
>>> next(q)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Où l’on voit bien que le send est pris en compte par la sous-queue, et la valeur ajoutée à la file. Je vous invite à essayer avec la seconde implémentation de big_queue (celle sans yield from), pour bien observer l’effet de la délégation du send.

On peut aussi noter que yield from n’attend pas nécessairement un générateur en paramètre, mais n’importe quel type d’itérable.

1
2
3
4
def gen_from_iterables():
    yield from [1, 2, 3]
    yield from 'abcdef'
    yield from {'x': 1, 'y': -1}

Et par exemple, si nous voulions réécrire la fonction chain du module itertools, nous pourrions procéder ainsi :

1
2
3
def chain(*iterables):
    for iterable in iterables:
        yield from iterable

Listes et générateurs en intension

Intéressons-nous maintenant aux sucres syntaxiques que sont les listes et générateurs en intension.

Listes en intension

Vous connaissez probablement déjà les listes en intension (comprehension lists), mais je vais me permettre un petit rappel.

Les listes en intension sont une syntaxe courte pour définir des listes à partir d’un itérable et d’une expression à appliquer sur chaque élément (un peu à la manière de map, qui lui ne permet que d’appeler un callable pour chaque l’élément).

Une expression étant en Python tout ce qui possède une valeur (même None), c’est-à-dire ce qui n’est pas une instruction (if, while, etc.). Il faut noter que les ternaires sont des expressions (a if predicat() else b), et peuvent donc y être utilisés.

Ainsi,

1
2
3
>>> squares = [x**2 for x in range(10)]
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

sera l’équivalent de

1
2
3
squares = []
for x in range(10):
    squres.append(x**2)

ou encore de

1
squares = list(map(lambda x: x**2, range(10)))

Le gain en lisibilité est net.

Cette syntaxe permet aussi d’appliquer des filtres, à la manière de filter. Par exemple si nous ne voulions que les carrés supérieurs à 10 :

1
2
>>> [x**2 for x in range(10) if x**2 >= 10]
[16, 25, 36, 49, 64, 81]

Une liste en intension peut directement être passée en paramètre à une fonction.

1
2
>>> sum([x**2 for x in range(10)])
285

Étant des expressions, elles peuvent être imbriquées dans d’autres listes en intension :

1
2
>>> [[x + y for x in range(5)] for y in range(3)]
[[0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 3, 4, 5, 6]]

Enfin, il est possible de parcourir plusieurs niveaux de listes dans une seule liste en intension :

1
2
3
>>> matrix = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
>>> [elem + 1 for line in matrix for elem in line]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Vous noterez que les for se placent dans l’ordre des dimensions que nous voulons explorer : d’abord les lignes, puis les éléments qu’elles contiennent.

Générateurs en intension

De la même manière que pour les listes, nous pouvons définir des générateurs en intension (generator expressions). La syntaxe est très similaire, il suffit de remplacer les crochets par des parenthèses pour passer d’une liste à un générateur.

1
2
3
>>> squares = (x**2 for x in range(10))
>>> squares
<generator object <genexpr> at 0x7f8b8a9a7090>

Et nous pouvons les utiliser tels que les autres itérables.

1
2
3
4
>>> list(squares)
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
>>> list(squares) # En gardant à l'esprit qu'ils se consumment
[]

Et pour finir, il est possible de simplifier encore la syntaxe quand un générateur en intension est seul paramètre d’une fonction, en supprimant les parenthèses redondantes.

1
2
3
4
>>> sum((x**2 for x in range(10)))
285
>>> sum(x**2 for x in range(10)) # Une paire de parenthèses est retirée
285

Liste ou générateur ?

Une question qui revient souvent est celle de savoir quand choisir une liste et quand choisir un générateur, voici donc un petit comparatif :

  • Les listes prennent généralement plus de place en mémoire : tous les éléments existent en même temps. Dans le cas d’un générateur, l’élément n’existe que quand l’itérateur l’atteint, et n’existe plus après (sauf s’il est référencé autre part) ;
  • Les générateurs peuvent être infinis (contrairement aux listes qui occupent un espace qui se doit d’être fini).
1
2
3
4
5
>>> def infinite():
...     n = 0
...     while True:
...         yield n
...         n += 1
  • Les générateurs ne sont pas indexables : on ne peut accéder à un élément particulier (il faut itérer jusque cet élément) ;
  • Les générateurs ont une durée de vie plus courte (ils ne contiennent plus rien une fois qu’ils ont été itérés en entier) ;
  • Du fait que les générateurs n’occupent que peu de place en mémoire, on peut les enchaîner sans crainte.
1
2
3
numbers = (x**2 for x in range(100))
numbers = zip(infinite(), numbers)
numbers = (a + b for (a, b) in numbers)

Ainsi, les éléments du premier générateur ne seront calculés qu’au parcours de numbers. Il est aussi possible de profiter des avantages de l’un et de l’autre en récupérant une liste en fin de chaîne, par exemple en remplaçant la dernière ligne par :

1
numbers = [a + b for (a, b) in numbers]

Ou en ajoutant à la fin :

1
numbers = list(numbers)

TP : map

Dans ce TP, nous allons réaliser un équivalent de la fonction map, que nous appellerons my_map.

Pour rappel, map permet d’appliquer une fonction sur tous les éléments d’un itérable. Elle reçoit en paramètres la fonction à appliquer et l’itérable, et retourne un nouvel itérable correspondant à l’application de la fonction sur chacune des valeurs de l’itérable d’entrée.

Un générateur se prête donc très bien à cet exercice : nous ferons de my_map une fonction génératrice.

Elle se contentera dans un premier temps d’itérer sur l’entrée, et de yielder le résultat obtenu pour chaque élément.

1
2
3
def my_map(f, iterable):
    for item in iterable:
        yield f(item)

Cette implémentation répond très bien à la problématique initiale.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
>>> for x in my_map(lambda x: x*2, range(10)):
...     print(x)
...
0
2
4
6
8
10
12
14
16
18

Seulement, pour aller un peu plus loin et mettre en pratique ce que nous avons vu dans le chapitre, nous allons faire en sorte de pouvoir changer la fonction f en cours de route.

Pour ce faire, nous communiquerons avec notre générateur à l’aide de sa méthode send. Nous voulons donc que chaque fois que yield retourne autre chose que None, cette valeur soit utilisée comme nouvelle fonction.

Une approche simpliste serait la suivante :

1
2
3
4
5
def my_map(f, iterable):
    for item in iterable:
        ret = yield f(item)
        if ret is not None:
            f = ret

Mais comme send provoque une itération supplémentaire du générateur, elle a l’inconvénient de faire perdre des valeurs. (les valeurs ne sont pas vraiment perdues, mais sont les valeurs de retour de send)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
>>> gen = my_map(lambda x: x+1, range(10))
>>> for x in gen:
...     print('Got', x)
...     if x == 5:
...         gen.send(lambda x: x+2)
...
Got 1
Got 2
Got 3
Got 4
Got 5
7
Got 8
Got 9
Got 10
Got 11

L’affichage du 7 étant dû à l’interpréteur interactif qui affiche la valeur de retour du send.

Pour palier à ce petit problème, nous pouvons dans notre générateur yielder None quand une fonction a été reçue. Ainsi, le retour du send sera le None transmis par yield, et la valeur ne sera pas perdue.

Nous réécrivons alors notre générateur en conséquence.

1
2
3
4
5
6
def my_map(f, iterable):
    for item in iterable:
        ret = yield f(item)
        if ret is not None:
            f = ret
            yield None

Et observons la correction.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
>>> gen = my_map(lambda x: x+1, range(10))
>>> for x in gen:
...     print('Got', x)
...     if x == 5:
...         gen.send(lambda x: x+2)
...
Got 1
Got 2
Got 3
Got 4
Got 5
Got 7
Got 8
Got 9
Got 10
Got 11

Mais notre générateur reste sujet à un problème plus subtil : des pertes se produisent si nous appelons yield plusieurs fois d’affilée.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
>>> gen = my_map(lambda x: x+1, range(10))
>>> for x in gen:
...     print('Got', x)
...     if x == 5:
...         gen.send(lambda x: x+2)
...         gen.send(lambda x: x*2)
...
Got 1
Got 2
Got 3
Got 4
Got 5
7
Got 8
Got 9
Got 10
Got 11

En effet, lors du premier send, nous retrons dans la condition du générateur pour arriver sur le yield None, valeur retournée par send. Mais nous ne nous inquiétons pas de savoir ce que retourne ce second yield (en l’occurrence, la fonction envoyée par le second send, qui n’est jamais prise en compte).

Vous l’aurez compris, il nous suffira donc de mettre en place une boucle autour du yield None et n’en sortir qu’une fois qu’il aura retourné None. Chaque valeur différente sera enregistrée comme nouvelle fonction f.

1
2
3
4
5
6
def my_map(f, iterable):
    for value in iterable:
        newf = yield f(value)
        while newf is not None:
            f = newf
            newf = yield None

Cette fois-ci, plus de problèmes !

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
>>> gen = my_map(lambda x: x+1, range(10))
>>> for x in gen:
...     print('Got', x)
...     if x == 5:
...         gen.send(lambda x: x+2)
...         gen.send(lambda x: x*2)
...
Got 1
Got 2
Got 3
Got 4
Got 5
Got 10
Got 12
Got 14
Got 16
Got 18

Quelques pages habituelles tirées de la documentation :

Je profite aussi de la fin de ce chapitre pour vous conseiller cet article de nohar sur les coroutines, une utilisation possible et courante des générateurs : https://zestedesavoir.com/articles/152/la-puissance-cachee-des-coroutines

J’aurais aimé abordé le sujet des coroutines et de la programmation asynchrone en Python, mais un cours entier sur le sujet n’est pas de trop !