Concept – Invariants et indices

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.

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;
   }
}

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

• L' initialisation de la répétitive (expression cpt ← 1) qui assure une valeur initiale connue pour toutes les variables servant à contrôler la répétitive
• La condition (cpt <= MAX), qui doit devenir fausse éventuellement (du moins pour les algorithmes avec lesquels se pratique l' enseignement de base) et qui doit donc être influencée par l' évolution des opérations à répéter
• Le traitement (Écrire cpt), qui est ici un simple affichage mais devrait constituer la partie importante du travail réalisé par la répétitive, et
• L' incrémentation (cpt ← cpt + 1), qui peut porter d' autres noms mais doit assurer la fin éventuelle de la répétitive – comprenons ici qu' une partie importante des premiers efforts investis dans l' écriture de répétitives par un(e) étudiant(e) dans un cours de programmation implique d' écrire une répétitive qui ne soit pas infinie et qui fasse véritablement le travail attendu

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.

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 à $1$, 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 $1$ à $N$ 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 $0$ à $N-1$ 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.

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 :

• La version faisant varier cpt de 1 à MAX inclusivement donne à cpt le rôle de représenter la prochaine valeur à afficher. En tout temps dans ce programme (sauf au moment précis où le traitement vient de se terminer), la valeur de cpt est celle de la prochaine valeur à afficher, alors que
• La version faisant varier cpt de 0 à MAX-1 inclusivement donne à cpt le rôle de représenter le nombre de valeurs ayant été affichées. En tout temps dans ce programme (sauf au moment précis où le traitement vient de se terminer), la valeur de cpt correspond au nombre de valeurs déjà affichées

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

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

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

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 :

• Un itérateur est un objet capable d'itérer à travers une séquence et capable de représenter à la fois la position logique d'un élément et cet élément en tant que tel. L'itérateur est une abstraction plus puissante et plus fondamentale que l'indice dans un tableau
• Une séquence a un début et une fin, qui sont tous deux des itérateurs
• Le début d'une séquence correspond à la position logique du premier élément de cette séquence, et
• La fin d'une séquence correspond à la position suivant logiquement celle du dernier élément de la séquence. Il doit toujours être possible de comparer un itérateur avec cette position, bien que vérifier ce qu' elle contient soit en général illégal

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 :

#include <iostream>
using namespace std;
int main() {
   const int MAX = 10;
   int tab[MAX] { };
   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] { };
   int *debut = tab;
   int *fin = tab + MAX;
   int *it;
   // lire des éléments dans le tableau
   it = debut;
   while (it != fin) {
      cin >> *it;
      ++it;
   }
   // afficher les éléments du tableau
   it = debut;
   while (it != fin) {
      cout << *it << ' ';
      ++it;
   }
}

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.

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

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.

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 $[1..N]$ de l'algorithme, l'invariant est que cpt représente la prochaine valeur à afficher, alors que dans la forme $[0..N-1)$ 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 :

• Cela clarifie l'algorithme à écrire derrière l' algorithme. L' individu devant écrire un algorithme et se devant d' expliciter les invariants voit en partie son travail guidé par une tâche en soi relativement simple: s' assurer que chaque étape impliquant une variable contrôlant le flux de la répétitive conserve les propriétés de l' invariant
• Cela facilite le choix d'une nomenclature pour les variables. L'individu devant écrire un algorithme peut plus facilement choisir des noms de variables et de constantes clairs en fonction du rôle de chacune du fait que le recours systématique à des invariants explicites indique souvent de lui-même un nom approprié pour elles, qu'il s'agisse de nbAffichees ou de prochaineValeur
• Cela impose une structure à l'algorithme. L'individu devant écrire un algorithme peut valider le choix de chaque étape en vérifiant que celui-ci n'invalide pas les invariants qu'il s'est fixé, et
• Cela clarifie l'intention derrière l'algorithme. Quiconque devra assurer l'entretien de l'algorithme sera en mesure de vérifier seul le respect d'invariants clairement explicités. Effets secondaires non négligeables, la présence d'invariants explicites dans un algorithme facilite le débogage et accélère la détection d'algorithmes fautifs

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

Lectures complémentaires

Quelques liens pour enrichir le propos.

• En 2022, Fernando Hurtado Cardenas préconise le recours systématique à des intervalles à demi-ouverts : https://fhur.me/posts/always-use-closed-open-intervals