¿Cuál es la diferencia entre tipos de datos abstractos y objetos?

Una respuesta sobre Programmers.SE caracteriza un ensayo de Cook (Los objetos no son ADT ) como diciendo

• Los objetos se comportan como una función característica sobre los valores de un tipo, más que como un álgebra. Los objetos usan abstracción de procedimiento en lugar de abstracción de tipo

• Los ADT generalmente tienen una implementación única en un programa. Cuando el lenguaje de uno tiene módulos, es posible tener múltiples implementaciones de un ADT, pero generalmente no pueden interactuar.

Me parece que, en el ensayo de Cook, resulta que para el ejemplo específico de un conjunto utilizado en el artículo de Cook, un objeto puede verse como una función característica . No creo que los objetos, en general, puedan verse como funciones características.

Además, el artículo de Aldritch El poder de la interoperabilidad: por qué los objetos son inevitables ¹ sugiere

La definición de Cook esencialmente identifica el despacho dinámico como la característica más importante del objeto

de acuerdo con esto y con Alan Kay cuando dijo

OOP para mí significa solo mensajes, retención local y protección y ocultación del proceso estatal, y un enlace tardío extremo de todas las cosas.

Sin embargo, estas diapositivas de conferencias complementarias al artículo de Aldritch sugieren que las clases de Java son ADT, mientras que las interfaces de Java son objetos, y de hecho el uso de interfaces "objetos" puede interactuar (una de las características clave de OOP dada por uno de los puntos anteriores) )

Mis preguntas son

1. ¿Estoy en lo cierto al decir que las funciones características no son una característica clave de los objetos y que Frank Shearar está equivocado?

2. ¿Son los datos que se comunican entre sí a través de interfaces Java ejemplos de objetos a pesar de que no usan despacho dinámico? ¿Por qué? (Entiendo que el despacho dinámico es más flexible, y que las interfaces son un paso hacia la mensajería de estilo objetivo-C / smalltalk / erlang).

3. ¿La idea del principio de inversión de dependencia está relacionada con la distinción entre ADT y objetos? (Vea la página de Wikipedia o The Talking Objects: A Tale About Message-Oriented Programming ) Aunque soy nuevo en el concepto, entiendo que implica agregar interfaces entre "capas" de un programa (ver el diagrama de la página de Wikipedia).

4. Proporcione cualquier otro ejemplo / aclaración de la distinción entre objetos y ADT, si lo desea.

¹ _{Este documento (publicado en 2013) es de fácil lectura y resume el artículo de Cook de 2009 con ejemplos en Java. Recomiendo al menos leerlo, no para responder a esta pregunta, sino solo porque es un buen artículo.}

Google planteó una pregunta similar con una respuesta que creo que es muy buena. Lo he citado a continuación.

Hay otra distinción al acecho que se explica en el ensayo de Cook que vinculé.

Los objetos no son la única forma de implementar la abstracción. No todo es un objeto. Los objetos implementan algo que algunas personas llaman abstracción de datos de procedimiento. Los tipos de datos abstractos implementan una forma diferente de abstracción.

Una diferencia clave aparece cuando considera métodos / funciones binarios. Con la abstracción de datos de procedimiento (objetos), puede escribir algo como esto para una interfaz Int set:

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

Ahora considere dos implementaciones de IntSet, digamos una respaldada por listas y otra respaldada por una estructura de árbol binario más eficiente:

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

Tenga en cuenta que unionWith debe tomar un argumento IntSet. No es el tipo más específico como ListIntSet o BSTIntSet. Esto significa que la implementación BSTIntSet no puede asumir que su entrada es un BSTIntSet y usar ese hecho para proporcionar una implementación eficiente. (Podría usar alguna información de tipo de tiempo de ejecución para verificarlo y usar un algoritmo más eficiente si lo es, pero aún podría pasar un ListIntSet y tener que recurrir a un algoritmo menos eficiente).

Compare esto con los ADT, donde puede escribir algo más parecido a lo siguiente en un archivo de firma o encabezado:

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

Programamos contra esta interfaz. En particular, el tipo se deja abstracto. No llegas a saber de qué se trata. Luego tenemos una implementación BST que luego proporciona un tipo concreto y operaciones:

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

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

Ahora, union realmente conoce las representaciones concretas de s1 y s2, por lo que puede explotar esto para una implementación eficiente. También podemos escribir una implementación respaldada por una lista y optar por vincularla en su lugar.

He escrito la sintaxis de C (ish), pero debería ver, por ejemplo, ML estándar para los tipos de datos abstractos realizados correctamente (donde puede, por ejemplo, utilizar más de una implementación de un ADT en el mismo programa aproximadamente calificando los tipos: BSTImpl. IntSetStruct y ListImpl.IntSetStruct, digamos)

Lo contrario de esto es que la abstracción de datos de procedimiento (objetos) le permite introducir fácilmente nuevas implementaciones que funcionan con las anteriores. por ejemplo, puede escribir su propia implementación LoggingIntSet personalizada y unirla con un BSTIntSet. Pero esto es una compensación: ¡pierde tipos informativos por métodos binarios! A menudo terminas teniendo que exponer más detalles de funcionalidad e implementación en tu interfaz que con una implementación ADT. Ahora siento que solo estoy volviendo a escribir el ensayo de Cook, así que realmente, ¡léelo!

Me gustaría agregar un ejemplo a esto.

Cook sugiere que un ejemplo de un tipo de datos abstractos es un módulo en C. De hecho, los módulos en C implican la ocultación de información, ya que hay funciones públicas que se exportan a través de un archivo de encabezado y funciones estáticas (privadas) que no. Además, a menudo hay constructores (por ejemplo, list_new ()) y observadores (por ejemplo, list_getListHead ()).

Un punto clave de lo que hace, digamos, un módulo de lista llamado LIST_MODULE_SINGLY_LINKED an ADT es que las funciones del módulo (por ejemplo, list_getListHead ()) asumen que los datos que están siendo ingresados ​​han sido creados por el constructor de LIST_MODULE_SINGLY_LINKED, en lugar de cualquier "equivalente "implementación de una lista (por ejemplo, LIST_MODULE_DYNAMIC_ARRAY). Esto significa que las funciones de LIST_MODULE_SINGLY_LINKED pueden asumir, en su implementación, una representación particular (por ejemplo, una lista individualmente vinculada).

LIST_MODULE_SINGLY_LINKED no puede interactuar con LIST_MODULE_DYNAMIC_ARRAY porque no podemos alimentar los datos creados, por ejemplo, con el constructor de LIST_MODULE_DYNAMIC_ARRAY, al observador de LIST_MODULE_SINGLY_LINKED porque una LISTA_Unida a.

Esto es análogo a la forma en que dos grupos diferentes del álgebra abstracta no pueden interoperar (es decir, no se puede tomar el producto de un elemento de un grupo con un elemento de otro grupo). Esto se debe a que los grupos asumen la propiedad de cierre del grupo (el producto de los elementos en un grupo debe estar en el grupo). Sin embargo, si podemos demostrar que dos grupos diferentes son de hecho subgrupos de otro grupo G, entonces podemos usar el producto de G para agregar dos elementos, uno de cada uno de los dos grupos.

Comparar los ADT y los objetos

• Cook vincula la diferencia entre ADT y objetos parcialmente al problema de expresión. En términos generales, los ADT se combinan con funciones genéricas que a menudo se implementan en lenguajes de programación funcionales, mientras que los objetos se acoplan con "objetos" Java a los que se accede a través de interfaces. Para los propósitos de este texto, una función genérica es una función que toma algunos argumentos ARGS y un tipo TYPE (precondición); basado en TYPE, selecciona la función apropiada y la evalúa con ARGS (condición posterior). Tanto las funciones genéricas como los objetos implementan polimorfismo, pero con funciones genéricas, el programador SABE qué función será ejecutada por la función genérica sin mirar el código de la función genérica. Con los objetos, por otro lado, el programador no sabe cómo manejará el objeto los argumentos, a menos que los programadores observen el código del objeto.

• Por lo general, el problema de la expresión se considera en términos de "¿tengo muchas representaciones?" vs. "tengo muchas funciones con poca representación". En el primer caso, uno debe organizar el código por representación (como es más común, especialmente en Java). En el segundo caso, uno debe organizar el código por funciones (es decir, tener una sola función genérica manejar múltiples representaciones).

• Si organiza su código por representación, entonces, si desea agregar funcionalidad adicional, se ve obligado a agregar la funcionalidad a cada representación del objeto; en este sentido, agregar funcionalidad no es "aditivo". Si organiza su código por funcionalidad, entonces, si desea agregar una representación adicional, se ve obligado a agregar la representación a cada objeto; en este sentido agregar representaciones en no "aditivo".

Ventaja de ADT sobre objetos

• Agregar funcionalidad es aditivo

• Posible aprovechar el conocimiento de la representación de un ADT para el rendimiento, o para demostrar que el ADT garantizará alguna condición posterior dada una condición previa. Esto significa que la programación con ADT se trata de hacer las cosas correctas en el orden correcto (encadenar las condiciones previas y las condiciones posteriores hacia una condición posterior "objetivo").

Ventajas de los objetos sobre los ADT

• Agregar representaciones en aditivo

• Los objetos pueden interactuar

• Es posible especificar condiciones previas / posteriores para un objeto y encadenarlas como es el caso con los ADT. En este caso, las ventajas de los objetos son que (1) es fácil cambiar las representaciones sin cambiar la interfaz y (2) los objetos pueden interactuar. Sin embargo, esto derrota el propósito de OOP en el sentido de smalltalk. (vea la sección "Versión de OOP de Alan Kay)

El despacho dinámico es clave para OOP

Ahora debería ser evidente que el despacho dinámico (es decir, el enlace tardío) es esencial para la programación orientada a objetos. Esto es para que sea posible definir procedimientos de forma genérica, sin asumir una representación particular. Para ser concreto, la programación orientada a objetos es fácil en Python, porque es posible programar métodos de un objeto de una manera que no asuma una representación particular. Es por eso que python no necesita interfaces como Java.

En Java, las clases son ADT. sin embargo, una clase a la que se accede a través de la interfaz que implementa es un objeto.

Anexo: la versión de OOP de Alan Kay

Alan Kay se refirió explícitamente a los objetos como "familias de álgebras", y Cook sugiere que un ADT es un álgebra. Por lo tanto, Kay probablemente quiso decir que un objeto es una familia de ADT. Es decir, un objeto es la colección de todas las clases que satisfacen una interfaz Java.

Sin embargo, la imagen de los objetos pintados por Cook es mucho más restrictiva que la visión de Alan Kay. Quería que los objetos se comporten como computadoras en una red, o como células biológicas. La idea era aplicar el principio de menor compromiso con la programación, de modo que sea fácil cambiar las capas de bajo nivel de un ADT una vez que las capas de alto nivel se hayan creado con ellas. Con esta imagen en mente, las interfaces de Java son demasiado restrictivas porque no permiten que un objeto interprete el significado de un mensaje , o incluso lo ignore por completo.

En resumen, la idea clave de los objetos, para Kay, no es que sean una familia de álgebras (como lo enfatiza Cook). Más bien, la idea clave de Kay era aplicar un modelo que funcionaba en grande (computadoras en una red) a pequeño (objetos en un programa).

editar: Otra aclaración sobre la versión de Kay de OOP: El propósito de los objetos es acercarse a un ideal declarativo. Deberíamos decirle al objeto qué hacer, no decirle cómo por microgestión es estado, como es habitual con la programación de procedimientos y los ADT. Se puede encontrar más información aquí , aquí , aquí y aquí .

editar: Encontré una muy, muy buena exposición de la definición de OOP de Alan Kay aquí .

Si nos fijamos en los proponentes de ADT, consideran que un ADT es lo que OOP llamaría una clase (estado interno, privado; se permite un conjunto limitado de operaciones), pero no se considera ninguna relación entre clases (básicamente, no hay herencia). El punto es que se puede obtener el mismo comportamiento con diferentes implementaciones. Por ejemplo, un conjunto puede implementarse como una lista, elementos en una matriz o tabla hash, o algún tipo de árbol.

Siempre lo entendí de esta manera:

1. Un ADT es una interfaz: es solo una colección de métodos, sus firmas de tipo, posiblemente con condiciones previas y posteriores.

2. Una clase puede implementar uno o más ADT, dando implementaciones reales para los métodos especificados en el ADT.

3. Un objeto es una instancia de una clase, con su propia copia de cualquier variable no estática.

Es posible que en la literatura, las distinciones sean diferentes, pero esta es la terminología "estándar" que escuchará en informática.

Por ejemplo, en Java, Collectiones un ADT, ArrayListes una clase y puede hacer un ArrayListobjeto con el newoperador.

En cuanto a la afirmación de que los ADT generalmente solo tienen una implementación, este no suele ser el caso. Por ejemplo, es posible que desee utilizar diccionarios basados ​​en árbol y en tabla hash en su programa, dependiendo de lo que esté almacenando. Compartirían un ADT, pero usarían diferentes implementaciones.