“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 143 — #153
i
i
i
i
i
i
i
i
3.5 Les types de données abstraits
143
Voici une autre implémentation qui satisfait les lois :
fun {NewStack} stackEmpty end
fun {Push S E} stack(E S) end
fun {Pop S E} case S of stack(X S1) then E=X S1 end end
fun {IsEmpty S} S==stackEmpty end
Tout programme qui utilise une pile fonctionnera avec les deux. C’est une conséquence
du fait que la pile est abstraite.
3.5.1 Les types abstraits sécurisés
Un grand problème des deux implémentations ci-dessus est que la pile n’est pas
sécurisée. La représentation interne des valeurs est visible pour les utilisateurs du type.
Si les utilisateurs sont des programmeurs disciplinés, cela ne posera peut-être pas de
problème. Mais ce n’est pas toujours le cas. Un utilisateur peut être tenté d’inspecter
la représentation ou même de construire de nouvelles valeurs de la représentation.
Par exemple, un utilisateur du type pile peut utiliser Length pour voir combien
d’éléments il y a sur la pile, si la pile est implémentée comme une liste. La tentation
d’agir ainsi peut être très forte s’il n’y a pas d’autre manière de trouver la taille d’une
pile. Une autre tentation est de bricoler le contenu d’une pile. Comme toute liste est
aussi une valeur légale de pile, l’utilisateur peut construire de nouvelles valeurs de la
pile, par exemple, en ajoutant ou en enlevant des éléments.
Tout utilisateur peut ajouter de nouvelles opérations sur les piles n’importe où dans
le programme. L’implémentation de la pile est donc étalée sur tout le programme au
lieu d’être limitée dans une petite partie. C’est une situation désastreuse, pour deux
raisons :
– Le programme est bien plus difficile à maintenir. Par exemple, si nous voulions
améliorer l’efficacité d’un dictionnaire en remplaçant une implémentation basée
sur une liste par une implémentation basée sur un arbre, nous devrions parcourir
tout le programme pour trouver les parties qui dépendent de l’implémentation
basée sur une liste. Il y a aussi le problème du confinement de fautes : si le
programme a des bugs dans une partie, cela peut contaminer les ADT, ce qui
contamine encore d’autres parties du programme et ainsi de suite.
– Le programme est sensible aux ingérences malicieuses. C’est un problème plus
subtil qui a un rapport avec la sécurité. Cela n’arrive pas avec des programmes
écrits par des personnes qui se font confiance. Cela arrive plutôt avec des programmes ouverts. Un programme ouvert peut interagir avec d’autres programmes
qui ne sont pas connus lors de son développement mais seulement lors de son
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.5 Les types de données abstraits
143
Voici une autre implémentation qui satisfait les lois :
fun {NewStack} stackEmpty end
fun {Push S E} stack(E S) end
fun {Pop S E} case S of stack(X S1) then E=X S1 end end
fun {IsEmpty S} S==stackEmpty end
Tout programme qui utilise une pile fonctionnera avec les deux. C’est une conséquence
du fait que la pile est abstraite.
3.5.1 Les types abstraits sécurisés
Un grand problème des deux implémentations ci-dessus est que la pile n’est pas
sécurisée. La représentation interne des valeurs est visible pour les utilisateurs du type.
Si les utilisateurs sont des programmeurs disciplinés, cela ne posera peut-être pas de
problème. Mais ce n’est pas toujours le cas. Un utilisateur peut être tenté d’inspecter
la représentation ou même de construire de nouvelles valeurs de la représentation.
Par exemple, un utilisateur du type pile peut utiliser Length pour voir combien
d’éléments il y a sur la pile, si la pile est implémentée comme une liste. La tentation
d’agir ainsi peut être très forte s’il n’y a pas d’autre manière de trouver la taille d’une
pile. Une autre tentation est de bricoler le contenu d’une pile. Comme toute liste est
aussi une valeur légale de pile, l’utilisateur peut construire de nouvelles valeurs de la
pile, par exemple, en ajoutant ou en enlevant des éléments.
Tout utilisateur peut ajouter de nouvelles opérations sur les piles n’importe où dans
le programme. L’implémentation de la pile est donc étalée sur tout le programme au
lieu d’être limitée dans une petite partie. C’est une situation désastreuse, pour deux
raisons :
– Le programme est bien plus difficile à maintenir. Par exemple, si nous voulions
améliorer l’efficacité d’un dictionnaire en remplaçant une implémentation basée
sur une liste par une implémentation basée sur un arbre, nous devrions parcourir
tout le programme pour trouver les parties qui dépendent de l’implémentation
basée sur une liste. Il y a aussi le problème du confinement de fautes : si le
programme a des bugs dans une partie, cela peut contaminer les ADT, ce qui
contamine encore d’autres parties du programme et ainsi de suite.
– Le programme est sensible aux ingérences malicieuses. C’est un problème plus
subtil qui a un rapport avec la sécurité. Cela n’arrive pas avec des programmes
écrits par des personnes qui se font confiance. Cela arrive plutôt avec des programmes ouverts. Un programme ouvert peut interagir avec d’autres programmes
qui ne sont pas connus lors de son développement mais seulement lors de son
© Dunod – La photocopie non autorisée est un délit