|
|
Les itérateurs de C#2 par Patrick
Smacchia |
Comprendre
les concepts d’énumérable et d’énumérateur
Plusieurs
itérateurs sur une même classe
Problèmes
avec les itérateurs de C#1
Un
premier exemple avec le mot-clé yield return
Les
itérateurs et la généricité
Plusieurs
itérateurs pour une même classe conteneur
Contraintes
syntaxique imposées par l’utilisation des mot-clés yield return et yield
break
Exemple d’un itérateur
récursif
Interprétation
des itérateurs par le compilateur de C#2
La
classe énumérateur est implémentée automatiquement par le compilateur
Une
machine à état est fabriquée pour chaque énumérateur
Exemples
avancés de l’utilisation des itérateurs de C#2
Définitions :
coroutine et de continuation
Un
exemple de continuation avec les itérateurs
Méthodes
anonymes, itérateurs et foncteurs
Une
limitation des itérateurs C#2
Pré-requis
Le seul
pré requis pour aborder la partie ‘avancée’ de cet article (i.e à
partir de Interprétation des itérateurs par le compilateur de C#2)
est d’avoir lu l’article
précédent consacré aux méthodes anonymes.
Introduction
Après avoir disséqué les méthodes anonymes de C#2, il est temps de procéder à une analyse minutieuse des itérateurs. Rappelons que pour cette fonctionnalité aussi, aucune instruction IL n’a été rajoutée à la version 2 de .NET. Toute la magie se situe au niveau du compilateur. Nous nous intéresserons tout d’abord au itérateurs de C#1 pour bien comprendre les motivations qui ont poussé à l'amélioration de cette partie du langage. Après une présentation ‘classique’ de la fonctionnalité proprement dite, nous analyserons minutieusement le travail du compilateur pour enfin, commenter des utilisations avancées.
Les itérateurs de C#1
Comprendre les concepts d’énumérable et d’énumérateur
Avant de nous lancer dans un exemple d’utilisation des itérateurs en C#1, il est nécessaire de comprendre les concepts d’énumérable et d’énumérateur.
On dit d’un objet qu’il est énumérable s'il constitue lui-même une collection d’objets et si on peut énumérer cette collection au moyen du mot-clé foreach. Concrètement, une condition suffisante (mais pas forcément nécessaire) pour qu’un objet soit énumérable est qu’il implémente l’interface System.Collections.IEnumerable.
On dit d’un objet que c’est un énumérateur s’il implémente l’interface System.Collections.IEnumerator.
Voici la définition de ces deux interfaces :
namespace System.Collections{
/// <summary>Exposes the enumerator, which supports a simple iteration
over a non-generic collection.</summary>
/// <filterpriority>2</filterpriority>
[System.Runtime.InteropServices.GuidAttribute("496B0ABE-CDEE-11d3-88E8-00902754C43A")]
public
interface IEnumerable{
/// <summary>Returns an enumerator that iterates through a collection.</summary>
/// <returns>An <see cref="T:System.Collections.IEnumerator" /> that can be used to
iterate through the collection.</returns>
/// <filterpriority>2</filterpriority>
[System.Runtime.InteropServices.DispIdAttribute(252)]
System.Collections.IEnumerator GetEnumerator();
}
/// <summary>Supports a simple iteration over a non-generic collection.</summary>
/// <filterpriority>2</filterpriority>
[System.Runtime.InteropServices.GuidAttribute("496B0ABF-CDEE-11d3-88E8-00902754C43A")]
public
interface IEnumerator{
/// <summary>Gets the current element in the collection.</summary>
/// <returns>The current element in the collection.</returns>
/// <filterpriority>2</filterpriority>
object
Current { get; }
/// <summary>Advances the enumerator to the next element of the
collection.</summary>
/// <returns>true if the enumerator was successfully advanced to the next
element; false, if the enumerator has passed the end of the collection.</returns>
/// <filterpriority>2</filterpriority>
bool
MoveNext();
//Sets the enumerator to its initial position,
which is before the first element in the collection.</summary>
/// <filterpriority>2</filterpriority>
void
Reset();
}
}
En analysant ces interfaces, on comprend qu’un client qui veut énumérer la collection d’objets détenue par un objet énumérable, demande à ce dernier un énumérateur au moyen de la méthode IEnumerator IEnumerable.GetEnumerator(). Ensuite, le client peut utiliser les méthodes IEnumerator.MoveNext() et IEnumerator.Reset() sur l’énumérateur retourné pour déplacer l’index courant dans la collection d’objet. Lorsqu’il veut obtenir un l’objet indexé, le client appelle l’accesseur get de la propriété Current. Dans un diagramme UML cela donne :
Si vous consultez maintenant votre GoF (Gang of Four, Design Pattern), vous vous apercevez que l’on vient de décrire le design pattern itérator.
Un exemple
Voici un exemple d’implémentation des
itérateurs en C#1. La classe Personnes
joue le rôle d’énumérable tandis que la classe PersonnesEnumerator joue le rôle de
l’énumérateur. Notez que la classe Personnes
aurait pu jouer à la fois le rôle de l’énumérable et de
l’énumérateur. Il aurait suffit qu’elle implémente en plus
l’interface IEnumerator.
Il est préférable d’isoler l’énumérateur dans une classe tierce
dédiée afin de, comme nous allons le voir, pouvoir implémenter plusieurs
énumérateurs pour un même énumérable :
using System;
using System.Collections;
public class Personnes : IEnumerable{
private class PersonnesEnumerator : IEnumerator{
private int index =
-1;
private Personnes P;
public PersonnesEnumerator(Personnes P){ this.P
= P; }
public bool
MoveNext(){
index++;
return index < P.m_Noms.Length;
}
public void Reset(){ index
= -1; }
public object
Current{ get { return
P.m_Noms[index]; } }
}
// la méthode GetEnumerator() de IEnumerable
public IEnumerator
GetEnumerator(){
return new PersonnesEnumerator(this);
}
string[] m_Noms;
// le constructeur qui initialise le tableau
public Personnes(params string[]
Noms){
m_Noms = new string[Noms.Length];
// Copie le tableau.
Noms.CopyTo(m_Noms,
0);
}
// l'indexeur qui retourne le Nom à partir de l'index
private string
this[int
index]{
get { return
m_Noms[index]; }
set { m_Noms[index] = value; }
}
}
class Program{
static void
Personnes arrPersonnes = new Personnes("Michel", "Christine",
"Mathieu", "Julien");
foreach (string s in arrPersonnes)
Console.WriteLine(s);
Console.ReadLine();
}
}
Un peu lourd pour une telle fonctionnalité, n’est ce pas ?! Heureusement que C#2 simplifie ceci.
Ce programme affiche:
Michel
Christine
Mathieu
Julien
Il est clair que le compilateur C# a interprété le
mot-clé foreach comme
ceci :
...
class Program{
static void
Personnes arrPersonnes = new Personnes("Michel", "Christine",
"Mathieu", "Julien");
IEnumerator e =
arrPersonnes.GetEnumerator();
while (e.MoveNext())
Console.WriteLine((string)e.Current);
Console.ReadLine();
}
}
Plusieurs itérateurs sur une même classe
En fait, l’énumérable n’est pas obligé d’implémenter l’interface IEnumerable. On peut déléguer cette responsabilité à une classe tierce, PersonnesEnumerable par exemple. Voici le programme précédent réécrit :
using System;
using System.Collections;
public class
Personnes // n'implémente pas IEnumerable{
private class PersonnesEnumerator : IEnumerator{
...
}
private class PersonnesEnumerable : IEnumerable{
private Personnes m_Personnes;
internal PersonnesEnumerable(Personnes
personnes) { m_Personnes = personnes; }
IEnumerator IEnumerable.GetEnumerator(){
return new PersonnesEnumerator(m_Personnes);
}
}
public IEnumerable
InOrder{ get { return
new PersonnesEnumerable(this); } }
...
}
class Program{
static void
Personnes arrPersonnes = new Personnes("Michel", "Christine",
"Mathieu", "Julien");
foreach (string s in arrPersonnes.InOrder)
Console.WriteLine(s);
Console.ReadLine();
}
}
On s’aperçoit que de cette façon il devient
possible d’implémenter plusieurs énumérateurs pour notre classe Personnes.
Par exemple un énumérateur Reverse pour parcourir la collection de personnes à
l’envers ou bien un énumérateur Shuffle pour la traverser de façon
aléatoire ou encore un énumérateur EvenPosOnly pour la parcourir en
ne tenant compte que des élément qui ont des positions paires.
Problèmes avec les itérateurs de C#1
En plus d’être assez lourde et malgré le fait
que le design pattern Iterator soit appliqué à la lettre, l’implémentation
des itérateurs en C#1 est peu puissante. En effet, il devient vite difficile
d’implémenter des itérateurs récursifs pour des collections à peine plus
exotiques que des listes, telles que des arbres.
Les itérateurs avec C#2
Un premier exemple avec le mot-clé yield return
C#2 introduit un nouveau mot-clé yield return pour implémenter très simplement des itérateurs. Vous n’avez plus à créer de classe spéciale pour implémenter un énumérateur ou un énumérable.
using System;
using System.Collections;
public class Personnes : IEnumerable{
string[] m_Noms;
public Personnes(params string[]
Noms){
m_Noms = new string[Noms.Length];
Noms.CopyTo(m_Noms, 0);
}
// la méthode GetEnumerator() de IEnumerable
public IEnumerator GetEnumerator(){
foreach (string
s in m_Noms)
yield return
s;
}
}
class Program{
static void
Personnes arrPersonnes = new Personnes("Michel", "Christine",
"Mathieu", "Julien");
foreach (string s in arrPersonnes)
Console.WriteLine(s);
Console.ReadLine();
}
}
Comme vous le voyez la syntaxe est largement plus simple qu’en C#1.
Cependant l’action du mot-clé yield return
doit vous paraître étrange. Comment yield return peut retourner un énumérateur
alors qu’il semble retourner une chaîne de caractères ? Et puis, qu’elle
est l’implémentation d’un tel énumérateur puisque clairement ce
programme ne fournit explicitement aucune classe qui implémente IEnumerator?
Un peu de patience, tout deviendra limpide lorsque l’on procédera à une
analyse du travail du compilateur C#2. Présentons d’abord l’étendue
des possibilités.
Une méthode peut parfaitement contenir plusieurs fois le mot-clé yield return. Ainsi, nous pouvons aussi écrire :
using System;
using System.Collections;
public class Personnes : IEnumerable{
public IEnumerator
GetEnumerator(){
yield return "Michel";
yield return "Christine";
yield return "Mathieu";
yield return "Julien";
}
}
class Program{
static void
Personnes arrPersonnes = new Personnes();
foreach (string
s in arrPersonnes)
Console.WriteLine(s);
Console.ReadLine();
}
}
D’après les deux exemples précédents, il
semble que l’on peut considérer que le programme se branche juste après
la dernière instruction yield
return à chaque itération (et au début pour la première
itération). Nous vérifierons que cette intuition est la bonne.
Les itérateurs et la généricité
Il eut été dommage que l’on continue à utiliser la propriété object Current de l’interface IEnumerator alors que la généricité de C#2 permet d’éviter l’utilisation du type object pour signifier, n’importe quel type. Ainsi, le framework redéfinit les interfaces IEnumerable et IEnumerator avec la généricité comme ceci :
namespace System.Collections.Generic{
[System.Runtime.InteropServices.ComVisibleAttribute(false)]
[System.CLSCompliantAttribute(false)]
public interface
IEnumerable<T>{
System.Collections.Generic.IEnumerator<T> GetEnumerator();
}
[System.Runtime.InteropServices.ComVisibleAttribute(false)]
[System.CLSCompliantAttribute(false)]
public interface
IEnumerator<T> : System.IDisposable{
T Current { get;
}
bool
MoveNext();
}
}
Notez que la méthode IEnumerator.Reset() a disparu et que les objets implémentant IEnumerator<T> sont disposables.
Grâce à la généricité, nous pouvons maintenant être
plus précis et spécifier au compilateur que notre énumérable contient une
collection de chaînes de caractères et non d’objets :
using System;
using System.Collections.Generic;
public class Personnes : IEnumerable<string>{
string[] m_Noms;
public Personnes(params string[]
Noms){
m_Noms = new string[Noms.Length];
Noms.CopyTo(m_Noms, 0);
}
// la méthode
GetEnumerator() de IEnumerable<T>
public IEnumerator<string>
GetEnumerator(){
foreach (string
s in m_Noms)
yield return s;
}
}
...
Plusieurs itérateurs pour une même classe conteneur
Comme en C#1, il est possible d’implémenter
plusieurs énumérateurs pour un même énumérable. Voici un exemple :
using System;
using System.Collections.Generic;
public class Personnes{
string[] m_Noms;
public Personnes(params string[]
Noms){
m_Noms = new string[Noms.Length];
Noms.CopyTo(m_Noms, 0);
}
public IEnumerable<string> Reverse{
get {
for (int i = m_Noms.Length - 1; i >= 0; i--)
yield
return m_Noms[i];
}
}
public IEnumerable<string> PositionsPaires{
get{
for (int i = 0; i < m_Noms.Length ; i++,i++)
yield
return m_Noms[i];
}
}
public IEnumerable<string> Concat{
get{
foreach
(string s in
Reverse)
yield
return s;
foreach
(string s in
PositionsPaires)
yield
return s;
}
}
}
class Program{
static void
Personnes arrPersonnes = new Personnes("Michel", "Christine",
"Mathieu", "Julien");
Console.WriteLine("-->Itérateur
Reverse");
foreach (string s in arrPersonnes.Reverse) Console.WriteLine(s);
Console.WriteLine("-->Itérateur
PositionsPaires");
foreach (string s in arrPersonnes.PositionsPaires) Console.WriteLine(s);
Console.WriteLine("-->Itérateur
Concat");
foreach (string
s in arrPersonnes.Concat) Console.WriteLine(s);
Console.ReadLine();
}
}
Ce programme affiche :
-->Itérateur Reverse
Julien
Mathieu
Christine
Michel
-->Itérateur PositionsPaires
Michel
Mathieu
-->Itérateur Concat
Julien
Mathieu
Christine
Michel
Michel
Mathieu
Le
mot-clé yield break
Il est possible que l’on ne souhaite énumérer
qu’une partie des objets d’un énumérable. Pour signifier à une
boucle foreach
de s’arrêter il suffit d’employer le mot-clé yield break.
...
public IEnumerator<string> GetEnumerator(){
// TODO ajouter le test que m_Noms ait au moins deux
éléments
for (int i = 0; i < 2;i++ )
yield return m_Noms[i];
yield break;
Console.WriteLine("hello");
// Warning : Unreachable code detected
}
...
Ce programme affiche :
Michel
Christine
Notez que le code situé dans le corps d’une méthode après le mot-clé yield break n’est pas atteignable (i.e il ne sera jamais exécuté). Si vous écrivez du code non atteignable, le compilateur émet un avertissement.
Contraintes syntaxique imposées par l’utilisation des mot-clés yield return et yield break
· Les mots-clé yield break et yield return ne peuvent apparaîtrent que dans le corps d’une méthode, le corps d’un accesseur d’une propriété ou dans le corps d’un opérateur.
· Les mots-clé yield break et yield return ne peuvent apparaîtrent dans le corps d’une méthode anonyme.
· Les mots-clé yield break et yield return ne peuvent apparaîtrent dans une clause finally.
· Les mots-clé yield break et yield return ne peuvent apparaîtrent dans une clause try qui admet au moins une clause catch.
· Les mots-clé yield break et yield return ne peuvent apparaîtrent dans une méthode qui a des arguments ref ou out. Concrètement, il ne faut pas qu’une telle méthode puisse retourner ni plus ni moins qu’un énumérateur.
Exemple
d’un itérateur récursif
Voici un exemple qui montre toute la puissance des
itérateurs de C#2 pour énumérer une structure de données non plate, telle
qu’un arbre binaire :
using System;
using System.Collections.Generic;
public class
Node<T>{
public Node(T item , Node<T> leftNode , Node<T>
rightNode){
m_Item = item;
m_LeftNode = leftNode;
m_RightNode = rightNode;
}
public Node<T>
m_LeftNode;
public Node<T>
m_RightNode;
public T m_Item;
}
public class BinaryTree<T>{
Node<T> m_Root;
public BinaryTree(Node<T> Root){
m_Root = Root;
}
public IEnumerable<T>
InOrder{
get{
return PrivateScanInOrder(m_Root);
}
}
private IEnumerable<T>
PrivateScanInOrder(Node<T> root){
if (root.m_LeftNode != null){
foreach
(T item in PrivateScanInOrder(root.m_LeftNode)){
yield
return item;
}
}
yield return
root.m_Item;
if (root.m_RightNode != null){
foreach
(T item in PrivateScanInOrder(root.m_RightNode)){
yield
return item;
}
}
}
}
class Program{
static void
BinaryTree<string>
binaryTree = new BinaryTree<string>(
new Node<string>( "A",
new Node<string>( "B"
, null , null
),new Node<string>( "C"
,
new Node<string>( "D" , null
, null ),new Node<string>( "E" , null
, null ))));
foreach (string
s in binaryTree.InOrder)
Console.WriteLine(s);
Console.ReadLine();
}
}
L’arbre binaire construit dans la méthode Main() est
celui ci:
Le
programme affiche ceci:
B
A
D
C
E
Interprétation des itérateurs par le compilateur de C#2
Voici la section qui va enfin expliquer ce que fait le compilateur C#2 lorsqu’il rencontre les mots-clé yield break et yield return. Il faut garder à l’esprit qu’aucune instruction IL n’a été rajoutée par rapport à .NET1 pour implémenter cette fonctionnalité (contrairement aux génériques où le système de type Common Type System a été revu).
La classe énumérateur est implémentée automatiquement
par le compilateur
Il est temps de préciser que toute méthode qui contient une instruction yield doit retourner un énumérable ou un énumérateur. En conséquence, toute méthode qui contient une instruction yield doit avoir pour type de retour une des interfaces System.Collections.Generic.IEnumerable<T>, System.Collections.IEnumerable, System.Collections.Generic.IEnumerator<T> ou System.Collections.IEnumerator. Dans tous les cas, cela donne lieu au retour d’un énumérateur puisque la seule raison d’implémenter un énumérable et de pouvoir fournir un énumérateur.
Comme vous vous en doutez si vous avec lu l’article précédent sur les méthodes anonymes, pour toute méthode qui contient une instruction yield le compilateur crée une classe. Cette classe implémente les quatre interfaces d’énumération si la méthode retourne une des deux interfaces énumérables. Dans ce cas, une instance de cette classe se retourne elle-même lorsqu’on la considère comme un énumérable et qu’on lui demande un énumérateur. Cette classe n’implémente que les deux interfaces d’énumérations si la méthode retourne une des deux interfaces d’énumération.
La méthode n’existe plus en tant que telle, mais son corps est alors dans la méthode MoveNext() de la nouvelle classe. Vérifions tout ceci sur un exemple :
using System;
using System.Collections.Generic;
class UneClasse{
public IEnumerable<string> UnIterateur(){
yield
return "str1";
yield return "str2";
yield return "str3";
}
}
class Program{
static void
UneClasse collec = new UneClasse();
foreach (string
s in collec.UnIterateur())
Console.WriteLine(s);
Console.ReadLine();
}
}
Le compilateur C#2 produit l’assemblage
suivant à partir du code précédent (l’assemblage est visualisé avec
l’outil Reflector
de Lutz Roeder qui supporte déjà les
assemblages de .NET2) :
Décompilons la méthode Main() pour vérifier qu’elle crée bien une instance de la classe <UnIterateur>d__0 (notez l’utilisation automatique du pattern using/dispose pour disposer l’itérateur) :
private static void
UneClasse classe1 = new UneClasse();
using
(IEnumerator<string>
enumerator1 = classe1.UnIterateur().GetEnumerator()){
string text1;
bool flag1;
goto Label_0022;
Label_0014:
text1 = enumerator1.get_Current();
Console.WriteLine(text1);
Label_0022:
flag1 = enumerator1.MoveNext();
if (flag1){
goto
Label_0014;
}
}
Console.ReadLine();
}
Voici un autre exemple tout aussi instructif :
using System;
using System.Collections.Generic;
class UneClasse{
public IEnumerable<int> UnIterateur(){
for (int
i = 0; i < 5; i++){
if (i
== 3) yield
break;
yield return i;
}
}
}
class Program{
static void
UneClasse collec = new UneClasse();
foreach (int
i in collec.UnIterateur())
Console.WriteLine(i);
Console.ReadLine();
}
}
Le compilateur C#2 produit l’assemblage suivant à partir du code précédent :
Une machine à état est fabriquée pour chaque énumérateur
Il est clair que le compilateur implémente notre méthode contenant un mot-clé yield, comme une machine à état. Pour cela, il a besoin de deux champs d’instances <>1__state et <>2__current. <>1__state définit l’état dans lequel se trouve la machine. Rappelez vous, nous avions déduit que le programme se branche juste après la dernière instruction yield return à chaque itération et au début pour la première itération. Cette magie est possible grâce au champs <>1__state. Le compilateur insère une instruction switch dés le début de la méthode pour que le programme se branche au bon endroit. Le compilateur positionne <>1__state pour la prochaine itération avant de quitter une itération.
Le champ <>2__current représente la valeur calculée par la dernière itération. Il est donc forcément du type de ce qu’on énumère (int32 dans nos deux derniers exemples).
Si notre entité énumérable est un objet, c’est à dire si la méthode qui contient une instruction yield est non statique (comme dans le premier cas), le compilateur produit un champ <>4__this qui référence l’objet énumérable. Dans le cas contraire aucun champ n’est créé.
Enfin, remarquez que si la méthode qui contient une
instruction yield
a des variables locales ou des arguments, ceux si sont capturés par le
compilateur qui en fait alors des champs de la classe qu’il crée (par
exemple le champs <i>5__1
capture la variable locale i dans le second exemple). Ceci est tout à fait comparable à
la capture de l’environnement lexical au moyen d’une fermeture que
l’on a vu dans le cas des méthodes anonymes. La classe fabriquée par le
compilateur est donc bien une fermeture et nul doute que l’on va pouvoir
détourner ceci pour allez plus loin que le concept d’itération.
Exemples avancés de l’utilisation des itérateurs de C#2
D’après la section précédente nous pouvons déduire deux propriétés intéressantes des itérateurs de C#2 absentes du mécanisme d’itération de C#1 :
· Les itérateurs de C#2 supporte le pattern ‘lazy évaluation’. C'est-à-dire que les éléments de la collection peuvent n’être produits que si besoin est. Autrement dit, comme un itérateur a un état (à l’instar d’une méthode anonyme), les éléments peuvent être calculés un par un, au fur et à mesure des demandes du client. Ils n’ont pas besoin d’être résident en mémoire.
·
Les itérateurs de C#2 peuvent itérer sur une
collection d’éléments à priori infinie (i.e bornée par les limites de la
machine).
Nous allons exploiter ces propriétés afin
d’utiliser les itérateurs dans d’autres contextes que
l’itération sur les éléments d’un énumérable.
Définitions : coroutine et de continuation
Les itérateurs de C#2 sont en fait une implémentation de la notion de coroutine. Une coroutine est une fonction qui a la particularité de reprendre son exécution là où elle s’était finie la dernière fois qu’on l’a exécuté. La notion de coroutine s’oppose à la notion plus connue de subroutine. Une subroutine est une fonction qui recommence au début à chaque exécution.
La notion de coroutine est une spécialisation de la notion de fermeture (présentée dans l’article précédent), puisque pour reprendre là où l’on s’était arrêté, il faut bien pouvoir sauver l’état des variables locales, cad le contexte d’exécution.
Le terme continuation désigne un contexte à partir duquel un programme peut poursuivre son exécution. Une continuation est donc l’ensemble des valeurs des variables locales union l’offset d’une instruction dans le corps d’une coroutine. Notez qu’une continuation est donc comparable à une pile d’un thread au niveau d’une fonction (stack frame en anglais).
Un exemple de continuation avec les itérateurs
Supposons une implémentation simplifiée d’un jeu d’échec. Les blancs commencent, puis les noirs jouent, puis les blancs jouent, puis les noirs jouent… Juste avant que les blancs jouent un coup, il peut être utile de sauver les résultats des calculs afin de pouvoir reprendre là où l’on en était lorsque les noirs auront joués. En C#1 il faudrait prévoir une classe pour stocker ces résultats. En C#2, grâce aux notions de coroutine et de continuation, il suffit juste d’une méthode contenant le mot-clé yield :
using System;
using System.Collections;
public class Program{
static IEnumerator
White(){
int resultatCalcul = 0;
while (true){
Console.WriteLine("white move, résultatCalcul=" + resultatCalcul);
resultatCalcul++;
yield return black;
}
}
static IEnumerator
Black(){
while (true){
Console.WriteLine("black move");
yield return
white;
}
}
static
IEnumerator black;
static IEnumerator
white;
static void
black = Black();
white = White();
IEnumerator enumerator = white; // honneur aux blancs
// on dispatche 5 fois
for
(int i = 0; i < 5;i++){
enumerator.MoveNext();
enumerator = (IEnumerator)enumerator.Current;
}
Console.ReadLine();
}
}
Ce programme affiche :
white move, résultatCalcul=0
black move
white move, résultatCalcul=1
black move
white move, résultatCalcul=2
Il faut bien comprendre le rôle des champs statiques black et white. Chaque fois que l’on appelle la méthode White(), un nouvel itérateur est créé. Il faut donc n’appeler cette méthode qu’une seule fois et stocker l’itérateur retourné dans le champ white.
Remarquez aussi que si on ne limitait pas
artificiellement le nombre de coups dans la méthode Main() (i.e si l’on remplaçait la
boucle for(int
i=0 : i<5 ;i++) par la boucle while(true) ou while(enumerator.MoveNext()))
les méthodes White()
et Black()
s’appelleraient en alternance sans fin. Si ces méthodes
s’appelaient d’une manière plus ‘traditionnelle’, ce
comportement ferait rapidement exploser la pile du thread. Ici il n’en
est rien. Cela vient du fait que la notion de continuation peut se comprendre
aussi comme une sorte de goto inter méthodes (rappelons qu’en C# l’utilisation du mot-clé goto doit être confinée dans le
corps d’une méthode).
La
pattern Pipeline
Les itérateurs sont particulièrement adaptés au
pattern pipeline que vous connaissez tous pour l’avoir utilisé dans vos
fenêtre de commande shell. Par exemple :
using System;
using System.Collections.Generic;
class Program{
static public
IEnumerable<int>
PipelineIntegerRange(int begin,int end){
System.Diagnostics.Debug.Assert(begin
< end);
for(int
i=begin;i<=end ;i++)
yield return i;
}
static public
IEnumerable<int>
PipelineMultiply(int factor , IEnumerable<int> input){
foreach (int
i in input)
yield return i * factor;
}
static public
IEnumerable<int>
PipelineFilterModulo(int modulo , IEnumerable<int> input ){
foreach (int
i in input)
if(
i%modulo == 0 )
yield
return i;
}
static public
IEnumerable<int>
PipelineJoin(IEnumerable<int> input1, IEnumerable<int>
input2){
foreach (int
i in input1)
yield
return i;
foreach (int
i in input2)
yield
return i;
}
static void
foreach (int
i in
PipelineJoin( PipelineIntegerRange(-4, -2),
PipelineFilterModulo(
3,
PipelineMultiply(
2,
PipelineIntegerRange(1,
10) ) ) ) )
Console.WriteLine(i);
Console.ReadLine();
}
}
Le programme affiche ceci:
-4
-3
-2
6
12
18
On comprend bien -4,-3 et -2 mais il est un peu plus compliqué de saisir le pourquoi du 6,12 et 18. Voici une explication schématisée:
PipelineIntegerRange(1,10)
produit 1 2 3 4 5 6 7 8 9 10
PipelineMultiply(2)
produit 2 4 6 8 10 12 14 16 18 20
PipelineFilterModulo(3)
produit 6
12 18
En faisant l’expérience de modifier le PipelineIntegerRange comme ceci…
...
static public
IEnumerable<int>
PipelineIntegerRange(int begin, int end){
System.Diagnostics.Debug.Assert(begin
< end);
for (int
i = begin; i <= end; i++){
Console.WriteLine("Production de:" + i);
yield return i;
}
}
...
…on obtient cette sortie :
Production
de:-4
-4
Production
de:-3
-3
Production
de:-2
-2
Production
de:1
Production
de:2
Production
de:3
6
Production
de:4
Production
de:5
Production
de:6
12
Production
de:7
Production
de:8
Production
de:9
18
Production
de:10
On voit bien qu’à aucun moment les entiers produits par un maillon du pipeline ne sont stockés d’une quelconque manière. Dés que le producteur initial (i.e PipelineIntegerRange) crée un entier, ce dernier est consommé immédiatement. Chaque maillon est un producteur et un consommateur d’entier (mis à part PipelineIntegerRange qui n’est que producteur d’entier).
Méthodes anonymes, itérateurs et foncteurs
Comme nous l’avons vu lors du précédent article, les méthodes anonymes sont conceptuellement proches de la notion de foncteurs du C++. Nous avons vu que certaines fonctionnalités de la STL étaient implémentées par certaines classes du framework. Il est aisé d’étendre ces fonctionnalités à tous types de collections et d’énumérables grâce aux itérateurs comme le montre le programme suivant :
using System;
using System.Collections.Generic;
class Program{
// nous aurions pu nommer Predicate ce qui est nommé ici Filtre
static public IEnumerable<T> Filter<T>(Predicate<T>
predicate, IEnumerable<T>
collection){
foreach (T item in
collection)
if
(predicate(item))
yield
return item;
}
static public IEnumerable<T> Transform<T>(Converter<T,T>
transformer, IEnumerable<T>
collection){
foreach (T item in collection)
yield return transformer(item);
}
static public IEnumerable<U> Converter<T, U>(Converter<T,
U> converter, IEnumerable<T>
collection){
foreach (T item in collection)
yield return converter(item);
}
static public
IEnumerable<int>
PipelineIntegerRange(int begin, int end){
System.Diagnostics.Debug.Assert(begin
< end);
for (int
i = begin; i <= end; i++)
yield return i;
}
static void
int modulo = 3;
int factor = 2;
foreach (string
s in Converter<int,string>( delegate(int item) { return "Hello:" + item.ToString(); },
Filter( delegate(int item) { return
(item % modulo == 0); },
Transform( delegate(int item) { return
item * factor; },
PipelineIntegerRange(1, 10)))))
Console.WriteLine(s);
System.Console.ReadKey();
}
}
Ce programme affiche :
Hello:6
Hello:12
Hello:18
Continuation
vs. Threading
Lorsque l’on parle de modèle producteur/consommateur, on est en général dans un contexte multithread. Cela fait deux fois que l’on parle de thread (rappelez vous, nous avons vu qu’une continuation est donc comparable à une pile d’un thread en train d’exécuter une fonction).
En fait, il est possible d’implémenter
certains patterns de concurrence avec les itérateurs de C#2. Voici un autre exemple
simple où un producteur calcule les nombres de la suite de Fibonacci tandis
qu’un consommateur affiche ces valeurs sur la console :
using System;
using System.Collections;
using System.Threading;
public class Program{
static AutoResetEvent
eventProducterDone = new AutoResetEvent(false);
static AutoResetEvent
eventConsumerDone = new AutoResetEvent(false);
static int
currentFibo;
static void
Fibo(){
int i1 = 1;
int i2 = 1;
currentFibo = 0;
// le producteur enclanche le mécanisme
eventProducterDone.Set();
while(true)
{
// on attend que le consommateur ait fini
eventConsumerDone.WaitOne();
// on produit
currentFibo = i1 + i2;
i1 = i2;
i2 =
currentFibo;
// on signale que l'on a produit
eventProducterDone.Set();
}
}
static void Main(){
Thread
threadProducteur = new Thread(Fibo);
// Notez la possibilité d’écrire directement le
nom d’une fonction à la place d’un délégué
threadProducteur.Start();
for (int
i = 1; i < 10; i++){
// on attend que le producteur ait fini
eventProducterDone.WaitOne();
// on consomme
Console.WriteLine(currentFibo);
// on signale que l'on a consommÃ
eventConsumerDone.Set();
}
Console.ReadLine();
}
}
Remarquez que l’état du thread producteur (i.e les valeurs de i1 et i2) est stocké à tout moment sur sa pile.
Voici la même problématique implémentée à
l’aide d’un itérateur :
using System;
using System.Collections.Generic;
public class Program{
static IEnumerator<int> Fibo(){
int i1 = 1;
int i2 = 1;
int currentFibo = 0;
while (true){
currentFibo = i1 + i2;
i1 = i2;
i2 = currentFibo;
// on signale que l'on a produit
yield return currentFibo;
}
}
static void
IEnumerator<int>
e = Fibo();
for (int
i = 1; i < 10; i++){
// on donne la main au producteur pour qu'il produise
e.MoveNext();
// on consomme
Console.WriteLine(e.Current);
}
Console.ReadLine();
}
}
Cette fois ci, les valeurs de i1 et i2 sont à tous moment stockées dans l’énumérateur (i.e la fermeture) créé par l’appel à la méthode Fibo().
Une limitation des itérateurs C#2
La limitation présentée dans la présente section ne sera pas gênante dans 99.99% des itérateurs créés. En fait je suis tombé dessus par hasard en essayant d’utiliser un itérateurs récursifs pour appliquer le crible d’Eratosthène qui permet de calculer les nombres premiers.
Le principe du crible est
simple. Voici un schéma pour l’expliquer :
2
3 4 5
6 7 8
9 10 11 12 13 14 15 16 17 18 19
20 21
3 5
7 9 11
13 15 17
19 21 3 est premier, 4,6,8,10,12,14,16,18 et 20 sont multiples de
2
5 7
11 13 17
19 5 est premier, 9 et 21 sont multiples de 3
7 11 13
17 19 7 est premier, il n’y a pas de multiple de 5 dans la
liste
11 13 17
19 11 est premier, il
n’y a pas de multiple de 7 dans la liste
13 17
19 13 est premier, il
n’y a pas de multiple de 11 dans la liste
17
19 17 est premier, il
n’y a pas de multiple de 13 dans la liste
19 19 est premier,
il n’y a pas de multiple de 17 dans la liste
Le premier nombre de chaque étape est un premier. A chaque étape on enlève ce nombre ainsi que tous ses multiples.
L’idée est d’avoir autant de pipeline que de nombres premiers et de faire la cascade sur un premier itérateur qui produit les entiers de 2 à N. Pour évaluer le nombre de pipeline nécessaire (i.e le nombre de nombres premiers entre 2 et N) on se sert d’un théorème conjecturé par Gauss et démontré par de la Vallée Poussin qui affirme que si P(N) désigne le nombre de nombres premiers inférieurs à N, alors :
Voici le programme et … ça marche !
using System;
using System.Collections.Generic;
class Program{
static public
IEnumerable<int>
PipelineIntegerRange(int begin, int end){
System.Diagnostics.Debug.Assert(begin
< end);
for (int
i = begin; i <= end; i++)
yield return i;
}
static public
IEnumerable<int>
PipelinePrime( IEnumerable<int> input ){
using (IEnumerator<int> e = input.GetEnumerator()){
e.MoveNext();
int premier = e.Current;
// le premier
nombre obtenu doit être un premier
Console.WriteLine(premier); ;
if
(premier != 0){
while
(e.MoveNext()){
// élimine tous les multiples de premier
if (e.Current % premier != 0)
yield
return e.Current;
}
}
}
}
const int
N = 100;
static void
Main(){
// Applique la
formule de Gauss/de la Vallée Poussin pour obtenir le nombre d'itérateur
int N_PREMIER = (int)Math.Floor( ((double)N)/Math.Log(N) );
// Produit un
pipeline de N_PREMIER PipelinePrime chainé avec un PipelineIntegerRang
// Chaque appel à PipelinePrime produit
un itérateur
List<IEnumerable<int>> list = new
List<IEnumerable<int>>();
list.Add(PipelinePrime(PipelineIntegerRange(2, N)));
for(int
i=1 ; i<N_PREMIER ; i++)
list.Add(PipelinePrime(list[i-1]));
// traverse toutes les valeurs du
dernier itérateur dans la chaine
// afin de
provoquer la cascade des calculs
foreach (int i in list[N_PREMIER-1]);
Console.ReadLine();
}
}
Je vous laisse le soin de modifier ce programme
pour avoir en bout de pipeline un itérateur qui produit les nombres
premiers…
La limitation de C#2 mise en évidence ici est l’impossibilité pour un itérateur de se référencer lui-même. En effet, on ne peut pas utiliser le mot clé this dans le corps d’une méthode contenant une instruction yield. Dans le cas d’une méthode d’instance, le mot clé this référence l’instance courante. Dans le cas d’une méthode statique le compilateur génère une erreur. Tous se passe comme si l’on n’était pas sensé savoir qu’une classe est produite par le compilateur et qu’un itérateur est une instance de cette classe ! J’imagine que l’on pourrait utiliser la réflexion pour récupérer une référence mais cela n’est pas satisfaisant.
Conclusion
Nous avons vu que les itérateurs de C#2 constituent un nouvel outil puissant et très adapté pour itérer, pour chaîner des traitement à la manière d’une pipeline de commande shell et pour implémenter certains paradigme dans le domaine de la concurrence. De même qu’avec les méthodes anonymes, la circonspection doit rester de mise. N’utilisez pas les itérateurs dans vos applications industrielles pour le plaisir (un peu comme je l’ai fait dans la dernière section :-)). Des objets et des classes sont produites implicitement et vous pouvez rapidement écrire du code incompréhensible.
Références :
Design
Patterns by GoF (Gang of Four) Erich Gamma, Richard Helm, Ralph
Johnson, John Vlissides
The C#
programming language de Anders Hejlsberg, Scott Wiltamuth, Peter Golde
Generic
algorithms for C# 2.0 using iterators and anonymous methods by Jonhathan
de Halleux
Iterators,
Not Just for Iteration Blog Wesner Moise
Implementation
of Iterators in C# 2.0 (Part 5) blog de Roshan James
Create Elegant
Code with Anonymous Methods, Iterators, and Partial Classes de Juval
Lowy
Fun
with Iterators and state machines blog de Matt Pietrek
Delegate based APIs blog de Krzysztof Cwalina
More Fun With Generics: Action,
Converter, Comparison blog de Scott
Allen
More
iterator fun with the producer/consumer pattern blog de Joe Duffy
External Iterators c2 Wiki
CoRoutines c2 Wiki
Continuation Explanation c2 Wiki
Continuations And
Coroutines c2
Wiki
Call With Current
Continuation c2
Wiki
Le langage de
programmation C++ Patrick Smacchia
Auteur : Patrick
Smacchia
Copyright © Octobre 2004
|
Patrick
Smacchia assure de nombreuses formations
sur .NET, à la fois dans l’industrie et dans le milieu universitaire
(Université
de Nice). Passionné par l’architecture logicielle, il aide
L’ouvrage Pratique de .NET et C# (O’Reilly 2003)
Après avoir construit plusieurs applications d’entreprises avec
C++/win32/COM/COM+/DCOM et Java/J2EE, il s’est tout naturellement
intéressé à .NET. De cette rencontre est né l’ouvrage Pratique de
.NET et C# (O’Reilly 2003) qui
couvre la plupart des aspects du développement sous .NET avec le
langage C# (architecture .NET sous jacente ; langage C# ;
bibliothèques ADO.NET, XML, WinForm, |
Patrick
les entreprises à concevoir et à développer leurs applications.
Ingénieur diplômé de