Prouver et analyser : la boîte à outils formalisée
Cours · informatique (tronc commun des prépas scientifiques), chapitre 10 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun
10.1 Introduction et motivation
Le premier semestre a pratiqué la discipline de programmation en artisan : spécifier, tester, exhiber un variant, énoncer un invariant. Ce chapitre la formalise en théorie outillée — non par goût de l'abstraction, mais parce que les programmes du second semestre (graphes, plus courts chemins) sont trop subtils pour l'intuition seule. On y précise d'abord ce qu'est un programme Python — la différence entre expression et instruction, et la notion d'effet de bord, source des bogues les plus déroutants du langage. On y définit ensuite avec exactitude ce que « cet algorithme est juste » veut dire : correction partielle (s'il s'arrête, le résultat est bon) et correction totale (il s'arrête, et le résultat est bon) — deux propriétés réellement distinctes, dont la séparation éclaire toute la méthodologie variant/invariant. On y systématise enfin les deux outils d'évaluation : le jeu de tests construit par partitionnement du domaine d'entrée, et la complexité — désormais en temps et en espace.
Le mot d'ordre du programme : on ne prouve pas systématiquement tous les algorithmes, mais on dégage l'idée qu'un algorithme doit se prouver et que sa programmation doit se tester. Les deux, toujours : la preuve garantit l'algorithme, le test contrôle le programme — et chacun attrape ce que l'autre laisse passer.
10.2 Expressions, instructions, effets de bord
10.2.1 Deux natures de code
Une expression désigne un calcul qui produit une valeur : 2 + 3, t[i] > m, len(t) - 1, f(x). Une instruction désigne une action qui modifie l'état du programme ou son déroulement : l'affectation x = 2 + 3, le return, le if, la boucle. Une expression peut figurer partout où une valeur est attendue ; une instruction, jamais.
Qu'en Python l'affectation soit une instruction — et non une expression qui vaudrait quelque chose — est un choix des concepteurs du langage. Conséquence heureuse : le grand classique du C, écrire if (x = 3) (affectation) en croyant tester x == 3 (comparaison), est en Python une erreur de syntaxe — le bogue est promu faute de frappe détectée. Conséquence à connaître : on ne peut pas écrire y = (x = 3) + 1 ; une chaîne d'affectations a = b = 0 est une forme spéciale, pas une expression.
10.2.2 Les effets de bord
Un fragment de code a un effet de bord s'il modifie un état observable au-delà de la valeur qu'il renvoie : modifier une liste ou un dictionnaire passé en argument, modifier une variable globale, écrire à l'écran ou dans un fichier. Une fonction sans effet de bord — qui ne fait que calculer sa valeur de retour — est dite pure.
def trie_copie(t: list) -> list: # PURE : t est intact,
return sorted(t) # la valeur de retour porte tout
def trie_en_place(t: list) -> None: # EFFET DE BORD assumé :
t.sort() # t est modifiée, rien n'est renvoyéLes deux conventions sont légitimes ; le danger est l'hybride non documenté — une fonction qui modifie son argument et renvoie quelque chose, ou pire, qui le modifie « par accident ». Le contrat (chapitre 1) doit toujours répondre : cette fonction modifie-t-elle ses arguments ?
L'affectation Python ne copie jamais les listes : elle partage (chapitre 8). L'effet de bord accidentel naît de ce partage :
def ajoute_zero(t: list) -> list:
t.append(0) # modifie la liste de L'APPELANT !
return t
notes = [12, 15]
copie = notes # alias, pas copie
ajoute_zero(notes)
# notes == copie == [12, 15, 0] : deux noms, une liste, un effet partout
Règles pratiques : pour ne pas modifier, travailler sur list(t) ; pour modifier, l'écrire dans la docstring et renvoyer None (la convention de t.sort() : l'absence de valeur de retour signale l'effet de bord).