Discipline de programmation, validation et test

La spécification d'une fonction dit, sans dire comment :

• sa signature : le type de chaque paramètre, le type du retour ;
• sa précondition : ce que l'appelant garantit sur les entrées ;
• sa postcondition : ce que la fonction garantit sur la sortie.

Le programme est catégorique : « les signatures des fonctions sont toujours précisées ».

Le programme demande l'« annotation d'un bloc d'instructions par une précondition, une postcondition, une propriété invariante », et précise : « ces annotations se font à l'aide de commentaires ».

/* Trie les n premiers termes de t par ordre croissant, en place.
   Précondition : n >= 0. */
void tri_selection(int t[], int n) {
    for (int i = 0; i < n - 1; i = i + 1) {
        /* INVARIANT : t[0..i-1] est trié, et tous ses termes sont
           inférieurs ou égaux à ceux de t[i..n-1]. */
        int mini = i;
        for (int j = i + 1; j < n; j = j + 1) {
            if (t[j] < t[mini]) { mini = j; }
        }
        int tmp = t[i]; t[i] = t[mini]; t[mini] = tmp;
    }
}

Une assertion est une condition dont on affirme qu'elle est vraie à cet endroit. Si elle est fausse, le programme s'arrête immédiatement avec un message précis.

#include <assert.h>
assert(n >= 1 && t != NULL);

assert (Array.length t >= 1)

Le programme « encourage » leur usage « par exemple pour valider des entrées ou pour le contrôle de débordements ».

Le programme demande de sensibiliser « à la différence de garanties apportées selon les langages, avec l'exemple d'un typage faible en C et fort en OCaml ».

int n = 3.9;          /* accepté : n vaut 3, la partie décimale est PERDUE */
char c = 300;         /* accepté : c vaut 44 */
char d = grand;       /* accepté, et SILENCIEUX : voir ci-dessous */
int* p = (int*) &c;   /* accepté : on lit 4 octets là où il y en a 1 */

let n : int = 3.9     (* ERREUR de compilation, et le message dit pourquoi *)

C convertit ; OCaml refuse.

Nuance mesurée. Sur une constante, C ne convertit pas tout à fait sans prévenir : gcc -Wall -Wextra signale les deux premières lignes — « implicit conversion from int to char changes value from 300 to 44 » et « from 3.9 to 3 ». Le compilateur voit la valeur, donc il voit la perte.

Le silence revient dès que la valeur vient d'une variable : char d = grand; ne produit aucun avertissement, car le compilateur ignore ce que grand contiendra. Le filet du compilateur s'arrête là où le calcul commence — et c'est précisément là que les débordements surviennent. D'où le partage du travail : en C, la vigilance est à la charge du programmeur et se matérialise en assertions ; en OCaml, une grande part est déléguée au compilateur — mais rien ne protège de l'arithmétique, ni d'une logique fausse.

exception Fichier_vide

let premiere_ligne nom =
  let f = open_in nom in
  try
    let l = input_line f in
    close_in f; l
  with End_of_file -> close_in f; raise Fichier_vide

Un jeu de tests est une liste de couples (entrée, sortie attendue). Le programme précise le niveau exigé : « il n'est pas attendu de connaissances sur la génération automatique de jeux de tests ; un étudiant est capable d'écrire un jeu de tests à la main, donnant à la fois des entrées et les sorties correspondantes attendues ».

let tests_maximum () =
  assert (maximum [| 5 |] = 5);                (* cas minimal *)
  assert (maximum [| 1; 2; 3 |] = 3);          (* maximum en dernier *)
  assert (maximum [| 3; 2; 1 |] = 3);          (* maximum en premier *)
  assert (maximum [| 2; 3; 2 |] = 3);          (* maximum au milieu *)
  assert (maximum [| 7; 7 |] = 7);             (* doublons *)
  assert (maximum [| -5; -2 |] = -2);          (* que des négatifs *)
  print_string "maximum : tous les tests passent\n"

Le graphe de flot de contrôle d'un programme a pour sommets ses blocs d'instructions et pour arcs les passages possibles de l'un à l'autre. Un chemin de l'entrée à la sortie est faisable s'il existe une entrée qui le fait emprunter.

Le programme demande de savoir écrire « un jeu de tests satisfaisant un critère de couverture des instructions (sommets) ou des branches (arcs) sur les chemins faisables ».

• Couverture des sommets : chaque bloc est exécuté au moins une fois. Le plus faible.
• Couverture des arcs : chaque transition est empruntée au moins une fois. Plus fort : il oblige à passer par le « sinon » d'un if sans else, que la couverture des sommets ignore.
• Couverture des chemins : chaque chemin complet est parcouru. Le plus fort, et souvent impraticable : $k$ conditionnelles en séquence donnent $2^k$ chemins, et une boucle en donne une infinité — d'où la précision du programme, « avec ou sans cycle ».

Quand une condition « comporte des conjonctions ou disjonctions », le programme demande « de ne pas se contenter de la traiter comme étant globalement vraie ou fausse mais de formuler des tests qui réalisent toutes les possibilités de la satisfaire ».

if (a > 0 || b > 0) { ... }

Un jeu de tests qui ne contiendrait que les lignes 1 et 4 satisfait la couverture des arcs — les deux branches sont prises — et laisse pourtant passer un && écrit à la place du || : sur ces deux lignes, les deux opérateurs donnent le même résultat. Les lignes 2 et 3 les séparent.