Qual é a diferença entre tipos de dados abstratos e objetos?

Uma resposta sobre Programmers.SE caracteriza um ensaio de Cook ( Objetos não são ADTs ) como dizendo

• Os objetos se comportam como uma função característica sobre os valores de um tipo, e não como uma álgebra. Os objetos usam abstração procedural em vez de abstração de tipo

• ADTs geralmente têm uma implementação exclusiva em um programa. Quando o idioma de uma pessoa possui módulos, é possível ter várias implementações de um ADT, mas elas geralmente não podem interoperar.

Parece-me que, no ensaio de Cook, acontece apenas que, para o exemplo específico de um conjunto usado no artigo de Cook, um objeto pode ser visto como uma função característica . Eu não acho que objetos, em geral, possam ser vistos como funções características.

Além disso, o artigo de Aldritch O poder da interoperabilidade: por que os objetos são inevitáveis ¹ sugere

A definição de Cook identifica essencialmente o despacho dinâmico como a característica mais importante do objeto

concordando com isso e com Alan Kay quando ele disse

OOP para mim significa apenas mensagens, retenção e proteção local e ocultação de processos estatais e vinculação tardia extrema de todas as coisas.

No entanto, essas palestras complementares ao artigo de Aldritch sugerem que as classes Java são ADTs, enquanto as interfaces Java são objetos - e, de fato, o uso de interfaces "objetos" pode interoperar (um dos principais recursos do OOP, conforme indicado por um dos pontos acima) )

Minhas perguntas são

1. Estou correto em dizer que funções características não são uma característica fundamental dos objetos e que Frank Shearar está enganado?

2. Os dados que se comunicam por meio de interfaces Java são exemplos de objetos, mesmo que não usem expedição dinâmica? Por quê? (Meu entendimento é que o envio dinâmico é mais flexível e que as interfaces são um passo em direção às mensagens de estilo objetivo C / smalltalk / erlang.)

3. A idéia do princípio da inversão de dependência está relacionada à distinção entre ADTs e objetos? (Veja a página da Wikipedia ou Os objetos que falam: uma história sobre programação orientada a mensagens ) Embora eu seja novo no conceito, entendo que ele envolve a adição de interfaces entre as "camadas" de um programa (consulte o diagrama da página da Wikipedia).

4. Forneça outros exemplos / esclarecimentos sobre a distinção entre objetos e ADTs, se desejar.

¹ _{Este artigo (publicado em 2013) é leitura fácil e resume papel de Cook 2009, com exemplos em Java. Eu recomendo pelo menos deslizá-lo, não para responder a essa pergunta, mas apenas porque é um bom papel.}

O Google levantou uma pergunta semelhante com uma resposta que eu acho muito boa. Eu citei abaixo.

Há outra distinção oculta aqui que é explicada no ensaio de Cook que eu vinculei.

Objetos não são a única maneira de implementar abstração. Nem tudo é um objeto. Objetos implementam algo que algumas pessoas chamam de abstração de dados procedurais. Os tipos de dados abstratos implementam uma forma diferente de abstração.

Uma diferença importante aparece quando você considera métodos / funções binários. Com a abstração de dados procedurais (objetos), você pode escrever algo parecido com isto para uma interface de conjunto Int:

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

Agora considere duas implementações do IntSet, digamos, uma suportada por listas e outra suportada por uma estrutura de árvore binária mais eficiente:

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

Observe que unionWith deve aceitar um argumento IntSet. Não é o tipo mais específico, como ListIntSet ou BSTIntSet. Isso significa que a implementação do BSTIntSet não pode assumir que sua entrada é um BSTIntSet e usar esse fato para fornecer uma implementação eficiente. (Ele pode usar algumas informações do tipo tempo de execução para verificá-las e usar um algoritmo mais eficiente, se for o caso, mas ainda pode receber um ListIntSet e precisar retornar a um algoritmo menos eficiente).

Compare isso com os ADTs, onde você pode escrever algo mais como o seguinte em um arquivo de assinatura ou cabeçalho:

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

Nós programamos contra essa interface. Notavelmente, o tipo é deixado abstrato. Você não sabe o que é isso. Em seguida, temos uma implementação BST e, em seguida, fornece um tipo e operações concretas:

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

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

Agora, a união realmente conhece as representações concretas de s1 e s2, para poder explorar isso para uma implementação eficiente. Também podemos escrever uma implementação apoiada em lista e optar por vincular a ela.

Eu escrevi a sintaxe C (ish), mas você deve examinar, por exemplo, o ML padrão para tipos de dados abstratos feitos corretamente (onde você pode, por exemplo, usar mais de uma implementação de um ADT no mesmo programa, classificando os tipos: BSTImpl. IntSetStruct e ListImpl.IntSetStruct, digamos)

O inverso disso é que a abstração de dados processuais (objetos) permite introduzir facilmente novas implementações que funcionam com as antigas. por exemplo, você pode escrever sua própria implementação LoggingIntSet personalizada e uni-la com um BSTIntSet. Mas isso é uma troca: você perde tipos informativos para métodos binários! Muitas vezes, você acaba expondo mais funcionalidades e detalhes de implementação em sua interface do que faria com uma implementação do ADT. Agora sinto que estou apenas redigitando o ensaio de Cook, então, sério, leia-o!

Eu gostaria de adicionar um exemplo a isso.

Cook sugere que um exemplo de um tipo de dado abstrato é um módulo em C. De fato, os módulos em C envolvem ocultação de informações, pois existem funções públicas que são exportadas por meio de um arquivo de cabeçalho e funções estáticas (privadas) que não. Além disso, geralmente existem construtores (por exemplo, list_new ()) e observadores (por exemplo, list_getListHead ()).

Um ponto chave do que faz, digamos, um módulo de lista chamado LIST_MODULE_SINGLY_LINKED um ADT, é que as funções do módulo (por exemplo, list_getListHead ()) assumem que os dados que estão sendo inseridos foram criados pelo construtor de LIST_MODULE_SINGLY_LINKED, em oposição a qualquer "equivalente" "implementação de uma lista (por exemplo, LIST_MODULE_DYNAMIC_ARRAY). Isso significa que as funções de LIST_MODULE_SINGLY_LINKED podem assumir, em sua implementação, uma representação específica (por exemplo, uma lista vinculada única).

LIST_MODULE_SINGLY_LINKED não pode operar com LIST_MODULE_DYNAMIC_ARRAY porque não podemos alimentar os dados criados, digamos com o construtor LIST_MODULE_DYNAMIC_ARRAY, para o observador do comportamento LIST_MODULE_SINGLY_LINKED, que representa apenas um objeto a partir de uma lista LIST_MODULE_SINGLY_LINKED.

Isso é análogo a uma maneira pela qual dois grupos diferentes da álgebra abstrata não podem interoperar (ou seja, você não pode levar o produto de um elemento de um grupo com um elemento de outro grupo). Isso ocorre porque os grupos assumem a propriedade de fechamento do grupo (o produto dos elementos em um grupo deve estar no grupo). No entanto, se pudermos provar que dois grupos diferentes são de fato subgrupos de outro grupo G, podemos usar o produto de G para adicionar dois elementos, um de cada um dos dois grupos.

Comparando os ADTs e objetos

• Cook vincula parcialmente a diferença entre ADTs e objetos ao problema de expressão. Grosso modo, os ADTs são acoplados a funções genéricas que geralmente são implementadas em linguagens de programação funcionais, enquanto objetos são acoplados a "objetos" Java acessados ​​por meio de interfaces. Para os fins deste texto, uma função genérica é uma função que recebe alguns argumentos ARGS e um tipo TYPE (pré-condição); com base em TYPE, seleciona a função apropriada e a avalia com ARGS (pós-condição). Funções e objetos genéricos implementam polimorfismo, mas com funções genéricas, o programador SABE qual função será executada pela função genérica sem observar o código da função genérica. Com objetos, por outro lado, o programador não sabe como o objeto manipulará os argumentos, a menos que os programadores examinem o código do objeto.

• Geralmente, o problema da expressão é pensado em termos de "eu tenho muitas representações?" vs. "eu tenho muitas funções com pouca representação". No primeiro caso, deve-se organizar o código por representação (como é mais comum, especialmente em Java). No segundo caso, deve-se organizar o código por funções (ou seja, ter uma única função genérica manipular várias representações).

• Se você organizar seu código por representação, se desejar adicionar funcionalidade extra, será forçado a adicionar a funcionalidade a todas as representações do objeto; nesse sentido, adicionar funcionalidade não é "aditivo". Se você organizar seu código por funcionalidade, se desejar adicionar uma representação extra - será forçado a adicionar a representação a cada objeto; nesse sentido, adicionar representações em não "aditivas".

Vantagem de ADTs sobre objetos

• Adicionar funcionalidade é aditivo

• Possível alavancar o conhecimento da representação de um ADT para desempenho ou provar que o ADT garantirá alguma pós-condição, dada uma pré-condição. Isso significa que programar com ADTs é fazer as coisas certas na ordem certa (encadear pré-condições e pós-condições em direção a uma condição de pós "objetivo").

Vantagens de objetos sobre ADTs

• Adicionando representações no aditivo

• Objetos podem interagir

• É possível especificar condições pré / pós para um objeto e encadeá-las, como é o caso dos ADTs. Nesse caso, as vantagens dos objetos são que (1) é fácil alterar representações sem alterar a interface e (2) os objetos podem interoperar. No entanto, isso derrota o objetivo da POO no sentido de conversa fiada. (consulte a seção "Versão de Alan Kay do OOP)

O envio dinâmico é a chave para o OOP

Deve ficar claro agora que o envio dinâmico (ou seja, ligação tardia) é essencial para a programação orientada a objetos. Isso é para que seja possível definir procedimentos de uma maneira genérica, que não assuma uma representação específica. Para ser concreto, a programação orientada a objetos é fácil em python, porque é possível programar métodos de um objeto de uma maneira que não assuma uma representação específica. É por isso que o python não precisa de interfaces como Java.

Em Java, as classes são ADTs. no entanto, uma classe acessada através da interface implementada é um objeto.

Adendo: versão de Alan Kay do OOP

Alan Kay se refere explicitamente a objetos como "famílias de álgebras", e Cook sugere que um ADT é uma álgebra. Portanto, Kay provavelmente significava que um objeto é uma família de ADTs. Ou seja, um objeto é a coleção de todas as classes que satisfazem uma interface Java.

No entanto, a imagem dos objetos pintados por Cook é muito mais restritiva do que a visão de Alan Kay. Ele queria que os objetos se comportassem como computadores em uma rede ou como células biológicas. A idéia era aplicar o princípio de menor comprometimento com a programação - para que seja fácil alterar as camadas de baixo nível de um ADT depois que as camadas de alto nível forem construídas usando-as. Com essa imagem em mente, as interfaces Java são muito restritivas porque não permitem que um objeto interprete o significado de uma mensagem ou até a ignore completamente.

Em resumo, para Kay, a idéia principal dos objetos não é que eles sejam uma família de álgebras (como enfatizado por Cook). Em vez disso, a ideia principal de Kay era aplicar um modelo que funcionasse em grandes (computadores em uma rede) aos pequenos (objetos em um programa).

editar: Outro esclarecimento sobre a versão de OOP de Kay: O objetivo dos objetos é aproximar-se de um ideal declarativo. Deveríamos dizer ao objeto o que fazer - não dizer como o micro-gerenciamento é estado, como é habitual em programação procedural e ADTs. Mais informações podem ser encontradas aqui , aqui , aqui e aqui .

edit: Encontrei uma exposição muito, muito boa da definição de OOP de Alan Kay aqui .

Se você observar os proponentes do ADT, eles consideram um ADT o que o OOP chamaria de classe (estado interno, privado; um conjunto limitado de operações permitido), mas nenhuma relação entre as classes (sem herança, basicamente) é considerada. O ponto é que, em vez disso, o mesmo comportamento pode ser obtido com diferentes implementações. Por exemplo, um conjunto pode ser implementado como uma lista, elementos em uma matriz ou hashtable, ou algum tipo de árvore.

Eu sempre entendi assim:

1. Um ADT é uma interface: é apenas uma coleção de métodos, suas assinaturas de tipo, possivelmente com condições anteriores e posteriores.

2. Uma classe pode implementar um ou mais ADTs, fornecendo implementações reais para os métodos especificados no ADT.

3. Um objeto é uma instância de uma classe, com sua própria cópia de quaisquer variáveis ​​não estáticas.

É possível que na literatura as distinções sejam diferentes, mas essa é a terminologia "padrão" que você ouvirá na ciência da computação.

Por exemplo, em Java, Collectioné um ADT, ArrayListé uma classe e você pode criar um ArrayListobjeto com o newoperador.

Quanto à afirmação de que os ADTs geralmente têm apenas uma implementação, esse geralmente não é o caso. Por exemplo, é possível que você queira usar dicionários baseados em árvore e em hashtable em seu programa, dependendo do que estiver armazenando. Eles compartilhariam um ADT, mas usariam implementações diferentes.