Générateur (programmation informatique)

En informatique , un générateur est une routine qui peut être utilisée pour contrôler le comportement d'itération d'une boucle . Tous les générateurs sont également des itérateurs . Un générateur est très similaire à une fonction qui renvoie un tableau , dans la mesure où un générateur a des paramètres , peut être appelé et génère une séquence de valeurs. Cependant, au lieu de créer un tableau contenant toutes les valeurs et de les renvoyer toutes en même temps, un générateur génère les valeurs une par une, ce qui nécessite moins de mémoire et permet à l'appelant de commencer à traiter les premières valeurs immédiatement. En bref, un générateur ressemble à une fonction mais se comporte comme un itérateur .

Les générateurs peuvent être implémentés en termes de constructions de flux de contrôle plus expressives , telles que les coroutines ou les continuations de première classe . Les générateurs, également connus sous le nom de semi-coroutines, sont un cas particulier (et plus faible que) des coroutines, dans la mesure où ils cèdent toujours le contrôle à l'appelant (lors du renvoi d'une valeur), plutôt que de spécifier une coroutine vers laquelle sauter ; voir la comparaison des coroutines avec les générateurs .

Les générateurs sont généralement invoqués à l'intérieur de boucles. La première fois qu'une invocation de générateur est atteinte dans une boucle, un objet itérateur est créé qui encapsule l'état de la routine du générateur à son début, avec des arguments liés aux paramètres correspondants . Le corps du générateur est ensuite exécuté dans le contexte de cet itérateur jusqu'à ce qu'une action de rendement spéciale soit rencontrée ; à ce moment-là, la valeur fournie avec l' action de rendement est utilisée comme valeur de l'expression d'invocation. La prochaine fois que la même invocation de générateur est atteinte dans une itération ultérieure, l'exécution du corps du générateur reprend après l' action de rendement , jusqu'à ce qu'une autre action de rendement soit rencontrée. En plus de l' action de rendement , l'exécution du corps du générateur peut également être terminée par une action de finition , à ce moment-là, la boucle la plus interne englobant l'invocation du générateur est terminée. Dans des situations plus compliquées, un générateur peut être utilisé manuellement en dehors d'une boucle pour créer un itérateur, qui peut ensuite être utilisé de diverses manières.

Étant donné que les générateurs calculent leurs valeurs générées uniquement à la demande, ils sont utiles pour représenter des flux , tels que des séquences qui seraient coûteuses ou impossibles à calculer en une seule fois. Il s'agit par exemple de séquences infinies et de flux de données en direct.

Lorsqu'une évaluation rapide est souhaitable (principalement lorsque la séquence est finie, car sinon l'évaluation ne se terminera jamais), on peut soit convertir en liste , soit utiliser une construction parallèle qui crée une liste au lieu d'un générateur. Par exemple, en Python, un générateur gpeut être évalué en liste lvia l = list(g), tandis qu'en F#, l'expression de séquence seq { ... }s'évalue paresseusement (un générateur ou une séquence) mais [ ... ]s'évalue rapidement (une liste).

En présence de générateurs, les constructions de boucle d'un langage – telles que for et while – peuvent être réduites à une seule construction de boucle end loop ... ; toutes les constructions de boucle habituelles peuvent alors être confortablement simulées en utilisant des générateurs appropriés de la bonne manière. Par exemple, une boucle à distance comme for x = 1 to 10peut être implémentée comme une itération à travers un générateur, comme dans Python for x in range(1, 10). De plus, breakpeut être implémentée comme l'envoi de finish au générateur puis l'utilisation continuedans la boucle.

Les générateurs sont apparus pour la première fois dans CLU (1975), étaient une fonctionnalité importante du langage de manipulation de chaînes Icon (1977) et sont désormais disponibles dans Python (2001), C# , Ruby , PHP , ECMAScript (à partir de ES6/ES2015 ) et d'autres langages. Dans CLU et C#, les générateurs sont appelés itérateurs , et dans Ruby, énumérateurs .

La norme Common Lisp finale ne fournit pas nativement de générateurs, mais diverses implémentations de bibliothèques existent, telles que SERIES documentée dans CLtL2 ou pygen.

Une instruction yield est utilisée pour implémenter des itérateurs sur des abstractions de données définies par l'utilisateur.

string_chars = iter (s: chaîne) renvoie (char); index: int := 1; limite : int := chaîne$taille(s); tant que l'index <= limite faire rendement (chaîne$fetch(s, index)); indice := indice + 1; fin; fin de la chaîne_chars; pour c: char dans string_chars(s) faire ... fin; 

Chaque expression (y compris les boucles) est un générateur. Le langage possède de nombreux générateurs intégrés et implémente même une partie de la sémantique logique en utilisant le mécanisme du générateur ( la disjonction logique ou « OU » est effectuée de cette façon).

L'impression des carrés de 0 à 20 peut être réalisée à l'aide d'une co-routine en écrivant :

carrés locaux , 
j 
carrés 
:= 
créer 
( seq ( 0 ) 
^ 
2 ) 
tous les 
j 
:= 
|@ carrés 
faire 
si 
j 
<= 
20 
alors 
écrire ( j ) 
sinon 
casser

Cependant, la plupart du temps, les générateurs personnalisés sont implémentés avec le mot-clé « suspend » qui fonctionne exactement comme le mot-clé « yield » dans CLU.

Le C n'a pas de fonctions génératrices comme construction de langage, mais, comme elles sont un sous-ensemble de coroutines , il est simple de les implémenter en utilisant n'importe quel framework qui implémente des coroutines empilables, comme libdill. Sur les plateformes POSIX, lorsque le coût du changement de contexte par itération n'est pas un problème, ou qu'un parallélisme complet plutôt qu'une simple concurrence est souhaité, un framework de fonctions génératrices très simple peut être implémenté en utilisant des pthreads et des pipes .

Il est possible d'introduire des générateurs dans C++ en utilisant des macros de préprocesseur. Le code résultant peut avoir des aspects très différents du C++ natif, mais la syntaxe du générateur peut être très épurée. L'ensemble des macros de préprocesseur définies dans cette source autorise les générateurs définis avec la syntaxe comme dans l'exemple suivant :

$generator ( descente ) 
{ 
int i ;
// placer le constructeur de notre générateur, par exemple 
// descente(int minv, int maxv) {...} // de $emit à $stop est un corps de notre générateur : $emit ( int ) // émettra des valeurs int. Début du corps du générateur. for ( i = 10 ; i > 0 ; -- i ) $yield ( i ); // similaire à yield en Python, // renvoie le prochain numéro dans [1..10], inversé. $stop ; // arrêt, fin de séquence. Fin du corps du générateur. };

Ceci peut ensuite être répété en utilisant :

int main ( int argc , char * argv []) { descent gen ; for ( int n ; gen ( n );) // invocation du générateur "obtenir le prochain" printf ( "le prochain numéro est %d " , n ); return 0 ; }

De plus, C++11 permet d'appliquer des boucles foreachbegin à n'importe quelle classe qui fournit les fonctions et end. Il est alors possible d'écrire des classes de type générateur en définissant à la fois les méthodes itérables ( beginet end) et les méthodes itératives ( operator!=, operator++et operator*) dans la même classe. Par exemple, il est possible d'écrire le programme suivant :

#include <iostream> int main () { pour ( int i : range ( 10 )) { std :: cout << i << std :: endl ; } renvoie 0 ; }

Une implémentation de gamme de base ressemblerait à ceci :

plage de classes { privée : int dernier ; int iter ;
public : 
range ( int fin ) : dernier ( fin ), iter ( 0 ) {}
// Fonctions itérables 
const range & begin () const { return * this ; } const range & end () const { return * this ; }
// Fonctions itératives 
bool operator != ( const range & ) const { return iter < last ; } void operator ++ () { ++ iter ; } int operator * () const { return iter ; } };

Perl ne fournit pas nativement de générateurs, mais le support est assuré par le module Coro::Generator qui utilise le framework de co-routine Coro. Exemple d'utilisation :

utiliser strict ; utiliser des avertissements ; # Activer le générateur { BLOCK } et générer use Coro::Generator ; # Référence de tableau sur laquelle itérer my $chars = [ 'A' ... 'Z' ];
# Nouveau générateur qui peut être appelé comme un coderef. 
my $letters = generator { my $i = 0 ; for my $letter ( @$chars ) { # récupère la lettre suivante de $chars yield $letter ; } };
# Appelez le générateur 15 fois. 
print $letters -> (), for ( 0 .. 15 );

L'exemple parallèle à Icon utilise la classe Range de Raku (anciennement/aka Perl 6) comme l'un des nombreux moyens de réaliser des générateurs avec le langage.

L'impression des carrés de 0 à 20 peut être réalisée en écrivant :

pour ( 0 .. *). map (* ** 2 ) -> $i { dernier 
si 
$i > 20 ; dire 
$i } 

Cependant, la plupart du temps, les générateurs personnalisés sont implémentés avec les mots-clés « collecter » et « prendre » dans un contexte paresseux.

Dans Tcl 8.6, le mécanisme du générateur est fondé sur des coroutines nommées .

proc generator { body } { coroutine gen [ incr :: disambiguator ] apply {{ script } { # Produire le résultat de [generator], le nom du générateur yield [ info coroutine ] # Effectuer la génération eval $script # Terminer la boucle de l'appelant en utilisant une exception 'break' return - code break }} $body }
# Utilisez une simple boucle 'for' pour effectuer le comptage réel de l' ensemble de génération [ generator { for {set i 10 } { $i <= 20 } { incr i } { yield $i } }]
# Extraire les valeurs du générateur jusqu'à ce qu'il soit épuisé 
while 1 { puts [ $count ] }

En Haskell , avec son modèle d'évaluation paresseux , chaque donnée créée avec un constructeur de données non strict est générée à la demande. Par exemple,

countFrom :: Entier -> [ Entier ] countFrom n = n : countFrom ( n + 1 )
de 10 à 20 :: [ Entier ] de 10 à 20 = takeWhile ( <= 20 ) $ countFrom 10
primes :: [ Integer ] primes = 2 : 3 : nextPrime 5 où nextPrime n | notDivisible n = n : nextPrime ( n + 2 ) | sinon = nextPrime ( n + 2 ) notDivisible n = tout (( /= 0 ) . ( rem n )) $ takeWhile (( <= n ) . ( ^ 2 )) $ tail primes

où (:)est un constructeur de liste non strict, cons , et $est simplement un opérateur « appelé avec » , utilisé pour la parenthèse. Cela utilise la fonction d'adaptateur standard,

takeWhile p [] = [] takeWhile p ( x : xs ) | p x = x : takeWhile p xs | else = []

qui parcourt la liste et s'arrête sur le premier élément qui ne satisfait pas le prédicat. Si la liste a déjà été parcourue jusqu'à ce point, il s'agit simplement d'une structure de données stricte, mais si une partie n'a pas été parcourue auparavant, elle sera générée à la demande. Les compréhensions de liste peuvent être utilisées librement :

carrésSous20 = prendrePendant ( <= 20 ) [ x * x | x < - compterÀpartirDe10 ] carrésPourLesNombresSous20 = [ x * x | x < - prendrePendant ( <= 20 ) $ compterÀpartirDe10 ]

Racket fournit plusieurs fonctionnalités liées aux générateurs. Tout d'abord, ses formes de boucle for fonctionnent avec des séquences , qui sont une sorte de producteur :

( pour ([ i ( dans la plage 10 20 )]) ( printf "i = ~s " i ))

et ces séquences sont également des valeurs de premier ordre :

( définir 10 à 20 ( dans la plage 10 20 )) ( pour ([ i 10 à 20 ]) ( printf "i = ~s " i ))

Certaines séquences sont implémentées de manière impérative (avec des variables d'état privées) et d'autres sont implémentées sous forme de listes paresseuses (éventuellement infinies). De plus, les nouvelles définitions de structure peuvent avoir une propriété qui spécifie comment elles peuvent être utilisées comme séquences.

Mais plus directement, Racket est livré avec une bibliothèque de générateurs pour une spécification de générateur plus traditionnelle. Par exemple,

#lang racket 
( require racket/generator ) ( define ( ints-from from ) ( generator () ( for ([ i ( in-naturals from )]) ; séquence infinie d'entiers à partir de 0 ( yield i )))) ( define g ( ints-from 10 )) ( list ( g ) ( g ) ( g )) ; -> '(10 11 12)

Notez que le noyau de Racket implémente de puissantes fonctionnalités de continuation, fournissant des continuations générales (réentrantes) composables, ainsi que des continuations délimitées. Grâce à cela, la bibliothèque de générateurs est implémentée dans Racket.

La communauté PHP a implémenté des générateurs dans PHP 5.5. Vous trouverez plus de détails dans la demande de commentaires originale : Générateurs.

Suite infinie de Fibonacci :

fonction 
fibonacci () : 
Générateur 
{ 
$last 
= 
0 ; 
$current 
= 
1 ; 
rendement 
1 ; 
while 
( true ) 
{ 
$current 
= 
$last 
+ 
$current ; 
$last 
= 
$current 
- 
$last ; 
rendement 
$current ; 
} 
}
foreach 
( fibonacci () 
comme 
$nombre ) 
{ 
echo 
$nombre , 
" " ; 
}

Suite de Fibonacci avec limite :

fonction 
fibonacci ( int 
$limit ) : 
Générateur 
{ 
rendement 
$a 
= 
$b 
= 
$i 
= 
1 ;
tant que 
( ++ $i 
< 
$limit ) 
{ 
rendement 
$a 
= 
( $b 
= 
$a 
+ 
$b ) 
- 
$a ; 
} 
}
foreach 
( fibonacci ( 10 ) 
comme 
$nombre ) 
{ 
echo 
" $nombre " ; 
}

Toute fonction contenant une instruction yield est automatiquement une fonction génératrice.

Ruby prend en charge les générateurs (à partir de la version 1.9) sous la forme de la classe Enumerator intégrée.

# Générateur à partir d'un objet Enumerator 
chars = Enumerator . new ( [ 'A' , 'B' , 'C' , 'Z' ] )
4 . fois { met les caractères . suivant }
# Générateur à partir d'un bloc 
count = Enumerator . new do | yielder | i = 0 loop { yielder . yield i += 1 } end
100 . fois { met count . next }

Java dispose d'une interface standard pour implémenter des itérateurs depuis ses débuts, et depuis Java 5, la construction « foreach » facilite la boucle sur les objets qui fournissent l' java.lang.Iterableinterface. (Le framework de collections Java et d'autres frameworks de collections fournissent généralement des itérateurs pour toutes les collections.)

enregistrement 
Paire ( int a , int b ) {};
Iterable < Integer > myIterable = Stream . iterate ( nouvelle paire ( 1 , 1 ), p -> nouvelle paire ( p . b , p . a + p . b )) . limit ( 10 ) . map ( p -> p . a ):: iterator ;
monIterable . forEach ( System . out :: println );

Ou obtenez un itérateur à partir de la super-interface Java 8 BaseStream de l'interface Stream.

enregistrement 
Paire ( int a , int b ) {};
// Enregistrer l'itérateur d'un flux qui génère une séquence fib 
Iterator < Integer > myGenerator = Stream // Génère une séquence Fib . iterate ( new Pair ( 1 , 1 ) , p - > new Pair ( p.b , p.a + p.b ) ) . map ( p - > p.a ) . iterator ( ) ;
// Imprimer les 5 premiers éléments 
for ( int i = 0 ; i < 5 ; i ++ ) { System . out . println ( myGenerator . next ()); }
System . out . println ( "terminé avec la première itération" );
// Imprimer les 5 éléments suivants 
pour ( int i = 0 ; i < 5 ; i ++ ) { System . out . println ( myGenerator . next ()); }

Sortir:

1 
1 
2 
3 
5 
terminé avec la première itération 
8 
13 
21 
34 
55

Un exemple de générateur C# 2.0 (il yieldest disponible depuis la version C# 2.0) : Ces deux exemples utilisent des génériques, mais ce n'est pas obligatoire. Le mot-clé yield permet également d'implémenter des itérations personnalisées avec état sur une collection, comme indiqué dans cette discussion.

// Méthode qui prend une entrée itérable (éventuellement un tableau) 
// et renvoie tous les nombres pairs. 
public static IEnumerable < int > GetEven ( IEnumerable < int > numbers ) { foreach ( int number in numbers ) { if (( number % 2 ) == 0 ) { yield return number ; } } }

Il est possible d'utiliser plusieurs yield returninstructions et elles sont appliquées en séquence à chaque itération :

classe publique CityCollection : IEnumerable < chaîne > { public IEnumerator < chaîne > GetEnumerator () { rendement retour "New York" ; rendement retour "Paris" ; rendement retour "Londres" ; } }

Dans XL , les itérateurs sont la base des boucles « for » :

importer IO = XL.UI.CONSOLE itérateur IntegerIterator (var out Counter : entier; Low, High : entier) écrit Counter dans Low..High est Compteur := Bas tant que Compteur <= Boucle haute rendement Compteur += 1 // Notez que I n'a pas besoin d'être déclaré, car « var out » est déclaré dans l'itérateur // Une déclaration implicite de I comme entier est donc faite ici pour I dans la boucle 1..5 IO.WriteLn "I=", je 

F# fournit des générateurs via des expressions de séquence , depuis la version 1.9.1. Ceux-ci peuvent définir une séquence (évaluée paresseusement, accès séquentiel) via seq { ... }, une liste (évaluée avec impatience, accès séquentiel) via [ ... ]ou un tableau (évalué avec impatience, accès indexé) via [| ... |]qui contiennent du code qui génère des valeurs. Par exemple,

seq { pour b dans 0 .. 25 faire si b < 15 alors donner b * b }

forme une séquence de carrés de nombres de 0 à 14 en filtrant les nombres de la plage de nombres de 0 à 25.

Les générateurs ont été ajoutés à Python dans la version 2.2 en 2001. Un exemple de générateur :

à partir de 
la saisie 
de l'import 
Iterator
def 
countfrom ( n : 
int ) 
-> 
Itérateur [ int ] : 
tandis que 
True : 
rendement 
n 
n 
+= 
1
# Exemple d'utilisation : impression des entiers de 10 à 20. 
# Notez que cette itération se termine normalement, même si 
# countfrom() est écrit comme une boucle infinie.
pour 
i 
dans 
countfrom ( 10 ): 
si 
i 
<= 
20 : 
print ( i ) 
sinon : 
break
# Un autre générateur, qui produit des nombres premiers indéfiniment selon les besoins. 
import 
itertools
def 
primes () 
-> 
Iterator [ int ]: 
Générer des nombres premiers indéfiniment selon les besoins.""" yield 2 n = 3 p = [ 2 ] while True : # Si la division de n par tous les nombres de p, jusqu'à et y compris sqrt(n), # produit un reste non nul, alors n est premier. if all ( n % f > 0 for f in itertools . takewhile ( lambda f : f * f <= n , p )): yield n p . append ( n ) n += 2

En Python, un générateur peut être considéré comme un itérateur qui contient une trame de pile gelée . Chaque fois qu'il next()est appelé sur l'itérateur, Python reprend la trame gelée, qui s'exécute normalement jusqu'à ce que l' yieldinstruction suivante soit atteinte. La trame du générateur est alors à nouveau gelée et la valeur générée est renvoyée à l'appelant.

PEP 380 (implémenté dans Python 3.3) ajoute l' yield fromexpression, permettant à un générateur de déléguer une partie de ses opérations à un autre générateur ou itérable.

Python possède une syntaxe calquée sur celle des compréhensions de listes , appelée expression génératrice, qui facilite la création de générateurs. Ce qui suit étend le premier exemple ci-dessus en utilisant une expression génératrice pour calculer les carrés à partir de la countfromfonction génératrice :

carrés 
= 
( n 
* 
n 
pour 
n 
dans 
countfrom ( 2 ))
pour 
j 
en 
carrés : 
si 
j 
<= 
20 : 
print ( j ) 
else : 
break

ECMAScript 6 (alias Harmony) a introduit les fonctions de générateur.

Une séquence infinie de Fibonacci peut être écrite à l'aide d'un générateur de fonctions :

fonction * fibonacci ( limite ) { let [ prev , curr ] = [ 0 , 1 ]; while ( ! limite || curr <= limite ) { rendement curr ; [ prev , curr ] = [ curr , prev + curr ]; } }
// délimité par la limite supérieure 10 
pour ( const n de fibonacci ( 10 )) { console . log ( n ); }
// générateur sans limite supérieure 
pour ( const n de fibonacci ()) { console . log ( n ); if ( n > 10000 ) break ; }
// itération manuelle 
let fibGen = fibonacci ( ); console.log ( fibGen.next ( ) . value ); // 1 console.log ( fibGen.next ( ) . value ) ; // 1 console.log ( fibGen.next ( ) . value ) ; // 2 console.log ( fibGen.next ( ) . value ) ; // 3 console.log ( fibGen.next ( ) . value ) ; // 5 console.log ( fibGen.next ( ) . value ) ; // 8
// reprend là où vous vous êtes arrêté 
pour ( const n de fibGen ) { console . log ( n ); if ( n > 10000 ) break ; }

Le package iterators peut être utilisé à cette fin.

bibliothèque ( itérateurs )
# Exemple ------------------ 
abc <- iter ( c ( 'a' , 'b' , 'c' )) nextElem ( abc )

Exemple dans Pharo Smalltalk :

Le générateur de nombre d'or ci-dessous renvoie à chaque invocation « goldenRatio next » une meilleure approximation du nombre d'or.

goldenRatio 
:= 
Générateur 
sur : [ : g 
| 
| xyzr | 
x 
:= 
0 . 
y 
:= 
1 . [ z 
:= 
x 
+ 
y . 
r 
:= ( z 
/ 
y ) asFloat . 
x 
:= 
y . 
y 
:= 
z . 
g 
rendement: 
r ] répéter ] .
nombre d'or 
suivant .

L'expression ci-dessous renvoie les 10 approximations suivantes.

Caractère 
cr 
join : (( 1 
à : 
10 ) collect : [ : dummy 
| 
ratio 
next ]) .

Voir plus dans Un joyau caché dans Pharo : Générateur.