Détection d'erreurs

Problème

On suppose qu'on souhaite réaliser une fonction en Python qui analyse un programme Python afin de dire si le programme va renvoyer une erreur.

Cette fonction nommée detection(nom_fichier) analysera le contenu d'un programme, et renverra True si le programme contient un erreur et False sinon.

On souhaite que ce problème soit décidable.

DéfinitionProblème de décision

Un problème de décision est dit décidable s'il existe un algorithme qui se termine en un nombre fini d'étapes, qui le décide, c'est-à-dire qui réponde par oui ou non à la question posée par le problème.

RemarqueUn programme en paramètre ?

Un programme en Python est une chaîne de caractères. Notre fonction detection aura donc la possibilité de lire le contenu de ce programme, et de l'analyser en tant que chaîne de caractères.

C'est la même chose que la commande python dans un terminal. En donnant le nom d'un fichier, le programme va être analysé par Python avant d'être exécuté.

ExempleUn exemple d'utilisation

Soit le programme suivant :

1
# mon_programme.py
2
k = 5
3
while k > 0:
4
    k = k - 1
5
print(1/k)

L'exécution de ce programme provoquera une erreur due à la division par zéro : ZeroDivisionError: division by zero

Donc, on s'attend à ce que la fonction detection("mon_programme.py") renvoie True.

Détecteur naïf

Si on cherche à reproduire le résultat ci-dessus, on peut facilement imaginer que la fonction detection() exécute le programme et analyse son résultat. Cela donne la fonction suivante :

1
def detection_naif(nom_fichier):
2
    fichier = open(nom_fichier)
3
    programme = fichier.read()
4
    try:
5
        exec(programme)
6
        return False # Pas d'erreurs !
7
    except:
8
        return True # Une erreur est détectée

Ainsi, si le programme lève une exception, la fonction renvoie True. Sinon, la fonction renvoie False.

Malheureusement, cette fonction ne répond pas à la question posée. En effet, si on teste notre fonction avec le programme ci-dessous :

1
# etrange.py
2
while True:
3
    print("Hey")

alors l'appel à detection_naif("etrange.py") ne renvoie rien. Or, comme indiqué plus haut, le problème doit être décidable (ce n'est pas le cas avec cet exemple).

Détecteur parfait

Supposons désormais qu'on possède une fonction detection_parfaite() qui fonctionne parfaitement comme escompté. Montrons que ce n'est pas possible à l'aide d'un programme contre-exemple :

1
# echec.py
2
if detection_parfaite("echec.py"):
3
    print("Et bah non, y a pas d'erreurs !")
4
else:
5
    print("Perdu ! Il y a une erreur")
6
    print(1 / 0)

Voici les deux cas possibles :

  • Soit le programme echec.py contient une erreur.

    La fonction detection_parfaite("echec.py") renvoie True.

    Le programme s'exécute sans erreur.

    => IMPOSSIBLE

  • Soit le programme echec.py ne contient pas d'erreur.

    La fonction detection_parfaite("echec.py") renvoie False.

    Le programme s'exécute avec erreur.

    => IMPOSSIBLE

Donc, par preuve par l'absurde, la fonction detection_parfaite() n'existe pas.

Donc, on vient de prouver que le problème de detection d'erreur est indécidable.