Programmation objet et types abstraits de données en NSI

En NSI, la programmation objet n’est au programme qu’en Terminale. Toutefois, on gagne à l’aborder dès la classe (!) de Première, car elle simplifie certains apprentissages. Le langage choisi est Python 3, qui est précisément un langage de programmation objet. Une progression est proposée ici, basée sur la POO, pour le cours sur les données structurées (listes, tuples et dictionnaires en 1ère, piles, files, listes chaînées, arbres binaires en Tle).

Programmation objet et objets connectés

En fait, dès la classe de 2nde (en SNT) il est possible d’aborder la POO, car certains objets connectés se programment en Python, en appelant des méthodes (de fait, les lutins de Scratch ressemblent beaucoup à des objets). On programme de tels objets en micropython, sur des cartes de type Arduino (ici, une ESP-32).

Sachant que la LED de la carte est sur la broche 15, on la gère logiciellement sous forme d’un objet Pin (broche) que l’on importe du module machine, et qu’on crée logiciellement ainsi :

>>> from machine import Pin
>>> led = Pin(15,Pin.OUT)
>>> dir(led)
['__class__', 'value', 'DRIVE_0', 'DRIVE_1', 'DRIVE_2', 'DRIVE_3', 'IN', 'IRQ_FALLING', 'IRQ_RISING', 'OPEN_DRAIN', 'OUT', 'PULL_DOWN', 'PULL_UP', 'WAKE_HIGH', 'WAKE_LOW', 'board', 'init', 'irq', 'off', 'on']

La fonction dir donne la liste des méthodes de la broche, et on constate qu’il y a plusieurs constantes (dont le nom s’écrit en majuscules ; si seule la première lettre est en majuscule, on convient qu’il s’agit d’un objet), parmi lesquelles OUT, qui est un entier :

>>> led.OUT
3

Mais il y a aussi un on dont on se doute qu’il sert à allumer la LED, seulement

>>> led.on
<bound_method>

n’allume pas la LED et précise que on est une méthode (une fonction qui n’appartient qu’à la LED). Pour allumer la LED on doit appeler cette méthode (en précisant à qui on s’adresse, en précédant l’appel de la méthode du nom de la variable) avec on() :

>>> led.on()

Maintenant la LED est allumée. Pour l’éteindre on peut faire led.off() mais aussi modifier sa valeur; égale à 1 lorsqu’elle est allumée et à 0 lorsqu’elle est éteinte :

>>> led.value()
1
>>> led.value(0)
>>> led.value()
0

Ce TP a été fait en Première NSI mais aussi en 2nde SNT. Bien entendu, il y a des élèves qui se demandent pourquoi ils n’arrivent pas à allumer la LED à moitié avec

>>> led.value(0.5)
>>> led.value(0.000001)
>>> led.value()
1

On découvre expérimentalement que Pin(15) est une sortie numérique (elle ne peut prendre que les valeurs 0 ou 1, toute valeur non nulle étant assimilée à 1). Pour simuler l’allumage graduel de la LED, il faut moduler en largeur d’impulsions cette sortie numérique, à l’aide d’un objet PWM (Pulse Width Modulation) :

>>> from machine import PWM
>>> p = PWM(led)
>>> dir(p)
['__class__', 'deinit', 'duty', 'duty_ns', 'duty_u16', 'freq', 'init']
>>> p.duty()
512
>>> p.duty(8)

Cette fois-ci la LED est faiblement allumée.

Cours de Première NSI basé sur la POO

Les types au programme de Première NSI sont

• les types de base (booléens bool, entiers int, flottants float et chaînes de caractères str) y compris les fonctions,
• les types construits (tableaux list, n-uplets tuple et dictionnaires dict).

Pour vérifier que [1,2,3] est un tableau, on peut lui appliquer la fonction type :

>>> tab = [1,2,3]
>>> type(tab)
<class 'list'>

ou, mieux, la fonction dir :

>>> dir(tab)
['__add__', '__class__', '__class_getitem__', '__contains__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'clear', 'copy', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']

Pourquoi est-ce mieux que de chercher simplement le type de la variable ? Parce qu’avec cet affichage, on n’apprend pas que tab est une liste, mais qu’est-ce qu’une liste, ou plutôt qu’est-ce qu’on peut faire avec. Par exemple la présence d’une méthode __add__ permet d’additionner des tableaux :

>>> tab + [1,2]
[1, 2, 3, 1, 2]

La présence d’une méthode __len__ permet d’utiliser la fonction len :

>>> len(tab)
3

Les méthodes dont le nom commence, et finit, par un double underscore (on les appelle méthodes dunder) sont celles que les tableaux (facétieusement appelés listes en Python) héritent d’autres objets, et qui ne caractérisent pas les tableaux. Les autres par contre permettent de voir qu’on a affaire à un objet auquel on peut ajouter quelque chose :

>>> tab.append(5)
>>> tab
[1, 2, 3, 5]

où l’on peut insérer quelque chose :

>>> tab.insert(2,8)
>>> tab
[1, 2, 8, 3, 5]

que l’on peut trier :

>>> tab.sort()
>>> tab
[1, 2, 3, 5, 8]

ou dont on peut retirer un élément :

>>> tab.pop()
8
>>> tab
[1, 2, 3, 5]

La fonction dir permet (en se concentrant sur les méthodes non dunder) d’obtenir un résumé du cours (ici, sur les tableaux de Python) et, par là, de donner plus d’autonomie aux élèves en pratique Python. Le programme de Terminale stipule que

Distinguer des structures par le jeu des méthodes qui les caractérisent.

Il s’agit d’une allusion au duck typing cher à Python. On verra plus bas qu’une bonne partie du cours de Terminale s’appuie sur ce principe. Mais avant cela, on peut aborder des méthodes dunder qui clarifient beaucoup de choses sur les types construits vus en Première.

Mutabilité, immuabilité et aliasing

Seules les fonctions sont appelables (callables) c’est-à-dire que seules les fonctions possèdent une méthode __call__ :

>>> [o for o in [str,list,tuple,dict] if '__call__' in dir(o)]
[]

Concrètement cela signifie qu’on ne peut utiliser les parenthèses qu’avec des fonctions. Si on essaye avec un tableau on a ceci :

>>> tab(2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'list' object is not callable

Pour accéder à un élément d’un des types construits (à partir d’un index ou d’une clé) on doit utiliser les crochets :

>>> tab[2]
3

La possibilité de lire un élément d’une collection (et donc de parcourir la collection) est la conséquence de la présence d’une méthode __getitem__ :

>>> [o for o in [str,list,tuple,dict] if '__getitem__' in dir(o)]
[<class 'str'>, <class 'list'>, <class 'tuple'>, <class 'dict'>]

Les chaînes de caractères et les types construits sont suscriptables : on peut utiliser la notation des crochets pour examiner l’intérieur de ces objets. Les fonctions par contre ne sont pas suscriptables :

>>> from math import *
>>> sin[pi/2]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'builtin_function_or_method' object is not subscriptable
>>> sin(pi/2)
1.0

En fait, pour les tableaux, il est également possible d’utiliser la notation des crochets pour modifier un des éléments du tableau :

>>> tab[2] = 13
>>> tab
[1, 2, 13, 5]

En fait les tableaux ne sont pas seulement suscriptables, ils sont également mutables. Cela est dû à leur méthode __setitem__, ce qui fait qu’on peut savoir quels sont les types mutables au programme de NSI :

>>> [o for o in [str,list,tuple,dict] if '__setitem__' in dir(o)]
[<class 'list'>, <class 'dict'>]

En fait, seuls les tableaux et les dictionnaires sont mutables. Les autres types (y compris les types de base) sont immuables. Cela n’a donc pas de sens de donner une méthode append ou pop à un tuple. L’intérêt des objets immuables est qu’on peut les hasher :

>>> hash(tab)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

On verra plus bas comment simuler en Python un dictionnaire par une table de hashage, mais pour l’instant, il est bon de savoir que les clés des dictionnaires doivent être hashables, et qu’on ne peut donc pas utiliser de tableaux ni de dictionnaires comme clés de dictionnaires : les clés doivent être immuables pour être hashables.

La mutabilité des tableaux de Python pose problème :

>>> tab1 = [1,2,3]
>>> tab2 = tab1
>>> tab1
[1, 2, 3]
>>> tab2
[1, 2, 3]
>>> tab2[1] = 8
>>> tab2
[1, 8, 3]
>>> tab1
[1, 8, 3]

En voulant modifier tab2, on a aussi modifié tab1. Une solution consisterait à travailler, non sur tab1, mais sur une copie d’icelui :

>>> tab1 = [1,2,3]
>>> tab2 = tab1.copy()
>>> tab2[1] = 8
>>> tab1
[1, 2, 3]

La méthode copy() n’étant pas au programme de NSI, on peut lui préférer la liste en compréhension (qui, elle, est au programme) :

>>> tab1 = [1,2,3]
>>> tab2 = [x for x in tab1]
>>> tab2[1] = 8
>>> tab1
[1, 2, 3]

Cours de Terminale NSI basé sur la POO

En Terminale (et parfois au bac) les élèves ont parfois à créer leurs propres objets, avec l’instruction class. Un bon exemple d’utilisation de cette construction est constitué des structures de données qui sont au programme, à savoir les piles, les files, les listes chaînées, les arbres binaires, les arbres et les graphes. Cela est très proche de l’approche du livre de Christine Froidevaux et al, basé sur une axiomatique des types abstraits de donnés.

Les graphes

Les graphes sont plutôt compliqués à programmer objet, en raison du nombre de méthodes dont on a besoin. D’ailleurs des modules Python spécialisés (graphviz, networkx) existent déjà.

Les arbres étant des graphes particuliers (connexes sans cycle) ne sont pas non plus traités en POO.

Les arbres binaires

Un arbre binaire a une racine et deux sous-arbres (gauche et droit) qui sont chacun soit None, soit un arbre binaire :

class Arbre():
    def __init__(self,nom):
        self.label = nom
        self.G = None
        self.D = None
    def est_une_feuille(self):
        return self.G is None and self.D is None
    def greffe_gauche(self,greffe):
        self.G = greffe
    def greffe_droite(self,greffe):
        self.D = greffe    

et pour un arbre binaire de recherche, on ajoute une méthode de recherche (c’est le but) et d’insertion (de manière que la structure d’arbre binaire de recherche soit un invariant) :

    def dedans(self,clef):
        if self.label==clef:
            return True
        elif self.label>clef and self.G is not None:
            return self.G.dedans(clef)
        elif self.label<clef and self.D is not None:
            return self.D.dedans(clef)
        else:
            return False    

    def ajouter(self,clef):
        assert not self.dedans(clef)
        if self.label>clef:
            if self.G is None:
                self.greffe_gauche(BST(clef))
            else:
                self.G.ajouter(clef)
        elif self.label<clef:
            if self.D is None:
                self.greffe_droite(BST(clef))
            else:
                self.D.ajouter(clef)
        else:
            self=BST(clef)    

Listes chaînées

Plus simples que les arbres binaires, les listes chaînées en héritent : selon le modèle de Newell et Shaw (1957) une liste chaînée est un arbre binaire dans lequel chaque nœud n’a qu’un enfant droit :

class Liste:
    def __init__(self,label):
        self.label = label
        self.suivant = None
    def est_final(self):
        return self.suivant is None
    def suite(self):
        return self.suivant
    def ajout(self,elt):
        if self.est_final():
            self.suivant = Liste(elt)
        else:
            self.suivant.ajout(elt)

On a essentiellement redéfini le vocabulaire, en nommant final ce qui s’appelait feuille et suivant ce qui s’appelait enfant droit.

Piles

Une pile est un objet doté de méthodes d’empilement et de dépilement, ainsi qu’un test de vacuité. La méthode permettant de créer une pile vide n’est autre que le __init__ de Python :

class Pile:
    def __init__(self):
        self.tab = []
    def est_vide(self):
        return self.tab == []
    def empiler(self,elt):
        self.tab.append(elt)
    def depiler(self):
        return self.tab.pop()

Files

La classe File peut se définir d’une manière similaire à la classe Pile :

class File:
    def __init__(self):
        self.tab = []
    def est_vide(self):
        return self.tab == []
    def enfiler(self,elt):
        self.tab.append(elt)
    def defiler(self):
        return self.tab.pop(0)

ou alors à l’aide de deux piles (au programme de Terminale NSI) :

class File:
    def __init__(self):
        self.pile1 = Pile()
        self.pile2 = Pile()
    def est_vide(self):
        return self.pile1.est_vide() and self.pile2.est_vide()
    def flush(self):
        while not self.pile1.est_vide():
            self.pile2.empiler(self.pile1.depiler())
    def enfiler(self,elt):
        self.pile1.empiler(elt)
    def defiler(self):
        if self.pile2.est_vide():
            self.flush()
        return self.pile2.depiler()

Dictionnaires

La construction des dictionnaires n’est pas vraiment au programme, tout au plus peut-on y lire :

Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire.

Cependant, avec des élèves qui ont déjà quelque expérience en POO, on peut envisager de simuler les dictionnaires (y compris leur affichage) en Python :

def h(o):
    return hash(o) % 256

class Dictionnaire:
    def __init__(self):
        self.clefs = [None]*256
        self.valeurs = [None]*256
    def __setitem__(self,clef,valeur):
        self.clefs[h(clef)] = clef
        self.valeurs[h(clef)] = valeur
    def __getitem__(self,clef):
        return self.valeurs[h(clef)]
    def __repr__(self):
        s = '{'
        for i in range(len(self.clefs)):
            if self.clefs[i] is not None:
                s += str(self.clefs[i])
                s += ':'
                s += str(self.valeurs[i])
                s += ', '
        return s + '}'

Ce dictionnaire light de Python s’utilise comme le vrai dictionnaire :

>>> dico = Dictionnaire()
>>> dico[2] = 3
>>> dico[5] = 8
>>> dico
{2:3, 5:8, }

Le cours complet en pdf

Afin de voir la proportion de POO dans le cours, voici celui-ci (sur les trois années du lycée) :

Cours de SNT (2nde) :

Cours de Première NSI :

Cours de Terminale NSI :