Nous allons aborder trois thèmes liés à la
spécification des programmes et à la gestion des erreurs :
- le typage, qui permet la détection précoce d’incohérences dans un programme ;
- le test systématique et rigoureux des différentes fonctions composant un programme ;
- les invariants de structure, qui spécifient les propriétés internes des structures de données complexes.
En programmation, la notion de type désigne une classification des objets manipulés en fonction de leur nature. D’un langage à l’autre, ces informations sont plus ou moins présentes, mais on gagne toujours à ne pas les ignorer.
","title":"Types"},{"edit":"Chaque valeur manipulée par un programme Python est associée à un type, qui caractérise la nature de cette valeur. On a ainsi un type int pour les nombres entiers, et d’autres types de base illustrés dans le tableau suivant.
| valeur | type | description |
| 1 | int | nombres entiers |
| 3.14 | float | nombres décimaux |
| True | bool | booléens |
| “abc'\" | str | chaînes de caractères |
| None | NoneType | valeur indéfinie |
| (1 , 2) | tuple | n-uplets |
| [1, 2, 3] | list | tableaux |
| {1, 2, 3} | set | ensembles |
| {’a’: 1, ’b’: 2} | dict | dictionnaires |
En outre, chaque nom de classe Python définit un type, de même nom, pour les instances de cette classe.
En Python, on dispose d’une fonction type permettant d’obtenir le type de la valeur passée en paramètre.
En jouant avec cette fonction dans la boucle interactive, on pourra par exemple vérifier que {} en Python désigne le dictionnaire vide et non l’ensemble vide, observer que les fonctions peuvent être vues comme des valeurs dont le type est tout simplement appelé fonction, ou encore remarquer que les classes elles-mêmes ont le type, type!
Les types permettent de caractériser les opérandes ou paramètres qui sont ou non acceptables pour certaines opérations. En particulier, l’utilisation de valeurs qui seraient par nature incompatibles avec une opération donnée lève une exception TypeError qui est généralement accompagnée
d’information sur les types qui ne conviennent pas.
Dans le cas d'opérateurs comme + qui peuvent avoir de multiples significations (on parle ici de surcharge de cet opérateur), les types des opérandes permettent également de préciser ce aui doit être fait.
| exemple | opérande | effet | résultat |
| 1+2 | int | addition | 3 |
| 1.2 + 3.4 | float | addition | 4.6 |
| True + True | bool | addition | 2 |
| \"abc\" + \"de\" | str | concaténation | \"abcde\" |
| (1, 2) + (3, 4) | turple | concaténation | [1, 2, 3, 4) |
| [1, 2] + [3, 4] | | list | concaténation | [1, 2, 3, 4] |
En Python, la gestion des types est qualifiée de dynamique : c'est au moment de l'exécution du programme, lors de l'interprétation de chaque opération de base, que l’interprète Python vérifie la concordance entre les opérations et les types des valeurs utilisées.
Bien que le langage Python ne nous y pousse pas explicitement, il est utile d’avoir en tête les types des différentes variables et expressions contenues dans les programmes que nous écrivons ou lisons : cette information, qu’on peut rapprocher de la notion de dimension des grandeurs physiques, aide à la compréhension de l’ensemble et évite les incohérences.
Erreurs. L’addition d’un nombre entier et d’un tableau n’a pas de sens en Python.
>>> 1 + [2, 3]
Traceback (most recent call last):
File \"<stdin>\", line 1, in <module>
TypeError: unsupported operand type(s) for +:
int” and ’list’
Bien qu’en Python les types ne jouent réellement un rôle qu’au niveau des opérations de base, il est indispensable lors de la définition d’une fonction d’avoir en tête les types attendus pour les paramètres et l’éventuel type du résultat.
Cette information est même une information cruciale à fournir dans l'interface d’un module, pour préciser la description faite de chaque fonction et éviter autant que possible leur mauvaise utilisation.
En effet, l'utilisateur d’un module n’étant pas censé avoir besoin de lire le code de ce module, lui présenter à l'exécution une erreur de type survenant à l’intérieur de ce code qu’il aurait dû pouvoir ignorer est pour le moins discourtois.
De manière plus générale, même sans parler d'interface il est utile de concevoir clairement le type des données associées à chaque variable d’un programme.
Pour inclure ces informations sur les types dans le programme lui-même il est possible d’annoter le code d’un programme, et en particulier les définitions de variables et de fonctions.
Ainsi, lors de la première définition d’une variable x destinée à représenter un nombre entier.
Nous pouvons utiliser la notation suivante :
x: int = 42
Dans cette instruction d’affectation ordinaire, le nom de la variable est suivi d’un symbole : (deux-points) et du type associé à cette variable.
Pour fournir les informations de types sur les paramètres et le résultat d’une fonction, des annotations similaires sont incluses dans la première ligne de la définition, c’est-à-dire la ligne donnant les noms de la fonction et de ses paramètres. Pour illustrer nos propos, nous allons reprendre le code des programmes 6 et 7. Par exemple, notre fonction contient_doublon du programme 7, qui attend un tableau t (type list en Python) et renvoie un booléen (type bool), peut ainsi voir la première ligne de sa définition annotée comme ceci :
def contient _doublon(t: list) -> bool:
Comme le montre cet exemple on annote un paramètre de la même manière qu’une variable, en faisant suivre son nom par le symbole : (deux-points) et le type attendu pour ce paramètre. On indique le type du résultat d’une fonction à la fin de la ligne, juste avant le : marquant le début du corps de la fonction, après une flèche ->.
L’annotation des fonctions du programme 6 suit le même principe. La fonction crée n'attend aucun paramètre et renvoie un tableau.
def cree() -> list:
La fonction contient attend pour paramètres un tableau et un entier, et renvoie un booléen. Les deux paramètres annotés sont séparés par une virgule, comme ils l’étaient avant d’être annotés.
def contient(s: list, x: int) -> bool:
La fonction ajoute attend pour paramètres un tableau et un entier, et ne renvoie pas de résultat. On note l’absence de résultat en indiquant None comme type de retour 1.
def ajoute(s: list, x: int) -> None:
En Python, ces annotations ont uniquement un rôle de documentation.
L’interprète lui-même ne fait aucune vérification de cohérence, lors de lappel d’une fonction ou de l’utilisation d’une variable, entre les types déclarés et
les types des valeurs effectivement utilisées. Les annotations fournissent en revanche des informations importantes pour toute personne amenée à lire le
programme ou à utiliser ses fonctions.
En outre, des outils externes peuvent être utilisés pour faire des vérifications globales de cohérence des types dans des programmes Python. Ces outils, eux, utilisent les annotations apportées par le programmeur.
En Python, les types connus pour les valeurs structurées comme les n-uplets et les tableaux restent très superficiels : le couple d’entiers (1, 2) et le triplet mixte (1, \"abc\", False) ont tous les deux le type tuple.
De même un tableau d’entiers et un tableau de chaînes de caractères auront tous deux le type list, et la même confusion s'applique aux ensembles ou encore aux dictionnaires.
À l'inverse de Python, de nombreux langages de programmation ont une gestion dite statique des types, en procédant à des vérifications au moment de la compilation des programmes. Dans de tels langages, un programme comportant des incohérences entre des opérations et les valeurs auxquelles elles s'appliquent ne sera jamais exécuté.
L'intérêt de ces vérifications en amont est de faire que les incohérences soient détectées aussi tôt que possible, et de manière systématique. Avec
de tels langages, il se passe donc parfois plus de temps avant qu’un programme ne puisse être exécuté pour la première fois, puisqu'il faut corriger au préalable les éventuelles incohérences détectées par le compilateur. En revanche, on gagne énormément de temps sur le débogage, puisqu'on évite les erreurs que ces incohérences auraient immanquablement causées lors des tests, ou pire, lors de l’utilisation réelle.
Les vérificateurs de types, inclus dans ces langages à typage statique ou disponibles comme outils externes pour Python, utilisent les annotations de types données par le programmeur. Certains langages sont mêmes capables d’une inférence de types, c'est-à-dire qu'ils déterminent par eux-mêmes le type de chaque élément du programme, sans l’aide du programmeur.
Un outil libre historique pour la vérification statique des types en Python est mypy (http://www.
mypy-lang.org).
L'outil peut être ajouté à toute installation standard
de Python, et fournit un programme que l’on peut exécuter sur un ensemble de fichiers .py pour réaliser la vérification et, le cas échéant, obtenir la liste des erreurs.
Depuis, plusieurs grandes compagnies ont également produit leur vérificateur, qu’il s'agisse comme mypy d'outils à exécuter à part (pytype de Google ou pyre de Facebook), ou d'outils intégrés à un environnement de développement (l'éditeur pycharm de JetBrains ou le
Visual Studio Code de Microsoft).
"},{"edit":"On peut cependant être plus précis dans la description
des types de ces éléments composites, en associant le type de l’élément lui-même et le ou les types de ses composants. On dit que le type de l’élément principal est paramètré par le ou les types de ses composants.
Le tableau suivant donne quelques exemples compatibles avec la syntaxe des annotations de types de Python.
| type | description |
| Tuple[int, bool] | couple d’un entier et d’un booléen |
| List[int] | tableau d’entiers |
| Set[str] | ensemble de chaînes de caractères |
| Dict[str, int] | dictionnaire dont les clés sont des chaînes de caractères et les valeurs des entiers |
Notez que les types paramétrés de ce tableau sont écrits avec une première
lettre majuscule : il ne s’agit pas directement des types de base tuple, list, set et dict de Python, mais de nouvelles versions définies dans le module typing (et qui doivent donc être importées avant utilisation).
Lorsque l’on manipule des structures de données particulières, il est courant de fournir un nouveau nom (appelé alias) à leur type.
Ainsi, la structure de données représentant un ensemble de l’un ou l’autre des programmes 6, 9 ou 10 pourrait être simplement nommée Ensemble dans
l'interface du module correspondant, et les trois fonctions auraient alors les types suivants.
cree() -> Ensemble
contient(s: Ensemble, x: int) -> bool
ajoute(s: Ensemble, x: int) -> None
Cette pratique a de nombreux avantages. En premier lieu elle présente à l'utilisateur du module un nom
représente et non la manière dont il est réalisé en interne.
Par conséquent, cette pratique accompagne également l’encapsulation : le type présenté par l'interface ne dépend pas des détails d’implémentation, et n’a donc pas à être modifié en cas d’évolution de la représentation interne.
Remarque : les types donnés pour cree, contient et ajoute valent pour toutes les réalisations que nous avons données de ces fonctions, bien que ces dernières adoptent des représentations très différentes. En effet, dans le programme 6 le type Ensemble serait défini par
Ensemble = List[int]
alors que dans le programme 9 nous aurions
Ensemble = List[List{int]]
Notez que dans le cas où un tel module est réalisé à l’aide d’une classe,par exemple dans le programme 12, le nom de la classe définit le nom du type correspondant. Le détail de la signification de Ensemble est alors déduit de la définition de la classe.
Les annotations de types d’une méthode d’une classe sont exactement les mêmes que celles des fonctions ordinaires. Il faut simplement noter que le premier paramètre, self, désignant un objet de la classe contenant la méthode, son type sera nécessairement cette classe elle-même.
class Chrono:
def texte(self: Chrono) -> str:
def avance(self: Chrono, s: int) -> None:
L'interface fournie aux modules représentant des ensembles d’entiers pourra être adaptée pour
des ensembles d’autres types d'éléments.
En donnant un type EnsembleC pour des ensembles de chaînes de caractères, il suffira d’écrire les types
adaptés suivants.
cree() -> EnsembleC
contient(s: EnsembleC , x: str) -> bool
ajoute(s: EnsembleC, x: str) -> None
On peut même imaginer un module d’ensembles généralistes, capable de
gérer des ensembles homogènes d'éléments d’un type arbitraire. On peut
ainsi avoir une variante paramétrée Ensemble [T] du type Ensemble, où T
est un paramètre de type non précisé (on l'appelle parfois variable de type,
où le mot « variable » doit cette fois être compris au sens mathématique et
plus au sens informatique). L'interface devient alors
cree() -> Ensemble[T]
contient(s: Ensemble[T], x: T) -> bool
ajoute(s: Ensemble[T], x: T) -> None
et n’impose plus un type particulier d'éléments dans l’ensemble, mais seulement une cohérence entre le type des éléments contenus dans l’ensemble et le
types des éléments que l'on veut ajouter ou dont l’on veut tester la présence.
Le même module fournissant ces ensembles de type Ensemble[T] pourra alors être utilisé par un client pour des ensembles d’entiers (Ensemble[int] ),par un autre pour des ensembles de couples d’entiers et de chaînes de caractères (Ensemble[Tuple[int, str]], etc.
Pour se conformer à une telle interface générique, un module doit réaliser les différentes opérations sans utiliser d'opérations spécifiques à un type particulier.
La stratégie rudimentaire utilisée dans le programme 1 donne un tel exemple : l’opération s.append(x) n’agit que sur le tableau s et n’a pas besoin de consulter la valeur de x, et l'opération x in s ne consulte x et les éléments de l’ensemble que pour tester leur égalité deux à deux, ce qui est possible quels que soient les types des éléments.
Les autres programmes que nous avons donnés en revanche utilisent d’une manière ou l’autre le fait
que les éléments de l’ensemble étaient des entiers. Ainsi, en réalisant un module générique on s’interdit certaines optimisations qui tireraient parti d’une nature particulière des éléments manipulés. En revanche on gagne en réutilisabilité du code, ce qui est l’un des objectifs de la modularité!
Le programme 10 réalisant une table de hachage simple pourrait facilement être transformé en un module d’ensembles capable de gérer une grande variété de types d'éléments : il suffit, à chaque fois que l’on détermine le numéro du paquet d’un élément
x avec une opération
p = x % n
de faire à la place
p = hash(x) % n.
La fonction hash de Python, appelée fonction de hachage, prend en paramètre un élément de n'importe quel type « hachable » et renvoie un entier (le code de hachage de cet élément). Cette fonction est utilisée
en interne par les ensembles et dictionnaires de Python.
Grâce à cette combinaison il est possible d’avoir des structures pour les ensembles et les dictionnaires qui soient à la fois génériques et très efficaces.
Le module typing permet d'introduire des variables de type avec l'opération TypeVar. On peut alors utiliser
ces variables dans les annotations.
from typing import TypeVar, List
T = TypeVar(’T’)
Ensemble = List[T]
def contient(s: Ensemble, x: T) -> bool:
Notez que pour pouvoir écrire Ensemble[T] en Python tel que nous l'avons fait dans le texte il faut utiliser les mécanismes d’héritage (hors programme) pour indiquer que le type Ensemble est un cas particulier d'un type spécial Generic[T] défini dans le module typing.
Nous prendrons cependant la liberté d’utiliser cette notation paramétrée partout où elle sera utile pour clarifier les interfaces.
Tester et mettre le résultat ici (code et figure).
Même si on a correctement spécifié et documenté une programme, il reste possible de faire une erreur en écrivant son code.
Pour détecter ces éventuelles erreurs, on peut utiliser le programme sur quelques cas concrets et vérifier qu’il produit effectivement les résultats attendus.
On appelle cela le test
Mettre le résultat ici (code et figure).
Lorsqu'un programme se termine, il signale au système d'exploitation s'il a terminé son exécution normalement, ou bien au contraire s'il s'est arrête sur une erreur, à l’aide d'un code de sortie, qui est un entier.
Lorsqu'un programme Python parvient sans erreur au terme de la séquence de ses instructions, il termine avec le code 0, qui désigne une exécution qui s'est correctement déroulée. De même, un appel à exit() termine le programme avec le code 0.
Tout code de sortie non nul signale un problème et la valeur de l’'entier peut être utilisée pour distinguer plusieurs raisons différentes pour l'échec du programme. Un appel à exit(\"message\") ou une instruction assert qui évalue sa condition à False termine le programme avec le code de sortie 1.
On peut utiliser exit avec un entier en argument. comme par exemple exit(42), pour terminer le programme avec un code de sortie de son choix.
Pour cela, on peut appliquer la fonction indice maximum _tableau au tableau suivant [2, 3, 1] et observer le résultat.
>>> indice maximum _tableau([2, 3, 1])
1
Si le résultat renvoyé par la fonction n’est pas celui qui était attendu, alors le programme est manifestement erroné et il convient de trouver et corriger l'erreur.
Si le résultat est bien celui attendu, comme ici, cela ne signifie pas nécessairement qu’il n’y pas d'erreur.
Le programme peut contenir une erreur qui ne se révélerait que sur d’autres tableaux. Il faut donc effectuer d’autres tests.
Par exemple, comme la spécification de indice_maximum_tableau mentionne le cas particulier du tableau vide, il est intéressant de tester la fonction sur ce cas.
>>> indice _maximum_tableau([])
None
De nombreuses autres situations méritent encore d’être testées, par exemple des cas particuliers où la valeur maximale est située au début ou à la fin du tableau, où encore le cas d’un tableau ne contenant que des entiers négatifs.
"},{"edit":"Mettre le résultat ici (code et figure).
Plutôt que d’effectuer les tests dans la boucle interactive de Python, une meilleure solution consiste à les inclure dans le même fichier que le programme. En particulier, plutôt que de vérifier visuellement que chaque résultat obtenu est bien celui qui était attendu, on peut faire vérifier ceci par l'interprète Python, par exemple avec la construction assert et un test.
def indice_maximum_tableau(t) :
#Ecrire le code ici
return 1
assert indice_maximum_tableau([2, 3, 1]) == 1
assert indice_maximum_tableau([]) == None
assert indice_maximum_tableau([3, 1, 3, 7]) == 3
assert indice_maximum_tableau([8, 3, 1, 3, 7]) == 0
assert indice_maximum_tableau([-3, -1, -3, -7]) == 1
Ecrire la fonction indic_ maximum_tableau.et tester le code.
Si l’un de ces tests échoue, il faut rectifier le programme. Une fois l'erreur corrigée, il convient de relancer tous les tests, y compris ceux qui avaient
déjà été effectués avec succès.
En effet, en corrigeant une erreur, on peut en introduire une autre. (C’est même assez courant.) Il est donc intéressant d’avoir écrit tous les tests dans le fichier où est définie la fonction indic_ maximum_tableau.
Pour un test donné, c'est la spécifion qui indique le résultat attendu. On à une situation un peu plus délicate lorsque plusieurs réponses sont correctes. En particulier, que devrait renvoyer la fonction indice__maximum_tableau sur le tableau
[3, 1, 3] où l'élément maximum apparaît deux fois?
La spécification n'indique pas que l’une des deux occurrences doit être préférée à l’autre.
Ainsi, à moins d’être certain que le programme donnera toujours la préférence à la première occurrence, on ne peut écrire le test sous la forme
assert indice_maximum_tableau(([3, 1, 3]) == 0
puisque la réponse 2 serait également acceptable. Dans ce cas nous ne pouvons que vérifier que le résultat obtenu est bien un des resultats admissibles.
On pent le faire de la manière suivante.
m = indice_maximum_tableau([3,1,3])
assert m == 0 or m == 2
Tester votre fonction avec les 2 exemples de test.
","title":"Spécification non déterministe"},{"edit":"Mettre le résultat ici (code et figure).
On peut définir de nombreux tests pour un programme donné sur la seule base de sa spécification. Il suffit donc d'avoir décidé ce que devait exactement faire une fonction pour commencer à écrire les tests associés.
En particulier. il est tout à fait imaginable, et c'est même une pratique courante, d'écrire un certain nombre de tests pour une fonction avant même d’avoir écrit le code de cette fonction.
Dans le cas d’un travail en équipe et une fois la spécification décidée en commun, on peut même confier la définition des tests et l'écriture du programme à deux personnes différentes. Cette pratique vise à éviter que le même oubli se glisse à la fois dans le programme et dans les tests et passe ainsi inaperçu.
","title":"Quand définir ses tests?"},{"edit":"Mettre le résultat ici (code et figure).
En général on ne peut pas écrire un ensemble de tests exhaustif, qui suffirait à exclure toute erreur. Les entiers de Python, par exemple, sont en nombre infini, de même que les tableaux d’entiers, les chaînes, etc.
Il est donc exclu de tous les tester individuellement. Le mieux qu’on puisse faire a priori est de trouver un « bon » ensemble de tests, qui soit suffisant pour donner une bonne confiance dans le programme testé.
Il est délicat de déterminer à quel moment un ensemble de tests est suffisant. L'objectif est que les tests réunis couvrent tous les «comportements» possibles du programme, ce qui est un concept assez vague.
Voici une liste de points d'usage général à garder en tête et à compléter au cas par cas.
- Si la spécification du programme mentionne plusieurs cas, chacun de ces cas doit faire l’objet d’un test
- Si une fonction renvoie une valeur booléenne, essayer d’avoir des tests impliquant chacun des deux résultats possibles.
- Si le programme s'applique à un tableau, il faut inclure un test couvrant le cas du tableau vide.
- Si le programme s’applique à un nombre, il peut être utile de tester pour ce nombre des valeurs positives, des valeurs négatives, ainsi que Zéro.
- Si le programme fait intervenir un nombre appartenant à un certain intervalle, il peut être utile d'inclure des tests dans lesquels le nombre est aux limites de cet intervalle. En particulier, si le programme fait intervenir un indice d’un tableau, on peut inclure des tests dans lesquels
cet indice sera 0 ou l'indice maximal.
","title":"Bons ensembles de test"},{"edit":"Mettre le résultat ici (code et figure).
On n'eflectue que des tests en accord avec cette précondition. Eu effet, lorsque les conditions d'utilisation d'une fonction ne sont pas remplies, la spécification ne dit rien de ce que doit être le résultat
.
On ne saurait alors déterminer un € résultat attendu » auquel comparer le résultat obtenu.
","title":"Tests et précondition"},{"edit":"En plus des critères informels évoqués ici, on
utilise également dans l'industrie quelques critères quantitatifs appelés critères de couverture, mesurant par exemple le pourcentage des instructions du programme qui sont effectivement exécutées lors d'au moins un des tests.
Nous venons d'insister sur la nécessité de tester ses programmes.
Maintenant, nous mettons en œuvre sur un exemple de test sur un programme de tri.
Plus précisément, on suppose que l’on cherche à tester ici une fonction Python tri qui trie un tableau d’entiers, en place, par ordre croissant.
On suppose par ailleurs qu’on n’a pas accès au code Python de cette fonction tri. Elle pourrait avoir été écrite par quelqu'un d'autre, voire même proposée dans un module Python dont nous n’avons pas le code source.
Dans de telles circonstances, on appelle cela un «test en boîte noire», une image qui évoque que la fonction que nous sommes en train de tester est cachée dans une boîte opaque, sans que nous puissions l’observer autrement qu’en l'appelant sur des arguments donnés et en examinant le résultat.
Pour tester notre fonction de tri, on écrit une fonction test qui prend en argument un tableau t, appelle la fonction tri sur ce tableau, puis vérifie que le tableau t est bien trié.
def test(t):
tri(t)
for i in range(0, len(t) - 1):
assert t[i] <= t[i+i]
On utilise ici l'instruction assert pour faire cette vérification. Ainsi, si le tableau n’a pas été trié correctement, l'exécution de la fonction test sera
interrompue avec une exception AssertionError. Avec cette fonction test, on peut commencer à écrire quelques tests élémentaires, sur un tableau vide,
un tableau ne contenant qu’un seul élément, un tableau manifestement non trié, etc.
test([])
test ([1])
test([2, 1])
C’est un bon début. Cependant, notre fonction test est un peu trop naïve. En effet, elle vérifie que le tableau t a bien été trié mais elle omet de vérifier qu’il contient bien les mêmes éléments qu'avant l’appel.
Une fonction tri qui écrirait la valeur 0 dans toutes les cases du tableau passerait les tests !
Plus subtilement, une fonction qui ajouterait ou supprimerait un élément pourrait encore passer les tests.
Le cas extrême serait celui d’une fonction qui supprime tous les éléments du tableau :
def tri(t):
t.clear()
Modifions donc la fonction test pour qu’elle vérifie également que les éléments sont toujours les mêmes qu'initialement.
Ce n’est pas complètement évident à réaliser. On peut imaginer faire une copie du tableau t avant d’appeler tri(t) puis vérifier que tout élément de cette copie est dans t et que tout élément de t est dans cette copie.
Malheureusement, c’est là encore un peu naïf. En effet, une fonction tri qui changerait le tableau [2, 1, 1] en le tableau [1, 2, 2] passerait ce test, sans pour autant être correct. Il faut donc vérifier que les éléments sont les mêmes, avec pour chacun le même nombre d’occurrences avant et après.
Il y a de multiples façons de réaliser une telle vérification.
Le programme 14 en propose une, à l’aide d’une fonction occurrences qui construit un dictionnaire à partir des éléments d’un tableau et d’une fonction identiques qui vérifie que deux dictionnaires sont
identiques.
Maintenant que nous disposons d’une fonction test correcte, on peut relancer les trois tests qu’on a faits plus haut mais surtout passer à des tests un peu plus ambitieux. On commence par se donner une fonction qui construit un tableau aléatoire, d’une taille donnée et dont les éléments sont pris dans un intervalle également donné.
On se sert pour cela de la fonction randint de la bibliothèque random.
def tableau_aleatoire(n, a, b):
return [a + randint(0, b - a) for _ in range(n)]
t = tableau_aleatoire(20,-15,15)
print(t)
Enfin, on lance des tests sur des tableaux de différentes tailles et dont les valeurs sont prises dans des intervalles variables.
def test(t) :
print(t)
for n in range(100):
test(tableau_aleatoire(n, 0, 0))
test(tableau_aleatoire(n, - n // 4, n // 4))
test(tableau_aleatoire(n, - 10 * n, 10 * n))
Ici, on fait varier la taille n du tableau entre 0 et 99. En particulier, on teste donc la fonction sur un tableau vide, ce que nous avions fait plus haut explicitement avec test([]).
Par ailleurs, le choix des intervalles n’est pas anodin. Le premier, à savoir 0..0, aura pour effet de tester la fonction de tri sur des tableaux contenant uniquement la valeur 0, c’est-à-dire des valeurs toutes égales.
Cela peut paraître stupide, mais c’est en réalité un très
bon test. Il n’est pas rare qu’un programmeur suppose, inconsciemment ou non, que les valeurs manipulées sont distinctes.
Le deuxième intervalle, à savoir -n//4..n//4 a l'objectif similaire de créer des doublons. En effet, un
tableau de taille 10 dont les valeurs sont comprises entre —3 et 2 contiendra nécessairement des doublons.
Le troisième intervalle est au contraire d’une
amplitude 20 fois supérieure à la taille du tableau, ce qui réduira les collisions.
Enfin, remarquons qu’on a délibérément inclus des valeurs négatives dans ces intervalles. Là encore, c’est pour mieux éprouver la fonction tri. dans le cas où elle ne fonctionnerait correctement que sur des entiers positifs ou nuls.
Programme 14 — Tester une fonction de tri
def occurrences(t):
\"\"\"renvoie le dictionnaire des occurrences de t\"\"\"
d = {}
for x in t:
if x in d:
d[x] += 1
else:
d[x] = 1
return d
def identiques(d1, d2):
\"\"\"test si deux dictionnaires sont identiques\"\"\"
for x in d1:
assert x in d2
assert d1[x] == d2[x]
for x in d2:
assert x in d1
assert d2[x] == d1[x]
def test(t):
\"\"\"teste la fonction tri sur le tableau t\"\"\"
occ = occurrences(t)
tri(t)
for i in range(0, len(t) - 1):
assert t[i] <= t[i+1]
identiques(occ, occurrences(t))
Pour être complet, mentionnons que la fonction tri doit bien entendu terminer, sans quoi elle ne peut être considérée comme correcte. Notre fonction test n’est évidemment pas en mesure de déterminer cela.
On pourrait imaginer interrompre la fonction tri passé
un certain délai, mais cela n’est pas facile à mettre en œuvre, d’une part, et le choix d’un tel délai est délicat, d'autre part. En pratique, on observe que la fonction test ne termine pas et on interrompt le programme (avec un Ctri-C). On en déduit qu’on a trouvé un problème avec la fonction tri.
Au delà de la correction, on souhaite le plus souvent vérifier également les performances de nos programmes.
Parfois, la théorie nous permet de prédire les performances (tel algorithme sera linéaire en la taille des données, tel autre quadratique, etc.) mais il n’en reste pas moins une certaine distance entre la théorie et la pratique qu’il peut être intéressant d'évaluer.
Ainsi, on peut connaître précisément la complexité d’un algorithme de tri et pour autant ne pas savoir s’il va permettre de trier un tableau d’un million d’entiers en un temps raisonnable.
Par ailleurs, un programme pourrait avoir passé avec succès tous les tests de correction dont nous avons parlé plus haut et être pour autant victime d’un bug qui
affecte uniquement ses performances.
Pour évaluer les performances d’une fonction ou d’un programme, une méthode simple mais efficace consiste à mesurer son temps d'exécution sur différentes entrées. Pour réaliser une telle mesure, on peut utiliser la fonction perf_counter ou la fonction time de la bibliothèque time.
La première est plus précise que la seconde mais n’est disponible que depuis la version 3.3 de Python.
Ces deux fonctions renvoient le nombre de secondes écoulées depuis un instant de référence (le démarrage de l'ordinateur, le premier janvier 1970 à minuit : heure Unix).
import time
t1 = time.time()
print(t1)
t2 = time.time()
print(t2)
dt = t2 - t1
print(dt)
Tester le code ci-dessus et conclure.
Comme on le constate, cette valeur a une précision en dessous de la seconde.
La valeur proprement dite ne nous intéresse pas vraiment mais la différence entre les deux valeurs renvoyées par time.time() à deux moments différents
nous donne le temps écoulé.
Ainsi, on peut mesurer le temps passé dans l’appel à une certaine fonction tri comme ceci :
t = time.time()
tri(tab)
print(time.time() - t)
Bien entendu, c’est là une mesure relativement grossière du temps, car notre système d’exploitation est multitâche, c’est-à-dire qu'il exécute plusieurs
programmes en même temps.
Néanmoins, si le processeur n’est pas occupé à d’autres programmes demandant beaucoup de calcul,
c'est là une mesure suffisante pour des tests de performance, surtout dès lors que les temps relevés dépassent la seconde.
Mettre le résultat ici (code et figure).
Plutôt que de mesurer les performances d’un seul appel, il est préférable d'essayer de faire varier les entrées, dans le but de relier la taille de ces entrées avec la mesure du temps d'exécution.
Avec la petite boucle suivante, on mesure la performance d’une fonction tri sur des tableaux dont la taille double à chaque étape.
for k in range(10, 16):
n = 2 ** k
tab = tableau_aleatoire(n, -100, 100)
t = time.time()
tri(tab)
print(n, time.time() - t)
Ici, la fonction tableau_aleatoire est supposée construire un tableau aléatoire de taille n, comme on l’a fait plus haut dans cette section. On note qu’on a pris soin de ne pas mesurer le temps passé dans cette fonction, mais seulement celui passé dans la fonction tri.
On obtient par exemple les chiffres ici donnés à gauche :
| n | temps(s) |
| 1024 | 0.023916959762573242 |
| 2048 | 0.07994365692138672 |
| 4096 | 0.3072216510772705 |
| 8192 | 1.2350132465362549 |
| 16384 | 4.926177501678467 |
| 32768 | 20.367548942565918 |
Un tel affichage sur deux colonnes, de la valeur de n d’une part et du temps d'exécution d’autre part, nous facilite la compréhension des performances de notre fonction tri. Ici, on constate immédiatement que, lorsque la valeur de n double, le temps d’exécution fait plus que doubler.
Mieux encore, on observe qu’il quadruple. Il s’agit donc là très probablement d’un algorithme de tri quadratique (comme le tri par insertion). Si la lecture est difficile, on
peut également copier-coller ces valeurs dans un tableur ou plus générale-ment dans un quelconque outil qui saura les analyser ou les afficher.
Ici, on a affiché un graphique construit par l'outil gnuplot à partir de ces valeurs.
Mettre le résultat ici (code et figure).
Dans la séquence précédent, nous avons expliqué qu'un objet encapsule un certain nombre d’attributs, avec lesquels on interagit notamment par l'intermédiaire de méthodes. Il n’est pas rare
que ces attributs satisfassent des invariants. En voici quelques exemples :
- un attribut représente un mois de l’année et sa valeur doit être comprise entre 1 et 12;
- un attribut contient un tableau d’entiers représentant un numéro de sécurité sociale et sa taille doit être égale à 13 (et un numéro de sécurité sociale vérifie par ailleurs un certain nombre d’autres invariants) :
- un attribut contient un tableau qui doit être trié en permanence ;
- deux attributs x et y représentent une position sur une grille N x N et se doivent de respecter les inégalités 0 <x<N et 0<y<N;
- etc.
On trouvera dans cet ouvrage d’innombrable exemples de tels invariants, souvent implicites. On a pris ici l'exemple d’attributs, car le principe d’encapsulation nous permet d'espérer pouvoir maintenir ces invariants. Il suffit en effet que le constructeur de la classe les garantisse. par construction ou par vérification, puis que les méthodes qui modifient des attributs maintiennent les invariants. Ainsi, si on est en train de définir une classe C avec deux attributs x et y passés en arguments au constructeur, et que ces deux attributs doivent vérifier un invariant, on commencera par s'assurer que c’est bien le cas.
class C:
def __init__(self, x, y):
if not (...invariant...):
raise ValueError(?’...une explication...’)
self.x = x
self.y = y
On pourrait être tenté de faire confiance à l'utilisateur, mais une programmation défensive est toujours une bonne idée.
De même, si on écrit une méthode qui modifie un ou plusieurs attributs, on peut ajouter une vérification explicite :
def deplace(self):
if ... :
self.x += 1
self.y += 1
assert ...invariant...
Cette fois, il ne s’agit pas de faire confiance à l’utilisateur mais plutôt d’avoir confiance dans notre capacité à programmer correctement. Là encore, une
programmation défensive n’a que des avantages.
Lorsque la vérification d’un invariant commence à être complexe à écrire et/ou coûteuse à exécuter, il peut être une bonne idée de la déporter dans une méthode spécifique.
def valide(self):
vérifie l’invariant
... et lève une exception si besoin ...
Les bénéfices sont nombreux. D'une part, on peut l’invoquer à de multiples endroits, sans avoir à dupliquer le code qui fait la vérification. En particulier,
on limite ainsi le risque d’erreur dans le code qui vérifie l’invariant.
D'autre part, on peut facilement débrancher le test de l’invariant s’il s'avère coûteux, par exemple en ajoutant un simple return tout au début de la méthode valide une fois la classe mise au point. Enfin, on peut avantageusement utiliser une telle méthode pendant le test de notre classe.
Comme on l’a expliqué, le principe d'encapsulation
est également valable pour les modules, dont une partie des données peut être volontairement cachée. Là encore, ces données peuvent être sujettes à des invariants. On peut alors procéder exactement comme avec les objets, en testant l’invariant dynamiquement et/ou en fournissant une fonction valide qui effectue la vérification.
Pour chacune des fonctions suivantes, proposer un type pour chacun de ses arguments et un type pour son résultat :
def f1(t):
return t[0] + 1
def f2(x):
return str(3.14 x x)
def f3(p):
x, y = p
return 2*x+7y
def f4(s):
s.add(42)
def f5(d, s):
if s != \"toto\":
d[s] += 1
return d[s]
Dans certains cas, il peut y avoir plusieurs solutions.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def f1(t: list) -> int:
def f2(x: float) -> str:
def f3(p: tuple) -> int:
def f4(s: set) -> NoneType:
def f(d: dict, s: str) -> int:
On suppose avoir écrit une fonction mult(x, y) qui calcule et renvoie le produit de deux entiers x et y reçus en arguments.
L'idée est que cette fonction ne se contente pas d’appeler l'opération * mais réalise un autre algorithme, comme la multiplication russe, la méthode de Karatsuba.
def taille(x):
n=1
while x > 0:
x //= 2
n += 1
return n
def karatsuba(x, y, n):
\"\"\"multiplie x et y par La méthode de Karatsuba\"\"\"
if n <= 1:
return x * y
n //=2
m = 1 << n
a , b = x>>n , x%m
c , d = y>>n , y%m
ac= karatsuba(a, c, n)
bd = karatsuba(b, d, n)
abcd = karatsuba(a - b, c - d, n)
return (ac << (2*n)) + ((ac+bd -abcd) << n) +bd
def mult(x, y):
n = max(taille(abs(x)), taille(abs(y)))
return karatsuba(x, y, n)
print(mult(1000,1000))
Proposer des tests de correction pour cette
fonction mult.
Proposer ensuite des tests de performances.
Tracer la caractéristique et conclure
Mettre le résultat ici (code et figure).
Pour ce qui est des tests de correction, une bonne
idée consiste à tester que les multiplications par 0 et par 1 donnent bien les résultats attendus. C’est également une bonne idée d'inclure des valeurs négatives, car il est tout à fait plausible que la fonction mult soit correcte uniquement sur des entiers positifs. Voici de premiers tests tout à fait raisonnables :
from random import randint
#Test de correction
for _ in range(1000):
x = randint(-100, 100)
assert mult(0, x) == 0
assert mult(x, 0) == 0
assert mult(1, x) == x
assert mult(x, 1) == x
y = randint(-100, 100)
assert mult(x, y) == x * y
assert mult(y, x) == x * y
En particulier, la dernière ligne vérifie que la multiplication est bien com-
mutative.
Pour ce qui est des tests de performances, on peut mesure le temps d’exécution de la fonction mult sur deux entiers de n chiffres chacun, pour différente valeur de n. On peut prendre par exemple des valeurs de n qui doublent à chaque étape, c’est-à-dire des puissances de 2.
Pour construire un nombre de n chiffres, on le tire au hasard entre 10^(n-1) et 10^n - 1.
#Test de performance
import time
from random import randint
for k in range(1, 17):
n=2**k
min, max = 10**(n-1),10**n - 1
x = randint(min, max)
y = randint(min, max)
t = time.time()
z = mult(x, y)
print(n, time.time() - t)
En traçant la caractéristique, on voit que le temps d'exécution est à peu près multiplié par 4 lorsque
le nombre de chiffres est multiplié par 2.
Il s’agit donc là d’un algorithme de complexité quadratique (en le nombre de chiffres n), ce qui est la complexité de la méthode naïve ou encore de la multiplication russe.
Proposer des tests pour tester la fonction miroir(ch) qui prend en argument une chaîne de caractères ch et renvoie la chaîne contenant les caractères de ch en ordre inverse.
def miroir(ch) :
ch2 = \"\"
for lettre in ch :
ch2 = lettre + ch2
return ch2
print(miroir(\"Bonjour\"))
Mettre le résultat ici (code et figure).
Il y a plusieurs façons d'écrire une fonction test qui
vérifie le comportement de la fonction miroir sur une chaîne ch donnée. On peut vérifier que la longueur est la même et que les caractères sont bien inversés :
def test(ch):
n = len(ch)
m = miroir(ch)
assert len(m) == n
for i in range(n):
assert m[i] == ch[n - 1 - i]
print(\"test ok\")
test(\"bonjour\")
Il y a une solution plus simple, cependant, car Python nous fournit déjà cette opération de miroir, avec ch[::-1], et il suffit donc de comparer les deux chaînes :
def test(ch):
assert miroir(ch) == ch[::-1]
print(\"test ok\")
test(\"bonjour\")
Pour ce qui est du jeu de tests, maintenant, on se donne une fonction pour
from random import randint
def chaine_aleatoire(n):
return ''.join([chr(randint(65, 90)) for _ in range(n)])
print(chaine_aleatoire(50))
Ici, on a choisi de prendre des caractères entre 'A' et 'Z’ mais il faudrait en toute rigueur tester la fonction miroir sur l’ensemble des caractères UTF-8 (ce que ce peut faire en tirant au hasard un entier entre 0 et Ox10FFFF puis en lui appliquant chr). Enfin, on peut tester avec des chaînes de différentes longueurs :
for n in range(100):
test(chaine_aleatoire(n))
Il est important d'inclure la chaîne vide (longueur 0), ainsi que des chaînes de longueur impaire (la fonction miroir pourrait ne fonctionner correctement que sur des chaînes de longueur paire).
On suppose qu’une classe portion contient un tableau dans un attribut tab et délimite une portion de ce tableau à l’aide de deux autres attributs deb et fin. La portion s'étend de l'indice deb inclus à l’indice fin exclu.
Écrire une méthode valide
def valide(self):
assert ...
qui vérifie que les attributs deb et fin définissent bien une portion valide du tableau tab.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
assert 0 <= self.deb <= self.fin <= len(self.tab)
#On utilise ici le fait que Python permet de chaîner les
#inégalités :
def valide(self):
assert 0 <= self.deb <= self.fin <= len(self.tab)
On suppose avoir écrit une fonction retire_com(nomf). Cette fonction ouvre en lecture un fichier dont le nom est donné en argument et qui doit obligatoirement se terminer par l'extension «.py».
Pour un tel fichier « {.py », la fonction crée un nouveau fichier «{_sanscomm.py » qui est une copie du fichier original dont on a retiré tous les commentaires. Si le
fichier de destination existe déjà, il est écrasé.
La fonction renvoie True en cas de succès et False en cas d’erreur.
Lister les conditions sous lesquelles cette fonction peut renvoyer False.
Mettre le résultat ici (code et figure).
- L’argument nomf ne se termine pas par « .py ».
- Le fichier nomf n'existe pas.
- Le fichier nomf existe, mais l’utilisateur n’a pas les droits en lecture.
- Le fichier nomf existe, mais c’est un répertoire.
- Le fichier de sortie existe, mais l'utilisateur ne possède pas les droits en écriture sur ce fichier (il ne pourra donc pas écraser son contenu).
- Le fichier de sortie n'existe pas et l'utilisateur n’a pas les droits en écriture sur le répertoire de destination (il ne peut donc pas créer de fichier).
- Le fichier de destination existe et est un répertoire (l’utilisateur ne pourra pas l’écraser).
- (Rare) Le fichier source est un lien symbolique dont la cible n'existe pas.
- (Très Rare) Il ne reste plus assez d'espace disque pour stocker le fichier de sortie.
De façon générale, à part pour la première condition que l’on peut tester facilement avec nomf .endswith(\".py\"}), on ne va pas tester individuellement
toutes les conditions d’erreurs sur les fichiers. Il est plus judicieux d’encadrer les fonctions systèmes par un bloc try except et de rattraper les grandes classes d’exceptions : toutes les erreurs sauf la première et la dernière lèveront l'exception OSError avec un message approprié.
La dernière sera une exception IOError.
On souhaite que les instances de la classe Chrono ébauchée ci-dessous respectent les invariants de structure suivants : la valeur de l’attribut heures est comprise entre 0 et 23, et les valeurs des attributs minutes et secondes sont comprises entre 0 et 59.
class Chrono:
\"\"\"lune classe pour représenter un temps mesuré en
heures, minutes et secondes\"\"\"
def __init__(self, h, m, s):
self.heures = h
self.minutes = m
self.secondes = s
def avance(self, s):
self.secondes += s
self.minutes += self.secondes // 60
self.secondes = self.secondes % 60
self.heures += self.minutes // 60
self.minutes = self.minutes % 60
Que manque-t-il à ce code pour que ces invariants soient bien toujours valides quoiqu'il arrive?
Le corriger, en précisant au besoin la spécification de
chacune des méthodes.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Le code de la méthode avance prend garde à ne pas
induire de dépassement sur les minutes et les secondes, mais ne gère pas les heures.
On pourrait ajouter une ultime ligne
self.heures = self.heures % 24
à son code, après la dernière ligne actuelle.
Dans ce cas, avancer d’une seconde à partir de 23h 59m 59s amène à 0h 0m 0s.
Notez que cette méthode fonctionne également pour les valeurs négatives de s.
La fonction __init__, elle, ne fait aucune vérification.
On pourrait restreindre son utilisation et imposer qu’elle ne prenne en paramètres que des nombres entiers, pris dans les bons intervalles.
def __init__(self, h: int, m: int, s: int):
if h<0 or h > 23 or m < 0 or m > 59 \\
or s < 0 or s > 59 :
raise ValueError(’heure invalide’)
self.heures = h
....