Cours 1: Type abstrait.
Ce cours s'inspire fortement du livre Types de données et algorithmes
de Christine Froidevaux, Marie-Claude Gaudel et Michèle Soria, McGraw-Hill 1990.
Un type abstrait de donnée (ADT pour Abstract Data Type ) est la représentation
formelle d'un ensemble et des opérations (fonctions) définies sur ses éléments.
Pour illustrer cette définition, nous allons prendre l'exemple du type abstrait
Vecteur . Le langage que nous emploierons tout au long du cours
sera un dialecte inspiré de C. Ainsi, la description des types et des
algorithmes sera implémentable, les parties qui ne pourront être exprimées en
C l'étant sous forme de commentaires dans le programme.
Voici ci-dessous la signature du type abstrait Vecteur .
Vecteur creer_vecteur(unsigned int taille);
Vecteur ecrire_vecteur(Vecteur v, unsigned int i, Element e);
Element lire_vecteur(Vecteur v, unsigned int i);
unsigned int taille_vecteur(Vecteur v);
Les noms choisis, s'ils sont d'une grande aide concrète, ont le défaut de suggérer une sémantique au lieu de la formaliser. Par exemple, la signature suivante
est équivalente, mais ne suggère rien.
c: I -> V
e: V x I x E -> V
l: V x I -> E
t: V -> I
La sémantique des opérations peut être fixée par un ensemble de préconditions et d'axiomes.
Par exemple, voici les préconditions et les axiomes fixant la sémantique du type Vecteur (les axiomes sont donnés en commentaire, n'étant pas généralement
exprimables en C).
// v: Vecteur; e: Element; i, j: unsigned int;
// préconditions:
// creer_vecteur(i) est-défini-ssi i>=0
// lire_vecteur(v, i) est-défini-ssi 0<=i<taille_vecteur(v)
// ecrire_vecteur(v, i, e) est-défini-ssi 0<=i<taille_vecteur(v)
// axiomes:
// 0<=i<taille_vecteur(v) =>
// lire_vecteur(ecrire_vecteur(v,i,e),i) == e
// 0<=i<taille_vecteur(v) && 0<=j<=taille_vecteur(v) && i!=j =>
// lire_vecteur(ecrire_vecteur(v,i,e),j) == lire_vecteur(v,j)
// taille_vecteur(creer_vecteur(i)) == i
// 0<=i<taille_vecteur(v) =>
// taille_vecteur(ecrire_vecteur(v,i,e)) == taille_vecteur(v)
Les préconditions définissent les domaines de validité des opérations.
En supposant qu'à l'entrée d'une fonction ses préconditions soient
vraies, alors l'implémentation garantit qu'à la sortie les axiomes
seront toujours satisfaits.
Le premier axiome lie les opérations de lecture et d'écriture dans le vecteur.
Il précise que toute implémentation d'un type vecteur doit garantir qu'une
écriture suivie d'une lecture d'une même entrée du vecteur retourne l'élément écrit.
Le second axiome indique qu'une écriture en i ne modifie aucune
autre entrée j .
Le troisième axiome lie la création d'un vecteur de taille fixée à l'opération
d'observation de cette taille.
Le dernier axiome impose que la taille d'un vecteur ne soit pas altérée par
une écriture.
On pourra remarquer qu'à sa création, un vecteur n'est pas initialisé (la
sémantique ne l'impose pas). La lecture d'une entrée non initialisée retourne
un élément quelconque.
D'une façon générale, un ensemble d'axiomes doit être complet et
consistant . La complétude assure qu'on a suffisamment d'axiomes
pour décrire les propriétés souhaitées. La consistance assure qu'il n'y a pas
de contradiction dans les axiomes.
Une fois le type défini, on peut en donner des implémentations. Toutes ces
implémentations devront satisfaire l'ensemble des axiomes.
Par exemple, voici une implémentation possible du type Vecteur .
Remarquons qu'il n'est pas nécessaire d'inclure les tests de précondition.
La programmation par contrat prévoit que si les
préconditions sont respectées en entrant dans une fonction (le contrat
est respecté par l'appelant) alors la fonction effectue son calcul
(le contrat est respecté par l'appelé). C'est donc à l'appelant de
s'assurer qu'il respecte les préconditions.
En phase de mise au point de l'implémentation, on active la vérification
des préconditions. Ensuite, on la désactive en mettant les instructions
de test en commentaire.
// fichier vecteur.c
#include <stdio.h>
#include "vecteur.h"
typedef struct {unsigned int taille; Element *t;} St;
Vecteur creer_vecteur(unsigned int taille) {
St *s;
s = (St *) malloc(sizeof(St));
s->t = (Element *) malloc(sizeof(Element)*taille);
s->taille = taille;
return (Vecteur) s;
}
Vecteur ecrire_vecteur(Vecteur v, unsigned int i, Element e) {
// précondition: 0<=i<taille_vecteur(v)
if (i >= taille_vecteur(v)) {
fprintf(stderr, "ecrire_vecteur: i = %d >= taille = %d\n",
i, taille_vecteur(v));
exit(1);
}
((St *)v)->t[i] = e;
return v;
}
Element lire_vecteur(Vecteur v, unsigned int i) {
// précondition: 0<=i<taille_vecteur(v)
if (i >= taille_vecteur(v)) {
fprintf(stderr, "lire_vecteur: i = %d >= taille = %d\n",
i, taille_vecteur(v));
exit(1);
}
return (((St *)v)->t[i]);
}
unsigned int taille_vecteur(Vecteur v) {
return (((St *)v)->taille);
}
Un Vecteur est une structure regroupant un entier (pour la taille)
et un pointeur sur les éléments du vecteur.
La création du vecteur alloue la structure et un tableau des éléments.
L'adresse de la structure donne accès au vecteur.
Une écriture place l'élément dans le tableau, à l'entrée requise.
Une lecture accède à l'entrée de tableau désignée.
La taille est accessible.
Notons aussi que l'implémentation vecteur.c inclus la spécification
vecteur.h qui ressemble à celle donnée plus haut (à quelques détails
de C près).
On peut remarquer que le type Vecteur est paramétré par le type
d'éléments du vecteur. On dit que le type Vecteur est générique .
Le type Element est lui-même un type abstrait.
Voici la définition du type abstrait Element_entier .
Element creer_element();
Element ecrire_element(Element e, int i);
int lire_element(Element e);
// axiomes:
// e: Element; i: int;
// lire_element(ecrire_element(creer_element(), i)) == i
Voici son implémentation (il peut paraître un peu laborieux de représenter un
entier comme un objet pointé et alloué, mais l'implémentation donnée fixe
le cadre général d'une implémentation d'un type Element quelconque).
// fichier element_int.c
#include "element_int.h"
Element creer_element() {
int *p;
p = (int *) malloc(sizeof(int));
return (Element) p;
}
Element ecrire_element(Element e, int i) {
*((int *)e) = i;
return e;
}
int lire_element(Element e) {
return *((int *)e);
}
Pour implémenter un Vecteur d' Element_entier , il suffit
de lier le type Element utilisé dans la définition de Vecteur au type Element_entier . Cela n'est valide que si le type
Element_entier est une variété du type Element qui en
respecte la sémantique (les axiomes d' Element sont vérifiés pour
toutes les valeurs d' Element_entier ).
A titre d'exemple, voici un programme main_int.c employant des
vecteurs d'entiers.
Nous allons voir que les détails d'implémentations sont nombreux, le choix
du langage imposant un certain nombre de contraintes.
// fichier main_int.c
#include "element_int.h"
#include "vecteur.h"
#define TAILLE_V1 100
#define TAILLE_V2 10
main() {
Vecteur v1, v2;
unsigned int i;
Element e;
v1 = creer_vecteur(TAILLE_V1);
v2 = creer_vecteur(TAILLE_V2);
for (i=0; i<TAILLE_V2; i++) {
e = creer_element();
e = ecrire_element(e, i);
v2 = ecrire_vecteur(v2, i, e);
printf("%d ", lire_element(lire_vecteur(v2, i)));
}
printf("\n");
e = creer_element();
e = ecrire_element(e, 99);
v1 = ecrire_vecteur(v1, 99, e);
printf("%d", lire_element(lire_vecteur(v1, 99)));
printf("\n");
}
Les spécifications vecteur.h et element_int.h données ci-dessous sont tout ce que l'implémentation de main_int.c connait
des types Vecteur et Element_entier .
Voici element_int.h
// fichier element_int.h
#include "element_def.h"
Element creer_element();
Element ecrire_element(Element e, int i);
int lire_element(Element e);
// axiomes:
// e: Element; i: int;
// lire_element(ecrire_element(creer_element(), i)) == i
Voici vecteur.h
// fichier vecteur.h
#include "element_def.h"
#include "vecteur_def.h"
Vecteur creer_vecteur(unsigned int taille);
Vecteur ecrire_vecteur(Vecteur v, unsigned int i, Element e);
Element lire_vecteur(Vecteur v, unsigned int i);
unsigned int taille_vecteur(Vecteur v);
// v: Vecteur; e: Element; i, j: unsigned int
// préconditions:
// creer_vecteur(i) est-défini-ssi i>=0
// lire_vecteur(v, i) est-défini-ssi 0<=i<taille_vecteur(v)
// ecrire_vecteur(v, i, e) est-défini-ssi 0<=i<taille_vecteur(v)
// axiomes:
// 0<=i<=taille_vecteur(v) =>
// lire_vecteur(ecrire_vecteur(v,i,e),i) == e
// 0<=i<=taille_vecteur(v) && 0<=j<=taille_vecteur(v) && i!=j =>
// lire_vecteur(ecrire_vecteur(v,i,e),j) == lire_vecteur(v,j)
// taille_vecteur(creer_vecteur(i)) == i
// 0<=i<=taille_vecteur(v) =>
// taille_vecteur(ecrire_vecteur(v,i,e)) == taille_vecteur(v)
Les fichiers def.h ne servent qu'à pallier une insuffisance de C.
Il n'est pas possible d'employer un type avant de l'avoir complètement
défini. On réduit donc cette définition au strict minimum pour ne pas
anticiper l'implémentation. Le type est déclaré comme un pointeur sur void . (Notons que l'emploi d'un langage objet comme C++ nous éviterait de telles
contorsions).
Voici le fichier vecteur_def.h .
// fichier vecteur_def.h
typedef void *Vecteur;
Voici le fichier element_def.h . La constante ELEMENT_DEF permet
d'éviter d'inclure plusieurs fois le fichier.
// fichier element_def.h
#ifndef ELEMENT_DEF
typedef void *Element;
#endif
#define ELEMENT_DEF
Voici maintenant le fichier make_vecteur_int pour construire
l'exécutable main_int .
# fichier make_vecteur_int
main_int: main_int.o vecteur.o element_int.o
cc -o main_int main_int.o vecteur.o element_int.o
main_int.o: main_int.c vecteur.h vecteur_def.h element_def.h element_int.h
cc -c main_int.c
vecteur.o: vecteur.c vecteur.h vecteur_def.h element_def.h
cc -c vecteur.c
element_int.o: element_int.c element_int.h element_def.h
cc -c element_int.c
Pour adapter le type Vecteur à des éléments de type caractère, on doit fournir un type abstrait Element_caractere . Le voici.
// fichier element_char.h
#include "element_def.h"
Element creer_element();
Element ecrire_element(Element e, char c);
char lire_element(Element e);
Voici son implémentation.
// fichier element_char.c
#include "element_char.h"
Element creer_element() {
char *p;
p = (char *) malloc(sizeof(char));
return (Element) p;
}
Element ecrire_element(Element e, char c) {
*((char *)e) = c;
return e;
}
char lire_element(Element e) {
return *((char *)e);
}
Voici un programme main_char qui emploie des vecteurs de caractères.
// fichier main_char.c
#include "element_char.h"
#include "vecteur.h"
#define TAILLE_V1 100
#define TAILLE_V2 10
main() {
Vecteur v1, v2;
unsigned int i;
Element e;
v1 = creer_vecteur(TAILLE_V1);
v2 = creer_vecteur(TAILLE_V2);
for (i=0; i<TAILLE_V2; i++) {
e = creer_element();
e = ecrire_element(e, 'a'+i);
v2 = ecrire_vecteur(v2, i, e);
printf("%c", lire_element(lire_vecteur(v2, i)));
}
printf("\n");
e = creer_element();
e = ecrire_element(e, 'Z');
v1 = ecrire_vecteur(v1, 99, e);
printf("%c", lire_element(lire_vecteur(v1, 99)));
printf("\n");
}
Bien entendu, les fichiers element_def.h , vecteur.h ,
vecteur_def.h et vecteur.c restent inchangés.
Voici enfin le makefile pour construire main_char .
# fichier make_vecteur_char
main_char: main_char.o vecteur.o element_char.o
cc -o main_char main_char.o vecteur.o element_char.o
main_char.o: main_char.c vecteur.h vecteur_def.h element_def.h element_char.h
cc -c main_char.c
vecteur.o: vecteur.c vecteur.h vecteur_def.h element_def.h
cc -c vecteur.c
element_char.o: element_char.c element_char.h element_def.h
cc -c element_char.c