Quelle est la différence entre les types de données abstraits et les objets?

Une réponse sur Programmers.SE caractérise un essai de Cook (les objets ne sont pas des ADT ) comme disant

• Les objets se comportent comme une fonction caractéristique sur les valeurs d'un type, plutôt que comme une algèbre. Les objets utilisent l'abstraction procédurale plutôt que l'abstraction de type

• Les ADT ont généralement une implémentation unique dans un programme. Lorsque le langage de l'utilisateur possède des modules, il est possible d'avoir plusieurs implémentations d'un ADT, mais ils ne peuvent généralement pas interagir.

Il me semble que, dans l'essai de Cook, il se trouve que pour l'exemple spécifique d'un ensemble utilisé dans l'article de Cook, un objet peut être considéré comme une fonction caractéristique . Je ne pense pas que les objets, en général, puissent être considérés comme des fonctions caractéristiques.

Aussi, le papier d'Aldritch Le pouvoir de l'interopérabilité: pourquoi les objets sont inévitables ¹ suggère

La définition de Cook identifie essentiellement la répartition dynamique comme la caractéristique la plus importante de l'objet

d'accord avec cela et avec Alan Kay quand il a dit

Pour moi, la POO signifie uniquement la messagerie, la conservation et la protection locales et la dissimulation du processus étatique, et la liaison tardive extrême de toutes choses.

Cependant, ces diapositives de conférence complémentaires à l'article d'Aldritch suggèrent que les classes Java sont des ADT tandis que les interfaces Java sont des objets - et en effet, l'utilisation d'interfaces "objets" peut interagir (l'une des principales caractéristiques de la POO comme indiqué par l'un des points ci-dessus). ).

Mes questions sont

1. Ai-je raison de dire que les fonctions caractéristiques ne sont pas un élément clé des objets et que Frank Shearar se trompe?

2. Les données qui communiquent entre elles via des interfaces Java sont-elles des exemples d'objets même si elles n'utilisent pas la répartition dynamique? Pourquoi? (Je crois comprendre que la répartition dynamique est plus flexible et que les interfaces sont une étape vers la messagerie de type objectif-C / smalltalk / erlang.)

3. L'idée du principe d'inversion de dépendance est-elle liée à la distinction entre ADT et objets? (Voir la page Wikipedia ou The Talking Objects: A Tale About Message-Oriented Programming ) Bien que je sois nouveau dans le concept, je comprends qu'il implique l'ajout d'interfaces entre les "couches" d'un programme (voir le diagramme de la page wikipedia).

4. Veuillez fournir tout autre exemple / clarification de la distinction entre objets et ADT, si vous le souhaitez.

¹ _{Cet article (publié en 2013) est facile à lire et résume l'article de Cook 2009 avec des exemples en Java. Je recommande fortement au moins de l'écrémer, non pas pour répondre à cette question, mais simplement parce que c'est un bon papier.}

Google a soulevé une question similaire avec une réponse qui, je pense, est très bonne. Je l'ai cité ci-dessous.

Il y a une autre distinction qui se cache ici qui est expliquée dans l'essai Cook que j'ai lié.

Les objets ne sont pas le seul moyen d'implémenter l'abstraction. Tout n'est pas un objet. Les objets implémentent quelque chose que certains appellent l'abstraction des données procédurales. Les types de données abstraits implémentent une forme d'abstraction différente.

Une différence clé apparaît lorsque l'on considère les méthodes / fonctions binaires. Avec l'abstraction de données procédurales (objets), vous pourriez écrire quelque chose comme ceci pour une interface d'ensemble Int:

interface IntSet {
  void unionWith(IntSet s);
  ...
}

Considérons maintenant deux implémentations d'IntSet, disons une qui est soutenue par des listes et une qui est soutenue par une structure d'arbre binaire plus efficace:

class ListIntSet implements IntSet {
  void unionWith(IntSet s){ ... }
} 
class BSTIntSet implements IntSet {
  void unionWith(IntSet s){ ... }
}

Notez que unionWith doit prendre un argument IntSet. Pas le type le plus spécifique comme ListIntSet ou BSTIntSet. Cela signifie que l'implémentation BSTIntSet ne peut pas supposer que son entrée est un BSTIntSet et utiliser ce fait pour donner une implémentation efficace. (Il pourrait utiliser certaines informations de type d'exécution pour le vérifier et utiliser un algorithme plus efficace s'il l'est, mais il pourrait toujours être passé un ListIntSet et avoir à revenir à un algorithme moins efficace).

Comparez cela aux ADT, où vous pouvez écrire quelque chose de plus comme suit dans un fichier de signature ou d'en-tête:

typedef struct IntSetStruct *IntSetType;
void union(IntSetType s1, IntSetType s2);

Nous programmons contre cette interface. Notamment, le type est laissé abstrait. Vous ne savez pas ce que c'est. Ensuite, nous avons une implémentation BST puis fournit un type concret et des opérations:

struct IntSetStruct {
 int value;
 struct IntSetStruct* left;
 struct IntSetStruct* right;
}

void union(IntSetType s1, IntSetType s2){ ... }

Maintenant, l'union connaît en fait les représentations concrètes de s1 et s2, il peut donc l'exploiter pour une implémentation efficace. Nous pouvons également écrire une implémentation basée sur une liste et choisir de la lier à la place.

J'ai écrit la syntaxe C (ish), mais vous devriez regarder par exemple ML standard pour les types de données abstraits fait correctement (où vous pouvez par exemple utiliser plus d'une implémentation d'un ADT dans le même programme à peu près en qualifiant les types: BSTImpl. IntSetStruct et ListImpl.IntSetStruct, disons)

L'inverse est que l'abstraction des données procédurales (objets) vous permet d'introduire facilement de nouvelles implémentations qui fonctionnent avec les anciennes. Par exemple, vous pouvez écrire votre propre implémentation LoggingIntSet personnalisée et l'union avec un BSTIntSet. Mais c'est un compromis: vous perdez des types informatifs pour les méthodes binaires! Souvent, vous finissez par devoir exposer plus de fonctionnalités et de détails d'implémentation dans votre interface qu'avec une implémentation ADT. Maintenant, j'ai l'impression de retaper juste l'essai de Cook, alors vraiment, lisez-le!

Je voudrais ajouter un exemple à cela.

Cook suggère qu'un exemple d'un type de données abstrait est un module en C. En effet, les modules en C impliquent la dissimulation d'informations, car il existe des fonctions publiques qui sont exportées via un fichier d'en-tête, et des fonctions statiques (privées) qui ne le font pas. De plus, il y a souvent des constructeurs (par exemple list_new ()) et des observateurs (par exemple list_getListHead ()).

Un point clé de ce qui fait, par exemple, un module de liste appelé LIST_MODULE_SINGLY_LINKED un ADT est que les fonctions du module (par exemple list_getListHead ()) supposent que les données entrées ont été créées par le constructeur de LIST_MODULE_SINGLY_LINKED, par opposition à tout "équivalent" "implémentation d'une liste (par exemple LIST_MODULE_DYNAMIC_ARRAY). Cela signifie que les fonctions de LIST_MODULE_SINGLY_LINKED peuvent assumer, dans leur implémentation, une représentation particulière (par exemple une liste liée individuellement).

LIST_MODULE_SINGLY_LINKED ne peut pas interagir avec LIST_MODULE_DYNAMIC_ARRAY car nous ne pouvons pas alimenter les données créées, par exemple avec le constructeur de LIST_MODULE_DYNAMIC_ARRAY, à l'observateur de LIST_MODULE_SINGLY_LINKED car LIST_MODULE_SINGLY_LINKED car un objet, comme une liste, suppose qu'un comportement (LIST_MODULE_SINGLY_LINKED)

Ceci est analogue à une façon dont deux groupes différents de l'algèbre abstraite ne peuvent pas interagir (c'est-à-dire que vous ne pouvez pas prendre le produit d'un élément d'un groupe avec un élément d'un autre groupe). En effet, les groupes assument la propriété de fermeture du groupe (le produit des éléments d'un groupe doit être dans le groupe). Cependant, si nous pouvons prouver que deux groupes différents sont en fait des sous-groupes d'un autre groupe G, alors nous pouvons utiliser le produit de G pour ajouter deux éléments, un de chacun des deux groupes.

Comparaison des ADT et des objets

• Cook lie partiellement la différence entre les ADT et les objets au problème d'expression. En gros, les ADT sont couplés à des fonctions génériques qui sont souvent implémentées dans des langages de programmation fonctionnels, tandis que les objets sont couplés à des "objets" Java accessibles via des interfaces. Aux fins de ce texte, une fonction générique est une fonction qui accepte certains arguments ARGS et un type TYPE (pré-condition); en fonction de TYPE, il sélectionne la fonction appropriée et l'évalue avec ARGS (post-condition). Les fonctions génériques et les objets implémentent le polymorphisme, mais avec les fonctions génériques, le programmeur SAIT quelle fonction sera exécutée par la fonction générique sans regarder le code de la fonction générique. Avec les objets d'autre part, le programmeur ne sait pas comment l'objet va gérer les arguments, à moins que les programmeurs ne regardent le code de l'objet.

• Habituellement, le problème d'expression est pensé en termes de "ai-je beaucoup de représentations?" vs "ai-je beaucoup de fonctions avec peu de représentation". Dans le premier cas, il faut organiser le code par représentation (comme c'est le plus courant, surtout en Java). Dans le second cas, il faut organiser le code par fonctions (c'est-à-dire qu'une seule fonction générique gère plusieurs représentations).

• Si vous organisez votre code par représentation, alors, si vous souhaitez ajouter des fonctionnalités supplémentaires, vous êtes obligé d'ajouter la fonctionnalité à chaque représentation de l'objet; en ce sens, l'ajout de fonctionnalités n'est pas «additif». Si vous organisez votre code par fonctionnalité, alors, si vous voulez ajouter une représentation supplémentaire - vous êtes obligé d'ajouter la représentation à chaque objet; en ce sens l'ajout de représentations n'est pas "additif".

Avantage des ADT sur les objets

• L'ajout de fonctionnalités est additif

• Possibilité de tirer parti de la connaissance de la représentation d'un ADT pour la performance, ou de prouver que l'ADT garantira une certaine postcondition étant donné une condition préalable. Cela signifie que la programmation avec ADT consiste à faire les bonnes choses dans le bon ordre (enchaîner les pré-conditions et les post-conditions vers une post-condition "objectif").

Avantages des objets par rapport aux ADT

• Ajout de représentations dans l'additif

• Les objets peuvent interagir

• Il est possible de spécifier des conditions de pré / post pour un objet, et de les enchaîner comme c'est le cas avec les ADT. Dans ce cas, les avantages des objets sont que (1) il est facile de changer les représentations sans changer l'interface et (2) les objets peuvent interagir. Cependant, cela va à l'encontre du but de la POO dans le sens de smalltalk. (voir la section "Version d'OOP d'Alan Kay)

La répartition dynamique est la clé de la POO

Il devrait être évident maintenant que la répartition dynamique (c'est-à-dire la liaison tardive) est essentielle pour la programmation orientée objet. Il en est ainsi qu'il est possible de définir des procédures de manière générique, qui ne suppose pas une représentation particulière. Pour être concret - la programmation orientée objet est facile en python, car il est possible de programmer les méthodes d'un objet d'une manière qui n'assume pas une représentation particulière. C'est pourquoi python n'a pas besoin d'interfaces comme Java.

En Java, les classes sont des ADT. cependant, une classe accessible via l'interface qu'elle implémente est un objet.

Addendum: la version d'AOP de Alan Kay

Alan Kay a explicitement qualifié les objets de "familles d'algèbres", et Cook suggère qu'un ADT est une algèbre. Par conséquent, Kay voulait probablement dire qu'un objet est une famille d'ADT. Autrement dit, un objet est la collection de toutes les classes qui satisfont une interface Java.

Cependant, l'image des objets peints par Cook est beaucoup plus restrictive que la vision d'Alan Kay. Il voulait que les objets se comportent comme des ordinateurs dans un réseau ou comme des cellules biologiques. L'idée était d'appliquer le principe du moindre engagement à la programmation - afin qu'il soit facile de changer les couches de bas niveau d'un ADT une fois que les couches de haut niveau ont été construites en les utilisant. Avec cette image en tête, les interfaces Java sont trop restrictives car elles ne permettent pas à un objet d'interpréter la signification d'un message , voire de l'ignorer complètement.

En résumé, l'idée clé des objets, pour Kay - n'est pas qu'ils sont une famille d'algèbres (comme le souligne Cook). L'idée clé de Kay était plutôt d'appliquer un modèle qui fonctionnait dans le grand (ordinateurs en réseau) au petit (objets dans un programme).

edit: Une autre clarification sur la version Kay de OOP: Le but des objets est de se rapprocher d'un idéal déclaratif. Nous devons dire à l'objet ce qu'il doit faire - ne pas lui dire comment la microgestion est l'état, comme c'est la coutume avec la programmation procédurale et les ADT. Plus d'informations peuvent être trouvées ici , ici , ici et ici .

edit: J'ai trouvé un très bon exposé de la définition d'Alan Kay de POO ici .

Si vous regardez les partisans de l'ADT, ils considèrent qu'un ADT est ce que l'OOP appellerait une classe (état interne, privé; un ensemble limité d'opérations autorisé), mais aucune relation entre les classes (pas d'héritage, fondamentalement) n'est considérée. Le point étant à la place que le même comportement peut être obtenu avec différentes implémentations. Par exemple, un ensemble peut être implémenté sous forme de liste, d'éléments dans un tableau ou une table de hachage, ou une sorte d'arbre.

Je l'ai toujours compris de cette façon:

1. Un ADT est une interface: c'est juste un ensemble de méthodes, leurs signatures de type, éventuellement avec des conditions pré et post.

2. Une classe peut implémenter un ou plusieurs ADT, en donnant des implémentations réelles pour les méthodes spécifiées dans l'ADT.

3. Un objet est une instance d'une classe, avec sa propre copie de toutes les variables non statiques.

Il est possible que dans la littérature, les distinctions diffèrent, mais c'est la terminologie "standard" que vous entendrez en informatique.

Par exemple, en Java, Collectionest un ADT, ArrayListest une classe et vous pouvez créer un ArrayListobjet avec l' newopérateur.

Quant à l'affirmation selon laquelle les ADT n'ont généralement qu'une seule implémentation, ce n'est souvent pas le cas. Par exemple, il est possible que vous souhaitiez utiliser à la fois des dictionnaires basés sur des arborescences et des tables de hachage dans votre programme, selon ce que vous stockez. Ils partageraient un ADT, mais utiliseraient différentes implémentations.