Boucles à base de générateurs et de transformations : un exemple plus complet
24 déc. 2011 Olivier Azeau En français 0
Dans un billet précédent, j'avais évoqué une approche pour l'écriture de boucles permettant d'expliciter la combinaison de diverses exigences.
Le reproche fait dans les commentaires de ce billet est que cette approche serait moins lisible et rendrait inutilement le code plus compliqué.
Pour ma part, je campe sur mes positions. L'approche n'est moins lisible que pour des exemples triviaux que l'on ne rencontre jamais dans un programme réel.
La complexité inhérente à ces programmes fait que, au final, un programme est plus facilement maintenu s'il se base sur une combinaison de générateurs et de transformations indépendantes que s'il se base sur des boucles où tous les ingrédients sont mélangés.
Ce débat me semble par ailleurs être une illustration de la différence entre "simple" et "facile" mise en lumière par Rich Hickey. Les boucles while/for sont certainement plus faciles à écrire au début mais elle ne donnent pas ce qu'il y a de plus simple à maintenir et faire évoluer.
Essayons donc de voir ce que cela donne avec un programme à peine plus riche que des exemples d'une ou deux lignes.
Soit un programme qui :
- demande à l'utilisateur de choisir une fonction parmi les suivantes :
- mettre un entier au carré
- calculer la somme des entiers inférieurs ou égaux à un entier donné
- calculer le k-ième terme de la suite de Syracuse à partir d'un entier donné, k étant un entier saisi par l'utilisateur
- demande à l'utilisateur de choisir un filtre parmi les suivants :
- prendre les k premiers éléments, k étant un entier saisi par l'utilisateur
- prendre les éléments inférieurs ou égaux à k, k étant un entier saisi par l'utilisateur
- prendre les éléments impairs inférieurs ou égaux à k, k étant un entier saisi par l'utilisateur
- Lorsque l'utilisateur a fait ces choix, affiche les images par la fonction choisie précédemment des entiers naturels strictement positifs restreints au filtre lui aussi choisi précédemment
Exemples d'utilisation :
- L'utilisateur choisit "mise au carré", puis "4 premiers éléments". Le programme affiche : 1, 4, 9, 16
- L'utilisateur choisit "somme des entiers inférieurs ou égaux", puis "impairs inférieurs à 17". Le programme affiche : 1, 3, 15
- L'utilisateur choisit "3ème terme de la suite de Syracuse", puis "éléments inférieurs à 6". Le programme affiche : 2, 4, 5, 1
Voici une implémentation à base de générateurs et de transformations. Le code complet est disponible sur github.
J'ai essayé de décrire la démarche étape par étape mais je ne parle pas de ce qui a, dans le cas présent, un intérêt moindre, comme par exemple le découplage au niveau de l'"interface utilisateur" pour faciliter l'écriture des tests.
Allons-y.
J'écris un test pour le cas "mettre un entier au carré" + "prendre les k premiers éléments, k étant un entier saisi par l'utilisateur" et je ne me prends pas la tête pour son implémentation.
[Test] public void Compute_Square_For_FourFirstItems() { var ui = new FakeUserInteraction( "square", "first items", "4" ); Computer.Execute(ui); Assert.That (ui.DisplayedMessage, Is.EqualTo("1, 4, 9, 16")); } |
public class Computer { public static void Execute(ITalkToUser ui) { ui.Display("1, 4, 9, 16"); } } |
Je rajoute un test pour le même cas mais avec un k différent. Après une implémentation naïve, le refactoring m'amène à faire une boucle "for" sur le nombre d'éléments et à afficher et à calculer les carrés dans cette boucle.
Il est évident que, à cet instant, je n'ai pas un besoin impérieux de faire appel à d'autres concepts.
[Test] public void Compute_Square_For_FiveFirstItems() { var ui = new FakeUserInteraction( "square", "first items", "5" ); Computer.Execute(ui); Assert.That (ui.DisplayedMessage, Is.EqualTo("1, 4, 9, 16, 25")); } |
public static void Execute(ITalkToUser ui) { var dontCare = ui.Ask("choose operation"); var dontCareAgain = ui.Ask("choose filter"); var numberOfItems = int.Parse(ui.Ask("number of items")); var results = new List<int>(); for(var i=1; i <= numberOfItems; i++) results.Add(i*i); ui.Display(string.Join(", ", results)); } |
Je rajoute un test pour le cas "mettre un entier au carré" + "prendre les éléments inférieurs ou égaux à k, k étant un entier saisi par l'utilisateur" et je commence par une implémentation naïve pour passer au vert.
[Test] public void Compute_Square_For_UnderTwenty() { var ui = new FakeUserInteraction( "square", "under", "20" ); Computer.Execute(ui); Assert.That (ui.DisplayedMessage, Is.EqualTo("1, 4, 9, 16")); } |
public static void Execute(ITalkToUser ui) { var dontCare = ui.Ask("choose operation"); var filter = ui.Ask("choose filter"); if( filter == "under" ) { ui.Display("1, 4, 9, 16"); } else { var numberOfItems = int.Parse(ui.Ask("number of items")); var results = new List<int>(); for(var i=1; i <= numberOfItems; i++) results.Add(i*i); ui.Display(string.Join(", ", results)); } } |
Un premier refactoring m'amène à rendre similaires les deux cas : ce sont tous les deux des boucles qui calculent des carrés
public static void Execute(ITalkToUser ui) { var dontCare = ui.Ask("choose operation"); var filter = ui.Ask("choose filter"); var results = new List<int>(); if( filter == "under" ) { var maxValue = int.Parse(ui.Ask("max value")); for(var i=1; i*i <= maxValue; i++) results.Add(i*i); } else { var numberOfItems = int.Parse(ui.Ask("number of items")); for(var i=1; i <= numberOfItems; i++) results.Add(i*i); } ui.Display(string.Join(", ", results)); } |
Un deuxième refactoring m'amène à extraire la fonction qui détermine le point d'arrêt de la boucle. On notera l'utilisation de lambda expressions avec fermeture pour capturer le paramètre k de la condition d'arrêt (soit un nombre d'éléments, soit une valeur maximale).
J'ai toujours ma boucle "for" mais je viens de réaliser une opération importante : le choix de la condition d'arrêt est, dans sa totalité (incluant le dialogue utilisateur), externalisé dans une fonction "ChooseFilter".
public static void Execute(ITalkToUser ui) { var dontCare = ui.Ask("choose operation"); var results = new List<int>(); var untilConditionIsVerifiedFor = ChooseFilter(ui); for(var i=1; untilConditionIsVerifiedFor(i); i++) results.Add(i*i); ui.Display(string.Join(", ", results)); } static Func<int,bool> ChooseFilter(ITalkToUser ui) { var filter = ui.Ask("choose filter"); if( filter == "under" ) { var maxValue = int.Parse(ui.Ask("max value")); return i => (i*i <= maxValue); } else { var numberOfItems = int.Parse(ui.Ask("number of items")); return i => (i <= numberOfItems); } } |
Je rajoute un test pour le cas "calculer la somme des entiers inférieurs ou égaux à un entier donné" + "prendre les k premiers éléments, k étant un entier saisi par l'utilisateur".
Comme toujours, je commence par une implémentation qui me permet de rapidement passer au vert.
[Test] public void Compute_IntegerSum_For_FiveFirstItems() { var ui = new FakeUserInteraction( "integer sum", "first items", "5" ); Computer.Execute(ui); Assert.That (ui.DisplayedMessage, Is.EqualTo("1, 3, 6, 10, 15")); } |
public static void Execute(ITalkToUser ui) { var results = new List<int>(); var operation = ui.Ask("choose operation"); if( operation == "integer sum" ) { results.AddRange(new int[] {1,3,6,10,15}); } else { var untilConditionIsVerifiedFor = ChooseFilter(ui); for(var i=1; untilConditionIsVerifiedFor(i); i++) results.Add(i*i); } ui.Display(string.Join(", ", results)); } |
Ensuite, toujours la même approche : je rends les deux cas similaires. En l'occurrence, j'explicite la boucle de calcul des "sommes de n premiers entiers"
public static void Execute(ITalkToUser ui) { var results = new List<int>(); var operation = ui.Ask("choose operation"); if( operation == "integer sum" ) { var untilConditionIsVerifiedFor = ChooseFilter(ui); for(var i=1; untilConditionIsVerifiedFor(i); i++) results.Add(i*(i+1)/2); } else { var untilConditionIsVerifiedFor = ChooseFilter(ui); for(var i=1; untilConditionIsVerifiedFor(i); i++) results.Add(i*i); } ui.Display(string.Join(", ", results)); } |
Pour terminer le refactoring, j'externalise le choix de l'opération.
public static void Execute(ITalkToUser ui) { var results = new List<int>(); var operation = ChooseOperation(ui); var untilConditionIsVerifiedFor = ChooseFilter(ui); for(var i=1; untilConditionIsVerifiedFor(i); i++) results.Add(operation(i)); ui.Display(string.Join(", ", results)); } static Func<int,int> ChooseOperation(ITalkToUser ui) { var operation = ui.Ask("choose operation"); if( operation == "integer sum" ) { return i => i*(i+1)/2; } else { return i => i*i; } } |
Je rajoute maintenant le cas de test "calculer la somme des entiers inférieurs ou égaux à un entier donné" + "prendre les éléments inférieurs ou égaux à k, k étant un entier saisi par l'utilisateur".
Une première implémentation m'amène à modifier le choix de la condition d'arrêt en y injectant l'opération réalisée.
[Test] public void Compute_IntegerSum_For_UnderTwelve() { var ui = new FakeUserInteraction( "integer sum", "under", "12" ); Computer.Execute(ui); Assert.That (ui.DisplayedMessage, Is.EqualTo("1, 3, 6, 10")); } |
public static void Execute(ITalkToUser ui) { var results = new List<int>(); var operation = ChooseOperation(ui); var untilConditionIsVerifiedFor = ChooseFilter(ui,operation); for(var i=1; untilConditionIsVerifiedFor(i); i++) results.Add(operation(i)); ui.Display(string.Join(", ", results)); } static Func<int,bool> ChooseFilter(ITalkToUser ui, Func<int,int> operation) { var filter = ui.Ask("choose filter"); if( filter == "under" ) { var maxValue = int.Parse(ui.Ask("max value")); return i => (operation(i) <= maxValue); } else { var numberOfItems = int.Parse(ui.Ask("number of items")); return i => (i <= numberOfItems); } } |
Cela fonctionne mais me laisse insatisfait : j'avais réussi à découpler le choix de la condition d'arrêt de l'opération et là j'ai dû réintroduire le couplage.
Pour corriger cela, il me faut sortir de la logique de la boucle "for". Je vais commencer par changer la structure de la boucle en introduisant un générateur de nombre entiers suivi d'un filtre (TakeWhile) et d'une projection (Select).
public static void Execute(ITalkToUser ui) { var operation = ChooseOperation(ui); var conditionIsVerified = ChooseFilter(ui,operation); var results = Integers() .TakeWhile (conditionIsVerified) .Select (operation); ui.Display(string.Join(", ", results)); } static IEnumerable<int> Integers() { int n = 1; while(true) { yield return n; n++; } } |
Dans un deuxième temps, je change l'écriture de mon filtre : plutôt que d'utiliser un TakeWhile avec une condition d'arrêt qui dépend du résultat de l'opération, je crée une fonction de filtrage qui dépend directement du choix utilisateur.
public static void Execute(ITalkToUser ui) { var operation = ChooseOperation(ui); var results = Integers().Select(operation); var filteredResults = ChooseFilter(ui)(results); ui.Display(string.Join(", ", filteredResults)); } static Func<IEnumerable<int>,IEnumerable<int>> ChooseFilter(ITalkToUser ui) { var filter = ui.Ask("choose filter"); if( filter == "under" ) { var maxValue = int.Parse(ui.Ask("max value")); return e => e.TakeWhile( n => n <= maxValue); } else { var numberOfItems = int.Parse(ui.Ask("number of items")); return e => e.Take(numberOfItems); } } |
A ce stade de l'écriture de mon programme, où j'ai implémenté 2 types d'opérations et 2 types de filtres, j'ai réussi à séparer les divers concepts.
Je me retrouve donc avec quatre éléments indépendants :
- un générateur de nombre entiers
- la définition d'une opération en quelques lignes à partir d'éléments externes (un choix utilisateur)
- la définition d'un filtre en quelques lignes sur des entiers à partir d'autres éléments externes (un autre choix utilisateur)
- une fonction principale qui ne dépend pas directement des éléments externes et qui tient en 4 lignes tout en restant limpide
public class Computer { public static void Execute(ITalkToUser ui) { var operation = ChooseOperation(ui); var results = Integers().Select(operation); var filteredResults = ChooseFilter(ui)(results); ui.Display(string.Join(", ", filteredResults)); } static IEnumerable<int> Integers() { int n = 1; while(true) { yield return n; n++; } } static Func<int,int> ChooseOperation(ITalkToUser ui) { var operation = ui.Ask("choose operation"); if( operation == "integer sum" ) { return i => i*(i+1)/2; } else { return i => i*i; } } static Func<IEnumerable<int>,IEnumerable<int>> ChooseFilter(ITalkToUser ui) { var filter = ui.Ask("choose filter"); if( filter == "under" ) { var maxValue = int.Parse(ui.Ask("max value")); return e => e.TakeWhile( n => n <= maxValue); } else { var numberOfItems = int.Parse(ui.Ask("number of items")); return e => e.Take(numberOfItems); } } } |
L'état où nous nous trouvons actuellement présente deux avantages (qui vont généralement de paire) :
- le code a une structure simple (éléments indépendants) qui reste facile à comprendre pour peu que l'on fasse l'effort d'apprendre des concepts qui vont au delà de l'écriture "classique" des boucles en programmation impérative.
- le code est maintenable : on va pouvoir faire évoluer les éléments indépendants sans toucher aux autres. C'est ce que nous allons voir tout de suite.
Je rajoute un test pour le cas "calculer la somme des entiers inférieurs ou égaux à un entier donné" + "prendre les éléments impairs inférieurs ou égaux à k, k étant un entier saisi par l'utilisateur".
La nouveauté ici est le filtre sur les éléments impairs.
Sans surprise, il me suffit de modifier la définition du filtre en fonction des choix utilisateurs sans toucher aux autres parties du code.
[Test] public void Compute_IntegerSum_For_OddUnderSeventeen() { var ui = new FakeUserInteraction( "integer sum", "odd under", "17" ); Computer.Execute(ui); Assert.That (ui.DisplayedMessage, Is.EqualTo("1, 3, 15")); } |
static Func<IEnumerable<int>,IEnumerable<int>> ChooseFilter(ITalkToUser ui) { var filter = ui.Ask("choose filter"); if( filter == "odd under" ) { var maxValue = int.Parse(ui.Ask("max value")); return e => e.TakeWhile( n => n <= maxValue ).Where( n => n%2==1 ); } else if( filter == "under" ) { var maxValue = int.Parse(ui.Ask("max value")); return e => e.TakeWhile( n => n <= maxValue ); } else { var numberOfItems = int.Parse(ui.Ask("number of items")); return e => e.Take(numberOfItems); } } |
Si je veux rajouter une opération, même une qui ne soit pas triviale, pas de problème non plus : je ne modifie que la partie "ChooseOperation".
Je rajoute un test pour le cas "calculer le k-ième terme de la suite de Syracuse à partir d'un entier donné, k étant un entier saisi par l'utilisateur" + "prendre les éléments inférieurs ou égaux à k, k étant un entier saisi par l'utilisateur".
[Test] public void Compute_SyracuseThirdItem_For_UnderSix() { var ui = new FakeUserInteraction( "syracuse", "3", "under", "6" ); Computer.Execute(ui); Assert.That (ui.DisplayedMessage, Is.EqualTo("2, 4, 5, 1")); } |
static Func<int,int> ChooseOperation(ITalkToUser ui) { var operation = ui.Ask("choose operation"); if( operation == "syracuse" ) { var rank = int.Parse(ui.Ask("rank")); return i => SyracuseSequence(i).ElementAt(rank-1); } else if( operation == "integer sum" ) { return i => i*(i+1)/2; } else { return i => i*i; } } static IEnumerable<int> SyracuseSequence(int seed) { var n = seed; while(true) { yield return n; if(n%2==0) n = n/2; else n = 3*n+1; } } |
J'espère avoir pu montrer que l'utilisation de générateurs et de diverses transformations (projections, filtres) pouvait avantageusement remplacer des boucles qui deviennent rapidement trop complexes dès que l'on est confronté à une variété de cas qui vont au delà du simple calcul et de la simple condition d'arrêt.
Et je crois qu'il ne faut pas se bloquer sur quelques concepts qui peuvent paraitre, au début, trop complexes pour ce que l'on veut faire. On y gagne rapidement en lisibilité et maintenabilité et, avec l'habitude, cette façon d'écrire devient aussi naturelle que les structures de boucle plus connues.