Programmation, tests et calculabilité

Objets, classes et modularité

Un programme de grande taille se découpe en petites briques que l'on peut comprendre, tester et réutiliser séparément.

class Compte:

    def __init__(self, titulaire, solde):

        self.titulaire = titulaire

        self.solde = solde

    def deposer(self, montant):

        self.solde = self.solde + montant

c = Compte("Léa", 20)

c.deposer(15)

print(c.solde)   # 35

Ici Compte est la classe, titulaire et solde sont des attributs, __init__ (le constructeur) et deposer sont des méthodes. On accède à un attribut avec objet.attribut et on appelle une méthode avec objet.methode(...).

Exemple : une pile (LIFO) a pour interface empiler, depiler, est_vide. On peut l'implémenter avec une liste Python, ou avec une liste chaînée. Celui qui utilise la pile n'a pas besoin de savoir laquelle.

class Pile:

    def __init__(self):

        self.contenu = []

    def empiler(self, x):

        self.contenu.append(x)

    def depiler(self):

        return self.contenu.pop()

    def est_vide(self):

        return len(self.contenu) == 0

Modules et API

Un module est un fichier Python qui regroupe des fonctions et des classes. On l'utilise avec import.

from math import sqrt

print(sqrt(49))   # affiche sept, sous forme de flottant

L'API (interface de programmation) d'une bibliothèque est la liste de ce qu'elle propose : noms, paramètres, rôle, décrits dans sa documentation. Pour sqrt, l'API dit : « prend un nombre positif, renvoie sa racine carrée ». On n'a pas besoin de connaître le code interne. Remarque : Python affiche les nombres décimaux avec un point (7.0), alors qu'en français on écrit 7,0.

class Compte:

    def __init__(self, titulaire, solde):

        self.titulaire = titulaire

        self.solde = solde

    def deposer(self, montant):

        self.solde = self.solde + montant

Mise au point : spécification, assertions et tests

Un programme correct est un programme qui fait ce qu'on a spécifié. Pour s'en assurer, on documente, on protège et on teste.

• La docstring (texte entre """ sous la ligne def) décrit ce que fait la fonction, ses paramètres et ce qu'elle renvoie. Elle sert de documentation (help(maximum)).

• La précondition est une condition que les arguments doivent respecter. On la vérifie avec assert.

• Un jeu de tests est un ensemble de cas dont on connaît le résultat attendu.

def maximum(liste):

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

    assert len(liste) > 0, "la liste doit être non vide"

    m = liste[0]

    for x in liste:

        if x > m:

            m = x

    return m

assert maximum([3, 8, 5]) == 8       # cas général

assert maximum([4]) == 4             # un seul élément

assert maximum([-7, -2, -9]) == -2   # valeurs négatives

Si une assertion est fausse, Python s'arrête avec une AssertionError : le bogue est signalé tout de suite.

Cas limites et flottants

Un bon jeu de tests contient des cas limites : liste vide, un seul élément, valeurs négatives, zéro, très grandes valeurs. Les bogues se cachent souvent là.

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)

Récursivité

Une fonction est récursive quand elle s'appelle elle-même. Elle comporte 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.

def somme_chiffres(n):

    if n < 10:

        return n

    return n % 10 + somme_chiffres(n // 10)

La version itérative (paradigme impératif) utilise une boucle while et une variable accumulatrice :

def somme_chiffres_iter(n):

    s = 0

    while n > 0:

        s = s + n % 10

        n = n // 10

    return s

La version récursive est plus proche de la définition mathématique ; l'itérative évite d'empiler les appels.

Terminaison, correction et coût

• Terminaison : on exhibe une quantité entière positive qui diminue strictement à chaque appel (ici, le nombre de chiffres de n, ou n lui-même).

• Correction : on la prouve par récurrence (forte si l'appel porte sur une valeur plus petite quelconque).

Exemple : l'exponentiation rapide.

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)

Si $n$ est pair, on divise $n$ par 2 : $x^n = (x^{n/2})^2$. Si $n$ est impair, on se ramène à un exposant pair : $x^n = x \cdot x^{n-1}$. Après un appel impair vient forcément un appel pair, donc l'exposant est au moins divisé par 2 tous les deux appels. Le nombre d'appels est en $O(\log_2 n)$, contre $n$ multiplications pour la méthode naïve.

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 aussi une donnée : c'est un texte, que l'on peut stocker, copier, transmettre à une autre fonction. C'est ce que fait un compilateur, un interpréteur ou un antivirus.

On dit qu'un problème est décidable s'il existe un algorithme qui le résout pour toutes les entrées en un temps fini. Il est indécidable sinon. La calculabilité ne dépend pas du langage choisi : ce qu'on ne peut pas faire en Python, on ne peut pas le faire en un autre langage.

Conséquence : aucun outil ne peut vérifier automatiquement, pour tous les programmes, qu'ils s'arrêtent. Les outils de vérification existent, mais ils sont limités à certaines familles de programmes ou peuvent répondre « je ne sais pas ».

Revenons à la question du début : l'outil universel qui détecte les programmes qui bouclent n'existe donc pas. Cela ne dispense pas de tester, au contraire : c'est pourquoi on combine tests, assertions et preuves au cas par cas.

L'essentiel

• Une classe définit des attributs et des méthodes ; un objet en est une instance. L'interface dit ce qu'on peut faire, l'implémentation dit comment.

• Un module regroupe du code réutilisable ; son API et sa documentation suffisent pour l'utiliser.

• On met au point un programme avec une docstring, des préconditions (assert) et un jeu de tests incluant les cas limites. On ne compare pas deux flottants avec ==.

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

• Le problème de l'arrêt est indécidable : aucun algorithme ne peut décider, pour tout programme, s'il s'arrête.