Programmation des fonctions en `Python`

I/ Position du problème

1) Définition

On dit que deux entiers sont incommensurables si la fraction qu'ils forment est simplifiée au maximum.

Ceci veut dire qu'il n'existe aucun entier qui les divise tous les deux.

Le but du problème est de programmer une fonction Python qui s'applique à deux entiers et dit s'ils sont incommensurables.

2) Algorithme

Un algorithme est connu depuis plus de 2000 ans, il est cité dans le livre X des Éléments d'Euclide (théorème 2) :

Si, de deux grandeurs inégales proposées, on retranche toujours alternativement la plus petite de la plus grande, sans que le reste mesure la grandeur précédente : telles grandeurs seront incommensurables.

3) Types et prototypage

On veut une fonction qui dit si les entiers sont incommensurables, donc

cette fonction accepte deux entiers en entrée,
cette fonction renvoie un booléen.

On la type donc ainsi : def sont_incommensurables(x:int,y:int)-> bool:

Puisque la fonction renvoie un booléen, il faudra que chaque occurrence d'un return soit suivie d'une expression booléenne. Et on pourra utiliser cette fonction dans d'autres scripts Python, avec des choses comme if sont_commensurables(x,y): ou while sont_commensurables(x,y):.

4) Solution du problème

On propose cette traduction en Python, du texte d'Euclide :

deux grandeurs inégales proposées : on les nomme x et y
on retranche est noté -= en Python
toujours ... sans que correspond à un while
sans que le reste mesure la grandeur précédente veut dire qu'on boucle tant que les deux variables diffèrent l'une de l'autre, qu'on note while x!=y:
alternativement la plus petite de la plus grande donne un test if x<y: y -= x
telles grandeurs seront incommensurables si on s'arrête avant qu'une des variables x et y soit devenue divisible par l'autre. Sauf dans le cas où les deux variables sont devenues égales à 1. On finira donc par
```
    if x==1:
              return True
    else:
              return False
```
que l'on peut simplifier en return x==1

Finalement la fonction telle que décrite par Euclide est

def sont_incommensurables(x,y):
    while x!=y:
        if x<y:
            y -= x
        else:
            x -= y
    return x==1

II/ Causes de bugs

1) Syntaxe

En Python, d'expérience, les erreurs les plus fréquentes sont

les erreurs d'indentation (un if et un else qui ne sont pas à la verticale l'un de l'autre par exemple)
l'oubli d'un double-point à la fin d'une ligne commençant par if, else, for, while, def ou class...
une parenthèse ouverte mais pas refermée comme dans print('hello'
des guillemets pas (ou mal) refermés comme dans print('hello) ou print('hello")

2) Nom des variables

Si une variable s'appelle x1 lors de sa création, l'appeler par la suite xl donnera une erreur, parce que le chiffre 1 n'est pas la lettre l...

Il est d'ailleurs conseillé de donner aux variables des noms explicites précisant leur rôle et leur type : cela aide à déboguer sans forcément nécessiter de commentaire. De fait, la fonction précédente se code mieux avec

def sont_incommensurables(entier1,entier2):
    while entier1!=entier2:
        if entier1<entier2:
            entier2 -= entier1
        else:
            entier1 -= entier2
    return entier1==1

qui rappelle que les variables sont censées être entières (grandeur1 et grandeur2 étaient plus conformes au texte d'Euclide mais ne précisaient pas le type des variables).

Lorsqu'une variable porte un nom formé de plusieurs mots, comme il n'est pas autorisé d'y mettre des espaces, il est d'usage en Python, d'utiliser les espaces soulignées : le_nom_de_variable_le_plus_original_du_monde plutôt que leNomDeVariableLePlusOriginalDuMonde qu'on pratique dans d'autres langages. D'ailleurs le seul espace souligné underscore est autorisé comme nom de variable. On peut donc s'en servir comme joker le jour où on ne trouve vraiment pas de nom pour une variable de boucle. Pour répéter quelque chose 5 fois, plutôt que for je_ne_sais_pas_comment_appeler_cette_variable in range(5), on peut faire for _ in range(5) mais si on a besoin d'autres variables à usage unique, il faudra les nommer autrement...

3) Structure

L'oubli des règles de priorité opératoire (on effectue les multiplications avant les additions et les and avant les or) peut mener à des comportements imprévus de la fonction.

Cette version de la fonction ne donne pas de résultat (elle plante) parce qu'elle ne fait pas toujours varier les variables

def sont_incommensurables(entier1,entier2):
    while entier1!=entier2:
        if entier1<entier2:
            entier2 -= entier1
    return entier1==1

En effet, il manque la clause else et la fonction ne sait pas quoi faire lorsque entier1 est plus grand (ou égal) que entier2. Il ne fait rien et boucle sans fin.

Une erreur similaire est de faire varier la condition de sortie d'une boucle comme dans

plafond = 5
variable = 0
while variable<plafond:
    variable += 1
    plafond += 2
    print(variable,plafond)

Dans le cas des fonctions, il y a l'utilisation de print au lieu de return ou l'oubli de return, comme dans

def sont_incommensurables(entier1,entier2):
    while entier1!=entier2:
        if entier1<entier2:
            entier2 -= entier1
        else:
            entier1 -= entier2

qui ne donne pas de message d'erreur mais ne dit pas si les entiers sont incommensurables.

4) Sémantique

Une autre erreur fréquente est d'écrire une expression au lieu d'une instruction. Par exemple si on a besoin de tripler une variable x, écrire x*3 au lieu de x *= 3 ou x = x*3 mène à un comportement imprévu de la fonction puisque la simple écriture d'une expression (sans préciser quoi faire avec) n'a pas d'effet.

III/ Assertions

Au cas où quelque chose d'imprévu se passe lors de l'appel d'une fonction, il faut mieux qu'il y ait arrêt du calcul avec signalement de l'imprévu (débordement de mémoire, risque de calcul infini, types incohérents etc). Pour afficher des messages d'alerte, on peut utiliser (entre autres exceptions) l'instruction assert qui est suivie d'un booléen et éventuellement du message à afficher (une chaîne de caractères). L'instruction assert peut jouer plusieurs rôles.

1) Précondition

Telle qu'elle est définie, la fonction sont_incommensurables peut être appelée avec n'importe quel type de valeurs. Or elle n'a de sens que pour des entiers, et le calcul ne se termine pas si l'une des deux valeurs est nulle. Par exemple un appel à sont_incommensurables(3,0) boucle sans fin, alors qu'avec

def sont_incommensurables(entier1,entier2):
    assert type(entier1)==int, 'je voulais un entier'
    assert entier1>0, 'il fallait un entier positif'
    assert type(entier2)==int, 'je voulais un entier'
    assert entier2>0, 'il fallait un entier positif'
    while entier1!=entier2:
        if entier1<entier2:
            entier2 -= entier1
        else:
            entier1 -= entier2
    return entier1==1

l'appel à sont_incommensurables(3,0) donne l'affichage

    assert entier2>0, 'il fallait un entier positif'
AssertionError: il fallait un entier positif

qui précise mieux de quelle manière la fonction a été mal utilisée.

Les préconditions (@requires dans why3) servent à restreindre le domaine de définition de la fonction (par exemple 0 n'a pas d'inverse, un nombre négatif n'a pas de racine carrée etc).

2) Postcondition

Les postconditions (@ensures dans why3) servent à faire des preuves de correction. Pour prouver que la fonction est correcte, la première question est de formaliser la postcondition (un booléen). Dire que deux nombres sont incommensurables, c'est dire que leur commune mesure (ou leur pgcd) est 1. Or le module fractions de Python possède une fonction gcd qui calcule justement le pgcd de deux entiers (cette fonction utilise d'ailleurs une amélioration de l'algorithme d'Euclide). On peut s'en servir pour calculer avant tout le pgcd des deux variables, puis vérifier la postcondition selon laquelle la valeur finale de entier1 n'est égale à 1 que si le pgcd aussi vaut 1. On va même prétendre que de toute façon, la valeur finale de entier1 est égale au pgcd :

from fractions import gcd

def sont_incommensurables(entier1,entier2):
    le_pgcd = gcd(entier1,entier2)
    while entier1!=entier2:
        if entier1<entier2:
            entier2 -= entier1
        else:
            entier1 -= entier2
    assert entier1==le_pgcd
    return entier1==1

Si jamais la postcondition n'était pas vraie, on verrait un message d'erreur d'assertion. Le fait que les tests ne donnent pas ce genre de message d'erreur, laisse penser que la fonction n'est pas boguée. Pour prouver ce qu'on soupçonne, il faut utiliser why3 ou analogue.

3) Invariant

Pour prouver la correction d'une fonction, on utilise un (ou plusieurs) invariant. L'instruction assert, placée au début d'une boucle, permet de tester un invariant. Par exemple on soupçonne qu'à chaque passage dans la boucle, les deux variables entier1 et entier2 sont divisibles par le pgcd :

from fractions import gcd

def sont_incommensurables(entier1,entier2):
    le_pgcd = gcd(entier1,entier2)
    while entier1!=entier2:
        assert entier1%le_pgcd==0
        assert entier2%le_pgcd==0
        if entier1<entier2:
            entier2 -= entier1
        else:
            entier1 -= entier2
    return entier1==1

L'absence de message d'erreur montre expérimentalement que cela semble bien être un invariant.

4) Tests

L'instruction assert peut même servir à faire des tests. Une fois programmée la fonction sont_incommensurables, on peut mettre dans le fichier Python des instructions d'assertion, qui montrent par leur silence la réussite des tests. Il est important de choisir un jeu de valeurs couvrant des cas différents (par exemple des petits nombres, des nombres commensurables, des nombres non commensurables, des nombres égaux etc). Par exemple

assert sont_incommensurables(1,5)
assert not sont_incommensurables(12,16)
assert not sont_incommensurables(6,8)
assert not sont_incommensurables(8,6)
assert not sont_incommensurables(7,7)

On peut aussi donner des exemples de tests dans la documentation en ligne de la fonction. Par exemple avec

from fractions import gcd

def sont_incommensurables(entier1,entier2):
    """Donner deux entiers positifs et la fonction 
    dit s'ils sont incommensurables.
    Exemples
    >>> sont_incommensurables(3,5)
        True
    >>> sont_incommensurables(4,6)
        False
    (en effet ils ont 2 en commun)
    """
    assert type(entier1)==int, 'je voulais un entier'
    assert entier1>0, 'il fallait un entier positif'
    assert type(entier2)==int, 'je voulais un entier'
    assert entier2>0, 'il fallait un entier positif'
    le_pgcd = gcd(entier1,entier2)
    while entier1!=entier2:
        assert entier1%le_pgcd==0
        assert entier2%le_pgcd==0
        if entier1<entier2:
            entier2 -= entier1
        else:
            entier1 -= entier2
    assert entier1==le_pgcd
    return entier1==1

en écrivant

help(sont_incommensurables)

on obtient

Help on function sont_incommensurables in module __main__:

sont_incommensurables(entier1, entier2)
    Donner deux entiers positifs et la fonction 
    dit s'ils sont incommensurables.
    Exemples
    >>> sont_incommensurables(3,5)
        True
    >>> sont_incommensurables(4,6)
        False
    (en effet ils ont 2 en commun)

Il y a des IDE qui affichent l'aide dans des phylactères au survol par la souris. Il est donc utile de mettre une aide lorsqu'on programme une fonction. En fait le plus sûr est de programmer la fonction dans l'ordre suivant :

la spécification (def ...),
l'aide en ligne avec des exemples,
Les préconditions,
Les postconditions,
Et seulement à la fin, les instructions.

IV/ Autres outils

Certains IDE (algorea, Thonny, python tutor...) possèdent un mode pas-à-pas permettant de voir ce qui se passe à chaque pas de l'exécution du programme. Cela aide à voir à quel moment arrive un imprévu et donc à quel endroit exact se situe le bug.

En phase de mise au point la fonction print peut s'arriver utile, éventuellement combinée avec la fonction type...

Lorsque l'interpréteur Python découvre une erreur, il affiche en général un message assez précis sur la nature de l'erreur et la ligne où elle est apparue.

Le module dis de Python permet de désassembler une fonction compilée. Par exemple en insérant au début d'un script

from dis import *

un simple

dis(sont_incommensurables)

produit l'affichage suivant :

  5           0 SETUP_LOOP              51 (to 54)
        >>    3 LOAD_FAST                0 (entier1)
              6 LOAD_FAST                1 (entier2)
              9 COMPARE_OP               3 (!=)
             12 POP_JUMP_IF_FALSE       53

  6          15 LOAD_FAST                0 (entier1)
             18 LOAD_FAST                1 (entier2)
             21 COMPARE_OP               0 (<)
             24 POP_JUMP_IF_FALSE       40

  7          27 LOAD_FAST                1 (entier2)
             30 LOAD_FAST                0 (entier1)
             33 INPLACE_SUBTRACT
             34 STORE_FAST               1 (entier2)
             37 JUMP_ABSOLUTE            3

  9     >>   40 LOAD_FAST                0 (entier1)
             43 LOAD_FAST                1 (entier2)
             46 INPLACE_SUBTRACT
             47 STORE_FAST               0 (entier1)
             50 JUMP_ABSOLUTE            3
        >>   53 POP_BLOCK

 10     >>   54 LOAD_FAST                0 (entier1)
             57 LOAD_CONST               1 (1)
             60 COMPARE_OP               2 (==)
             63 RETURN_VALUE

Il s'agit d'un programme en assembleur pour le test de non commensurabilité.

Programmation des fonctions en Python