LINUX.ORG.RU

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

 


0

1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



Последнее исправление: thomasreese (всего исправлений: 1)

Мое мнение: правильно написанный класс является реализацией принципов АТД. И не более того. По-моему, ты слишком заморачиваешься на этот счет. Главное, это понять суть идеи.

kovrik ★★★★★
()

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

Да, причём на английской:

In computer science, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects (and possibly cost) of those operations.

Тему можно закрывать.

Deleted
()
Ответ на: комментарий от Deleted

погодите, не закрывайте. Остался только этот вопрос: ГЛАВНЫЙ ВОПРОС?: Правильно ли я понимаю следующее?: Класс - один из способов воплощения концепции АТД, и кроме того, класс дополняет эту концепцию путем введения иных концепций, таких как полиморфизм и наследование?

thomasreese
() автор топика

Если достаточно сильно зациклиться на простом понятии, то получится концепция.

const86 ★★★★★
()
Ответ на: комментарий от const86

меня больше интересует концепция АТД, а не понятие «концепция» ;-)

thomasreese
() автор топика

АТД — это: типы как объекты, каррированные функции как стрелки, HOFs как экспоненциалы, чистота, ссылочная прозрачность, аппликативность и свободные (при совпадении доменов-кодоменов) композиции, equational theory settings / reasoning как следствие, в терминах ТК, в том числе, начальные алгебры / финальные ко-алгебры как фреймворк для описания индуктивных рекурсивных данных (как выход - результаты, значения) и ко-индуктивных ко-рекурсивных потоков данных (как вход); функторы, монады, Kleisli категории - многие индуктивные [возможно] рекурсивные типы данных которые функторы (начиная с Identity, Maybe и List), также, обычные суммы, произведения и степени, то есть кортежи/записи, объединения/варианты и функции - writer, error и reader/environment, для функций более специального вида - prompt, parser, state и cont, par/conc/async как cont для fork/join/io/done языка; функторы, ко-монады, coKleisli категории - ко-индуктивные ко-рекурсивные типы данных которые функторы (простейшие потоки и деревья, например), те же произведения и степени (суммы?), указатели и изменяемые подструктуры (линзы, как функции в), зипперы; свободные монады вокруг типов данных которые функторы - iteratees (которые сами по себе потоки, то есть финальные коалгебры для соответвующих (строго-позитивных таки) функторов), разные языки (eDSL на ADT) и их интерпретаторы; ко-свободные ко-монады для типов данных которые функторы - ?; (под)категории и стрелки - линзы (категория, тензор, но не вполне стрелка), обычные функции, Kleisli стрелки, coKleisli стрелки, стрелки biKleisli категорий, функции ограниченные типом - списки-в-списки, потоки-в-потоки, деревья-в-деревья, сигналы-в-сигналы и поведения-в-поведения (как оно применяется в FRP) и т.п., автоматы, симуляции, преобразователи, некоторые языки-eDSL-на-ADT, опять же; монадические трансформеры как определённого вида натуральные трансформации для определённого вида функторов над разными монадами - WriterT, ErrorT, ReaderT, StateT, ContT, MaybeT, ListT и т.д., например, ReaderT (ConstEnvironment, MutableScope, Resources) IO - эффекты, injectable read-only / write окружение, список ресурсов пополняемый их захватами по мере выполнения и автоматически освобождаемый в конце; полугруппы, моноиды, сворачиваемые и обходимые типы и т.п. категорные и алгебраические типы и классы как «паттерны» и средства декомпозиции.

anonymous
()

Завтра ищешь в интернете книжку Dive into python. Похуй если ничего не поймешь. Затем идешь на python.org и изучаешь стандартную библиотеку от корки до корки. Потом зубришь, именно, сука, вызубриваешь конвенцию по написанию питоньего кода - PEP8, чтобы от зубов отскакивало. Когда напишешь свою первую имиджборду, по пути изучив верстку на html+css, скачиваешь и изучаешь любой питоний асинхронный вебсервер, рекомендую Tornado или Gevent. Как переделаешь имиджборду, чтобы выдавала по крайней мере 5 тысяч запросов в секунду, можешь идти дальше - тебя ждет увлекательный мир хайлоада. Apache Hadoop, сверхбыстрые асинхронные key-value хранилища, MapReduce. Отсос хиккующих выблядков / просто неудачников типа рейфага или сисярп/джава-хуесосов, которые сосут хуй по жизни не заставит себя ждать и уже через пол года ты будешь получать такие суммы, что любая баба будет течь при одном упоминании твоей зарплаты.

anonymous
()

Всё просто - АТД - это ковариантные функторы, анафорические макросы, пандорические захваты, кластеры метапарадигм, катаморфизмы, эпиморфизмы, анаморфизмы, параморфизмы наконец

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.