Générateur (informatique)

En informatique, un générateur est une routine qui produit des éléments les uns après les autres. Un générateur ressemble à une fonction qui renvoie un tableau : il a des paramètres, il peut être appelé et génère une suite d'éléments. Par contre, au lieu de produire toutes les éléments d'un coup, de les mettre dans un tableau, puis de renvoyer le tableau, il renvoie les éléments un à un.

L'intérêt est d'utiliser moins de mémoire vive^[1] et de pouvoir commencer un traitement sur les éléments qui ont déjà été produit, sans attendre que tous les éléments sont produits.

Selon les langages et usages, on peut définir un générateur par une fonction qui utilise le mot-clé yield pour produire un élément, ou alors en définir avec une compréhensions de listes.

Un générateur suit le patron de conception itérateur^[2].

On peut aussi créer des générateurs qui produisent une infinité d'éléments. Par exemple, un générateur renvoyant tour à tour les éléments de la suite de Fibonacci, ou alors un générateur renvoyant tour à tour tous les nombres premiers serait un tel générateur.

C'est une routine non transparente référentiellement^[pas clair], généralement sans argument^[pas clair].

Implémentation

Généralement un générateur est implémenté avec le mot-clé yield : une instruction de programmation qui sert à imposer la constructivité d'une fonction. Son utilisation dans une fonction permet de retourner un générateur.

Elle est plus souvent présente dans les langages à haut niveau comme PHP, Python, Ruby ou le C#.

Exemple en C#

En C#, le mot-clé yield est suivi de return pour retourner la valeur suivante ou break pour interrompre l'itération.

using System.Collections.Generic;

public class Mots
{
    // Tableau contenant des mots :
    public string[] mots;

    // Constructeur
    public Mots(params string[] mots)
    { this.mots = mots; }

    // Énumérer tous les mots jusqu'à trouver
    // le mot contenu dans le paramètre dernier (exclu)
    // ou la fin du tableau.
    public IEnumerable<string> TousLesMotsJusquA(string dernier)
    {
        foreach(string mot in mots)
            if (mot.Equals(dernier)) yield break; // fin prématurée de l'itération
            else yield return mot; // élément de l'itération
        // fin normale de la boucle d'itération
    }
}

public class TestProgram
{
    public static void Main()
    {
        Mots fruits = new Mots( "pomme", "poire", "abricot", "fraise", "kiwi" );
        foreach( string fruit in fruits.TousLesMotsJusquA("fraise") )
            Console.WriteLine( fruit );
    }
}

Exemple en JavaScript

Les générateurs sont apparus avec ES6 (en 2013).

function* fourInts() {
  let int = 0;
  while (int < 4) {
    yield int;
    int++;
  }
}

const gen = fourInts();   // création
alert(gen.next().value);  // 0
alert(gen.next().value);  // 1
alert(gen.next().value);  // 2
alert(gen.next().value);  // 3
alert(gen.next().value);  // undefined

Exemple en PHP

Les générateurs sont apparus en PHP 5.5.0 (en 2013).

function fibonacci()
{
    $last = 0;
    $current = 1;
    yield 1;
    while (true) {
        $current = $last + $current;
        $last = $current - $last;
        yield $current;
    }
}

foreach (fibonacci() as $number) {
    echo $number, "\n";
}

Exemple en Python

Les générateurs sont apparus sur la V2.2 en 2001. Appeler la méthode next() d'un générateur exécutera la fonction et retournera une valeur. Le yield procède comme un return mais la fonction est liée à un générateur et le prochain appel de la méthode next() reprendra l'exécution là où elle en était^[3].

def fonction(max):
    print('début fonction')
    for x in range(0, max+1):
        yield x
        print('incrémente x')

gen = fonction(2)
gen.next()
# début fonction
# 0
gen.next()
# incrémente x
# 1

NB : depuis Python 3.3, les générateurs peuvent aussi contenir des return^[4].

Exemple en Ruby

En Ruby, l'opérateur yield va entrainer l'exécution du bloc de code passé en paramètre :

def delimit
  puts "before yield"
  yield if block_given?
  puts "after yield"
end

delimit{ puts "in yield" } #=> "before yield\n" "in yield\n" "after yield\n"

Voir aussi

• Coroutine

Références

1. (en) « Python Generators to reduce RAM usage »
2. What is the difference between an Iterator and a Generator?
3. (en) « The yield statement », sur documentation de python.org
4. (en) « Generators and Iterators »

• Portail de l’informatique