18 janvier 2022

crédits photo : Nicolas Singer

La boucle est une des principales structures dans un programme informatique. Son but est de répéter une instruction ou une série d'instructions jusqu'à qu'une condition soit atteinte (ou pour toujours dans le cas des boucles infinies). Tous les langages de programmation possèdent une syntaxe pour définir ces boucles, et même plusieurs syntaxes dans le cas des langages modernes. On va voir dans ce post, que choisir la bonne syntaxe en fonction de ce que l'on veut faire permet à son code d'être à la fois plus clair et plus élégant.

Le principe des boucles

Une boucle dans un programme, c'est quoi en fait ? On l'a dit plus faut, une boucle est une structure algorithmique qui permet de répéter une instruction plusieurs fois.

Imaginons que vous vouliez afficher 10 fois à l'écran le mot coucou. Sans boucle, on écrira cela :

print("coucou")
print("coucou")
print("coucou")
print("coucou")
print("coucou")
print("coucou")
print("coucou")
print("coucou")
print("coucou")
print("coucou")

Pas top, et évidemment pas réaliste si on veut afficher 1000 fois coucou à l'écran.

L'idée est donc d'utiliser une forme syntaxique qui permet de dire que l'instruction print("coucou") doit s'exécuter dix fois.

La préhistoire

Pour bien comprendre ce que propose les langages de programmation récents, prenant nous au jeu de remonter au langage que l'on peut considérer comme le plus ancien de tous : le langage machine que l'on appelle parfois l'assembleur.

Dans ce type de langage, il n'y a tout simplement aucune syntaxe spéciale pour définir les boucles.

Mais alors comment on fait ?

Le comportement normal d'un programme assembleur est d'exécuter les instructions en séquence dans l'ordre dans lequel elles se présentent.

Cet itinéraire peut être modifié par des instructions qui permettent de sauter directement vers une instruction placée à un autre endroit du programme. Faire une boucle consiste alors à rebrousser chemin, c'est-à-dire à sauter vers une instruction que l'on a déjà exécuté et qui se situe avant celle où se trouve actuellement. De la sorte, on exécute à nouveau une portion déjà réalisée, exactement comme un randonneur qui serait téléporté à nouveau à son point de départ pour refaire l'itinéraire parcouru.

En assembleur on repère l'emplacement d'une instruction en y associant une étiquette. On mettra donc l'étiquette à l'endroit où commence la boucle. A l'endroit où elle finit, on écrira une condition qui teste si le code doit être refait et qui si c'est le cas téléporte le processeur à l'étiquette.

Voici le code qui fait cela (bon ok ce n'est pas complètement de l'assembleur car dans ce type de langage il n'y pas d'instruction print et on ne manipule pas comme cela les chaines de caractères, mais ce qui est autour est bien de l'assembleur) :

MOVE #0, D0 // on met la valeur zéro dans la variable `D0`
etiquette:
   print("coucou")
   ADD #1, D0 // on incrémente D0
   CMP #10, D0 // on compare D0 avec dix
   BNE etiquette: // sauter à la ligne etiquette si la condition précédente est fausse

Si on avance un peu dans le temps, on quitte l'assembleur, et on arrive à une version élémentaire d'un des premiers langages grand public, le Basic, un langage fait au départ pour apprendre la programmation.

Dans les Basic primitifs, il n'y avait pas non plus de forme syntaxique pour les boucles, et on écrivait quelque chose de similaire à l'assembleur (notez que les lignes sont numérotées, ce qui permet de se brancher sur une ligne en citant son numéro avec l'instruction GOTO) :

10 I = 0 // on met la valeur zéro dans la variable I
20 print("coucou")
30 I = I + 1 // on incrémente la variable I
40 IF I < 10 GOTO 20 // si I ne vaut pas encore dix, sauter à la ligne 20

Ceux qui voudraient se replonger au temps béni où on devait numéroter les lignes de son programme peuvent se référer à ce manuel de programmation : How to program your commodore C64. Et oui j'ai appris à programmer sur un commodore 64, c'était en 1984.

Heureusement les langages ont évolué, avec en particulier l'apparition des langages dits structurés qui précisément vont nous donner des outils pour structurer notre code, et en particulier nos boucles.

Les langages structurés

Passons en effet aux langages disposant de formes syntaxiques évoluées permettant de définir les boucles. Ces formes permettent de baliser une séquence de code à répéter, et à indiquer à quelle condition ce code doit se répéter.

Sans remonter aux ancêtres que sont Fortran, Cobol, ou plus tard Pascal, voyons ce que proposent les langages actuels comme C, Java, Javascript, Python ou Ruby.

Leur structure de base est la boucle dite while qui délimite la partie du code à répéter (on appelle cette partie le corps de la boucle) et qui répète ce code tant qu'une condition est vérifiée. Revisitons notre affichage dans ces langages (vous pouvez cliquer sur les onglets pour afficher la version du code correspondant au langage sélectionné) :

int i = 0;
while (i < 10) {
    printf("coucou");
    i++;
}

Si vous trouvez que les exemples dans les trois premiers langages se ressemblent furieusement, vous n'avez pas tort. La syntaxe issue du C, basée en particulier sur des accolages pour délimiter les sections de code, a été très à la mode à une époque et s'est imposée dans toute une série de langages. On remarque ici l'originalité de Python qui utilise l'indentation pour délimiter le début et la fin du corps de la boucle, et de Ruby, qui délimite la fin de la section avec le mot clé end.

La plupart des langages proposent une forme alternative de la boucle while qui permet de tester la condition à la fin du corps de boucle et non pas au début. c'est le fameux do ... while que l'on appelle aussi parfois le repeat ... until. En voici quelques exemples :

int i = 0;
do {
    printf("coucou");
    i++;
}
while (i < 10);

On remarquera que Python et Ruby n'ont pas vraiment de structures do ... while mais permettent d'en créer l'équivalent en utilisant l'instruction break qui fait sortir du corps de la boucle dès qu'elle est exécutée. Si vous mettez cette instruction à la fin du corps de boucle en la précédant d'une condition, vous avez en effet l'équivalent d'un do ... while.

C'est l'occasion de dire que tous les langages permettent de sortir d'une boucle sans attendre la fin du corps, et c'est souvent l'instruction break qui permet cela. Cela peut avoir son utilité, par exemple pour sortir des boucles infinies ou pour quitter une boucle immédiatement.

Notons aussi que certains langages proposent l'instruction next qui permet d'abandonner la suite du corps de la boucle et de revenir immédiatement tester la condition. Utile par exemple si on souhaite court-circuiter une itération pour passer directement à la suivante.

Mais assez de détails et revenons au fonctionnement général de nos boucles.

La boucle for

La plupart des boucles while s'écrivent un peu de la même façon : On commence par initialiser une ou plusieurs variables, on teste une condition (qui en général dépend des variables que l'on vient d'initialiser), on exécute le corps de boucle, on fait évoluer les variables de la condition, et on recommence !

Pour tirer parti de ce fait, et aussi pour garder dans le corps de la boucle uniquement les instructions que l'on veut répéter, la plupart des langages proposent une autre façon d'écrire les boucles : la boucle for.

Celle-ci permet de définir d'un seul coup et juste avant le corps de la boucle, la partie initialisation, puis la partie condition, et enfin la partie évolution des paramètres de la condition.

La boucle for est donc une forme plus compacte de la boucle while, qui permet de bien séparer la partie qui fait tourner la boucle, de la partie qui est répétée.

Voici comment cette forme est proposée dans différents langages :

for (int i = 0; i < 10; i++)
    printf("coucou");
}

Vous noterez qu'il n'y a pas d'exemples en Python ou en Ruby. En effet, ces deux langages ne proposent pas cette forme compacte. Ne criez pas au scandale, nous allons voir pourquoi dans quelques lignes.

Les boucles et les listes

Arrêtons-nous un moment sur les types principaux d'usage des boucles dans un code informatique. A quoi servent-elles le plus souvent ?

On s'en doute, l'exemple que nous avons utilisé et qui consiste à afficher 10 fois à l'écran la même chose, ne représente pas un cas réel d'utilisation.

Si vous débutez en informatique, il va falloir me croire sur parole : dans la plupart des cas, les boucles servent à parcourir des listes de données.

Qu'on les appelle tableaux, collections, séries ou listes, ces structures de données représentent un ensemble ordonné et fini d'éléments. Comprenez par là que leurs éléments sont numérotés et que leur nombre est connu.

Parcourir ces listes, c'est passer en revue chacun de leurs éléments, du premier au dernier. Avec une boucle, cela consiste à utiliser un compteur qu'on initialise à zéro (en informatique, le premier élément d'une liste a souvent pour numéro zéro), et tant que ce compteur n'est pas supérieur à la longueur de la liste, on va chercher l'élément de numéro compteur, on fait ce qu'on doit faire avec, et on incrémente le compteur.

Prenons donc un nouvel exemple. On a une liste de cinq nombres, on veut afficher la valeur de chacun de ses nombres. Chaque langage a sa propre syntaxe pour noter des listes d'éléments, voici le code réalisant cela pour chacun d'entre eux avec la boucle for pour les langages qui en ont une, ou le while traditionnel pour Python et Ruby qui n'en n'ont pas :

int liste[] = { 2, 4, 23 , 14, 2 };
for (int i = 0; i < sizeof(liste)/sizeof(int) ; i++)
    printf(liste[i]);
}

Pendant longtemps, les exemples de code ci-dessus ont été l'unique façon de parcourir des listes. Mais une évolution dans les langages de programmation va nous proposer une alternative à la fois plus compacte et plus élégante. Il est temps pour la boucle foreach de faire son entrée...

La boucle foreach

La boucle foreach est une révolution. C'est une vraie boucle, mais son objectif principal n'est pas de répéter un bloc de code. Son objectif est de parcourir chaque élément d'une liste, et pour chacun de ses éléments, d'exécuter un bloc de code (notez la différence). Elle s'écrit en indiquant :

1. le nom de la variable qui va correspondre successivement à chaque élément de la liste
2. le nom de la liste que l'on souhaite parcourir
3. le corps de la boucle exécuté pour chaque élément de la liste, avec en l'intérieur la variable qui vaut l'élément en cours de parcours.

Sa forme théorique est la suivante (théorique car la syntaxe exacte dépend du langage) :

for (variable in liste) {
    // ces lignes sont exécutées pour chaque élément de la liste
    // avec variable qui représente l'élément en question
}

Alors on y gagne quoi ? C'est pareil dans le sens où le corps de la boucle va être exécuté plusieurs fois (autant de fois que la longueur de la liste), mais c'est bien mieux qu'avant, car la boucle foreach décharge le programmeur de s'occuper de la longueur de la liste et de l'index de ses éléments. Plus besoin de compteur, plus besoin de condition d'arrêt !

Le foreach est tellement puissant, que les langages qui l'ont intégré dès le départ, comme Python ou Ruby, ont fait l'impasse sur la boucle for vu précédemment. Java qui a intégré le foreach seulement depuis sa version 5, continue de proposer à la fois le for et le foreach, mais pour le parcours des listes, aucun intérêt d'utiliser encore le for.

Les examples ci-dessous, qui remplacent les boucles classiques (while ou for) par un foreach, montrent bien son intérêt (pas d'exemple en C, puisque ce langage ancien ne propose pas de foreach). Ne vous laissez pas abuser par le mot clé for qui reste le même que dans la boucle for traditionnelle. C'est la syntaxe située après ce for initial qui détermine s'il s'agit d'un for ou d'un foreach.

List<Integer> liste = Arrays.asList(2, 4, 23 , 14, 2);
for (Integer nombre : liste) {
    System.out.println(nombre);
}

En résumé, pour le cas particulier des boucles utilisées pour parcourir des listes, la structure foreach est à privilégier !

Seul bémol, cette structure foreach a un petit inconvénient, c'est qu'on ne connaît plus le numéro d'ordre de l'élément parcouru. Dans les boucles classiques, c'est la variable qui nous servait de compteur qui nous donnait cette information. Or il peut arriver dans votre code que vous souhaitiez appliquer un traitement différent, par exemple aux éléments de positions paires et aux éléments de positions impaires.

Certains langages proposent une variante du foreach qui permet de récupérer les index. En voici quelques exemples en Javascript, Python et Kotlin. Pour les autres langages, il faudra revenir aux boucles classiques ou introduire une variable supplémentaire qu'on incrémentera dans le corps de boucle.

let liste  = [ 2, 4, 23 , 14, 2 ];
for (const [index, nombre] of liste.entries()) {
    // on teste si l'index est pair. Pour cela on utilise le symbole % qui représente
    // le modulo, cad le reste de la division entière.
    // Si pas de reste quand on divise par deux, c'est que le nombre est pair.
    if (index % 2 === 0) console.log("En position paire : " + nombre);
    else console.log("En position impaire:" + nombre)
}

Le foreach pour autre chose que le parcours de liste ?

On l'a dit, le foreach est taillé sur mesure pour le parcours des listes. Mais pour les autres cas ? Revenons à l'exemple que nous avons pris au tout début de ce post : Afficher dix fois à l'écran un message. Est-il possible de le revisiter avec un foreach ?

Le foreach répète un bloc de code autant de fois que la longueur d'une liste. Si nous sommes capables de créer facilement une liste dont la longueur est le nombre de répétitions voulu, c'est gagné !

C'est justement ce dont sont capables les langages modernes comme Kotlin, Python ou Ruby. Ils possèdent une forme syntaxique souvent appelée range (étendue en français) qui permet de créer une liste d'entiers compris entre une valeur de départ et une valeur d'arrivée.

En Python par exemple, c'est la fonction range(inf, sup) qui retourne une liste de tous les entiers situés entre inf inclus et sup exclus.

Par exemple si l'on écrit liste = range(0, 5), on obtient la liste : [0, 1, 2, 3, 4].

En Kotlin et en Ruby, c'est la notation inf..sup qui réalise la même chose.

Récrivons donc notre exemple du départ, dans lequel on souhaite afficher 10 fois coucou à l'écran, cette fois avec un foreach

for nombre in range(0,10):
    print("coucou")

Plutôt sympa par rapport à la lourdeur d'un while ou d'un for n'est-ce pas ?

En résumé, dans les langages modernes, les boucles while et for ont tendance à être avantageusement remplacées par le foreach dans la plupart des cas.

Seules les boucles les plus complexes ou la boucle infinie justifient encore l'usage du while :

while (true) {
    ... // code qui ne se terminera jamais
    ... // sauf si un break nous en fait sortir
}

Mais revenons à nos listes. Si le foreach a présenté une évolution importante dans la façon de les parcourir, une autre manière de faire s'est imposée ces dernières années : l'utilisation de l'algorithmique fonctionnelle. Elle n'a que des avantages, et il faut apprendre à l'utiliser. C'est l'objet de la section qui suit.

Parcourir des listes avec la programmation fonctionnelle

Les langages implémentant les principes de la programmation fonctionnelle proposent encore une autre façon de parcourir les listes.

Encore une autre façon ! Mais pourquoi ?

Pour comprendre il faut à nouveau prendre un peu de recul sur le pourquoi on est amené à parcourir des listes. L'exemple utilisé jusqu'à maintenant, et qui consiste à afficher les éléments de la liste, est trompeur. Plus souvent, on parcourt des listes pour calculer quelque chose :

1. Calculer la somme de ses éléments
2. Calculer son plus petit ou son plus grand élément
3. Calculer une nouvelle liste contenant le carré de tous les éléments de la liste.
4. Calculer une nouvelle liste constituée des éléments ayant un certain identifiant
5. Calculer si la liste contient ou pas un certain élément.

Souvent ces calculs s'enchainent. Par exemple on peut être amené à calculer la racine carrée des éléments positifs d'une liste, puis d'en faire la somme. Essayons de résoudre ce dernier calcul en programmation procédurale :

List<Integer> liste = Arrays.asList(4, 16, -4 , 9, -25);
double somme = 0;
for (Integer n : liste) {
   if (n > 0) {
       somme = somme + Math.sqrt(n);
   }
}
System.out.println("Somme: "+somme);

Nous allons voir comment on écrit la même chose en programmation fonctionnelle.

En programmation fonctionnelle, une liste est vue comme un tout, sur lequel on va pouvoir agir de façon globale. Par exemple on va pouvoir transformer une liste en une autre liste, la filtrer (c'est-à-dire ne garder que les éléments qui nous intéressent), ou la réduire à un résultat qui dépend d'un calcul sur ses éléments.

Pour être plus précis les principales actions possibles sur les listes en fonctionnel sont les suivantes :

1. filter (parfois appelé select)

Cette action consiste à produire une nouvelle liste contenant uniquement les éléments sélectionnés. Pour savoir quels sont les éléments sélectionnés, on passe en argument une fonction qui sera appliquée à chaque élément de la liste et qui doit retourner vrai ou faux. Si la fonction retourne vrai, l'élément en question fait partie de la sélection, sinon il est écarté de la nouvelle liste.

Par exemple en javascript, si on veut calculer une liste contenant uniquement les éléments positifs d'une autre liste, on écrira nouvelleliste = liste.filter(n => n > 0)

2. map

Cette action consiste à produire une nouvelle liste de même longueur, où chaque élément est transformé en un autre élément. On passe en argument une fonction qui sera appliquée à chaque élément, et qui doit retourner l'élément transformé.

Par exemple en javascript, si on veut calculer une nouvelle liste qui contient le carré des éléments d'une autre liste, on écrira nouvellelist = liste.map (n => n * n)

3. reduce

Cette action consiste à produire un résultat calculé à partir de la valeur des éléments de la liste. On passe en argument une fonction qui sera appliquée à chaque élément. Cette fonction prend deux paramètres, un accumulateur qui contient le résultat calculé jusqu'à cet élément et l'élément auquel la fonction est appliquée.

Par exemple en javascript, si on veut calculer la somme des éléments d'une liste, on écrira somme = liste.reduce( (accumulateur, elem) => accumulateur + elem)

À chaque fois, on passe en argument à la méthode principale (filter, map ou reduce) une fonction. Passer une fonction en argument, voilà une caractéristique importante de la programmation fonctionnelle !

Arrêtons-nous quelques lignes sur la syntaxe qui permet de passer une fonction en paramètre.

Que signifie x => x * x ?

C'est l'équivalent de la fonction suivante :

function anonyme(x) {
    return x * x
}

Autrement dit, c'est une fonction sans nom (donc anonyme) qui prend quelque chose en paramètre, et qui retourne ce quelque chose multiplié par lui-même.

Que signifie (accumulateur, elem) => accumulateur + elem) ?

C'est l'équivalent de :

function anonyme(acc, x) {
    return acc + x
}

Autrement dit, une fonction sans nom qui prend deux paramètres, et qui en retourne la somme.

Généralisons. Que signifie ?

(a,b,c) => {
    // faire plein de choses avec a, b et c
    // et retourner quelque chose
}

C'est l'équivalent de la fonction suivante :

function anonyme(a,b,c) {
    // faire plein de choses avec a, b et c
    // et probalement retourner quelque chose
}

Ces notations abrégées à base de parenthèses et de flèches sont ce que l'on appelle des lambdas expressions et permettent d'être concis quand on doit définir des fonctions que l'on passe en paramètre. On n'est pas obligé de s'en servir. Voici comment par exemple on peut réécrire le fait de filtrer la liste sur ces éléments positifs :

function aucarre(x) {
    return x * x
}

liste = [ 2, 3, 1 ]
liste.filter(aucarre)

On a ici utilisé une vraie fonction (avec un nom, elle n'est donc pas anonyme), et on passe son nom à liste.filter. Mais c'est plus long, et donc on privilégiera la syntaxe lambdas expressions bien entendu.

Attention tous les langages ne permettent pas cela, mais tous les langages modernes ou les langages ayant su évoluer savent le faire. C'est le cas par exemple de Java, Javascript, Ruby, Kotlin, etc. Le cas de Python est un peu particulier. Il intègre des éléments de programmation fonctionnelle, mais sa syntaxe accuse le poids des âges. Pour ne pas compliquer nous n'utiliserons donc pas d'exemples en Python.

Nous en savons assez pour récrire en fonctionnel notre calcul procédural sur les racines carrées des éléments positifs d'une liste :

 List<Integer> liste = Arrays.asList(4, 16, -4 , 9, -25);
 somme = liste
    .stream()
    .filter( nombre -> nombre > 0)
    .map(nombre -> Math.sqrt(nombre))
    .reduce(0.0, (acc,n) -> acc + n);
 System.out.println("Somme : " + somme);

Pour mieux voir ce qu'on y gagne, affichons les deux versions Javascript dans le même code :

let liste  = [ 4, 16, -4 , 9, -25 ];

// calcul en procédural
somme = 0;
for (number of liste) {
  if (number > 0) somme += Math.sqrt(number);
}
console.log("Somme : " + somme);

// calcul en fonctionnel
somme = liste
  .filter(nombre => nombre > 0)
  .map(nombre => Math.sqrt(nombre))
  .reduce( (acc, n) => acc + n);

console.log("Somme : " + somme);

Laquelle préférez-vous ? La plupart des programmeurs trouvent la forme fonctionnelle plus claire.

La première forme déclare une variable initialisée à zéro. Quand on lit cette ligne, on ne sait pas encore à quoi cette variable va servir. On voit ensuite qu'on parcourt la liste, et que pour chaque élément on teste une condition sur la positivité de l'élément. Si c'est vrai, on ajoute la racine carrée de l'élément à la variable somme. Sinon on ne fait rien. A la fin, on affiche la variable somme.

C'est version de l'algorithme n'est pas très compliqué à comprendre, mais elle nécessite quand même une gymnastique mentale pour déduire qu'à la fin la variable somme contiendra la somme des racines carrées des éléments positifs de la liste.

Lisons maintenant la deuxième forme. Elle démarre par somme = . Donc on nous explique directement ce que vaut somme, c'est bien. On nous dit ensuite qu'on filtre la liste pour ne retenir que ses éléments positifs, puis, qu'on calcule la racine de tous les éléments restants, et qu'enfin on en fait la somme. C'est plus clair et c'est une des raisons pour laquelle la notation fonctionnelle remplace avantageusement les boucles foreach quand il s'agit d'effectuer des calculs sur les listes.

Conclusion

Ouf ! Nous arrivons à la fin de ce long post qui nous a mené des boucles primitives aux parcours fonctionnel des listes. Essayons de résumer la situation :

Si vous utilisez un des nombreux langages sortis ces dernières années, ou un vieux langage ayant décemment évolué (typiquement Java), vous avez toutes les chances de pouvoir remplacer les boucles classiques while ou for, par leur version plus évoluée le foreach. Seuls les cas les plus complexes ou les boucles infinies justifient encore l'usage du while.

Si l'objectif de votre boucle est de parcourir une liste, une collection, ou un tableau, il y a fort à parier que vous devriez la remplacer par une opération fonctionnelle de type filter, map ou reduce, voire éventuellement par un forEach fonctionnel si tout ce qui vous intéresse est d'appliquer un effet de bord à ses éléments (par exemple un affichage). Voici par exemple comment on affiche les éléments d'une liste en fonctionnel dans quelques langages :

List<Integer> liste = Arrays.asList(2, 4, 23, 14, 2);
liste.forEach(nombre -> System.out.println(nombre));

Bon code à tous !