Worldlex Wiki Les types abstraits de données (TAD) sont un concept théorique utilisé en sémantique formelle et en vérification de programmes , et, de façon moins stricte, dans la conception et l'analyse d' algorithmes , de structures de données et de systèmes logiciels . La plupart des langages informatiques courants ne permettent pas de spécifier formellement les TAD. Cependant, diverses fonctionnalités des langages de programmation correspondent à certains aspects de l'implémentation des TAD et sont souvent confondues avec les TAD eux-mêmes ; il s'agit notamment des types abstraits , des types de données opaques , des protocoles et de la conception par contrat . Par exemple, en programmation modulaire , le module déclare des procédures qui correspondent aux opérations du TAD, souvent accompagnées de commentaires décrivant les contraintes. Cette stratégie d'encapsulation permet de modifier l'implémentation du module sans perturber les programmes clients , mais le module ne définit un TAD qu'informellement. La notion de types abstraits de données est liée au concept d' abstraction des données , important en programmation orientée objet et dans les méthodologies de conception par contrat en génie logiciel .
Barbara Liskov et Stephen N. Zilles en 1974, dans le cadre du développement du langage CLU . La spécification algébrique était un sujet de recherche important en informatique autour de 1980 et était alors presque synonyme de types de données abstraits. Elle repose sur des fondements mathématiques en algèbre universelle .Définition
Formellement, un type abstrait de données (TAD) est analogue à une structure algébrique en mathématiques , composée d'un domaine, d'un ensemble d'opérations et d'un ensemble de contraintes que ces opérations doivent satisfaire . Le domaine est souvent défini implicitement, par exemple comme l' objet libre sur l'ensemble des opérations du TAD. L' interface du TAD se réfère généralement uniquement au domaine et aux opérations, et éventuellement à certaines contraintes sur ces opérations, telles que les préconditions et les postconditions ; mais pas aux autres contraintes, comme les relations entre les opérations, qui relèvent du comportement. Il existe deux principaux styles de spécification formelle du comportement : la sémantique axiomatique et la sémantique opérationnelle .
Bien que n'appartenant pas à l'interface, les contraintes restent essentielles à la définition du type abstrait de données (TAD) ; par exemple, une pile et une file d'attente possèdent des interfaces d'ajout/suppression d'éléments similaires, mais ce sont les contraintes qui distinguent le comportement « dernier entré, premier sorti » du comportement « premier entré, premier sorti ». Les contraintes ne se limitent pas à des équations, des formules logiques .
sémantique axiomatique
Dans l'esprit de la programmation fonctionnelle , chaque état d'une structure de données abstraite est une entité ou une valeur distincte. Dans cette perspective, chaque opération est modélisée comme une fonction mathématique sans effet de bord . Les opérations modifiant la structure de données abstraite sont modélisées comme des fonctions prenant l'ancien état comme argument et renvoyant le nouvel état. L'ordre d'évaluation des opérations est sans importance ; une même opération appliquée aux mêmes arguments (y compris les mêmes états d'entrée) renverra toujours les mêmes résultats (et états de sortie). Les contraintes sont spécifiées sous forme d'axiomes ou de lois algébriques que les opérations doivent respecter.
Sémantique opérationnelle
Dans l'esprit de la programmation impérative , une structure de données abstraite est conçue comme une entité mutable ; autrement dit, le temps y est pris en compte et la structure peut se trouver dans différents états à différents moments. Les opérations modifient alors l'état de la structure au fil du temps ; par conséquent, l'ordre d'évaluation des opérations est important, et une même opération sur une même entité peut avoir des effets différents selon le moment où elle est exécutée. Ceci est analogue aux instructions d'un ordinateur ou aux commandes et procédures d'un langage impératif. Pour souligner cette conception, on parle généralement d' exécution ou d'application des opérations , plutôt que d'évaluation , à l'instar du style impératif souvent employé pour décrire les algorithmes abstraits. Les contraintes sont généralement spécifiées sous forme de texte.
Opérations auxiliaires
Les présentations des types abstraits de données (TAD) se limitent souvent aux opérations essentielles. Les présentations plus complètes précisent généralement les opérations auxiliaires sur les TAD, telles que :
fonction de hachage standard à partir de l'état de l'instance ;l'analyse des algorithmes , et améliorer leur lisibilité.
Aliasage
Dans le style opérationnel, la gestion de plusieurs instances et l'impact potentiel de la modification d'une instance sur les autres restent souvent flous. Une pratique courante pour définir les types abstraits de données (TAD) consiste à décrire les opérations comme si une seule instance existait lors de l'exécution de l'algorithme, et que toutes les opérations s'appliquaient à cette instance. Par exemple, une pile peut avoir des opérations d'aliasing , stipulant que le résultat de les enregistrements abstraits , les opérations sur un champ F d'une variable d'enregistrement R impliquent clairement F , qui est distinct de R , mais en fait également partie . Un axiome d'aliasing partiel stipulerait que la modification d'un champ d'une variable d'enregistrement n'affecte aucun autre enregistrement.
Analyse de la complexité
Certains auteurs incluent également la complexité algorithmique (« coût ») de chaque opération, tant en termes de temps (pour les calculs) que d'espace (pour la représentation des valeurs), afin de faciliter l' analyse des algorithmes . Par exemple, on peut spécifier que chaque opération prend le même temps et que chaque valeur occupe le même espace, quel que soit l'état du type abstrait de données (TAD), ou encore que le TAD possède une « taille » et que les opérations sont linéaires, quadratiques, etc., par rapport à cette taille. Alexander Stepanov , concepteur de la bibliothèque standard de modèles ( STL) C++ , a inclus des garanties de complexité dans la spécification de la STL, en argumentant :
L'introduction de la notion de types de données abstraits visait à permettre l'interchangeabilité des modules logiciels. Or, l'interchangeabilité n'est possible que si les modules présentent un comportement de complexité similaire. Remplacer un module par un autre aux fonctionnalités identiques, mais avec des compromis de complexité différents, risque de décevoir l'utilisateur. Même en lui expliquant en détail l'abstraction des données, il refuserait d'utiliser le code. Les assertions de complexité doivent donc impérativement figurer dans l'interface.
— Alexandre Stepanov
D'autres auteurs ne partagent pas cet avis, arguant qu'un type abstrait de données (TAD) de type pile est identique, qu'il soit implémenté avec une liste chaînée ou un tableau, malgré la différence de coûts d'opération, et qu'une spécification de TAD devrait être indépendante de l'implémentation.
Exemples
Variable abstraite
Une variable abstraite peut être considérée comme le type abstrait de données non trivial le plus simple, avec la sémantique d'une variable impérative. Elle admet deux opérations : `x`
Les contraintes sont alorssi et seulement si x = y et s = t .
Comme dans d'autres branches des mathématiques, on suppose généralement que les états de la pile sont uniquement ceux dont l'existence peut être prouvée à partir des axiomes en un nombre fini d'étapes. Dans ce cas, cela signifie que chaque pile est une séquence finie de valeurs, qui devient la pile vide (Λ) après un nombre fini d' arbre binaire , liste , sac et ensemble . Ces types de données peuvent être déclarés par trois opérations : `null` , qui crée un conteneur vide ; `single` , qui crée un conteneur à partir d’un seul élément ; et `append` , qui combine deux conteneurs du même type. La spécification complète des quatre types de données s’obtient alors en ajoutant successivement les règles suivantes à ces opérations :
null est le neutre gauche et droit pour un arbre ajouter(null,A) = A, ajouter(A,null) = A. Les listes ajoutent que l'ajout est associatif ajouter(ajouter(A,B),C) = ajouter(A,ajouter(B,C)). Les sacs ajoutent de la commutativité ajouter(B,A) = ajouter(A,B). Enfin, les ensembles sont également idempotents. ajouter(A,A) = A.
L'accès aux données peut être spécifié par correspondance de modèles sur les trois opérations, par exemple une fonction membre pour ces conteneurs :
membre(X,single(Y)) = eq(X,Y) membre(X,null) = faux membre(X,ajouter(A,B)) = ou(membre(X,A), membre(X,B))
Il convient de veiller à ce que la fonction soit invariante selon les règles applicables au type de données. Au sein de chaque classe d'équivalence impliquée par le sous-ensemble d'équations choisi, elle doit produire le même résultat pour tous ses membres.
ADT courants
Voici quelques ADT courants qui se sont révélés utiles dans une grande variété d'applications :
CollectionChacun de ces types abstraits de données (TAD) peut être défini de nombreuses manières et variantes, qui ne sont pas nécessairement équivalentes. Par exemple, une pile abstraite peut comporter ou non une type de données graphique abstrait (TDGA). Il a été introduit par Nadia Magnenat Thalmann et Daniel Thalmann . Les TDGA offrent les avantages des TDA tout en permettant de construire des objets graphiques de manière structurée.
Mise en œuvre
Les types de données abstraits (TDA) sont des entités théoriques utilisées, entre autres, pour simplifier la description des algorithmes abstraits, classifier et évaluer les structures de données, et décrire formellement les systèmes de types des langages de programmation. Cependant, un TDA peut être implémenté . Cela signifie que chaque instance ou état du TDA est représenté par un type de données ou une structure de données concrète , et que chaque opération abstraite possède une procédure ou une fonction correspondante . Ces procédures implémentées satisfont aux spécifications et axiomes du TDA, dans une certaine mesure. En pratique, l'implémentation n'est pas parfaite, et les utilisateurs doivent être conscients des problèmes liés aux limitations de la représentation et des procédures implémentées.
Par exemple, les entiers peuvent être spécifiés comme un type abstrait de données (TAD), défini par les valeurs distinctes 0 et 1, les opérations d'addition, de soustraction, de multiplication, de division (en tenant compte de la division par zéro), de comparaison, etc., et se comportant conformément aux axiomes mathématiques classiques de l'algèbre abstraite, tels que l'associativité et la commutativité. Cependant, en informatique, les entiers sont le plus souvent représentés par des nombres binaires de 32 ou 64 bits . Les utilisateurs doivent être conscients des problèmes liés à cette représentation, comme le dépassement de capacité arithmétique , où le TAD spécifie un résultat valide mais que la représentation ne peut pas contenir cette valeur. Néanmoins, pour de nombreuses applications, l'utilisateur peut ignorer ces limitations et utiliser l'implémentation comme s'il s'agissait du type abstrait de données.
Il existe généralement plusieurs façons d'implémenter un même type abstrait de données (TAD), en utilisant différentes structures de données concrètes. Ainsi, par exemple, une pile abstraite peut être implémentée par une liste chaînée ou par un tableau . Différentes implémentations du TAD, possédant les mêmes propriétés et fonctionnalités, peuvent être considérées comme sémantiquement équivalentes et utilisées de manière relativement interchangeable dans le code qui utilise le TAD. Ceci offre une forme d' abstraction ou d'encapsulation, et confère une grande flexibilité lors de l'utilisation d'objets TAD dans différentes situations. Par exemple, différentes implémentations du TAD peuvent être plus efficaces dans certaines situations ; il est possible d'utiliser chacune d'elles lorsque cela est préférable, améliorant ainsi l'efficacité globale. Le code qui utilise une implémentation de TAD conformément à son interface continuera de fonctionner même si l'implémentation du TAD est modifiée.
Afin d'empêcher les clients de dépendre de l'implémentation, un type abstrait de données (TAD) est souvent encapsulé sous forme de type de données opaque ou de descripteur dans un ou plusieurs modules , dont l'interface ne contient que la signature (nombre et types des paramètres et des résultats) des opérations. L'implémentation du module — à savoir le corps des procédures et la structure de données concrète utilisée — peut ainsi être masquée à la plupart des clients du module. Cela permet de modifier l'implémentation sans impacter les clients. Si l'implémentation est exposée, on parle alors de type de données transparent.
Les langages orientés objet modernes, tels que C++ et Java , prennent en charge une forme de types de données abstraits. Lorsqu'une classe est utilisée comme type, il s'agit d'un type abstrait qui fait référence à une représentation implicite. Dans ce modèle, un type abstrait de données (TAD) est généralement implémenté comme une classe , et chaque instance du TAD est généralement un objet de cette classe. L'interface du module déclare généralement les constructeurs comme des procédures ordinaires, et la plupart des autres opérations du TAD comme des méthodes de cette classe. De nombreux langages de programmation modernes, tels que C++ et Java, sont fournis avec des bibliothèques standard qui implémentent de nombreux TAD de cette manière. Cependant, une telle approche ne permet pas d'encapsuler facilement les multiples variantes de représentation présentes dans un TAD. Elle peut également nuire à l'extensibilité des programmes orientés objet. Dans un programme purement orienté objet qui utilise des interfaces comme types, les types font référence à des comportements, et non à des représentations.
La spécification de certains langages de programmation reste volontairement vague quant à la représentation de certains types de données intégrés, ne définissant que les opérations possibles sur ces types. De ce fait, ces types peuvent être considérés comme des « types abstraits de données intégrés ». On peut citer en exemple les tableaux dans de nombreux langages de script, tels que Awk , Lua et Perl , qui peuvent être vus comme une implémentation de la liste abstraite.
Dans un langage de spécification formelle , les types abstraits de données (TAD) peuvent être définis de manière axiomatique, et le langage permet ensuite de manipuler les valeurs de ces TAD, offrant ainsi une implémentation simple et immédiate. La famille de langages de programmation OBJ , par exemple, permet de définir des équations pour la spécification et de les réécrire pour les exécuter. Cependant, ces implémentations automatiques sont généralement moins efficaces que les implémentations dédiées.
Exemple : implémentation de la pile abstraite
À titre d’exemple, voici une implémentation de la pile abstraite ci-dessus dans le langage de programmation C.
Interface de style impératif
Une interface de style impératif pourrait être :
Cette interface peut être implémentée de nombreuses manières. L'implémentation peut être arbitrairement inefficace, car la définition formelle du type abstrait de données (TAD), ci-dessus, ne précise ni l'espace mémoire que la pile peut utiliser, ni la durée de chaque opération. Elle ne précise pas non plus si l'état de la pile Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Plus d articles de Worldlex Wiki