В чем разница между абстрактными типами данных и объектами?

Ответ на Programmers.SE характеризует эссе Кука ( объекты не АТД ) , как говорят

• Объекты ведут себя как характеристическая функция над значениями типа, а не как алгебра. Объекты используют процедурную абстракцию, а не абстракцию типа

• ADT обычно имеют уникальную реализацию в программе. Когда у одного языка есть модули, возможно иметь несколько реализаций ADT, но они обычно не могут взаимодействовать.

Мне кажется, что в эссе Кука просто так получилось, что для конкретного примера набора, использованного в статье Кука, объект можно рассматривать как характеристическую функцию . Я не думаю, что объекты в целом можно рассматривать как характерные функции.

Кроме того, статья Олдрича Сила взаимодействия: почему объекты неизбежны ¹ предлагает

Определение Кука по существу определяет динамическую диспетчеризацию как наиболее важную характеристику объекта

соглашаясь с этим и с Аланом Кей, когда он сказал

Для меня ООП означает только обмен сообщениями, локальное хранение и защиту, а также сокрытие процесса состояния и крайнюю позднюю привязку всех вещей.

Однако эти сопутствующие слайды лекции к статье Олдрича предполагают, что классы Java являются ADT, в то время как интерфейсы Java являются объектами - и, действительно, использование «объектов» интерфейсов может взаимодействовать (одна из ключевых особенностей ООП, как указано в одной из вышеупомянутых пунктов) ).

Мои вопросы

1. Правильно ли мне сказать, что характерные функции не являются ключевой особенностью объектов и что Фрэнк Шиарар ошибается?

2. Имеются ли данные о том, что разговор друг с другом через Java интерфейсов, примеры объектов, даже если они не используют динамическую отправку? Почему? (Насколько я понимаю, динамическая диспетчеризация является более гибкой, и что интерфейсы - это шаг к обмену сообщениями в стиле target-C / smalltalk / erlang.)

3. Связана ли идея принципа инверсии зависимостей с различием между ADT и объектами? (См страницы Википедии или Говорящие объекты: Повесть о Message-Oriented Programming ) Несмотря на то, что я новичок в эту концепцию, я понимаю , что она включает в себя добавление интерфейсов между «слоями» программой (см википедии диаграммы страницы).

4. Просьба представить любые другие примеры / разъяснения различия между объектами и АТД, если вы хотите.

¹ _{Эта статья (опубликовано в 2013 году) легко читать и суммирует бумаги Кука 2009 с примерами на Java. Я настоятельно рекомендую , по крайней мере скользя его, чтобы не ответить на этот вопрос, но только потому , что это хорошая бумага.}

Google поднял аналогичный вопрос с ответом, который я считаю очень хорошим. Я процитировал это ниже.

Здесь скрывается еще одно различие, которое объясняется в эссе Кука, которое я связал.

Объекты - не единственный способ реализовать абстракцию. Не все это объект. Объекты реализуют то, что некоторые люди называют процедурной абстракцией данных. Абстрактные типы данных реализуют другую форму абстракции.

Ключевое различие появляется, когда вы рассматриваете двоичные методы / функции. С процедурной абстракцией данных (объекты) вы могли бы написать что-то вроде этого для интерфейса набора Int:

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

Теперь рассмотрим две реализации IntSet, скажем, одну, основанную на списках, и другую, основанную на более эффективной структуре двоичного дерева:

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

Обратите внимание, что unionWith должен принимать аргумент IntSet. Не более конкретный тип, такой как ListIntSet или BSTIntSet. Это означает, что реализация BSTIntSet не может предполагать, что его ввод является BSTIntSet, и использовать этот факт для эффективной реализации. (Он мог бы использовать некоторую информацию о типе времени выполнения, чтобы проверить ее и использовать более эффективный алгоритм, если он есть, но ему все же можно было бы передать ListIntSet и пришлось бы использовать менее эффективный алгоритм).

Сравните это с ADT, где вы можете написать что-то похожее на следующее в файле подписи или заголовка:

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

Мы программируем на этот интерфейс. Примечательно, что тип оставлен абстрактным. Вы не узнаете, что это такое. Затем у нас есть реализация BST, которая предоставляет конкретный тип и операции:

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

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

Теперь union на самом деле знает конкретные представления как s1, так и s2, поэтому он может использовать это для эффективной реализации. Мы также можем написать поддерживаемую списком реализацию и вместо этого выбрать ссылку на нее.

Я написал синтаксис C (ish), но вы должны взглянуть, например, на Standard ML, чтобы абстрактные типы данных выполнялись правильно (где вы можете, например, фактически использовать более одной реализации ADT в одной и той же программе, приблизительно квалифицируя типы: BSTImpl. Скажем, IntSetStruct и ListImpl.IntSetStruct)

Наоборот, процедурная абстракция данных (объекты) позволяет вам легко вводить новые реализации, которые работают со старыми. Например, вы можете написать свою собственную реализацию LoggingIntSet и объединить ее с BSTIntSet. Но это компромисс: вы теряете информативные типы для бинарных методов! Зачастую вам приходится раскрывать больше функциональных возможностей и деталей реализации в вашем интерфейсе, чем при реализации ADT. Теперь я чувствую, что перепечатываю эссе Кука, так что читайте!

Я хотел бы добавить пример к этому.

Кук предполагает, что примером абстрактного типа данных является модуль в C. Действительно, модули в C включают в себя сокрытие информации, поскольку существуют открытые функции, которые экспортируются через заголовочный файл, и статические (частные) функции, которые этого не делают. Кроме того, часто встречаются конструкторы (например, list_new ()) и наблюдатели (например, list_getListHead ()).

Ключевым моментом того, что делает, скажем, модуль списка с именем LIST_MODULE_SINGLY_LINKED ADT, является то, что функции модуля (например, list_getListHead ()) предполагают, что вводимые данные были созданы конструктором LIST_MODULE_SINGLY_LINKED, в отличие от любого «эквивалента». "реализация списка (например, LIST_MODULE_DYNAMIC_ARRAY). Это означает, что функции LIST_MODULE_SINGLY_LINKED могут принимать в своей реализации конкретное представление (например, односвязный список).

LIST_MODULE_SINGLY_LINKED не может взаимодействовать с LIST_MODULE_DYNAMIC_ARRAY, потому что мы не можем передать созданные данные, скажем, с помощью конструктора LIST_MODULE_DYNAMIC_ARRAY, наблюдателю от LIST_MODULE_SINGLY_LINKED, поскольку допускает, что LIST_MODULE_DYNAMIC_ARRAY не допускается, поскольку LIST_MODULE_DYNAMIC_AR является объектом, представляющим объект LIST_MODULE_SINGLY_LINK.

Это аналогично тому, как две разные группы из абстрактной алгебры не могут взаимодействовать (то есть вы не можете взять произведение элемента одной группы с элементом другой группы). Это потому, что группы принимают свойство замыкания группы (произведение элементов в группе должно быть в группе). Однако, если мы можем доказать, что две разные группы фактически являются подгруппами другой группы G, то мы можем использовать произведение G для добавления двух элементов, по одному из каждой из двух групп.

Сравнение АДТ и объектов

• Cook связывает разницу между ADT и объектами частично с проблемой выражения, Грубо говоря, ADT связаны с общими функциями, которые часто реализуются в функциональных языках программирования, а объекты связаны с Java-объектами, доступ к которым осуществляется через интерфейсы. Для целей настоящего текста, общая функция является функцией, которая принимает в некоторых аргументах ARGS и типа TYPE (предварительное условие); на основе TYPE он выбирает соответствующую функцию и оценивает ее с помощью ARGS (постусловие). Обе общие функции и объекты реализации полиморфизма, но с родовыми функциями, программист ЗНАЕТ, какая функция будет выполняться с помощью обобщенной функции, не глядя на код обобщенной функции. С объектами, с другой стороны, программист не знает, как объект будет обрабатывать аргументы, если только программисты не посмотрят на код объекта.

• Обычно проблема выражения рассматривается в терминах «у меня много представлений?» против "у меня много функций с небольшим представлением". В первом случае нужно организовать код по представлению (как это обычно происходит, особенно в Java). Во втором случае следует упорядочить код по функциям (т. Е. Иметь одну общую функцию, обрабатывающую несколько представлений).

• Если вы организуете свой код по представлению, то, если вы хотите добавить дополнительную функциональность, вы будете вынуждены добавлять функциональность в каждое представление объекта; в этом смысле добавление функциональности не является «аддитивным». Если вы организовываете свой код по функциональности, то, если вы хотите добавить дополнительное представление - вы вынуждены добавлять представление к каждому объекту; в этом смысле добавление представлений в не «аддитивном».

Преимущество АДЦ над объектами

• Добавление функциональности является аддитивным

• Возможно леверидж знание представления АТДА для исполнения, или доказать, что ADT будет гарантировать некоторое постусловие данного предварительным условием. Это означает, что программирование с АТД обо делать правильные вещи в правильном порядке (выстраивание вместе предварительных условий и постусловия к «цели» после состояния).

Преимущества объектов перед АДЦ

• Добавление представлений в аддитив

• Объекты могут взаимодействовать

• Можно указать до / условия для объекта, и цепь их вместе, как в случае с АТД. В этом случае преимущества объектов заключаются в том, что (1) легко изменять представления без изменения интерфейса и (2) объекты могут взаимодействовать. Тем не менее, это противоречит цели ООП в смысле малой речи. (см. раздел «ООП версия Алана Кея)

Динамическая отправка является ключом к ООП

Теперь должно быть очевидно, что динамическая диспетчеризация (т.е. позднее связывание) необходима для объектно-ориентированного программирования. Это связанно с тем, что можно определить процедуры в общем виде, что не предполагает конкретное представление. Быть конкретным - объектно-ориентированное программирование легко в Python, потому что можно программировать методы объекта так, чтобы не принимать определенное представление. Вот почему Python не нуждается в таких интерфейсах, как Java.

В Java классы являются ADT. однако класс, доступ к которому осуществляется через интерфейс, который он реализует, является объектом.

Приложение: версия ООП Алана Кея

Алан Кей явно упоминал объекты как «семейства алгебр», и Кук предполагает, что ADT является алгеброй. Следовательно, Кей, вероятно, имел в виду, что объект - это семейство ADT. То есть объект - это коллекция всех классов, которые удовлетворяют интерфейсу Java.

Тем не менее, картина предметов, нарисованных Кук, гораздо более ограничительна, чем видение Алана Кея. Он хотел, чтобы объекты вели себя как компьютеры в сети или как биологические клетки. Идея заключалась в том, чтобы применить принцип наименьшей приверженности к программированию, чтобы было легко менять низкоуровневые слои ADT, когда они построены с использованием высокоуровневых слоев. Имея это в виду, интерфейсы Java слишком ограничены, потому что они не позволяют объекту интерпретировать смысл сообщения или даже полностью его игнорировать.

Таким образом, ключевая идея объектов для Кея - не в том, что они представляют собой семейство алгебр (как подчеркивает Кук). Скорее, ключевой идеей Кея было применение модели, которая работала в большом (компьютеры в сети), к малому (объекты в программе).

редактировать: еще одно разъяснение Кей версии ООП: цель объектов состоит в том, чтобы приблизиться к декларативному идеалу. Мы должны сказать объекту, что делать, а не сказать, как с помощью микроуправления является состояние, как это принято в процедурном программировании и ADT. Больше информации можно найти здесь , здесь , здесь и здесь .

редактировать: я нашел очень, очень хорошее изложение определения ООП Алана Кея здесь .

Если вы посмотрите на сторонников ADT, они считают, что ADT будет тем, что ООП будет называть классом (внутреннее, частное состояние; разрешен ограниченный набор операций), но отношения между классами (в основном, без наследования) не рассматриваются. Дело в том, что одно и то же поведение может быть получено в разных реализациях. Например, набор может быть реализован в виде списка, элементов в массиве или хэш-таблице или в виде какого-либо дерева.

Я всегда понимал это так:

1. ADT - это интерфейс: это просто набор методов, их сигнатур типа, возможно, с условиями до и после.

2. Класс может реализовывать один или несколько ADT, предоставляя фактические реализации для методов, указанных в ADT.

3. Объект является экземпляром класса с собственной копией любых нестатических переменных.

Возможно, что в литературе различия различны, но это «стандартная» терминология, которую вы услышите в информатике.

Например, в Java Collectionесть ADT, ArrayListэто класс, и вы можете создать ArrayListобъект с помощью newоператора.

Что касается утверждения, что ADT обычно имеют только одну реализацию, то это часто не так. Например, возможно, вы захотите использовать в своей программе словари как на основе дерева, так и на основе хеш-таблицы, в зависимости от того, что вы храните. Они будут использовать ADT, но будут использовать разные реализации.