C# – Généricité et λ

Le présent article vise à survoler deux aspects importants de la programmation avec C#, soit la programmation générique et les expressions lambda, qu'on écrit habituellement λ.

Bases de programmation générique

Soit les trois méthodes suivantes :

// ...
static void Afficher(int val)
{
   Console.WriteLine("Valeur : {0}", val);
}
static void Afficher(float val)
{
   Console.WriteLine("Valeur : {0}", val);
}
static void Afficher(string val)
{
   Console.WriteLine("Valeur : {0}", val);
}
// ...

Vous remarquerez sans peine qu'elles ont toutes la même forme : même nom, même arité (même nombre de paramètres), même syntaxe à l'appel... Seuls des détails sémantiques diffèrent de l'une à l'autre : elles sont « pareilles » au type près!

Le polymorphisme est une approche permettant de généraliser de telles fonctionnalités. Dans l'exemple ci-dessous, toute classe implémentant l'interface IAffichable peut être affichée à travers la méthode Afficher(), bien que le code de la méthode Afficher() de chacun de ces IAffichable doive être rédigé explicitement :

// ...
interface Affichable
{
   void Afficher();
}
// ...
   static void Afficher(Affichable a)
   {
      a.Afficher();
   }
// ...

Cependant, cette approche a ses défauts. En particulier, elle est intrusive : il faut implémenter une interface ou dériver d'une classe pour en profiter, ce qui impose des choix au code qui souhaite être utilisé par la méthode de classe Afficher(). Parfois, on souhaitera en arriver à une solution moins fortement couplée, plus flexible.

La généricité permet d'exprimer des méthodes et des classes identiques sur le plan algorithmique, mais différant sur la base des types. Par exemple, une liste de quelque chose plutôt qu'une liste d'entiers, ou une méthode capable d'afficher quelque chose plutôt que spécifiquement une chaîne de caractères. Par convention, le type de ce quelque chose sera souvent indiqué par la lettre T (pour type) ou U (celle qui suit T dans l'alphabet), mais ce n'est qu'une convention :

// ...
static void Afficher<T>(T val)
{
   Console.WriteLine("Valeur: {0}", val);
}
// ...

Avec cette version de la méthode Afficher(), le code client déterminera les versions de Afficher() qui seront générées sur la base des types utilisés en pratique. Le compilateur générera une méthode distincte par type (ou combinaison de types) utilisé(s). Pour Afficher<T>(T), qui se limite à écrire l'instance de T à la console une fois celle-ci transformée en chaîne de caractères, le code fonctionnera essentiellement à tout coup car tous les types .NET se convertissent en string. Quelques exemples :

Afficher(3); // T est int
Afficher(3.5); // T est double
Afficher("J'aime mon prof"); // T est string

La généricité s'applique autant aux types qu'aux méthodes. Ainsi, il est possible de programmer une classe ListeEntiers capable d'organiser une liste chaînée de noeuds contrenant des int, mais il est mieux encore (car plus polyvalent) de programmer une classe Liste<T> capable d'organiser une liste chaînée de noeuds contenant des T. Ceci permet d'entreposer des éléments de type T, dicté par le code client; ce faisant, nous écrivons une seule classe générique et le compilateur en génère tous les cas particuliers pour nous, en fonction des besoins.

Comparez les deux versions :

Classe ListeEntiers RemarquesClasse Liste<T>
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ExerciceListeEntiers
{
   class ListeEntiers
   {

La seule différence entre les deux classes jusqu'ici est dans le nom (plus spécifique à gauche, plus générique à droite) et dans le marqueur (à droite) du fait que la classe Liste est générique sur la base d'un type qui y sera nommé T.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ExerciceListeGénérique
{
   class Liste<T>
   {
// ...
      class Noeud
      {
         public int Valeur
         {
            get;
            set;
         }
         public Noeud Successeur
         {
            get;
            set;
         }
         public Noeud(int valeur)
         {
            Valeur = valeur;
            Successeur = null;
         }
      }

Pour la représentation d'un noeud sous forme de classe interne et privée, la nuance entre les deux implémentations et que celle de gauche contient des int alors que cette de droite contient des T.

// ...
      class Noeud
      {
         public T Valeur
         {
            get;
            set;
         }
         public Noeud Successeur
         {
            get;
            set;
         }
         public Noeud(T valeur)
         {
            Valeur = valeur;
            Successeur = null;
         }
      }
// ...
      private Noeud Tête
      {
         get;
         set;
      }
      private Noeud Dernier
      {
         get;
         set;
      }
      public bool Vide
      {
         get { return Tête == null; }
      }
      public ListeEntiers()
      {
         Tête = null;
         Dernier = null;
      }

Pour tout ce qui tient aux noeuds plutôt qu'aux valeurs entreposées dans les noeuds, le code est identique de part et d'autre.

// ...
      private Noeud Tête
      {
         get;
         set;
      }
      private Noeud Dernier
      {
         get;
         set;
      }
      public bool Vide
      {
         get { return Tête == null; }
      }
      public Liste()
      {
         Tête = null;
         Dernier = null;
      }
// ...
      public void Ajouter(int valeur)
      {
         Noeud p = new Noeud(valeur);
         if (Vide)
         {
            Tête = p;
            Dernier = p;
         }
         else
         {
            Dernier.Successeur = p;
            Dernier = p;
         }
      }

L'ajout d'une valeur est identique de part et d'autre si on fait exception du type de la valeur ajoutée.

// ...
      public void Ajouter(T valeur)
      {
         Noeud p = new Noeud(valeur);
         if (Vide)
         {
            Tête = p;
            Dernier = p;
         }
         else
         {
            Dernier.Successeur = p;
            Dernier = p;
         }
      }
// ...
      public class Énumérateur
      {
         private Noeud Courant
         {
            get;
            set;
         }
         private ListeEntiers Source
         {
            get;
            set;
         }
         public Énumérateur(ListeEntiers src)
         {
            Source = src;
            Courant = null;
         }
         public bool HasNext
         {
            get
            {
               return Source != null &&
                      !Source.Vide &&
                      (Courant == null || Courant.Successeur != null);
            }
         }
         public void MoveNext()
         {
            if (Courant == null)
               Courant = Source.Tête;
            else
               Courant = Courant.Successeur;
         }
         public int Valeur
         {
            get { return Courant.Valeur; }
         }
      }
      public Énumérateur GetÉnumérateur()
      {
         return new Énumérateur(this);
      }
   }
}

Les énumérateurs sont eux aussi identiques au type de liste et de valeur près.

// ...
      public class Énumérateur
      {
         private Noeud Courant
         {
            get;
            set;
         }
         private Liste<T> Source
         {
            get;
            set;
         }
         public Énumérateur(Liste<T> src)
         {
            Source = src;
            Courant = null;
         }
         public bool HasNext
         {
            get
            {
               return Source != null &&
                      !Source.Vide &&
                      (Courant == null || Courant.Successeur != null);
            }
         }
         public void MoveNext()
         {
            if (Courant == null)
               Courant = Source.Tête;
            else
               Courant = Courant.Successeur;
         }
         public T Valeur
         {
            get { return Courant.Valeur; }
         }
      }
      public Énumérateur GetÉnumérateur()
      {
         return new Énumérateur(this);
      }
   }
}

Considérant que l'effort d'écriture est à peu près le même d'un côté comme de l'autre, pourquoi se priverait-on d'écrire des types et des fonctions génériques, résolvant d'un seul trait plusieurs problèmes plutôt qu'un seul? Cela dit, la situation n'est pas toujours aussi simple ou évidente que ce que nous avons présenté jusqu'ici...

Introduction aux instructions λ

Dans certains cas, passer de ListeEntiers à Liste<T> ne demande presque aucun effort du côté du code client. Un cas typique est celui de la méthode Afficher(), aperçue plus haut, qui est aussi simple à rédiger pour une Liste<T> que pour une ListeEntiers :

Afficher ListeEntiersAfficher Liste<T>
static void Afficher<T>(ListeEntiers lst)
{
   ListeEntiers.Énumérateur e = lst.GetÉnumérateur();
   while (e.HasNext)
   {
      e.MoveNext();
      Console.Write("{0} ", e.Valeur);
   }
   Console.WriteLine();
}
static void Afficher<T>(Liste<T> lst)
{
   Liste<T>.Énumérateur e = lst.GetÉnumérateur();
   while (e.HasNext)
   {
      e.MoveNext();
      Console.Write("{0} ", e.Valeur);
   }
   Console.WriteLine();
}

Dans d'autres cas, en C#, il est beaucoup moins évident de généraliser le code (c'est plus simple en C++ – voir ../Divers--cplusplus/templates.html pour des détails). Par exemple, imaginons une méthode capable de calculer la sommes des nombres impairs dans une liste… Est-ce une opération raisonnable sur des float? Sur des string? Pour cette raison, C# ne permet pas d'écrire directement quelque chose comme ce qui suit, à moins que l'on n'ajoute un peu d'information sémantique :

// ...
static T somme<T>(T x, T y) // non, malheureusement, ceci n'est pas légal tel quel
{
   return x + y;
}
// ...

Heureusement, il y a de l'espoir! Pour expliquer une manière de généraliser les programmes sans trop de douleur, procédons par étapes.

Représenter une méthode par sa signature – le type Func<T0, T1, ..., R>

Examinez le code suivant :

// ...
static T Appliquer<T>
   (T x, T y, Func<T, T, T> oper)
{
   return oper(x, y);
}
// ...

Un Func<T0,T1,...,R> représente une méthode qui :

C'est abstrait, mais... Est-ce utile? Examinons le code suivant :

// ...
static int Somme(int x, int y)
{
   return x + y;
}
static void Main(string[] args)
{
   Console.WriteLine(Appliquer(2, 3, Somme));
}
// ...

Cela peut sembler abusif pour afficher le résultat de l'expression 2 + 3, mais l'idée est de nous aider à mieux comprendre nos options.

Créer des fonctions au besoin – les λ

C# offre une syntaxe concise pour des objets qui se manipulent comme des fonctions. On nomme de tels objets des lambdas (lettre grecque λ). Avec une lambda, on peut écrire :

static void Main(string[] args)
{
   Console.WriteLine(Appliquer(2, 3, (int x, int y) => x + y) );
}

... ou même, quand ce n'est pas ambigu :

static void Main(string[] args)
{
   Console.WriteLine(Appliquer(2, 3, (x, y) => x + y));
}

En C#, l'écriture suivante :

(int x, int y) => x + y

... est équivalente à quelque chose comme :

static int NomInconnu(int x, int y) 
{
   return x + y;
}

Avec cette écriture compacte, le type de retour dépend du type de l'expression évaluée par la λ (donc, ici, le type de la somme de deux int).

La λ n'a pas de nom officiellement connu du programme. Pour cette raison, il est d'usage, pour profiter d'une λ, de la déposer dans un Func de signature appropriée

Func<int,int,int> somme = (x,y) => x+y;
Console.WriteLine(Appliquer(2, 3, somme));

Examinons, muni de ces nouveaux outils, un exemple de code client pour la version générique et la version non-générique d'une liste.

Classe ListeEntiers (code client) RemarquesClasse Liste<T> (code client)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ExerciceListeEntiers
{
   class Program
   {
      class ListeVideException : ApplicationException { }

De prime abord, les outils sont les mêmes de part et d'autre.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ExerciceListeGénérique
{
   class Program
   {
      class ListeVideException : ApplicationException { }
// ...
      static void Afficher(ListeEntiers lst)
      {
         ListeEntiers.Énumérateur e = lst.GetÉnumérateur();
         while (e.HasNext)
         {
            e.MoveNext();
            Console.Write("{0} ", e.Valeur);
         }
         Console.WriteLine();
      }

Tel que mentionné plus haut, pour une fonction se limitant à afficher les éléments d'une liste, les versions génériques et non-génériques sont à peu près identiques.

// ...
      static void Afficher<T>(Liste<T> lst)
      {
         Liste<T>.Énumérateur e = lst.GetÉnumérateur();
         while (e.HasNext)
         {
            e.MoveNext();
            Console.Write("{0} ", e.Valeur);
         }
         Console.WriteLine();
      }
// ...
      static int TrouverPlusPetit(ListeEntiers lst)
      {
         if (lst.Vide)
            throw new ListeVideException();
         ListeEntiers.Énumérateur e = lst.GetÉnumérateur();
         e.MoveNext();
         int résultat = e.Valeur;
         while (e.HasNext)
         {
            e.MoveNext();
            résultat = Math.Min(résultat, e.Valeur);
         }
         return résultat;
        }

Muni de ces outils, on peut aisément généraliser TrouverPlusPetit() pour obtenir une méthode TrouverMeilleur() qui, sur la base d'un critère qui prend deux T et retourne le « meilleur » des deux, applique ce critère à tous les éléments de la liste et retourne le« meilleur » du lot en fin de parcours.

Pour faire en sorte que TrouverMeilleur() ait un comportement équivalent à celui de TrouverPlusPetit(), une critère convenable serait Math.Min.

Notre algorithme TrouverMeilleur() aura une précondition, soit que la liste à laquelle il est appliqué soit non vide. Initialement, le « meilleur » sera le premier élément.

Notez que la solution générique sera plus abstraite et plus générale qu'auparavant, mais pas moins rapide.

// ...
      static T TrouverMeilleur<T>(Liste<T> lst, Func<T,T,T> meilleur)
      {
         if (lst.Vide)
            throw new ListeVideException();
         Liste<T>.Énumérateur e = lst.GetÉnumérateur();
         e.MoveNext();
         T résultat = e.Valeur;
         while (e.HasNext)
         {
            e.MoveNext();
            résultat = meilleur(résultat, e.Valeur);
         }
         return résultat;
      }
// ...
      static int CalculerSommeImpairs(ListeEntiers lst)
      {
         int résultat = 0;
         ListeEntiers.Énumérateur e = lst.GetÉnumérateur();
         while (e.HasNext)
         {
            e.MoveNext();
            if (e.Valeur % 2 != 0)
               résultat += e.Valeur;
         }
         return résultat;
      }

Muni de λ, on peut généraliser CalculerSommeImpairs() (à gauche) pour obtenir une méthode AccumulerSi() (à droite) qui prend en paramètre :

  • une valeur initiale init de type T. On veut 0 pour une somme, 1 pour un produit, "" pour une concaténation, etc.;
  • un prédicat (fonction booléenne) pred applicable à un T. Pensez ici à (n)=>(n % 2 != 0) pour un prédicat qui s'avère seulement si n est impair;
  • une fonction cumul applicable à deux T et qui retourne un T. Par exemple : somme de deux T, produit de deux T, minimum de deux T, etc.; et
  • cumule les éléments de la Liste<T> pour lequel pred s'avère étant donné init et cumul, et retourne le cumul ainsi calculé.
// ...
      static T AccumulerSi<T>(Liste<T> lst, T init, Func<T,bool> pred, Func<T,T,T> cumul)
      {
         T résultat = init;
         Liste<T>.Énumérateur e = lst.GetÉnumérateur();
         while (e.HasNext)
         {
            e.MoveNext();
            if (pred(e.Valeur))
               résultat = cumul(résultat, e.Valeur);
         }
         return résultat;
      }
// ...
      static void Main(string[] args)
      {
         ListeEntiers lst = new ListeEntiers();
         Random random = new Random();
         for (int i = 0; i < 10; ++i)
            lst.Ajouter(random.Next(1, 10));
         Afficher(lst);
         Console.WriteLine("Plus petite valeur: {0}", TrouverPlusPetit(lst));
         Console.WriteLine("Somme des valeurs impaires: {0}", CalculerSommeImpairs(lst));
      }
   }
}

Les programmes principaux de part et d'autre sont semblables, mais celui qui manipule une liste générique est plus flexible, donc plus utile.

// ...
      static void Main(string[] args)
      {
         Liste<int> lst = new Liste<int>();
         Random random = new Random();
         for (int i = 0; i < 10; ++i)
            lst.Ajouter(random.Next(1, 10));
         Afficher(lst);
         Console.WriteLine("Plus petite valeur: {0}", TrouverMeilleur(lst, Math.Min));
         Console.WriteLine("Somme des valeurs impaires: {0}", AccumulerSi(lst, 0, (i) => i % 2 != 0, (i, j) => i + j));
         Console.WriteLine("Produit des valeurs impaires: {0}", AccumulerSi(lst, 1, (i) => i % 2 != 0, (i, j) => i * j));
      }
   }
}

Voilà pour un (très) bref survol du sujet.

Lectures complémentaires

Quelques liens pour en savoir plus.

L'implémentation des méthodes anonymes en C#, texte portant plus sur les délégués que sur les λ mais les implémentations sont connexes, par Raymond Chen en 2006 :

Pour la perspective du langage C++ sur la généricité, voir :

Pour la perspective du langage C++ sur les expressions λ, voir :

Texte de 2015 par Eric Lippert sur l'interaction entre le transtypage et le code générique avec C# : http://ericlippert.com/2015/10/14/casts-and-type-parameters-do-not-mix/


Valid XHTML 1.0 Transitional

CSS Valide !