Considérons une application informatique de géométrie planaire. Cette application sera notamment appelée à résoudre des problèmes relatifs à des droites, qui devront donc être représentées en machine. On pourra par exemple opter pour la structure ci-dessous.
from algo import *
class Tdroite(Struct):
# coordonnées d'un point par lequel passe la droite
x = float
y = float
# angle que fait la droite avec l'axe des x
angle = float # ∈ [0..π[
On fournira alors une « boîte à outils » de fonctions et procédures pour la manipulation de droites représentées par cette structure :
Cette boîte à outils pourra alors être utilisée par les programmeurs de l’application pour résoudre des problèmes de géométrie plus complexes.
On a vu au premier semestre que le programmeur de l’application n’a besoin de connaître que les spécifications des algorithmes fournis pas la boîte à outils, par opposition à leur implémentation qui peut être changée, par exemple pour en améliorer la lisibilité et les performances. Tant que ces changements d’implémentation respectent la spécification, ils ne doivent en principe pas avoir d’impact sur l’application elle même.
L’approche « type abstraits » qui nous intéresse ici repose sur l’idée que le type structuré Tdroite doit être considéré comme faisant lui aussi partie de l’implémentation, et qu’à ce titre, le programmeur de l’application doit l’utiliser comme une « boîte noire » opaque (similaire aux types élémentaires), sans s’autoriser à accéder à ses champs. Nous allons illustrer par deux exemples les problèmes qui peuvent se poser lorsqu’il ne se plie pas à cette règle.
Sans rentrer dans le détail de l’implémentation de la boîte à outils (laissé en exercice), on peut voir que pour construire un objet Tdroite à partir des coordonnées cartésiennes de deux points distincts, on aura besoin de faire appel à la fonction atan pour déterminer le champ angle. Cette fonction, significativement plus coûteuse en temps de calcul que des opérations arithmétiques, sera également nécessaire pour déterminer si deux droites sont confondues. Enfin, l’implémentation du troisième algorithme n’est pas non plus triviale avec une telle représentation des droites.
Le programmeur de la boîte à outil peut donc décider de modifier le type Tdroite, par exemple comme ci-dessous.
class Tdroite(Struct):
# la droite est le lieux des points (x,y)
# tels que ax + by + c = 0, avec a ≠ 0 ou b ≠ 0
a = float
b = float
c = float
Les algorithmes de la boîte à outils peuvent être ré-écrits avec cette structure : leur implémentation sera à la fois plus lisible et plus efficace [1]. En revanche, il est intéressant de noter que leur spécification reste inchangée. On peut donc attendre que cette modification n’aie pas d’impact sur le code de l’application.
En pratique, cela ne sera vrai que si le programmeur de l’application s’est contenté de manipuler les Tdroite avec les fonctions de la boîte à outils. Si au contraire, son code accédait directement aux attributs x, y et angle de l’ancienne structure, il est évident qu’il ne fonctionnera plus et devra être modifié pour s’adapter aux modifications de la boîte à outils. On est en contradiction avec le principe de modularité.
| [1] | Ceci est vrai pour les trois algorithmes données en exemple, mais ne le sera pas pour n’importe quel algorithme. Notamment, un algorithme calculant l’angle entre deux droites séquentes serait plus efficace avec la première structure. La structure la plus appropriée dépend donc du type d’opérations auxquelles elle servira. |
Imaginons que le programmeur de l’application ait besoin d’appliquer une rotation d’angle θ à une Tdroite. Si la boîte à outil ne propose pas d’algorithme pour faire cela (et parfois, même si elle le propose), il peut être tenté d’ajouter simplement θ au champ angle. Or ceci est dangereux, car le champ angle peut alors sortir de l’intervalle [0 .. π[ auquel il est censé appartenir. Ce problème est plus subtil que le précédent, car il n’entraînera pas un dysfonctionnement systématique de l’application : selon la valeur de θ, la contrainte pourra rester satisfaite; et lorsqu’elle ne le sera pas, le problème pourra intervenir longtemps après la modification du champ angle.
Par ailleurs, même si le programmeur de l’application est consciencieux et fait en sorte de maintenir l’intégrité de la structure [2], le programmeur de la boîte à outils pourrait décider de modifier ultérieurement ces contraintes pour des raisons d’implémentation. Par exemple, il pourrait choisir de limiter la valeur du champ angle à l’intervalle ]-π/2 .. π/2]. Là encore, ce changement ne causerait pas un problème systématiquement, rendant sa correction plus délicate.
| [2] | ce qui suppose que ses contraintes d’intégrité sont correctement documentées par le programmeur de la boîte à outils, ce qui n’est hélas pas toujours le cas. |
La définition d’un type abstrait de données consiste à identifier les opérations nécessaires pour manipuler ce type. Ces opérations sont spécifiées comme des procédures et fonctions dont un (ou plusieurs) paramètre a pour type le type abstrait. L’ensemble de ces spécifications d’opération constitue la spécification du type abstrait. Seule cette spécification est nécessaire pour utiliser le type abstrait.
Le type abstrait est ensuite implémenté, d’une part en le décrivant comme un type structuré possédant les champs nécessaires, et d’autre part en implémentant les procédures et fonctions en conséquence.
L’utilisation du type abstrait devra se faire exclusivement en ayant recours aux opérations spécifiées, et sans jamais utiliser directement les champs de la structure. Cela suppose que, parmi les opérations disponibles pour le type abstrait, il en existe au moins une permettant de construire une valeur du type abstrait (c’est le cas de la première opération proposée dans l’exemple de la section précédente).
On a vu dans les exemples de la section précédente que la définition d’un type structuré implémentant un type abstrait peut comporter, sous forme de commentaires, un certain nombre de contraintes d’intégrités. Ces contraintes peuvent être nécessaire pour garantir que la structure ait un sens ou simplement constituer une forme canonique. Dans les exemples de la section précédente, la première définition de Tdroite impose une forme canonique : toute droite avec un angle négatif ou supérieur à π est équivalente à une droite avec un angle dans l’intervalle [0 .. π[. En revanche, dans la seconde définition de Tdroite, la contrainte a ≠ 0 ou b ≠ 0 est indispensable pour que la structure représente bien une droite (l’équation c = 0 ne représente pas une droite).
Ces contraintes sont nommées invariants de structure, ce qui signifie qu’elles doivent toujours être satisfaites, même lorsque les valeurs des champs de la structure évoluent. En fait, au sein de l’implémentation du type abstrait, il peut arriver que ces contraintes soient temporairement violées, mais il est impératif qu’elles soient vérifiées à l’entrée et à la sortie de toutes les opérations.
Ces invariants peuvent donc être considérés comme des pré-conditions / post-conditions implicites sur toutes opérations du type abstrait. Cependant, ils doivent demeurer implicites car ils relèvent de l’implémentation du type abstrait, tandis que les pré-conditions et post-conditions font partie de la spécification.
L’approche « type abstrait » n’implique pas que tout type structuré soit nécessairement considéré comme un type abstrait. Il existe des situations où il sera justifié de définir un type structuré « ouvert ».
Certains langages de programmation fournissent des constructions syntaxiques spécifiques pour définir les types abstraits, la plus courante étant la notion de classe, qui sera traitée dans un chapitre ultérieur. Le principal avantage est que, le compilateur ou l’interpréteur étant informés que la structure est un type abstrait, il peuvent effectuer des contrôles approprié, par exemple pour vérifier que les champs ne sont pas utilisés en dehors de l’implémentation du type abstrait lui même.
Cependant, il n’est pas nécessaire de disposer d’un langage spécifique pour pouvoir appliquer l’approche « type abstrait ». À défaut de constructions syntaxiques dédiées, on peut appliquer un certain nombre de conventions d’écriture. C’est l’approche que nous utiliseront dans un premier temps avec le langage algorithmique : nous nous contenterons de séparer par des commentaires la partie spécification de la partie implémentation, en déclarant bien sûr le type structuré dans la partie implémentation.
Indice
En C, où la spécification est dans un fichier .h et l’implémentation dans le fichier .c correspondant, il est possible de définir un type abstrait en ne déclarant le corps d’un type structuré que dans le fichier .c. Par exemple :
/*-- droite.h ----------------*/
typedef struct droite Tdroite;
/* spécifications des opérations... */
/*-- droite.c ----------------*/
struct droite { double x, y, angle; };
/* x,y : coordonnées d'un point de la droite
angle : angle de la droite avec l'angle des x,
dans l'intervalle [0 .. pi[
*/
/* implémentation des opérations... */
Ainsi, pour les programmes n’incluant que le fichier .h, le type Tdroite est effectivement opaque : sa structure interne n’est pas connue, et donc pas utilisable (ce qui implique en revanche de n’utiliser que des passages par adresse ou par référence pour les paramètres de ce type).
L’exemple du type abstrait Tdroite proposé plus haut est un peu trop complexe pour être traité complètement ici : le nombre d’opérations envisageable sur des droites est trop important. On traitera donc ici un cas plus simple : celui des vecteurs à deux dimensions. La suite de ce cours présentera un certain nombre d’exemples de type abstraits, notamment dans les chapitres dont l’intitulé commence par « Structure ».
Par définition, un espace vectoriel est muni de deux opérations : l’addition de deux vecteurs, qui donne un troisième vecteur, et la multiplication d’un vecteur par un réel, qui donne un nouveau vecteur.
Il nous faut également définir des opérations produisant des vecteurs. Étant donné que tout vecteur du plan peut être construit par addition et multiplication de deux vecteurs formant une base, on propose une unique opération de construction fournissant les deux vecteurs constituant cette base.
Enfin, il faut être capable de comparer les vecteurs entre eux. On fournit donc une fonction permettant de tester si deux Tvecteur sont égaux. Il faut noter que l’opérateur = n’est pas nécessairement approprié pour cela : il compare uniquement l’égalité entre les champs de la structure sous-jacente. Or on a vu dans les exemples précédent que, selon les choix d’implémentation, deux structures avec des valeurs de champs différentes peuvent représenter le même objet. Étant donné que la spécification ne doit faire aucune hypothèse sur l’implémentation, nous ne pouvons pas supposer que la représentation interne des Tvecteur sera univoque, et nous ne pouvons donc pas faire confiance à l’opérateur = pour comparer des valeurs d’un types abstraits.
Deux autres tests sont utilises à propos des vecteurs : celui permettant de savoir si un vecteur est le vecteur nul, et celui permettant de savoir si deux vecteurs sont colinéaires (i.e. si l’un peut être obtenu simplement en multipliant l’autre par un réel).
On obtient donc la spécification suivante :
######## Tvecteur: spécification ########
def base():
""""
:sortie v1: Tvecteur
:sortie v2: Tvecteur
:post-cond: v1 et v2 constituent une base de l'espace vectoriel :
ils sont non nuls et non colinéaires
""""
def egaux(v1, v2):
"""
:entrée v1: Tvecteur
:entrée v2: Tvecteur
:sortie eq: bool
:post-cond: eq est True si et seulement si v1 et v2 sont deux vecteurs
égaux
"""
def nul(v):
"""
:entrée v: Tvecteur
:sortie n: bool
:post-cond: n est True si et seulement si v est le vecteur nul
"""
def colineaires(v1, v2):
"""
:entrée v1: Tvecteur
:entrée v2: Tvecteur
:sortie co: bool
:post-cond: co est True si et seulement si v1 et v2 sont deux vecteurs
colinéaires
"""
def add(v1, v2):
"""
:entrée v1: Tvecteur
:entrée v2: Tvecteur
:sortie va: Tvecteur
:post-cond: va est le vecteur résultant de la somme de v1 et v2
"""
def mult(k, v):
"""
:entrée k: float
:entrée v: Tvecteur
:sortie vm: Tvecteur
:post-cond: vm est le vecteur résultant du produit de v1 par k
"""
Remarquons tout d’abord que la spécification ci-dessus ne fait absolument pas mention des coordonnées des vecteurs. En effet, ces coordonnées ne sont pas une caractéristiques intrinsèques au vecteur, mais dépendent de la base dans laquelle on le considère.
Quoi qu’il en soit, au moment de représenter un vecteur en mémoire, nous allons avoir recours aux types élémentaires, en l’occurrence le type réel. Nous allons donc utiliser une base implicite, et représenter les vecteurs par leurs coordonnées dans cette base.
On obtient donc l’implémentation suivante :
######## Tvecteur : Implémentation ########
from algo import *
class Tvecteur(Struct):
# coordonnées dans la base implicite
x = float
y = float
def base():
v1 = Tvecteur(x=1, y=0)
v2 = Tvecteur(x=0, y=1)
return v1, v2
def egaux(v1, v2):
eq = (v1.x == v2.x and v1.y == v2.y)
return eq
def nul(v):
n = (v1.x == 0 and v2.x == 0)
return n
def colineaires(v1, v2):
co = (not nul(v1) and not nul(v2) and
(v1.x * v2.x - v2.y * v1.y ) == 0)
return co
def add(v1, v2):
va = Tvecteur(x=(v1.x + v2.x), y=(v1.y + v2.y))
return va
def mult(k, v):
vm = Tvecteur(x=(k*v.x), y=(k*v.y))
On notera que le choix a été fait, pour des raison évidentes de simplicité, de faire retourner par la fonction base la base implicite utilisée pour le codage (i.e. les vecteurs de coordonnées (1,0) et (0,1) respectivement). Ceci n’est absolument pas une obligation. En fait, l’implémentation reste correcte quelles que soit les valeurs affectées aux vecteurs v₁ et v₂ par cette fonction, tant qu’ils sont non nuls et non colinéaires.