pile abstraite

Un des buts de la programmation objet est de réaliser des types de données abstraits.

Considérons le type abstrait de donnée pile:

transparent

Une pile

NOM
    pile[X] 
FONCTIONS
    vide : pile[X] -> Boolean
    nouvelle : -> pile[X]
    empiler : X x pile[X] -> pile[X]
    dépiler : pile[X] -> X x pile[X]
PRECONDITIONS
    dépiler(s: pile[X]) <=> (not vide(s))
    sommet(s: pile[X]) <=> (not vide(s))
AXIOMES
    forall x in X, s in pile[X]
            vide(nouvelle())
            not vide(empiler(x,s))
            dépiler(empiler(x,s))=(x,s)

Il faudrait vérifier que ce type abstrait définit bien ce que l'on entend par une pile. De même il faudrait vérifier que ces déclarations sont bien ``minimales'' et dans quelle mesure on pourrait en donner d'autres équivalentes.

Ici, le type pile est:

• indépendant de la représentation (abstrait),
• défini par son interface (fonctions) et les propriétés de cette interface (Axiomes) sous condition de réalisation des préconditions.

  Si les préconditions ne sont pas réalisées, pas d'engagement, mais exception.

• le type pile est générique: il doit être instancié pour un type particulier (le paramètre X).

Plusieurs implémentations sont possibles:

• avec des tableaux,
• avec des listes chaînées,
• ...

Quelques remarques:

• Une implémentation est correcte, si, les préconditions étant vérifiées, elle assure au moins les axiomes.
• Une implémentation (ou type concret) peut avoir d'autres fonctions (par exemple, permettant d'accéder efficacement aux éléments du tableau ou de la liste). Les propriétés de ces fonctions sont aussi spécifiées dans la définition du type.

  Elle peut avoir des états internes (par exemple l'état concret du tableau, l'état concret de la liste...).

  Mais l'utilisateur d'un type abstrait de données ne doit pas avoir accès aux fonctions autres que celles définies dans ce type abstrait et ne doit pas faire d'assertions au sujet de l'état concret (encapsulation).

Exercice : Comment faire en C pour qu'un type pile soit générique? Comment peut-on avoir des implémentations différentes de la pile en C sans avoir besoin de recompiler les programmes utilisant ces diverses implémentations?