1. Introduction

On dit qu'un TAD est "abstrait" car il est défini en termes mathématiques, indépendamment de toute implémentation dans un langage de programmation.

Dans le cycle de développement logiciel, on distingue ainsi trois phases (ou points de vue) :

Pour un TAD donné, il existe plusieurs implémentations possibles.

C'est cette contrainte qui nous guidera notamment dans la suite du cours lorsque nous introduirons les implémentations standards de quelques types abstraits courants.

2. Exemple de définition d'un TAD : le TAD Rectangle

Prenons l'exemple d'un cycle de développement logiciel qui aurait besoin de manipuler des rectangles.

Après analyse du problème, le concepteur définit le type abstrait "Rectangle" :

• le nom du TAD :
  Rectangle
• les opérations (... les choix faits dans cet exemple ont un but pédagogique et sont critiquables ... ) :
  • RectangleCreer(Réel centre_x, Réel centre_y, Réel longueur, Réel hauteur) -> Rectangle :
    Crée et retourne un rectangle centré sur (centre_x, centre_y) et de taille (longueur x hauteur) ;
  • RectangleTranslater (Rectangle r, Réel dx, Réel dy) -> Rectangle :
    Retourne le rectangle translaté de dx, dy ;
  • RectangleAireEtPerimetre (Rectangle r) -> Réel, Réel :
    Retourne l'aire et le périmètre du rectangle ;
  • RectangleEgal (Rectangle r1, Rectangle r2) -> Booléen :
    Retourne vrai si r1 et r2 représentent le même rectangle du plan ;
  • RectangleComparerAire (Rectangle r1, Rectangle r2) -> Entier :
    Compare les aires des rectangles. Retourne 0 si elles sont égales, un nombre strictement négatif si l'aire de r1 est inférieure à l'aire de r2 et un nombre strictement positif si l'aire de r1 est supérieure à l'aire de r2 ;
  • RectangleAfficher (Rectangle r) -> Néant :
    Affiche le rectangle dans une représentation compréhensible par l'utilisateur.
  • etc. (on pourrait considérer d'autres opérations sur les rectangles.)
• les préconditions :
  • RectangleCreer(Réel centre_x, Réel centre_y, Réel longueur, Réel hauteur) -> Rectangle :
    longueur et hauteur sont deux réels positifs ou nuls.
  • etc.

  L'ensemble des opérations que l'utilisateur pourra effectuer sur le TAD porte le nom d'API (pour Application Programming Interface), que l'on traduirait en français par "interface de programmation applicative", soit la manière dont le programmeur pourra programmer son application en utilisant les opérations du TAD.

  Il est courant de rappeler le nom du TAD dans une fonction afin de savoir à quel TAD elle se réfère. Imaginez que nous ajoutions le TAD Triangle. Comment savoir si l'opération Egal se rapporte à l'un ou l'autre ?

• les axiomes :
  • Aire(CreerRectangle(x, y, 0., 0.)) == 0.
  • RectangleEgal(RectangleCreer(x, y, l, L), RectangleCreer(x, y, l, L)) == vrai
  • etc.

Pour les axiomes, il faut assurer la complétude (tous les comportements sont modélisés) et la consistance (pas de contradiction entre les axiomes).

3. Notion de précondition en programmation et fonction assert(expressionBooleenne) en C

Les préconditions sont annoncées dans la documentation (le contrat) de la fonction. Par exemple, vous pourrez lire, en commentaire avant le prototype de la fonction dans le fichier .h, que si telle condition n'est pas vérifiée, alors le comportement de la fonction est imprédictible (unspecified).

Voici 2 exemples de préconditions sur 2 fonctions de la libc :

• double sqrt(double x); : PRECONDITION : "x > 0"
• void free(void *ptr);   : PRECONDITION : "ptr doit pointer une zone mémoire allouée dynamiquement."

Et un autre exemple, dans notre spécification du type abstrait Rectangle : on a décidé qu'il ne doit pas être possible de créer un rectangle de longueur ou hauteur négative. Ceci est spécifié par une précondition dans le contrat de l'opération l'opération RectangleCreer.

Par principe, une pré-condition est censée être garantie avant d’appeler la fonction, par le code appelant – et non pas dans la fonction elle même. Toutefois, en phase de développement (donc avant de livrer le programme), il est extrêmement utile de s’assurer que les préconditions d’une fonction sont bien vérifiée à chaque appel. Cela ralentit considérablement l’exécution du programme... mais permet de détecter au plus vite de nombreuses erreurs !

Pendant le développement, on pourrait écrire au début de chaque fonction une série de conditionnelles (if) qui chacune vérifie une pré-condition et qui affiche un message explicatif (par exemple « appel de la fonction invalide : pré-condition truc non vérifiée ») puis arrête brutalement le programme si elle n’est pas vérifiée en appelant exit(1).

Mais, idéalement, il faudrait que les préconditions soient vérifiées par la fonction pendant la phase de développement du programme. Puis, une fois que tout a été testé et que le programme est livré au client, on voudrait pour gagner du temps d'exécution qu'elles ne soient plus vérifiées par la fonction.

En C, c'est exactement le mécanisme d'assertion assert(expressionBooleenne)

                   gcc -DNDEBUG monFichier.c
                 

Par exemple, voici comment vérifier la précondition au début de la fonction rectangle_create() avec assert() :

            // fichier rectangle.c
            ...
            #include <assert.h>
            ...

            rectangle_t rectangle_create(double x, double y, double width, double height) {
              rectangle_t r;

              // vérification des préconditions dans la fonction avec assert
              assert(width >=0 &&  height >= 0) ;

              ...
            }
          

Une fiche plus détaillée sur les contrats de fonction et sur assert() est disponible sur le site du cours.

4. Exemple d'implémentation d'un TAD : une structure de données Rectangle

Parfois, dans le fichier source montad.c, il est utile d'insérer des fonctions supplémentaires qui facilitent l'écriture des fonctions de l'API. Ces fonctions ne seront utilisées que dans montad.c.

On distingue alors :

• les fonctions qui sont utiles et visibles de l'utilisateur. Elles définissent l'API du module. Elles sont dites "publiques". Leur prototype est donné dans montad.h. Par défaut, une fonction en C est publique ;
• celles qui ne sont utiles qu'au programmeur du TAD et doivent être invisibles de l'utilisateur. Elles sont dites "privées". Elles ne font pas partie de l'API du module. Leur prototype n'est pas donné dans montad.h. Enfin, en C, elles sont déclarées avec le mot-clef static.

4.1 API de la structure de données Rectangle

Pour le fichier d'en-tête rectangle.h de notre TAD "Rectangle", la définition du type C est simplissime : le type rectangle_t sera un type structuré à 4 champs double, pour la position (x, y) et la taille (longueur, hauteur).

La définition des prototypes des fonctions de l'API est également simple.

Seul le prototype traduisant l'opération RectangleAireEtPerimetre (Rectangle r) -> Réel, Réel nécessite un peu de réflexion.

En effet :

• Cette opération retourne 2 valeurs. Or, en C, une fonction ne peut retourner qu'une seule valeur avec return !
• Il est donc nécessaire ici d'avoir recours au passage par adresse pour au moins l'une des deux valeurs à retourner.
• Comme il n'y a pas de raison de privilégier l'aire ou le périmètre, on choisira plutôt dans ce cas d'avoir recours à deux paramètres pointeurs, pour l'aire et le périmètre — et la fonction ne retournera rien au sens de return.

Après cette intense réflexion, on peut écrire le contenu du fichier d'en-tête montad.h.

Ci-dessous, repérez :

• La garde (#ifndef _RECTANGLE_H_, #define _RECTANGLE_H_ ... #endif _RECTANGLE_H_), comme dans tout fichier d'en-tête .h ;
• Les conventions de nommage et l'usage de l'anglais ;
• Les commentaires, qui précisent le contrat de chaque fonction de l'API ;
• Dans ces commentaires, la mention des préconditions (e.g. fonction rectangle_create()) ;
• L'usage de pointeurs pour la fonction rectangle_get_area_and_perimeter().

      // fichier rectangle.h pour le TAD Rectangle
      #ifndef _RECTANGLE_H_
      #define _RECTANGLE_H_

      // 1. declaration du type rectangle_t
      typedef struct {
        double x;
        double y;
        double width;
        double height;
      } rectangle_t;

      // 2. prototype des fonctions de l'API du TAD Rectangle

      // Retourne un rectangle de centre (x, y) et de taille (width x height)
      // PRECONDITION : width > 0
      // PRECONDITION : height > 0
      rectangle_t rectangle_create(double x, double y, double width, double height);

      // Retourne le rectangle r translaté de (dx, dy)
      rectangle_t rectangle_translated(rectangle_t r, double dx, double dy);

      // Stocke l'aire et le périmètre de r
      // repectivement dans *parea et *pperimeter
      // PRECONDITION : parea et pperimeter pointent bien 2 variables de type double
      void rectangle_get_area_and_perimeter(rectangle_t r, double *parea, double *pperimeter);

      // Retourne 1 si r1 et r2 ont même position et taille, 0 sinon
      int rectangle_equal(rectangle_t r1, rectangle_t r2);

      // Retourne :
      //    0 si r1 et r2 ont la même aire
      //    un nombre >0 si r1 est plus grand que r2 (au sens de l'aire)
      //    un nombre <0 si r1 est plus petit que r2 (au sens de l'aire)
      int rectangle_compare_areas(rectangle_t r1, rectangle_t r2);

      // Affiche r dans le Terminal
      void rectangle_print(rectangle_t r);

      #endif
      

4.2 Fichier source de la structure de données Rectangle

Pour les curieux, on donne ci-dessous in extenso le code du fichier rectangle.c.

code complet de rectangle.c

    // fichier rectangle.c
    #include <stdlib.h>
    #include <stdio.h>
    #include <math.h>

    // Rq : on inclut toujours le fichier d'en-tete du module
    #include "rectangle.h"

    // PROTOTYPE DES FONCTIONS PRIVEES
    static double rectangle_area_private(rectangle_t r);
    static double rectangle_perimeter_private(rectangle_t r);


    rectangle_t rectangle_create(double x, double y, double width, double height) {
      rectangle_t r;
      // gestion des préconditions de la fonction avec assert
      assert(width >=0 &&  height >= 0) ;

      r.x = x;
      r.y = y;
      r.width = width;
      r.height = height;
      return r;
    }

    rectangle_t rectangle_translate(rectangle_t r, double dx, double dy) {
      rectangle result = r;
      result.x += dx;
      result.y += dy;
      return result;
    }

    void rectangle_get_area_and_perimeter(rectangle_t r, double *parea, double *pperimeter) {
      *parea      = rectangle_area_private(r);
      *pperimeter = rectangle_perimeter_private(r);
    }

    int rectangle_equal(rectangle_t r1, rectangle_t r2) {
      return r1.x == r2.x
              && r1.y == r2.y
              && r1.width == r2.width
              && r1.height == r2.height;
    }

    int rectangle_compare_areas(rectangle_t r1, rectangle_t r2) {
      double area1 = rectangle_area_private(r1);
      double area2 = rectangle_area_private(r2);
      if(area1 == area2) {
        return 0;
      }
      if(area1 > area2){
        return 1;
      }
      return -1;
    }


    void rectangle_print(rectangle_t r) {
      printf("Rectangle (x=%lf, y=%lf) (l=%lf ; w=%lf)\n", r.x, r.y, r.width, r.length);
    }

    ////////////////////////////////////////
    // code des fonctions privées du module
    ////////////////////////////////////////
    static double rectangle_area_private(rectangle_t r) {
      return r.width * r.height;
    }

    static double rectangle_perimeter_private(rectangle_t r) {
      // rq : le module assure que width et height sont toujours > 0
      return 2. * (r.width + r.height) ;
    }

    

Mais ce code n'est pas très intéressant... Pour les plus pressés d'entre vous, voici les quelques extraits qui appellent des commentaires.

• Le début du fichier rectangle.c :

  Dans notre exemple, pour faciliter l'écriture des fonctions de l'API, on a jugé utile de définir ainsi 2 fonctions utilitaires privées, qui ne font pas partie de l'API.

  Notez qu'on liste les prototypes de ces fonctions utilitaires privées au début du fichier source, et notez que ces fonctions sont déclarées avec le qualifieur static.

  
        // fichier rectangle.c
        #include <stdlib.h>
        #include <stdio.h>
        #include <math.h>
  
        // Rq : on inclut toujours le fichier d'en-tete du module
        #include "rectangle.h"
  
        // PROTOTYPE DES FONCTIONS PRIVEES
        static double rectangle_area_private(rectangle_t r);
        static double rectangle_perimeter_private(rectangle_t r);
  
        // ... le code de ces fonctions sera donné plus loin dans ce fichier ...
  
        ...
        

• Exemple de gestion de précondition :

  Si une précondition n'est pas respectée, la fonction "a le droit de faire n'importe quoi".

  On pourrait par exemple tester la précondition au début de la fonction et, si elle n'est pas vérifiée, afficher un message d'erreur (dans le flux d'erreur standard stderr) puis quitter violemment le programme avec exit(1);

  Beaucoup mieux : vérifier la précondition au début de la fonction avec assert(...);

  Voici un exemple :

  
        // fichier rectangle.c
        #include <assert.h>
        ...
  
        rectangle_t rectangle_create(double x, double y, double width, double height) {
          // vérification des préconditions de la fonction avec assert
          assert(width >=0 &&  height >= 0) ;
          .... ici, la suite du code de la fonction ...
        }
  
        ...
  
        

• Exemples d'usage des fonctions privées :

  
      // fichier rectangle.c
  
      ...
  
      void rectangle_get_area_and_perimeter(rectangle_t r, double *parea, double *pperimeter) {
        *parea      = rectangle_area_private(r);
        *pperimeter = rectangle_perimeter_private(r);
      }
  
      int rectangle_compare_areas(rectangle_t r1, rectangle_t r2) {
        double area1 = rectangle_area_private(r1);
        double area2 = rectangle_area_private(r2);
        if(area1 == area2) {
          return 0;
        }
        if(area1 > area2){
          return 1;
        }
        return -1;
      }
  
      ...
      

  Remarquez que :

  • Le comparateur rectangle_compare_areas() retourne bien un nombre nul, négatif ou positif, suivant les valeurs des aires ;
  • Dans la fonction rectangle_get_area_and_perimeter(), il n'a pas été nécessaire cette fois-ci de vérifier explicitement la précondition "les pointeurs pointent bien 2 variables de type double". En effet, le compilateur émettra un message d'erreur si l'on passe des adresses d'entiers, et si jamais ils pointent n'importe où, la fonction fera d'elle-même "n'importe quoi" — en l'occurrence très probablement une erreur de segmentation lors de l'exécution.

5. TAD conteneurs : stocker et manipuler plusieurs éléments

Notre exemple "TAD Rectangle" est fort simple (simpliste, même). Au-delà de cet exemple introductif, en fait :

La notion de type abstrait prend une grande importance lorsqu'il s'agit de stocker et manipuler plusieurs éléments de même type.

Pour faire cela, vous ne connaissez pour le moment que les tableaux en C. Ils s'avèrent rapidement insuffisants. On a besoin, en programmation, de nombreuses autres manières d'organiser et manipuler plusieurs éléments.

L'histoire de l'Informatique a donc conduit à définir formellement plusieurs TAD permettant de stocker et manipuler plusieurs éléments.

On appelle parfois ces TAD les "TAD conteneurs" (pour "conteneurs d'éléments").

Les principaux TAD conteneurs pour stocker et manipuler plusieurs éléments sont :

• les tableaux (déjà vus dans ce cours, bien sûr !)
• les tableaux redimensionnables
• les listes (vues dans ce cours)
• les piles (LIFO) (vues dans ce cours)
• les files (FIFO) (vues dans ce cours)
• les tables d’association ou dictionnaires (vues dans ce cours)
• les ensembles, au sens de Cantor.
• les files de priorité
• les arbres et leurs variantes (abordés dans ce cours)
• les graphes et leurs variantes (abordés dans ce cours)
• (...)

Le choix d'un TAD conteneur, puis l'implémentation de ce TAD au moyen d'un langage de programmation, ont un impact majeur sur ce qu'on pourra faire avec le "paquet d'éléments" et sur l'efficacité du programme.

Il est donc important de connaître ces principaux TAD et leur implémentation-type.

Dans la suite de ce cours, les TAD décrits seront les principaux TAD conteneurs permettant de stocker et manipuler "plusieurs éléments". Leur conception est acceptée de longue date : vous aurez donc uniquement le rôle de programmeur et d'utilisateur.

Néanmoins, vous vous rendrez vite compte à quel point vous aurez intérêt à programmer toutes vos structures de données comme des TAD, conteneurs ou pas : en procédant ainsi que nous avons vu, vous produirez naturellement et sans même vous en rendre compte un code à la fois pérenne, robuste et évolutif. Pour le dire autrement : vous appliquerez sans le savoir quelques préceptes fondamentaux du génie logiciel, l'ensemble des techniques permettant de garantir qu'un code sera à la fois efficace et aisé à maintenir et à utiliser — et dont le coût de développement sera donc davantage maîtrisable.