3.8. Types de Données Abstraits

Voir aussi

Un lien vers l’ancien cours : programmation procédurale

3.8.1. Principe

Le découpage d’un programme en modules ne doit pas se faire de façon aléatoire. Il faut bien y réfléchir, car cela définit l”architecture du projet. Le principe architecturale qui vous est imposé pour le projet, repose sur le principe de la mise en œuvre de barrière d’abstraction et l’utilisation de types abstraits de données.

Indication

Remarque

Il existe plusieurs méthodes comparables pour concevoir un programme procédural, mais pour ce projet, une méthode vous est imposée. Le fait d’imposer cette méthode de développement est discutable mais nous n’avons pas le temps d’aborder les différentes façons de faire. Le choix de la barrière d’abstraction a été fait en accord avec le reste du programme pédagogique de l’école. Si vous avez déjà pris d’autres habitudes de programmation, il faudra faire l’effort de vous adapter au style de programmation proposé. Cela ne veut pas forcément dire que vos habitudes sont mauvaises mais simplement qu’elles sont différentes. Un bon développeur doit savoir adapter ses méthodes de développement au contexte et parfois maîtriser plusieurs styles. Ainsi, même si vous pensez être à l’aise en informatique, prêtez bien attention aux règles de programmation préconisées dans ce cours, pour la réalisation de votre projet.

Le principe de la mise en œuvre de la barrière d’abstraction repose sur l’identification de types abstraits de données et permet le découpage du logiciel en modules indépendants. Ce principe n’est absolument pas imposé par le langage python, il s’agit d’un élément de méthodologie. Une fois ce découpage réalisé, la répartition des fonctions à travers les différents modules devient logique, favorisant ainsi l’homogénéité du code et le travail en équipe.

La barrière d’abstraction permet de cacher dans un module les détails d’implémentation des services rendus par ce module. Pour utiliser une fonction, il n’y a pas besoin de savoir comment elle est codée. Il suffit de connaître les spécifications qui fournissent une définition abstraite du service rendu. De plus, pour manipuler des données complexes à l’aide de fonctions, il n’est pas toujours nécessaire de savoir comment ces données sont structurées. C’est là qu’intervient la notion de type de donnée abstrait.

Indication

Type données abstrait.

1. Type : Un type de données abstrait est d’abord un type. Nous décidons de considérer qu’une telle structure de données utilisée dans le programme correspond à un nouveau type de donnée qui n’existe pas dans python. Par exemple, imaginons qu’un casse brique manipule des dictionnaires pour représenter la ou les balles du jeu :

ball= {'position':(5.0,0.0), 'speed':(0.0,0.0), 'radius'='1', 'state':'normal' }.

bonusBall= {'position':(0.0,0.0), 'speed':(0.0,1.0), 'radius'='1', 'state':'fast' }.

Nous pouvons décider de créer un nouveau type de données: Ball; en indiquant qu’une donnée de ce type est un dictionnaire comprenant des entrées pour les clés suivantes : 'position', 'speed', 'radius' et 'state'. La position et la vitesse sont des tuple de 2 réels. Le rayon est un entier. L’état est une chaîne de caractère.

2. Abstrait : On qualifie les types d’abstraits car on veut pouvoir manipuler les données sans se préoccuper de la manière dont elle sont codées. Par exemple, lorsque nous manipulons une donnée de type Ball avec une fonction move(ball), peu nous importe de savoir si la balle est une liste, un dictionnaire ou autre chose, tant que la fonction move qui prend en paramètre une donnée de type Ball remplit sont rôle et modifie la position de la balle. Dans cet exemple, « abstrait » signifie donc que je sais que je manipule une structure de type Ball; que je sais que cette structure contient des informations relatives à sa vitesse, sa position, son état et son rayon; mais que je ne sais pas comment elle est construite dans le détail:

Type : Ball = struct
        position : float,float
        speed : float,float
        radius : int
        state : str

Attention la définition du type ci-dessus n’est pas du code python. Il s’agit de ce qu’on souhaite trouver dans le document de conception. Il faudra être suffisamment rigoureux pour coder en accord avec ce qui aura été conçu, en respectant notamment scupuleusement le nommage des données.

Pour mettre en œuvre la barrière d’abstraction, il faudra être capable d’identifier des types de données. Puis, il suffira de créer un module par type de données. L’exemple suivant montre comment créer un module à partir des données utilisées pour créer des graphes de ville.

CintyInfo

Type : CityInfo = struct
    name : str
    population : int

Pour construire le module correspondant au type cityInfo:

1. Regrouper dans un module toutes les fonctions qui manipulent la même donnée : CityInfo.py. Déclarer le type CityInfo

class CityInfo : pass

2. Constructeur: Définir une fonction pour créer la donnée:

def create(name='',population=0):
    cityInfo=CityInfo()
    cityInfo.name=name
    cityInfo.population=population
    return cityInfo

3. Accesseurs: Proposer des accesseurs pour retrouver des informations décrites par la donnée. On utilise le mot clé get:

def get_name(cityInfo):
    return cityInfo.name
def get_population(cityInfo):
    return cityInfo.population

4. Mutateurs: Proposer des mutateurs pour modifier la donnée. On utilise le mot clé set.

def set_name(cityInfo, name):
    cityInfo.name=name
def set_population(cityInfo,number):
    cityInfo.population=number

5. Opérations: Coder l’ensembles des fonctions permettant de réaliser une opération sur les données.

def show(cityInfo):
    msg= "La ville de"+ cityInfo.name+" comporte "
    msg=msg+ cityInfo.population+ " habitants"
    print(msg)

6. Tests: Mettre en œuvre les tests unitaires permettant de s’assurer du bon fonctionnement du module.

#tests
if __name__=="__main__":
    #verification par jeu de test, comparaison visuelle, etc...
    ci=create()
    show(ci)

un autre exemple

Le type ``Ball``

Voici un autre exemple pour le type Ball:

#Ball.py
class Ball: pass

#constructeur
def create(radius):
    b=Ball()
    b.position=(0.0,0.0)
    b.speed=(0.0,0.0)
    b.radius=radius
    b.state='normal'
    return b

#accesseurs
def get_position(ball):
    return ball.position

def get_speed(ball):
    return ball.speed

def get_radius(ball):
    return ball.radius

def get_state(ball):
    return ball.state

#mutateurs
def set_position(ball, x, y):
    ball.position=(x,y)

def set_speed(ball,vx,vy):
    ball.speed=(vx,vy)

def set_radius(ball,radius):
    ball.radius=radius

def set_state(ball, state):
    ball.state=state


def move(ball, dt):
    # deplacement de la balle sur un pas de temps dt
    #... a implementer...

def stop(ball):
    ball.speed=(0,0)

#tests
if __name__=="__main__":
    #verification par comparaison visuelle
    my_ball=create(2)
    setSpeed(my_ball,2,4)
    print get_position(my_ball)
    move(my_ball, 10)
    print get_position(my_ball)

3.8.2. Règles de codage

1. Module: En dehors du programme principal Main.py (et sauf cas très particuliers), chacun des modules que vous concevrez devra correspondre à un type abstrait de données. Le module portera le nom du type. On fait toujours commencer le nom d’un type par une lettre majuscule, cela permet de différencier les variables des types. Le nom du module commence donc par une majuscule.

2. Constructeur: Au début d’un module on trouve le (ou les) constructeur(s) de la donnée. Un constructeur est une fonction qui capable de fabriquer la donnée.

#AbstractType.py
class AbstractType: pass


#constructeur

def create(parametres):

    #creation
    data=AbstractType()

    #initialisation en fonction des paramètres
    ...

    #retour de la donnee
    return data

A l’extérieur du module, on pourra appeler le constructeur de la manière suivante :

import AbstractType

d= AbstractType.create(...)

On s’obligera à toujours utiliser un constructeur et ne jamais créer soit même la donnée.

3. Accesseurs & Mutateurs: Ce sont des fonctions très simples qui permettent d’accéder au contenu des données. A l’occasion de ce cours, elle doivent être écrites de manière systématique pour chaque information définie par le type. Ces fonctions fournissent un outil de débogage très important, dès lors qu’on se force à les utiliser systématiquement pour manipuler les données.

#AbstractType.py

#accesseurs/mutateurs

def get_x(data):

    #recuperation de x dans data
    x=...

    return x

A l’extérieur du module, on appellera l’accesseur et le mutateur :

import AbstractType

d= AbstractType.create(...)

#reinitialisation de la valeur avec le mutateur
AbstractType.setX(d,'12')

#recuperation de la valeur avec accesseur
x=AbstractType.getX(d)

4. Opérations: On regroupe dans le module toutes les fonctions qui manipulent le type de données correspondant. Le premier paramètre d’une opération est en général une donnée du type correspondant. La difficulté est de penser les fonctions pour qu’elles ne manipulent qu’un type à la fois. Il est souvent utile de consulter le graphe de dépendance des modules pour concevoir correctement les fonctions. Parfois il faut décomposer une fonction à travers les modules pour obtenir un résultat pertinent. Ce point sera abordé dans la partie conception.

#AbstractType.py

#operations

def operation(data):

    #action a realiser sur la donnee
    data...

    #renvoie eventuel d une valeur
    return ...

A l’extérieur du module, on appellera la fonction :

import AbstractType

d= AbstractType.create(...)

#realisation d une operation:
AbstractType.operation(d)

5. Respect de la barrière d’abstraction: Respecter la barrière d’abstraction, c’est s’obliger à toujours manipuler une donnée avec des opérations fournies par le module correspondant. En dehors du code du module, il ne faut jamais modifier ou lire directement une donnée :

import Ball

b= Ball.create(5)

#ce qu il ne faut pas ecrire
print('radius=', b.radius)

#ce qu il faut ecrire
print 'radius=', Ball.getRadius(b)

Même si cela vous paraît fastidieux, il vous est fortement conseillé de respecter la barrière d’abstraction dès le début du codage. Cette règle est un garde-fou qui empêche de commettre des erreurs de conception. L’expérience montre qu’à chaque fois qu’un projet n’a pas respecté la règle, il n’a pu aboutir que dans la « douleur ». Si on se rappelle qu’un développeur passe la majeur partie de son temps à déboguer, le temps perdu à mieux coder n’est pas perdu…

3.8.3. Exercices

Player.py

Énoncé

• Soit le type suivant

Type : Player = struct
    position : int
    name : str
    items : list d'Item

• Une opération move incrémente la position du joueur de 1

• Une opération add_item ajout un Item dans la liste d’items.

• Le type Item est implémenté par module Item.py

Écrire le module Player.py

Solution

#Player.py
class Player: pass

def create(name="noname",position=0):
    p=Player()
    p.name=name
    p.position=position
    p.items=[]
    return p

def get_name(p):
    return p.name
def get_position(p):
    return p.position
def get_items(p):
    return p.items
#on peut aussi ajouter cet accesseur
def get_item(p,i):
    if i >0 and i<len(p.items):
        return p.items[i]
    else return None

def set_name(p,name):
    p.name=name
def set_position(p,position):
    p.position=position
def set_items(p,items):
    p.items=items

def move(p):
    p.position=p.position+1

def add_item(p,item):
    p.items.append(item)

if __name__=='__main__':
  '''ici les tests'''

structurer un programme déjà écrit

Énoncé

Il est préférable de réaliser cet exercice en dehors de l’ENIBOOK.

Solution

#main.py
import Cities

cities=None

#ne pas confondre cities et Cities, respectivement la reference vers la donnee et le module qui decrit le type abstrait.


def init():
	global cities
	#graphe
	my_cities=Cities.create()
	Cities.add_city(cities,'Brest',7,141000)
	Cities.add_city(cities,'Chateaulin',1,5000)
	Cities.add_city(cities,'Quimper',5,90000)
	Cities.add_city(cities,'Landivisiau',1,10000)
	Cities.add_city(cities,'Landerneau',0,15000)

	Cities.add_road(cities,'Brest','Chateaulin',46)
	Cities.add_road(cities,'Brest','Landerneau',26)
	Cities.add_road(cities,'Chateaulin','Quimper',28)
	Cities.add_road(cities,'Chateaulin','Landerneau',36)
	Cities.add_road(cities,'Landivisiau','Landerneau',17)
	
def ask_city():
	global cities
	name=raw_input('Choisissez un nom de ville')
	Cities.show_city_info(cities,name)


def main():
	init()
	ask_city()

if __name__ == '__main__':
	main()
	

#cityInfo

class CityInfo: pass

def create(nom,nb_school,population):
	info=CityInfo()
	info.name=nom
	info.nb_school=nb_school
	info.population=population
	return info

def get_name(i):
	return i['name']

def set_name(i,name):
	i['name']=name
	return

def get_population(i):
	return i['population']

def set_population(i,population):
	i['population']=population
	return

def get_nb_school(i):
	return i['nb_school']

def set_nb_school(i,nb):
	i['nb_school']=nb
	return
	
def show(i):
	msg='La ville de '+i['name']+' a une popuation de '+str(i['population'])+' habitants.'
	print msg
	return
if __name__=='__main__':
	'''ajouter les tests unitaires ici'''

#cities.py

#on importe le module que Cities utilisera 
import CityInfo

def create():
	#ici, on decide de code le type abstarait au moyen d'un liste... pourquoi pas! 
	return []

def add_city(cities,nom,nb_school,population):
	#on appelle le construction du module CityInfo
	info=CityInfo.create(nom,nb_school,population)
	c={'info':info,'roads':[]}
	cities.append(c)

def add_road(cities,name_1,name_2,km):
	#trouver les sommet
	
	s_1=find_city(cities,name_1)		
	s_2=find_city(cities,name_2)		
	
	#ajouter liens
	s_1['roads'].append((s_2,km))
	s_2['roads'].append((s_1,km))	
	
def get_distance(name_1,name_2):
	#return 0 if no way
	distance =0
	v_1=find_city(cities,name_1)		
	v_2=find_city(cities,name_2)		

	for link in v_1['roads']:
		v,km=link
		if v==v_2:
			distance=km
			break
			
	return distance

def find_city(cities,name):
	city=None
	for sommet in cities:
		#pour acceder au contenu de city en respectant la barrière d'abtraction, on utilise un accesseur
		if CityInfo.get_name(sommet['info'])==name:
			city=sommet		
	return city
	
def show_city_info(cities,name):
	for v in cities:
		if CityInfo.get_name(v['info'])==name:
			CityInfo.show(v['info'])
			return
	print 'Pas de ville de ce nom' 


if __name__=='__main__':
	'''ajouter les tests unitaires ici'''

Astuce

• Je sais décrire un TAD avec un papier et un crayon

• Je sais créer un module qui a le nom d’un TAD et contenant la définition du TAD avec le mot clé class

• Je sais coder de manière systématique les accesseurs et les mutateurs d’un TAD

• Je sais coder des fonctions manipulant un TAD dans le module du TAD

• Je sais ecrire un test dans le module d’un TAD

• J’ai moi même codé entièrement et testé un programme composé de 2 module qui met en oeuvre un TAD qui utilise un autre TAD.

• J’ai compris commment respecter la barrière d’abstraction