L'Agilitateur Création de logiciels : de l'agilité à l'artisanat

Le B.A.BA de la programmation, celui que tout le monde, ou presque, commence par apprendre en débutant l'écriture d'algorithmes, ce sont les structures de contrôle en programmation impérative : les tests, les boucles, les sauts...
Mais, avec le temps, cela devient, de moins en moins vrai. Les instructions de sauts ont commencé à disparaitre des langages informatiques quand deux illustres néerlandais et suisse ont évoqué leur nocivité.
En ce qui concerne les structure de tests, il a fallu attendre l'avènement des langages orientés objet pour que le polymorphisme devienne "mainstream". Aujourd'hui, on peut ouvertement se revendiquer anti-if.

La seule structure qui résiste encore bien, ce sont les boucles. Mais la redécouverte de la programmation fonctionnelle à travers sa présence à dose plus ou moins grande dans des langages "en vogue" (python, ruby, javascript, C#, scala...) fait que le développeur lambda^[1] peut commencer à entrevoir d'autres manières de décrire des opérations sur des ensembles d'éléments.

Je vais dans ce billet essayer de montrer ce que l'on peut faire en C# sur ce sujet.
Prenons un exemple simple : "afficher les carrés des entiers naturels inférieurs ou égaux à 10"

L'implémentation la plus courante ressemblera à une boucle sur des entiers au sein de laquelle seront mis en oeuvre le calcul et l'affichage adéquats :

for(var i=0; i<=10; i++)
  Console.WriteLine( i*i );

Ca fonctionne, mais ce n'est pas très explicite. L'énoncé du problème comporte 4 exigences distinctes et le code proposé ne permet pas de les expliciter et les implémenter indépendamment les unes des autres :

1. afficher
2. les carrés
3. des entiers naturels
4. inférieurs ou égaux à 10

Commençons par les points (3) et (4). Pour expliciter les éléments sur lesquels portent l'opération, on pourrait écrire quelque chose dans ce genre :

foreach(var n in Sequence.OfN().TakeWhile( n => n<=10 ))
  Console.WriteLine( n*n );

Sequence.OfN() n'est pas du code standard C#. On va supposer que cela retourne un IEnumerable<int> qui est l'ensemble des entiers naturels. On s'interessera plus tard à son implémentation.
Le TakeWhile( n => n<=10 ) est quelque chose qui devrait être désormais naturel à tous les développeurs C# qui connaissent LINQ et les lambda expressions.

On va maintenant expliciter le point (2) en remontant son calcul dans la définition de l'ensemble de nos éléments :

foreach(var n2 in Sequence.OfN().TakeWhile( n => n<=10 ).Select( n => n*n ))
  Console.WriteLine( n2 );

Pour en finir avec la boucle, il ne reste plus qu'à imaginer un moyen simple pour effectuer un affichage sur un ensemble d'éléments donné :

Sequence.OfN().TakeWhile( n => n<=10 ).Select( n => n*n ).Apply( n2 => { Console.WriteLine(n2); } );

Et voilà... Notre boucle s'est métamorphosée en la concaténation d'opérations indépendantes sur des suites d'éléments :

1. afficher => Apply( n2 => { Console.WriteLine(n2); } )
2. les carrés => Select( n => n*n )
3. des entiers naturels => Sequence.OfN()
4. inférieurs ou égaux à 10 => TakeWhile( n => n<=10 )

L'avantage d'une telle écriture, c'est que l'on n'est plus condamné à des algorithmes monolithiques où la modification d'une exigence a des impacts sur les autres. On a remplacé cela par des briques de lego que l'on peut facilement recombiner.

Passons maintenant à l'implémentation. Définissons d'abord quelques briques de base sur lesquelles viendront s'appuyer les autres :

• la définition d'une suite initiale d'éléments IEnumerable<T>. Pour cela, on utilisera 2 méthodes :
  • IEnumerable<T> Of<T>(params T ts) pour une suite définie par la liste explicite de ses éléments
  • IEnumerable<T> Of<T>(Func<T> next) pour une suite définie par une fonction génératrice (chaque appel renvoie l'élément suivant de l'énumération)
• les opérations de transformation d'un IEnumerable<T> vers un IEnumerable<U> : nul besoin d'écrire quoi que ce soit pour cela, il y a déjà de quoi faire avec le LINQ de base
• une opération de terminaison void Now<T>(this IEnumerable<T> seq). Toutes les autres opérations étant à évaluation différée, il nous faut une opération qui force l'exécution.

Tout cela fait beaucoup de blabla pour finalement peu de code :

public static class Sequence
{
  public static IEnumerable<T> Of<T>(params T[] ts)
  {
    return ts;
  }

  public static IEnumerable<T> Of<T>(Func<T> next)
  {
    sendNext:
    yield return next();
    goto sendNext; // on aurait pu faire un while(true) mais le goto est plus fun, non ?
    // En tout cas, les codes CLR générés sont identiques.
  }

  public static void Now<T>(this IEnumerable<T> seq)
  {
    seq.Count(); // Demander le compte des éléments est un moyen simple pour forcer l'énumération
  }
}

A partir de là, implémenter notre Sequence.OfN() est une simple formalité. Il suffit d'initier un ensemble d'élément avec une fonction qui renvoie consécutivement les entiers naturels :

public static IEnumerable<int> OfN()
{
  var n=0;
  return Sequence.Of( () => n++ );
}

L'application d'une action sur chaque élément n'est guère plus compliquée :

public static IEnumerable<T> Apply<T>(this IEnumerable<T> seq, Action<T> action)
{
  return seq.Select( item => {action(item);return item;} );
}

Pour être tout à fait précis, le Apply étant défini à évaluation différée, notre exemple initial devrait se terminer par un Now pour forcer l'exécution :

Sequence.OfN().TakeWhile( n => n<=10 ).Select( n => n*n ).Apply( n2 => { Console.WriteLine(n2); } ).Now();

Passons maintenant à quelque chose d'un peu plus évolué. Les carrés des 10 premiers entiers, c'est sympa, mais la réalité est souvent plus complexe.
Prenons, par exemple, l'affichage des 20 premiers termes d'une suite d'entiers définie par récurrence :

var u = 1;
for(var i=0; i<20; i++)
{
  Console.WriteLine( u );
  u = 2*u+1;
}

Notre nouvelle écriture ressemblera à ça :

Sequence.Recurrence(1, x => 2*x+1).Take(20).Apply( n => { Console.WriteLine(n); } ).Now();

La méthode Recurrence est assez facilement définie à partir des autres méthodes d'initialisation :

public static IEnumerable<T> Recurrence<T>(T u0, Func<T,T> f)
{
  var u = u0;
  return Sequence.Of(u0).Concat( Sequence.Of( () => u=f(u) ) );
}

Notre collection ne pourrait pas être complète sans la star des algorithmes de boucles favoris des débutants : la suite de Fibonnacci.
En version "classique" :

var u = 1;
var v = 0;
for(var i=0; i<20; i++)
{
  Console.WriteLine( u );
  var w = u;
  u = u+v;
  v = w;
}

Et en version "moderne" :

Sequence.Fibonnaci().Take(20).Apply( n => { Console.WriteLine(n); } ).Now();

public static IEnumerable<int> Fibonnaci()
{
  return Sequence.Recurrence(new {fib=1,fib2=0}, x => new {fib=x.fib+x.fib2, fib2=x.fib}).Select(x => x.fib);
}

On remarquera au passage l'utilisation de types anonymes statiques.

Et pour finir, un petit exemple avec condition d'arrêt portant sur les élements manipulés avec un autre classique, la division euclidienne :

var a = 34;
var b = 5;

var q = 0;
var r = a;
while(r >= b)
{
  Console.WriteLine( "( q = {0}, r = {1} )", q ,r );
  q++;
  r -= b;
}

var quotientAndRemainder = Sequence
  .Recurrence(new{q=0,r=a}, x => new{ q = x.q+1, r = x.r-b })
  .Apply( x => { Console.WriteLine(x); } )
  .SkipWhile(x => x.r>=b)
  .First();

C'est fini...
J'espère que ce petit aperçu sur la manière d'écrire des boucles "autrement" donnera des envies d'exploration à ceux qui n'avaient jamais envisagé ces techniques d'écriture de code.
Comme d'habitude, les commentaires sont les bienvenus !