Concept – Invariants et indices

L'idée d'écrire cet article m'est venue suit à la lecture du livre Accelerated C++, Practical Programming by Example par Andrew Koenig (qui signe souvent ARK, et qui est à la fois un proche de Bjarne Stroustrup et l'une des personnes qui, à ma connaissance, entretiennent la relation intellectuelle la plus intime avec C++) et Barbara E. Moo.

L'article se veut à la fois un article de base, s'adressant aux programmeuses et aux programmeurs débutant leur carrière et leur réflexion quant aux concepts sous-jacents à leur pratique, et un article plus fondamental quant à certains choix que nous faisons lorsque nous décrivons des tâches répétitives.

Parenthèse trop brève

Je suis tout à fait conscient que plusieurs apprécient réaliser des tâches répétitives. S'adonner à une tâche du genre peut être relaxant: brasser la soupe en bavardant avec des amis, tondre le gazon, griffoner des carrelages fins (Cross-Hatching) en prenant un verre... Comme tout le monde, j'éprouve du plaisir à relaxer tout en faisant progresser quelque dossier un tant soit peu mécanique. Cela dit, j'aime avoir le choix de faire ces choses. La liberté d'agir par plaisir fait toute la différence.

Je suis aussi conscient que plusieurs emplois humains seraient menacés par une automatisation massive et sauvage. Ce n'est pas une démarche que je préconise ou que j'appuie, mais cela fait partie du risque du tout progrès, de toute déstabilisation de l'existant. En même temps, voudrions-nous vraiment, collectivement, le monde demeure tel qu'il est? Il suffit de penser (avec un esprit critique, tout de même) aux commodités à notre disposition aujourd'hui en comparaison avec celles à notre disposition il y a un siècle ou un siècle et demi à peine pour y répondre.

Il y a un piège caché dans le progrès, d'ailleurs, piège envers lequel il nous faut toutes et tous être conscientisé(e)s: même les tâches intellectuelles sont à risque d'être automatisées. Informatiser la démarche intellectuelle et scientifique est un possible au moment d'écrire ces lignes, et tout(e) informaticien(ne) travaille en partie à la disparition de sa propre profession... telle qu'elle existe présentement, du moins. Idéalement, après tout, les programmes pourraient bien s'écrire et se déverminer d'eux-mêmes.

Derrière se constat s'en trouve un autre: ce n'est pas tant que disparition d'emplois que de transformations d'emploi qu'il faut parler. Lorsque les outils, les idées, les milieux, les défis... changent, le monde demeure et il en va de même pour nous, les humains. Notre plus grand défi est de nous adapter nous-mêmes au monde que nous contribuons à transformer (et, dans le cas de l'environnement en particulier, à retransformer le monde en un lieu capable de permettre notre propre existence, mais c'est là un dossier à part entière).

Dès les premiers pas d'une programmeuse ou d'un programmeur, l'idée selon laquelle il sera important dans sa carrière de permettre l'automatisation des tâches répétitives devient importante. L'espoir que les tâches plus mécaniques seront entreprises et accomplies par des automates alors que des humains pourront se consacrer à des tâches qui les rendront plus heureux fait partie intégrante de la démarche intellecutelle de l'informaticien(ne).

Habituellement, la formation servant à entraîner un(e) informaticien(ne) à penser les solutions aux problèmes impliquant des répétitives se fait à partir de problèmes très simples et comportant une partie visuelle. Par exemple, écrire un programme (en pseudocode et dans un langage donné – ici, C++) qui affichera les entiers de 1 à 10 inclusivement à l'écran.

Pseudocode Code C++
MAX ← 10
cpt ← 1
Tant que cpt <= MAX
   Écrire cpt
   cpt ← cpt + 1
#include <iostream>
using namespace std;
int main()
{
   const int MAX = 10;
   int cpt;
   cpt = 1;
   while (cpt <= MAX)
   {
      cout << cpt << endl;
      cpt = cpt + 1;
   }
}

Les éléments algorithmiques de base de cette forme répétitive sont tous présents :

Cette forme (initialisation, condition, traitement, incrémentation) est ce que nous appelons la forme classique de la répétitive. Développer chez l'étudiant(e) le réflexe d'appliquer cette forme de la répétitive tend à accélérer son apprentissage tout en réduisant le nombre de bugs qu'elle ou il aura à régler. Une discipline de pensée, donc, pour faciliter le démarrage de la réflexion. Sans structure de pensée simple et éprouvée pour débuter sa réflexion, l'étudiant(e) tend à entreprendre chaque répétitive comme un problème nouveau et à mener l'écriture de programmes comme un combat.

Notez que ce que je propose comme exemple ici correspond à notre démarche pédagogique au Collège Lionel-Groulx, qui se veut une approche enseignant d'abord la programmation au sens de démarche intellectuelle pratiquement indépendante du langage de programmation utilisé pour exprimer concrètement les idées et qui enseigne l'écriture dans un langage donné comme une transposition de l'algorithme préalablement réfléchi et pensé sous forme de pseudocode (cela explique entre autres l'utilisation, au moins le temps de développer des habitudes saines, des formes de code les plus portables possibles, incluant le recours à l'expression cpt = cpt + 1; plutôt que la forme plus compacte et plus efficace ++cpt;). Ce n'est pas la seule démarche possible, mais c'est la nôtre.

Ce choix que nous faisons n'est pas innocent. Plusieurs des problèmes de base sur les répétitives que nous proposons aux étudiant(e)s débutant leur formation avec nous reposent sur l'affichage de formes géométriques régulières, ce qui a le bon côté de donner des résultats visibles dans les cas où le tout fonctionne comme dans le cas où tout va mal.

Plusieurs des algorithmes les plus élégants pour ces problèmes s'expriment bien dans une notation comme celle utilisée dans le langage Pascal et sont un petit peu plus laborieux à exprimer avec une notation comme celle utilisée en langage C. Ce n'est pas tant un jugement favorable ou défavorable envers l'une ou l'autre de ces approches mais bien une conséquence de nos choix de problèmes.

Si les notations et ne vous disent rien, ne vous inquiétez pas car nous les aborderons plus bas, les deux étant centrales à notre propos.

Une philosophie même dans les gestes les plus humbles

Même un aussi petit programme traduit un biais intellectuel. Moi et mes collègues avons pour la plupart commencé notre réflexion intellectuelle (du moins de manière rigoureuse) face aux problèmes sur des séquences à l'aide de langages comme Pascal et Modula II. Nous avons tendance à penser les séquences comme débutant à , tout comme le font les indices des tableaux dans ces langages (où un tableau de N éléments rend ces éléments accessibles à l'aide des indices allant de à inclusivement).

L'approche philosophique ici est que les humains comptenent habituellement à partir de 1 et les tableaux sont conscients de leur propre taille. Un vieux gag dans le monde scientifique est que les informaticiens peuvent être reconnus au fait qu'ils comptent à partir de zéro, contrairement à tous les autres êtres humains, ce qui trahit le fait que l'approche du langage C (ci-dessous) est devenue si populaire au fil des ans.

En effet, une autre philosophie, sous-jacente au langage C et à ses dérivés syntaxiques (C++, Java, C# et plusieurs autres), est d'utiliser des indices commençant à zéro. Ainsi, pour ces langages, un tableau de N éléments rend ses éléments accesibles à l'aide des indices allant de à inclusivement.

Le langage C offre un modèle de programmation révélant plus des détails propres à l'organisation des données dans un ordinateur. En C, un tableau correspond à un pointeur (une adresse typée) sur son premier élément, et l'expression tab[i] pour un tableau tab et un entier i donnés correspond tout simplement à l'expression arithmétique sur des adresses *(tab+i) ce qui signifie l'élément se trouvant à l'adresse tab à laquelle on ajoute i fois la taille d'un de ses éléments. On comprendra qu'écrire tab[0] signifie parler de l'élément à l'adresse tab+0, donc à l'adresse tab, ce qui correspond au premier élément de tab.

Revenant au programme plus haut, une notation plus proche de celle de C et de ses dérivés syntaxiques nous aurait donné ceci.

Pseudocode Code C++
MAX ← 10
cpt ← 0
Tant que cpt < MAX Faire
   écrire cpt + 1
   cpt ← cpt + 1
#include <iostream>
using namespace std;
int main()
{
   const int MAX = 10;
   int cpt;
   cpt = 0;
   while (cpt < MAX)
   {
      cout << cpt + 1 << endl;
      cpt = cpt + 1;
   }
}

Ce programme est aussi valide que le précédent et donne les mêmes résultats, mais dit en même temps autre chose de par son écriture et surtout de par le rôle de la variable cpt. Si nous comparons les deux versions, nous voyons clairement que :

On pourrait formuler autrement le sens à donné à cpt dans les deux programmes mais l'essentiel à retenir est que le sens donné à la variable influence l'algorithme même dans un cas aussi simple.

Intervalles fermés et la intervalles à demi ouverts

La notation faisant varier les indices de à inclusivement exprime un intervalle fermé, et peut s'écrire de manière compacte sous la forme où les crochets indiquent l'inclusion des bornes. Ceci correspond à une répétitive de la forme proposée à droite. Remarquez que la constante est prise en considération dans la condition, ce qui explique sa présence dans la notation compacte de l'intervalle.

for(int i=1; i <= N ; ++i)
{
   //...
}

De son côté, la notation faisant varier les indices de à inclusivement exprime un intervalle à demi ouvert, et peut s'écrire de manière compacte sous la forme où la parenthèse fermante exprime l'exclusion de la borne supérieure. Ceci correspond à une répétitive de la forme proposée à droite. Remarquez que la constante est ici aussi prise en considération dans la condition, ce qui explique sa présence dans la notation compacte de l'intervalle.

for(int i=0; i < N ; ++i)
{
   // ...
}

Dans les deux cas, d'autres notations équivalentes pour les intervalles auraient été possibles. J'utiliserai celles-ci pour me rapprocher de l'usage habituel dans les cercles discutant de ces questions.

Intervalles à demi ouverts et itérateurs

En C++, l'idée d'intervalle à demi ouvert est poussé beaucoup plus loin qu'au simple niveau des indices entiers dans un tableau et se décline en approche philosophique à l'idée même d'itération. Tous les répétitives standardisées y ont la forme suivante :

Clairement, un itérateur est un objet décrivant une abstraction de la capacité de parcourir une séquence. Sur un tableau, la position d'un élément s'exprime à l'aide d'un pointeur et il est possible de déréférencer un pointeur à l'aide de l'opérateur *. Un pointeur est donc un itérateur sur un tableau.

La forme classique d'itération à travers un tableau d'entiers devient, suivant ce formalisme :

Code C++, itération avec indice Code C++, itération avec itérateur
#include <iostream>
using namespace std;
int main()
{
   const int MAX = 10;
   int tab[MAX] = { 0 };
   int cpt;
   // lire des éléments dans le tableau
   cpt = 0;
   while (cpt < MAX)
   {
      cin >> tab[cpt];
      ++cpt;
   }
   // afficher les éléments du tableau
   cpt = 0;
   while (cpt < MAX)
   {
      cout << tab[cpt] << ' ';
      ++cpt;
   }
}
#include <iostream>
using namespace std;
int main()
{
   const int MAX = 10;
   int tab[MAX] = { 0 };
   int *debut = tab;
   int *fin = tab + MAX;
   int *itt;
   // lire des éléments dans le tableau
   itt = debut;
   while (itt != fin)
   {
      cin >> *itt;
      ++itt;
   }
   // afficher les éléments du tableau
   itt = debut;
   while (itt != fin)
   {
      cout << *itt << ' ';
      ++itt;
   }
}

Remarquez que la version avec indices dépend de deux données (le tableau et l'indice courant dans le tableau) pour contrôler la répétitive et accéder aux éléments du tableau alors que la version avec itérateur est plus expressive, l'itérateur représentant à lui seul une position et ce qu'elle contient.

Évidemment, la forme classique d'une répétitive Tant que en C++ s'exprime habituellement à l'aide de sa forme compacte qu'est la répétitive for.

Code C++
#include <iostream>
using namespace std;
int main()
{
   const int MAX = 10;
   int tab[MAX] = { 0 };
   int *debut = tab + 0;
   int *fin = tab + MAX;
   // lire des éléments dans le tableau
   for (int *itt = debut; itt != fin; ++itt)
   {
      cin >> *itt;
   }
   // afficher les éléments du tableau
   for (int *itt = debut; itt != fin; ++itt)
   {
      cout << *itt << ' ';
   }
}

Je vous invite à suivre les liens proposés ici pour en savoir plus sur le sujet des itérateurs et de la programmation générique. Ce sont des sujets passionnants.

La beauté de cette formulation est qu'elle permet à la bibliothèque standard d'écrire des algorithmes génériques applicables à tout type de conteneur dans la mesure où celui-ci sait exprimer l'idée de séquence telle qu'elle s'applique à lui.

En effet, une séquence sur une liste chaînée, sur un tableau ou sur un arbre binaire demeure une séquence, et ce qui compte est de savoir la traverser. Le problème de traverser une liste chaînée dépend de son implémentation interne, après tout, et nos algorithmes ne devraient pas dépendre de tels détails.

Idée d'invariant

Revenant à nos moutons, donc, deux philosophies s'affrontent quant à la représentation conceptuelle d'intervalles et le choix de l'un ou de l'autre dépend beaucoup de la manière d'exprimer les idées. Dans les dérivés syntaxiques de C, l'intervalle à demi ouvert est presque toujours le meilleur choix du fait qu'il se colle aux standards de la bibliothèque et permet d'appliquer aux problèmes à résoudre toute la puissance des algorithmes et des conteneurs standards. C'est là un gain de productivité considérable.

De manière plus large et moins liée au langage C++, on retrouve derrière l'idée d'une répétitive celle d'invariant.

Un invariant pour une répétitive est une affirmation que la programmeuse ou le programmeur fait et dont elle ou il s'engage à assurer la véracité tout au long de l'exécution de la répétitive.

L'idée d'invariant est un formalisme pour cette brève discussion que nous avions entreprise plus haut quant à la nature du compteur dans la répétitive et quant à l'influence de cette décision quant à la nature du compteur sur l'ensemble de l'algorithme.

Donner un rôle clair à une variable est un cas type d'invariant. Dans la forme de l'algorithme, l'invariant est que cpt représente la prochaine valeur à afficher, alors que dans la forme de l'algorithme, l'invariant est que cpt représente le nombre de valeur déjà affichées.

Pour une programmeuse ou un programmeur, expliciter des invariants comporte plusieurs avantages :

Déterminer et expliciter les invariants d'un algorithme, à plus forte partie ceux d'une répétitive, est une saine pratique de programmation.

Une discussion plus approfondie des invariants est proposée dans Pratique-programmation.html#precondition_postcondition_invariant.


Valid XHTML 1.0 Transitional

CSS Valide !