I. Présentation du code

a) Nommer ses variables

• Il est important de donner des noms explicites à ses variables : sauf dans les cas vraiment "standard" (L, i, j, ...), on utilise un ou deux mots. C'est d'autant plus vrai pour les fonctions.
• Les noms des variables et fonctions sont en snake_case en Python :
  • tout en minuscule (sauf les acronymes) ;
  • un underscore _ entre les mots ;
  • soit tout en français sans accent, soit tout en anglais, pas de mélange.

b) Opérateurs de calculs

On peut faire des calculs entre des valeurs ou des variables.

a = 3 + 4
b = 13039 % 12

On met toujours des espaces avant et après un opérateur binaire. Pour un opérateur unaire, on ne met pas d'espace.

calcul = 3 * 5
nombre_negatif = -7

c) Les commentaires

Il est important de commenter votre code dès qu'il n'est pas évident ! Par exemple :

• commentaire inutile :

a = 3 # assigne 3 à la variable a

• commentaire utile :

cpt = 0 # la variable cpt compte le nombre de bouteilles dans la mer

d) Documenter ses fonctions

On peut (et on doit) ajouter une chaîne de documentation à ses fonctions. On peut ensuite accéder à cette chaîne avec help :

def salue(personne):
    """
    Prend en argument une personne (chaine de caractères) et la salue.
    Renvoie un booléen, `True` si la salutation a été retournée.
    """
    # code pour saluer une personne

help(salue)

e) Indentation

L'indentation de votre programme doit être parfaitement claire. À l'écrit, on trace des lignes !

II. Programmation défensive

a) Pré-conditions, post-conditions, invariant

Comment faire pour être certain qu'une boucle, ou qu'un bloc d'instructions, est correct ?

On écrit des conditions de la forme suivante :

• une pré-condition est respectée avant l'entrée dans la boucle ;
• pendant toute l'exécution de la boucle, un invariant reste vrai ;
• si ces deux propriétés sont respectées, on en déduit une post-condition qui sera vraie à la sortie de la boucle.

def somme(L):
    """
    Cette fonction prend en argument une liste d'entiers, et calcule et renvoie sa somme.
    """
    S = 0
    # pré-condition
    for i in range(len(L)):
        # invariant
        S += L[i]
    # post-condition
    return S

def insere(L_triee, x):
    """ Cette fonction prend en argument une liste triée d'entiers, et un élément x, et l'insère en place dans la liste. """
    ...

def tri_insertion(L):
    """Cette fonction prend en argument une liste d'entiers, et renvoie une nouvelle liste triée avec l'algorithme du tri par insertion."""
    L_triee = []
    # pré-condition
    for i in range(len(L)):
        # invariant
        insere(L_triee, L[i])
    # post-condition
    return L_triee

b) Assertions

Les assertions permettent de tester les conditions et invariants pendant l'exécution du code. Si la condition est fausse, une erreur est levée.

# pré-condition : la liste n'est pas vide
assert len(L) > 0

Par exemple :

def somme(L):
    """
    Cette fonction prend en argument une liste d'entiers, et calcule et renvoie sa somme.
    """
    S = 0
    #pré-condition : L est une liste d'entiers
    assert type(L) == list
    for i in range(len(L)):
        # invariant : L[i] est un entier et S contient la somme de L[0:i].
        assert type(L[i]) == int
        S += L[i]
    # post-condition : S contient la somme de L.
    return S

print(somme([1, 2, 3]))
print(somme([1, 2.5, 3]))

On peut observer l'invariant avec tracer_variables (du module affichage du site), qui affiche les valeurs des variables à la fin de chaque tour de boucle : à la fin du tour où i vaut , S contient bien la somme de L[0:k+1].

c) Tests

On appelle jeu de tests l'ensemble des tests d'un programme. Comment écrire des tests ?

• Partitionner l'espace d'entrée en catégories, et faire un test par catégorie.
• Tester les cas limites.

Par exemple, pour une fonction qui cherche l'indice du maximum d'une liste, on teste : une liste d'un seul élément, un maximum au début, au milieu, à la fin, un maximum présent plusieurs fois, des nombres négatifs.

def indice_max(L):
    """Renvoie l'indice de la première occurrence du maximum de L (non vide)."""
    i_max = 0
    for i in range(1, len(L)):
        if L[i] > L[i_max]:
            i_max = i
    return i_max

def test_indice_max():
    assert indice_max([7]) == 0                  # un seul élément
    assert indice_max([9, 1, 2]) == 0            # maximum au début
    assert indice_max([1, 9, 2]) == 1            # au milieu
    assert indice_max([1, 2, 9]) == 2            # à la fin
    assert indice_max([3, 9, 1, 9]) == 1         # plusieurs fois : la première occurrence
    assert indice_max([-5, -2, -8]) == 1         # nombres négatifs
    print("Tous les tests sont passés.")

test_indice_max()

III. Preuves de programme

Lorsqu'on ne veut pas dépendre d'un test, on peut prouver mathématiquement que notre programme est juste.

def exp(x, n):
    resultat = 1
    while n != 0:
        resultat *= x
        n -= 1
    return resultat

def exp(x, n):
    """ Prend en entrée un entier x et un entier positif n et renvoie x^n. """
    resultat = 1
    assert n >= 0
    while n != 0:
        resultat *= x
        n -= 1
    return resultat

Pour prouver la terminaison, on utilise un variant de boucle :

Dans la fonction exp ci-dessus, n est un variant de boucle : la boucle termine donc.

Pour prouver la correction partielle d'une boucle, on utilise un invariant : une propriété

1. vraie avant la boucle (initialisation) ;
2. qui, si elle est vraie au début d'un tour de boucle, l'est encore à la fin (conservation) ;
3. qui, à la sortie de la boucle, donne le résultat voulu (conclusion).

C'est une récurrence sur le nombre de tours de boucle.

Exemple : la fonction exp. Notons et les valeurs des arguments au départ, et la valeur de la variable n au cours de l'exécution. Montrons que la propriété

est un invariant de boucle.

1. Initialisation : avant la boucle, et , donc .
2. Conservation : supposons vraie au début d'un tour. Pendant le tour, resultat est multiplié par et diminue de 1 : la nouvelle valeur de est .
3. Conclusion : à la sortie de la boucle, , donc : la fonction renvoie bien .

Avec la terminaison (le variant ), la fonction est totalement correcte.

On peut observer l'invariant pendant l'exécution :

Exercices

def somme(L):
    S = 0
    i = 0
    while i < len(L):
        S += L[i]
        i += 1
    return S