Langages et programmation

n = 7                         # affectation
total = 0                     # affectation ; la séquence est l'enchaînement des lignes

for i in range(1, n + 1):     # boucle bornée : on sait qu'il y aura n tours
    total = total + i

if total > 20:                # conditionnelle
    message = "grand"
else:
    message = "petit"

reste = n                     # boucle non bornée : on ne sait pas combien de tours
etapes = 0
while reste > 1:
    reste = reste // 2
    etapes = etapes + 1

print(total, message, etapes) # appel de fonction

3.2 Diversité et unité des langages

3.2.1 Le même programme, quatre fois

Voici la recherche du plus grand élément d'un tableau, écrite dans quatre langages. Vous ne connaissez que le premier ; l'exercice consiste justement à lire les autres sans les connaître.

# Python
def maximum(t):
    m = t[0]
    for x in t:
        if x > m:
            m = x
    return m

/* C */
int maximum(int t[], int n) {
    int m = t[0];
    for (int i = 0; i < n; i++) {
        if (t[i] > m) {
            m = t[i];
        }
    }
    return m;
}

(* OCaml *)
let maximum t =
  let m = ref t.(0) in
  for i = 0 to Array.length t - 1 do
    if t.(i) > !m then m := t.(i)
  done;
  !m

// JavaScript
function maximum(t) {
    let m = t[0];
    for (let i = 0; i < t.length; i++) {
        if (t[i] > m) {
            m = t[i];
        }
    }
    return m;
}

3.2.2 Des styles différents

Le programme demande de savoir que les langages diffèrent par leur style :

• impératif — on décrit une suite d'instructions qui modifient l'état de la machine. C'est le style des quatre programmes ci-dessus, et celui de ce livre.
• fonctionnel — on décrit le résultat comme une composition de fonctions, en évitant de modifier des variables. OCaml, Haskell ; Python le permet en partie.
• objet — on regroupe les données et les opérations qui les manipulent. Java, C++, et Python là aussi.
• logique — on énonce des faits et des règles, et le langage cherche lui-même les conséquences. Prolog.
• événementiel — le programme réagit à des événements plutôt que de dérouler un fil. C'est le style d'une page Web qui répond aux clics, que nous verrons au chapitre 10.

La distinction se voit mieux côte à côte :

Figure : Ce qui sépare un langage de programmation d'un langage formel : la présence, ou l'absence, du corpus de constructions élémentaires.

3.3 Spécifier avant d'écrire

3.3.1 Le prototype

Écrire le prototype d'abord, c'est se forcer à savoir ce qu'on veut avant de savoir comment l'obtenir. En Python, on le complète d'une docstring — la chaîne placée juste sous la ligne def — qui devient la documentation de la fonction.

3.3.2 Préconditions et postconditions

Figure : La spécification est un contrat à deux parties. C'est ce qui permet d'utiliser une

fonction sans lire son code — et de la réécrire sans prévenir ses utilisateurs.</div>

C'est un contrat à deux parties : l'appelant s'engage sur la précondition, la fonction s'engage sur la postcondition. Si l'appelant ne tient pas sa part, la fonction ne promet rien.

def moyenne(t):
    """Moyenne arithmétique des éléments de t.

    Précondition  : t est un tableau NON VIDE de nombres.
    Postcondition : le résultat est compris entre le plus petit et le plus
                    grand élément de t.
    """
    assert len(t) > 0, "moyenne d'un tableau vide"
    m = sum(t) / len(t)
    return m

L'instruction assert vérifie une condition et interrompt le programme avec un message si elle est fausse. Elle transforme un commentaire — que personne ne lit — en un garde-fou qui se déclenche.

AttentionUne postcondition doit tenir compte du chapitre 2

On serait tenté d'écrire, avant le return :

assert min(t) <= m <= max(t)      # FAUX sur des flottants

C'est vrai en mathématiques, et faux sur machine. Sur t = [0.1, 0.1, 0.1], la somme calculée vaut 0.30000000000000004 et la moyenne 0.10000000000000002, qui est strictement supérieure à max(t). L'assertion échoue sur une fonction pourtant correcte.

Il faut donc écrire la postcondition avec une tolérance, comme au chapitre 2 :

assert min(t) - 1e-9 <= m <= max(t) + 1e-9

Retenez la leçon générale : une propriété mathématique vraie ne se transpose pas mécaniquement en assertion dès que des flottants sont en jeu.

3.4 Mettre au point : les jeux de tests

Capacité attendue

« Utiliser des jeux de tests. »

3.4.1 Ce qu'un jeu de tests doit contenir

Méthode : Construire un jeu de tests

Un bon jeu de tests comporte trois familles de cas :

• les cas ordinaires, ceux qu'on imagine spontanément ;
• les cas limites : tableau à un seul élément, valeur nulle, éléments tous égaux, maximum en première position, maximum en dernière position, valeurs négatives ;
• les cas interdits, qui doivent violer la précondition et provoquer l'erreur attendue — un test qui vérifie que le programme refuse bien ce qu'il doit refuser.

3.4.2 Un jeu de tests qui passe ne prouve rien

Voici une fonction maximum subtilement fausse :

def maximum_faux(t):
    m = 0                  # <-- l'erreur est ici
    for x in t:
        if x > m:
            m = x
    return m

Soumettons-la à un jeu de tests d'apparence sérieuse :

Appel	Attendu	Obtenu
`maximum_faux([3, 1, 4])`	4	4   ✓
`maximum_faux([5])`	5	5   ✓
`maximum_faux([2, 7, 1])`	7	7   ✓
`maximum_faux([0, 0, 0])`	0	0   ✓
`maximum_faux([-3, -1, -7])`	$-1$	0   $\times$

Quatre tests sur cinq passent. Le cinquième révèle que la fonction ne cherche pas le maximum du tableau, mais le maximum entre $0$ et les éléments du tableau. Un jeu de tests qui n'aurait contenu que des valeurs positives aurait déclaré cette fonction correcte.

Figure : Pourquoi « le succès d'un jeu de tests ne garantit pas la correction ». Seule une preuve

— les invariants du chapitre 7 — parle de tout le disque à la fois.</div>

Important

Le programme le formule sans détour : « le succès d'un jeu de tests ne garantit pas la correction d'un programme ». Tester montre la présence d'erreurs, jamais leur absence. C'est pourquoi le chapitre 7 introduira les invariants : eux seuls permettent de prouver qu'un algorithme est correct, sur toutes les entrées à la fois.

def tester(fonction, cas):
    """Exécute un jeu de tests et affiche un rapport.

    cas est un tableau de couples (arguments, resultat_attendu).
    Renvoie le nombre d'échecs — donc 0 si tout passe.
    """
    echecs = 0
    for arguments, attendu in cas:
        obtenu = fonction(*arguments)
        if obtenu == attendu:
            print("  ok   ", arguments, "->", obtenu)
        else:
            print("  ECHEC", arguments, "-> attendu", attendu, ", obtenu", obtenu)
            echecs = echecs + 1
    print(echecs, "echec(s) sur", len(cas), "cas")
    return echecs

iRemarque

Cette fonction est volontairement minuscule. Les langages disposent d'outils de test bien plus riches — en Python, le module unittest ou la bibliothèque pytest. Leur usage n'est pas au programme ; le raisonnement, si.

3.5 Utiliser une bibliothèque

Capacité attendue

« Utiliser la documentation d'une bibliothèque. »

Définition 3.4Bibliothèque

Une bibliothèque est un ensemble de fonctions déjà écrites, testées et documentées, qu'un programme peut utiliser sans les réécrire.

import math
import random

math.sqrt(2)          # racine carrée
math.isclose(0.1 + 0.2, 0.3)   # la comparaison prudente du chapitre 2
random.randint(1, 6)  # entier aléatoire entre 1 et 6, bornes comprises

Méthode : Lire une documentation

Devant une fonction inconnue, quatre questions, toujours les mêmes :

• que renvoie-t-elle exactement ?
• quels arguments attend-elle, dans quel ordre, et lesquels sont facultatifs ?
• quelles sont ses préconditions — que se passe-t-il hors du domaine prévu ?
• les bornes sont-elles incluses ? random.randint(1, 6) peut renvoyer $6$, range(1, 6) s'arrête à $5$. Deux fonctions voisines, deux conventions opposées : seule la documentation le dit.

Sous Python, help(random.randint) affiche la documentation sans quitter l'interpréteur.

Hors programme : Ce que le programme n'exige pas

« Aucune connaissance exhaustive d'une bibliothèque particulière n'est exigible. » Il n'est pas demandé de mémoriser le contenu de math ou de random : il est demandé de savoir trouver et lire ce dont on a besoin.

Piste de projet : Une bibliothèque, écrite comme telle

Reprendre les fonctions des chapitres 1 et 2 — conversions de base, complément à deux, additionneur, conversion d'encodage — et en faire un vrai module : un fichier representation.py où chaque fonction possède son prototype, sa docstring, ses préconditions vérifiées par assert, et un fichier de tests séparé qui les exerce toutes.

L'exigence de qualité est le sujet même du projet : le module doit être utilisable par un autre groupe sans qu'il ait à lire le code, en s'appuyant seulement sur les docstrings. C'est le meilleur critère d'évaluation qui soit — et il se vérifie en échangeant les modules entre groupes.

Continuer sur Adloun : animation, QCM, fiches, exercices