Rappelons qu’une fonction est un bloc d’instructions qui a reçu un nom, dont le fonctionnement dépend d’un certain nombre de paramètres (les arguments de la fonction) et qui renvoie un résultat (au moyen de l’instruction return).
def nom_de_la_fonction (arguments ): # le nom de la fonction, et les paramètres d’appels bloc_d’instructions # on parcourt ce bloc
Dans la pratique, on appelle la fonction en lui passant des arguments, et elle nous renvoie l’expression qui suit le premier return rencontré. Le parcours de la fonction est alors terminé (avec retour au programme “appelant”), et il faut procéder à un nouvel appel à cette fonction pour que son contenu soit à nouveau évalué depuis le début.
Plusieurs appels à cette fonction peuvent ainsi produire une séquence de résultats.
On peut cependant imaginer un autre mécanisme. Notre fonction renverrait un résultat, puis resterait en sommeil (dans l’état où elle se trouve alors). Un nouvel appel de la fonction la “réveillerait” là où on l’avait laissée, lui permettant de nous renvoyer un nouveau résultat (et de se mettre, là encore, en attente). Dans ces situations d’attente, la fonction conserverait son “contexte” (notamment la valeur de ses variables locales), pour permettre un redémarrage propre.
Ce mécanisme est exactement celui des générateurs, qui sont des fonctions définies comme on l’a vu jusqu’à présent, à ceci près que l’instruction return est remplacée par yield (mot anglais qui signifie “donner”, “produire”).
Un exemple classique permettra de comprendre ce dont il s’agit.
On sait que la suite de Fibonacci {(F_n)_{n\ge0}} est définie par {F_0=0}, {F_1=1}, et, pour tout {n\ge2}, {F_n=F_{n-1}+F_{n-2}}.
Voici trois fonctions calculant à leur manière les éléments successifs de la suite de Fibonacci (seule la troisième est un générateur, car elle rend un résultat au moyen de yield).
|
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 fibo3(n): x, y = 0, 1 for k in range(n+1): yield x x, y = y, x+y def fibo2(n): x, y = 0, 1 for k in range(n): x, y = y, x+y return x def fibo1(n): l = [x] = [0]; y = 1 for k in range(n): x, y = y, x+y l.append(x) return l >>> fibo1(10) # fibo1(n) renvoie une liste de n + 1 valeurs [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> [fibo2(n) for n in range(0,11)] # liste des F_n renvoyés par fibo2 (0 ≤ n ≤ 10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> [u for u in fibo3(10)] # la liste des F_n obtenus avec fibo3, pour (0 ≤ n ≤ 10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> list(fibo3(10)) # idem [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] |
La fonction fibo1 est un peu particulière puisqu’un seul appel à fibo1(n) génère la liste {[F_0,F_1,\ldots,F_n]}. En revanche l’expression fibo2(n) renvoie le seul nombre de Fibonacci {F_n}. Évaluer [fibo2(n) for n in range(0,11)] est donc ici assez maladroit puisque ça provoque des recalculs systématiques.
Les exemples ci-dessus ne permettent pas de distinguer la différence fondamentale de fonctionnement entre fibo3 et les deux autres fonctions. Essayons d’y voir un peu plus clair ! Tout d’abord, rien ne permet de différencier les objets fibo1, fibo2, et fibo3 : ce sont trois objets de type “function”, situés quelque part en mémoire :
|
1 2 |
>>> fibo1, fibo2, fibo3 (<function fibo1 at 0x103f707a0>, <function fibo2 at 0x103f70830>, <function fibo3 at 0x103f708c0>) |
La différence essentielle tient au résultat de l’évaluation de fibo1(n) (c’est une liste), fibo2(n) (c’est l’entier {F_n}) et fibo3(n) (c’est un “générateur”). La première chose à bien comprendre est qu’évaluer fibo3(n) ne provoque pas immédiatement le calcul de ces valeurs : on crée seulement un mécanisme, qui va fonctionner à la demande, et qui va fournir, au coup par coup, chacun des entiers {F_0,F_1,\ldots,F_n}.
|
1 2 3 4 5 6 |
>>> fibo1(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> fibo2(10) 55 >>> fibo3(10) <generator object fibo3 at 0x103f77910> |
Plaçons par exemple le générateur fibo3(10) dans la variable f . Pour demander à f de générer (de “yielder” diraient certains) une nouvelle valeur, on évalue next(f )
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
>>> next(f) # Actionne le générateur f . On obtient ici F_0 = 0. 0 >>> next(f) # entre deux évaluations de next(f), l'état actuel du générateur est préservé 1 >>> next(f) # chaque évaluation de next(f) fournit une nouvelle valeur. ici F(2) = 1 1 >>> next(f) # on obtient maintenant F(3) = 2 2 >>> next(f), next(f), next(f), next(f) # quatre next(f) ⇒ quatre nouvelles valeurs F(k) (3, 5, 8, 13) >>> next(f), next(f), next(f) # encore trois nouvelles valeurs (21, 34, 55) >>> next(f) # c'est la demande de trop! Traceback (most recent call last): File "<pyshell#54>", line 1, in <module> next(f) StopIteration |
L’exemple précédent montre que le générateur f =fibo3(10) constitue un mécanisme qui peut être sollicité à tout moment par next(f ). Chaque appel renvoie la valeur qui suit l’instruction yield dans le corps de la fonction fibo3.
On voit clairement que le code de la fonction fibo3 est “suspendu” entre deux appels successifs (avec préservation du contenu des variables locales). D’autre part, le code de la fonction fibo3 montre que l’instruction yield est sollicitée au sein de la boucle for k in range(0,n) (avec n = 10 dans notre exemple). Chaque évaluation de next(f ) avance d’une étape dans cette boucle. Quand cette boucle est terminée, l’évaluation de next(f ) se traduit par une erreur de type StopIretation (et c’est normal car on sort enfin du code de la fonction fibo3, mais pas par un yield).
La fonction next accepte un argument par défaut, qui rattrape StopIteration quand on dépasse le nombre d’itérations :
|
1 2 |
>>> next(f,"c'est fini, là, ok?") "c'est fini, là, ok?" |
Ce qui est spécialement intéressant dans le fonctionnement d’un générateur, c’est qu’il permet de former les valeurs successives d’une suite virtuellement infinie. Modifions par exemple la fonction fibo3 en supprimant l’argument n :
|
1 2 3 4 5 |
def fibo4(): x, y = 0, 1 # le début de la suite de Fibonacci while True: # ad vitam aeternam yield x # délivre la valeur courante de la suite x, y = y, x+y # actualise les deux termes consécutifs |
L’expression fibo4() crée alors un générateur qui permet de délivrer les valeurs successives de la suite de Fibonacci, ad libitum, et au rythme qu’on veut…
|
1 2 3 4 5 |
>>> f = fibo4() # prêt à engendrer les nombres de Fibonacci >>> [next(f) for k in range(0,10)] # les dix premières valeurs [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] >>> [next(f) for k in range(0,5)] # les cinq suivantes [55, 89, 144, 233, 377] |
Important : si f est un générateur, on peut en solliciter toutes les valeurs au moyen de boucles “for indice in f” (si l’ensemble des valeurs est fini, c’est préférable). Dans ce cas c’est la boucle qui déclenche elle-même le mécanisme “next” et qui rattrape l’exception de fin d’itération. En reprenant les notations précédentes, voici comment “yielder” les 10 premières valeurs de la suite de Fibonacci.
|
1 2 3 |
>>> g = fibo3(10) # crée le générateur (mais ne calcule pas les F_n !!) >>> for k in g: print(k,end=' ') # demande et imprime les dix premiers F_n 0 1 1 2 3 5 8 13 21 34 55 |
Autre possibilité, déjà évoquée, avec le constructeur list (qui lui aussi prend en charge le mécanisme d’itération) :
|
1 2 |
>>> list(fibo3(15)) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] |