Объяснение концепции АТД

[Igor95]

Доброго времени суток, форумчане!
P.S - если я запостил не туда (неверный топик, ветка или еще что), то, пожалйста, переместите

Итак, желание написать этот пост возникло после углубления в концепцию абстрактных типов данных. Я не особо хорошо понимал чем же отличаються АТД от классов. Все же, после долгих размышлений я пришел к неким выводам и объяснениям, которыми, собственно, и хочу поделиться.

Начнем с определения АТД. Наверное лучшее определение АТД дано на википедии).

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

Вопрос: Почему в названии фигурирует именно "тип данных", а не "структура данных"?
Ответ: Потому, что тип данных как таковой определяет именно набор операций и множнство значений, применямых относительно типа данных.

АТД позволяет нам работать на высоком уровне абстрации (а не на низком). Это достигается абстракцией реализации - т.е нам не важно из чего состоит объект, нам важны операции, относительно него. (или так: неважно какой у объекта цвет кожи, важно то какие функции он выполняет).
В книге Стива МакКоннела "Совершенный код" очень хорошо обсуждаются АТД и какую роль они играют при создании класса.
"Совершенный код": При написании очередного класса очень важно подумать о нем как о АТД:
Мое объяснение этого утверждения: нам нужно сосредоточиться над логической группировкой и созданием операций, предоставляемых классом (т.е контракт), вне зависимости от того, какими данными этот класс будет оперировать в будущем (при дальнейшем, детальном проектировании)

Пример из реальной жизни:
Есть строительная компания "OOO как-то там"... создатели этой компании изначально (еще раз: изначально!) определили контракт, который они будут выполнять отосительно своих клиентов. Т.е в этот контракт входят пункты:
- осуществить постройку
- закупка материалов для постройки
- предоставление материалов
- еще что-то
- и что-то еще
Заметьте, что они не думали о персонале или о процессе строительста или о строительных материалов (т.е о том, как будет выполнен контракт), они от этого абстрагировались.
В последствии, создатели компании наймут персонал или уволят кого-то, перестроят структуру управления компанией или создадут филиалы в других странах... но одно останется неизменным: КОНТРАКТ! Конечно, филиалы - это наследники, и они могут дополнять контракт (но не изменять/замещать его! - это уже из области LSP).

Т.е важен контракт, а не низкоуровневая реализация при работе с АТД или его создании.

Так в чем же отличие АТД от класса, зачем понадобилось вводить понятие "АТД", если можно было ограничиться и понятием "класс"?

Во-первых понятие "АТД" возникло задолго до появления понятия "класс". Я считаю, что класс лишь дополнил концепцию АТД.
Дело в том, что при создании класса мы уже по-сути должны были выделить данные, с которыми он будет оперировать и которые ббудут его составлять. В случае с АТД мы концентрировались только на операциях, но не на данных с которыми можно было бы эти операции соотнести. В случае с классом мы уже будем концентироваться и данных и дальнейшем их поддержании, структуризации, построении иерархии классов, определять как будут себя вести объекты отдельного класса из иерархии (полиморфизм). Осталось неизменным и определнным в начале проектирования класса одно: АТД.

Изначально созданный АТД, в последствии, может быть применен для создания классов во множествах отдельных разрабатываемых систем.

Класс = АТД + полиморфизм + наследование. - из книги Стива МакКоннела "Совершенный код".

Выводы:
- Классы дополняют АТД.
- АТД позволяет сосредоточиться на интерфейсе, а не на реализации АТД. Ведь мы думаем об операциях, в первую очередь.
- АТД позволяет работать с высокоуровневыми абстракциями и не задумываться как они реализованы на низком уровне.
- В центре внимания АТД - интерфейс.

P.S - может это и довольно глупо с моей стороны писать пост, посвященный АТД, но здесь я смог выразить свои мысли и премеры относительно этого понятия (не пинайте сильно :-)).
Если у Вас есть какие-нибудь размышления/дополнения/замечания к статье, то пожалуйста, оставьте комментарий.

Спасибо, что прочли.

Дополнительные материалы и использованные источники:
- http://www.cs.iastate.edu/~hridesh/t...p50-liskov.pdf
- Стив МакКоннел - "Совершенный код"

[Igor95]

Итак, мое представление АТД может быть реализовано так:

// ADTConcept.cpp : Defines the entry point for the console application.
//

class ADT_Stack
{
public:
	virtual void push() = 0;
	virtual void pop() = 0;
	virtual void find(const ListElement&) = 0;
};

class ListStack : public ADT_Stack
{
public:
	virtual void push()
	{
		// implementation
	}
	virtual void pop()
	{
		// implementation
	}
	virtual void find(const ListElement& _listElement)
	{
		// implementation
	}
private:
	List m_list;
};

class ArrayStack : public ADT_Stack
{
public:
	virtual void push()
	{
		// implementation
	}
	virtual void pop()
	{
		// implementation
	}
	virtual void find(const ListElement& _listElement)
	{
		// implementation
	}
private:
	ListElement *listElements; // pointer to implement dynamically-allocated array
};

Как видите, интерфейс не меняется, но меняется лишь способ достижения требуемого поведения.

[Utkin]

функций-членов

Это c и c++. Где же абстрагирование ? Вы жестко привязались к языку программирования.

АТД позволяет нам работать на высоком уровне абстракции (а не на низком).

Это капитан Очевидность. Итак ясно что высокий не низкий.

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

Это зависит от уровня субъекта. Кто Вы в данный момент - пользователь АТД или его разработчик. И если Вы разработчик, то для Вас важны все аспекты и структуры данных при проектировании имеют первостепенное значение.

логической группировкой и созданием операций, предоставляемых классом (т.е контракт)

Что за контракт? Давайте подробней.

создатели этой компании изначально

Создатели компании изначально определили структуру подразделений, набрали кадры, выработали определяющие документы типа устава, учетной политики, кадровой политики, набрала таджиков для выполнения черновой работы и т.д. И только после огромной проделанной работы контора готова браться за контракты. Дальше комментировать не стал и так ИМХО ошибка в смещении акцентов налицо и класс и АТД требуют от разработчика уделить внимание типам и структурам данных. Что касается юзеров класса, то тут достаточно инкапсуляции и концепции интерфейсов - пользователь должен знать имя метода и его параметры (то есть опять упираемся в типы данных, а не только в операцию) и ничего более, касательно вызываемого метода. Это общая концепция, она возникла давно и не связана ни с классами ни с АТД. И еще - очень много пишете про полиморфизм, осторожней с ним. Фактически с математической точки зрения он не влияет на алгоритм - скорость реализации остается прежней, сложность алгоритма математически та же самая. Компьютеру без разницы - он выполнит алгоритм что с полиморфизом, что без. С очень большой натяжкой и при грубом приближении полиморфизм можно назвать синтаксическим сахаром - фишкой немного облегчающим жизнь программиста (но только не много, бездумное использование дает отрицательный эффект). Поскольку нет точных критериев, которые могли бы однозначно прогнозировать эффективность полиморфизма, не стоит ставить его в основу разработки. Если у Вас имеется какая-то методика, позволяющая добиваться определенных результатов, требует политика конторы-разработчика или есть готовы шаблоны и ответы на частные случаи, то конечно есть смысл использовать готовые решения. Но без фанатизма там.

[Igor95]

Это c и c++. Где же абстрагирование ? Вы жестко привязались к языку программирования.

Хорошо, давайте назовем их методами. Только вот причем здесь C и C++, да и ввобще любой другой язык. Насколько мне известно, в языках, поддерживающих парадигму ООП, функции, являющиеся членами классов, назваются методами или функциями-членами. Поправьте, если не прав :-)

Что за контракт? Давайте подробней.

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

Вчера, во время дискуссии на тему АТД возник вопрос... а чем же АТД отличается от интерфейса как такового? По версии википедии (ссылка приведена в первом посте) АТД представляется в виде интерфейса. Отсюда, следуя логике, АТД == интерфес. Опять же, если интерфейс является абстракцией реализации класса, то АТД утверждает, что может содержать как данные так и методы, в то время как интерфейс содержит лишь методы.

Правильно ли я понимаю следующее?:
Класс - один из способов воплощения концепции АТД, и кроме того, класс дополняет эту концепцию путем введения иных концепций, таких как полиморфизм и наследование?

P.S - помогите разобраться :-)

[Utkin]

Поправьте, если не прав :-)

В делфи обычно не упоминается функция-член и вообще там и процедуры есть. В с# есть методы класса.
Про остальное - будьте внимательны к мелочам. Класс ничего не добавляет. Добавляет ООП. Далее наследование это свойство структурного программирования. То есть относиться не только к ООП.
АТД это наверно базовые алгоритмы, которые можно применить не только в одной задаче. Где-то переплетается с обобщенным программированием (ИМХО, разумеется).

Класс - один из способов воплощения концепции АТД

Думаю да, в ООП это наверно будет правильно.

[Igor95]

Из википедии:

Класс — разновидность абстрактного типа данных в объектно-ориентированном программировании (ООП), характеризуемый способом своего построения.

Штука в том, что понятие АТД зародилось с появлением понятия модуль.

"В 1972 году была напечатана работа Дэвида Парнаса (David Parnas) [5], в которой впервые был сформулирован принцип разделения программы на модули. Модули – это компоненты программы, которые имеют два важных свойства:

Модули скрывают в себе детали реализации.
Модули могут быть повторно использованы в различных частях программы.
Парнас представлял модули как абстрактные машины, хранящие внутри себя состояния и позволяющие изменять это состояние посредством определенного набора операций. Эта концепция является базовой, как для концепции абстрактных типов данных, так и для объектно-ориентированного программирования.

Понятие абстрактного типа данных впервые в явном виде было сформулировано в совместной работе Стивена Жиля и Барбары Лисков [1]. В разделе «Смысл понятия абстракции» авторы обсуждают, каким образом понятие абстракции может быть применимо к программному коду. Абстракция – это способ отвлечься от неважных деталей и, таким образом, выбрать наиболее важные признаки для рассмотрения. В процессе создания программы разработчик строит программную модель решаемой задачи. В процессе построения программной модели разработчик оперирует элементами этой модели. Программный код структурируется соответствующим образом. Для выделения программных сущностей в коде программы естественно использовать механизм абстракции. В работе Жиля и Лисков рассматривался механизм т.н. поведенческой абстракции или, в терминологии авторов, функциональной абстракции.

Функциональная абстракция подразумевает выделение набора операций (функций) для работы с элементами программной модели. Таким образом, сущности программной модели представляются с помощью набора операций. Так осуществляется поведенческая абстракция сущности в программном коде. Сами авторы исполюзовали термин «operational cluster», т.е. набор операций, и назвали такой набор операций абстрактным типом данных (АТД)."

Это из статьи - http://www.rsdn.ru/article/alg/adt/adt.xml

Отсюда, из последнего аьзацца АТД можно понять как некий способ абстрагирования от данных (т.е их инкапсуляция) и сосредоточения внимания на операциях, что совпадает с определением понятия интерфейс...
Т.е АТД - это попытка аозволяет думать в рамках интерфейса, инкапсулировав (или абстрагировавшись) от данных, которые обеспечивают работу интерфейса.
И получается, что когда говорят, думайте в первую очередь об АТД, а не о классах, то подразумевают, что разработчик должен думать о том как обеспечить такой уровень абстракции, что:
- совокупность методов, составляющих интерфейс АТД, была логически сгруппирована (т.е все методы семантически служили бы одной цели, были бы целостносными).
- не нужно было бы заглядывать в реализацию класса (т.е изучать его поля/свойства) для того, чтобы понять как он работает. иначе астракией такой АТД не будет.
Т.е АТД помогает управлять сложностью путем инкапсуляции деталей реализации АТД (его данных) и тем самым позволив разраьотчику думать в рамках интерфейса, а не АТД в общем.

[Utkin]

Не надо сюда натягивать интерфейс так рьяно . Вы как-то плавно пытаетесь сравнять АТД и интерфейсы. В основе АТД именно работа с данными, в основе интерфейса - способ взаимодействия между программными блоками. Как бы Вы не пытались все смешать это разные вещи. АТД это не вещь в себе это алгоритмы, которые направлены на обработку данных в максимально общем не сцепленном виде.

Т.е АТД - это попытка аозволяет думать в рамках интерфейса, инкапсулировав (или абстрагировавшись) от данных, которые обеспечивают работу интерфейса.

Определитесь со своим статусом. Кто вы в данный момент - разработчик АТД или тот кто будет использовать АТД подключая соответствующие модули в свои программы?

[Igor95]

Определитесь со своим статусом. Кто вы в данный момент - разработчик АТД или тот кто будет использовать АТД подключая соответствующие модули в свои программы?

Разве разработчик не иожет использовать свои АТД после того как их разработал? :-)

Как понять "в не сцепленном виде"?

В википедии сказано, что АТД представляется в виде интерфейсов... Я лишь пытаюсь это как-то с АТД связать...

http://ru.wikipedia.org/wiki/%D0%90%...BD%D1%8B%D1%85

[Utkin]

Как понять "в не сцепленном виде"?

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

Я лишь пытаюсь это как-то с АТД связать...

Слишком рьяно. Ну вот отвлеченный пример - функция тоже имеет интерфейс - то есть имя, оформленное по правилам языка программирования, параметры, правила их описания, порядок следования и пр. АТД это набор методов для работы с какими-то абстрактными данными. Все просто, не надо нагромождать.

Разве разработчик не иожет использовать свои АТД после того как их разработал? :-)

Так можно сказать про любую функцию, не только АТД. Смысл тогда заострять внимание на АТД. Для работы с функцией мне тоже пофигу как она там работает - умножает или использует сдвиг байтов вправо\влево. Инкапсуляция однако. Я просто шлю параметр и читаю результат. Как видите никакой разницы - так зачем тогда писать про это?

[Igor95]

Слишком рьяно. Ну вот отвлеченный пример - функция тоже имеет интерфейс - то есть имя, оформленное по правилам языка программирования, параметры, правила их описания, порядок следования и пр. АТД это набор методов для работы с какими-то абстрактными данными. Все просто, не надо нагромождать.

Если АТД - это набор методов, то это и есть интерфейс. Дело в том, что в языках программирования: C#, Java, C++ интерфейсы обычно представляются в виде набора методов, четко согласующихся друг с другом. Интерфейсы не содержат данные, с которыми методы интерфейса должны взаимодействовать.
Это противоречит определению АТД:
АТД - набор данны и операций над ними....