Programmation, tests et calculabilité

Spécifier, tester, documenter

Une fonction a un contrat : ce qu'elle attend (précondition), ce qu'elle renvoie (postcondition). On l'écrit dans une docstring, juste sous la ligne def. Elle sert à celui qui utilise la fonction sans lire son code.

Une précondition se vérifie avec assert : si la condition est fausse, le programme s'arrête avec une erreur claire, au lieu de produire un résultat faux en silence.

Un jeu de tests est une série de assert qui comparent le résultat obtenu au résultat attendu. On teste :

• un cas général ;

• les cas limites : liste à un seul élément, valeur nulle, valeurs négatives, liste vide ;

• des cas où l'on connaît la réponse à l'avance.

Trouver un bogue

Causes fréquentes : mauvaises bornes d'un range, variable mal initialisée, division par zéro, condition non exhaustive, comparaison de flottants avec ==.

Pour les flottants, 0.1 + 0.2 == 0.3 est faux à cause des arrondis : on compare avec une tolérance, par exemple abs(a - b) < 1e-9.

def maximum(liste):

    """Renvoie le plus grand élément de liste (non vide)."""

    m = liste[0]

    for x in liste:

        if x > m:

            m = x

    return m

def moyenne(liste):

    s = 0

    for i in range(1, len(liste)):

        s = s + liste[i]

    return s / len(liste)

Programmation objet et modularité

Une classe décrit un type d'objets : ses attributs (les données) et ses méthodes (les fonctions qui agissent sur l'objet). Un objet est une instance de la classe. self désigne l'objet courant et __init__ est le constructeur.

class Compte:

    def __init__(self, titulaire, solde):

        self.titulaire = titulaire

        self.solde = solde

    def deposer(self, montant):

        self.solde = self.solde + montant

c = Compte("Lina", 80)

c.deposer(20)

print(c.solde)   # 100

Ici : classe Compte, attributs titulaire et solde, méthodes __init__ et deposer. On accède à un attribut par objet.attribut et on appelle une méthode par objet.methode(...).

Interface et implémentation

L'interface d'une structure est la liste de ses opérations (leurs noms, ce qu'elles font). L'implémentation est la façon dont elles sont programmées. Une pile a pour interface empiler, depiler, est_vide ; on peut l'implémenter avec une liste Python ou avec une liste chaînée : le code utilisateur ne change pas.

Modules et API

Un module est un fichier Python réutilisable. On l'importe : from math import sqrt. Son interface (API) est l'ensemble des fonctions documentées qu'il propose : on s'en sert sans connaître leur code, en lisant leur documentation.

Avantages de la modularité : on découpe un gros programme en morceaux, on réutilise le code, on teste chaque module séparément, et on travaille à plusieurs.

class Compte:

    def __init__(self, titulaire, solde):

        self.titulaire = titulaire

        self.solde = solde

    def deposer(self, montant):

        self.solde = self.solde + montant

Récursivité et paradigmes

Une fonction est récursive si elle s'appelle elle-même. Il faut toujours :

• un cas de base qui s'arrête sans appel récursif ;

• un appel récursif sur un problème plus petit, qui se rapproche du cas de base.

La version itérative (paradigme impératif) utilise une boucle et une variable modifiée. La version récursive (style plus fonctionnel) exprime directement la définition. Le paradigme objet organise le code en classes.

Terminaison et correction

• Terminaison : on exhibe une quantité entière positive qui diminue strictement à chaque appel (ici $n$, puis $n // 10$).

• Correction : on la prouve par récurrence, la propriété pour les petites valeurs servant à la prouver pour $n$ (récurrence forte).

def puissance(x, n):

    if n == 0:

        return 1

    if n % 2 == 0:

        y = puissance(x, n // 2)

        return y * y

    return x * puissance(x, n - 1)

Calculabilité : le problème de l'arrêt

Un programme est écrit dans un fichier texte : c'est donc aussi une donnée. Un compilateur, un antivirus ou un éditeur de code prennent des programmes en entrée. On peut passer un programme en argument d'une autre fonction, voire à lui-même.

La calculabilité étudie ce qu'un algorithme peut ou non résoudre, indépendamment du langage de programmation. Un problème est décidable s'il existe un algorithme qui répond toujours (oui ou non) en temps fini.

Problème de l'arrêt : existe-t-il une fonction arret(prog, donnee) qui renvoie True si prog(donnee) s'arrête et False s'il boucle indéfiniment ?

Conséquence : aucun outil automatique ne peut vérifier, pour tout programme, qu'il se termine (ni, plus généralement, qu'il est correct). Les outils de vérification fonctionnent donc sur des familles restreintes de programmes, et les tests restent indispensables.

Vers le début : les tests ne font que révéler la présence de bogues, et aucun logiciel ne peut tout vérifier à notre place.

L'essentiel

• Une fonction se spécifie par une docstring et des préconditions (assert), et se teste par un jeu de tests incluant les cas limites. Un test réussi ne prouve pas la correction.

• Une classe regroupe attributs et méthodes ; l'interface (opérations) est distincte de l'implémentation.

• Un module s'utilise par son API documentée ; la modularité facilite réutilisation, tests et travail en équipe.

• Une fonction récursive a un cas de base et un appel sur un problème plus petit ; on justifie la terminaison par une quantité strictement décroissante.

• Un programme est une donnée ; le problème de l'arrêt est indécidable.