Абстрактный тип данных Общие положения о данных Абстрактный тип данных общие положения спецификация, представление, реализация 1
Что такое данные? Набор различных информационных объектов, над которыми выполняются те или иные действия операторами программы, называются данными. Данные - непременный атрибут любой программы. Ими могут быть: - отдельные биты; - последовательность независимых битов; -числа в разных формах представления; -байты и группы независимых байтов; -массивы чисел; -связные списки; -отдельные файлы и системы файлов. 2
Универсальное представление этого многообразия данных сложно и нецелесообразно Целесообразно разделить их на типы 3
Что такое тип данных? Тип данных определяется: – Форматом представления в памяти компьютера по определенным соглашениям алгоритмического языка, но без необходимости вычислений; – Множеством допустимых значений, которые может принимать принадлежащая к выбранному типу переменная или константа; – Множеством допустимых операций, применимых к этому типу. 4
Примеры типов данных Целочисленные типы Вещественный тип Логический тип Символьный тип Перечисляемый тип Интервальный тип Указатели 5
Целочисленные типы имеется пять предопределенных целочисленных типов: Shortint, Integer, Longint, Byte и Word. Каждый тип обозначает определенное подмножество целых чисел. Значение одного целочисленного типа может быть явным образом преобразовано к другому целочисленному типу с помощью приведения типов. 6
Вещественный тип К вещественному типу относится подмножество чисел, представляемых в формате с плавающей точкой и с фиксированным числом цифр. Запись значения в формате с плавающей запятой обычно включает три значения - m, b и e - таким образом, что m * b ^ e = n, где b всегда равен 2, а m и e являются целочисленными значениями в диапазоне вещественного типа. Эти значения m и e далее определяют диапазон представления и точность вещественного типа. Пример: 0. 143 E+22, где m - 0. 143; b=2(подразумевается), e=22. Имеется пять видов вещественных типов: вещественное (Real), с одинарной точностью (Single), с двойной точностью (Double), с повышенной точностью (Extended) и сложное (Comp). 7
Логический тип Существует 4 предопределенных логических (булевских) типа: Boolean, Byte. Bool, Word. Bool и Long. Bool. Значения булевского типа обозначаются встроенными идентификаторами констант False и True. Логические переменные могут использоваться для хранения результатов каких - либо логических вычислений. Для булевых переменных разрешены только 2 операции сравнения "="(равно) и ""(неравно). 8
Символьный тип Множеством значений этого типа являются символы, упорядоченные в соответствии с расширенным набором символов кода ASCII. Это буквы ["A". . . "Z", "a". . . "z"], цифры ["0". . . "9"], знаки препинания и специальные символы. Переменная этого типа в памяти занимает один байт. 9
Перечисляемый тип Перечислимые типы определяют упорядоченные множества значений через перечисление идентификаторов, которые обозначают эти значения. Упорядочение множеств выполняется в соответствии с последовательностью, в которой перечисляются идентификаторы. Type Week = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday); 10
Интервальный тип Интервальный тип представляет собой диапазон значений из порядкового типа. Определение интервального типа включает наименьшее и наибольшее значение в поддиапазоне. Type Interval = 0. . . 1000; Такая декларация типа указывает компилятору, что для переменных этого типа допустимы только числа из указанного диапазона. Тем самым в программе могут быть автоматически организованы проверки корректности операций присвоения для этих переменных. 11
Общее для типов данных Каждому из типов данных соответствует множество простых операций. INTEGER-операции +, -, *, div, mod REAL - операции + , -, *, / BOOLEAN- операции - конъюнкция (и), дизъюнкция V (или), отрицание (не) CHAR-операции ORD (с) -N: (С в ASCII), CHR (I) I -тый символ в ASCII По мере возрастания объемов и сложности представления информации возникает необходимость в удобных формах ее представления, хранения и обработки. 12
Определение абстрактный тип данных (АТД или abstract data type, или ADT), - это множество абстрактных объектов, представляющих элементы данных, и определенные на нем наборы операций, которые могут быть выполнены над элементами этого множества. 13
АТД – обобщение типов данных Абстрактные типы данных (АТД) можно рассматривать как средство расширения языков программирования. Сравним абстрактный тип данных с таким знакомым понятием, как процедура. Процедуру можно рассматривать как обобщённое понятие оператора. Две характерные особенности процедур – обобщение и инкапсуляция, отлично характеризуют абстрактные типы данных. АТД можно рассматривать как обобщение простых типов данных (целых, действительных и т. д.), точно также как процедура является обобщением простых операторов (+, - и т. д.) 14
Преимущества АТД Абстрактные структуры данных предназначены для удобного хранения и доступа к информации. Они предоставляют удобный интерфейс для типичных операций с хранимыми объектами, скрывая детали реализации от пользователя. Конечно, это весьма удобно и позволяет добиться большей модульности программы. 15
Пример Для автоматизированного управления температурой в различных комнатах большого здания полезным АТД был бы ТЕРМОСТАТ. В программе может быть много переменных типа ТЕРМОСТАТ, соответствующих реальным термостатам в различных помещениях здания. АТД может быть описан своим именем, множеством значений и допустимыми операциями так же, как и любой другой тип данных. Описание для типа ТЕРМОСТАТ: – Тип данных: ТЕРМОСТАТ – Область значений: температура может изменяться в диапазоне от 0 до 50 градусов (по Цельсию). – Операции: Выше, Ниже, Установить, Проверить, Тревога. (Можно придумать много полезных операций, но слишком большое их количество ухудшает абстракцию) 16
Уровни абстракции Уровни абстракции напоминают слои программного обеспечения. Высшие уровни абстракции отражают представление пользователя о решении задачи. Нижние уровни абстракции – возможности языка программирования. 17
Пример абстракции на уровне пользователя Архитектор представляет дом в виде стен, полов, окон, дверей и т. д. В этом случае тип данных Рисунок. Двери мог бы стать хорошим абстрактным типом. Тип данных: Рисунок. Двери Операции: Рисовать. Дверь Стереть. Дверь Рисовать. Двойную. Дверь ……. Рисунок. Двери являются абстракцией высокого уровня, отражающего взгляд пользователя на проблему 18
Пример абстракции на уровне программиста Программист может предложить другой уровень абстракции для этих объектов, например, прямоугольник. Тип данных: Прямоугольник Операции: Рисовать. Прямоугольник Стереть. Прямоугольник Разделить. Прямоугольник. На. Части ……. Прямоугольник – абстракция более низкого уровня, поскольку она ближе к реализации. 19
Конструкторы АТД Каждый АТД должен содержать операции построения значений своего типа. Такие операции называются конструкторами. Конструкторов должно быть достаточно для порождения всего множества значений данного типа. АТД, удовлетворяющий этому свойству, называется полным. Неполный АТД – ошибка проектирования. 20
Рекомендации к выбору операций абстрактного типа данных Целесообразно включение следующих операций: – операции-конструкторы, – операции проверки, – операции преобразования типов, – операции ввода-вывода, – операции копирования, – операции-селекторы. Постарайтесь свести к минимуму число операций. Простой АТД легче понять. Поддерживайте связь операций с выбранной абстракцией типа. 21
Первичный конструктор Операции, создающие новые значения АТД вне зависимости от его предшествующего значения, называются первичными конструкторами. Каждый АТД включает по меньшей мере один первичный конструктор: без него невозможно сформировать начальное значение. 22
Использование скрытых типов Абстрактные типы данных лучше объявлять в виде скрытых типов. Это позволяет переместить описание структуры данных в модуль реализации, где оно преимущественно используется. Они также обеспечивают возможность предотвращения прямого доступа к компонентам типа со стороны импортера. Поскольку скрытый тип всегда реализуется с помощью указателя, то в АТД должны быть включены три операции. – Создать - операция, создающая узел соответствующей структуры. – Уничтожить - операция по освобождению памяти узла скрытого типа. – Присвоить - операция копирования полей динамической структуры узла скрытого типа. 23
Что такое спецификация и реализация у абстрактного типа данных Абстрактный тип данных - это способ определения некоторого понятия в виде класса объектов с некоторыми свойствами и операциями. В языке программирования такое определение оформляется как специальная синтаксическая конструкция, называемая в разных языках капсулой, модулем, кластером, классом, пакетом, формой и т. д. Эта конструкция в самой развитой форме содержит: спецификацию типа данных, включающую описание интерфейса (имя определяемого типа, имена операций с указанием их профилей) и абстрактное описание операций и объектов, с которыми они работают, некоторыми средствами спецификации; реализацию типа данных, включающую конкретное описание тех же операций и объектов. 24
Классификация типов данных по способу описания и защиты пакетированный, если описание типа данных собрано в одном месте (в одном пакете), т. е. его объекты и операции объединены в одно понятие; он имеет определение, которое может содержать, однако, лишь его реализацию; инкапсулированный, если тип данных пакетированный, его определение содержит описание интерфейса и реализацию, а также предусмотрена инкапсуляция реализации; абстрактный, если тип данных инкапсулированный и его спецификация включает абстрактное описание. 25
Составляющие спецификации Программирование, как процесс, начинается с постановки задачи (ее определения), или спецификации задачи. Далее повсеместно в тексте используются спецификации, состоящие из шести составляющих: – Название - название решаемой задачи; – Описание - несколько предложений, описывающих суть задачи; – Вход - детальное описание предполагаемой формы входных данных; – Выход - детальное описание предполагаемой формы выходных данных; – Ошибки - подробный список ситуаций, возникающих при неправильных входных данных; – Пример - пример выполнения в терминах вход-выход. 26
П р и м е р спецификации Абстрактный тип данных СТЕК, реализующий широко известную структуру данных, которая характеризуется тем, что в нее можно "поместить" некоторый элемент и "выбрать" из нее элемент, помещенный туда самым последним. Синтаксическая часть спецификации типа данных СТЕК имеет вид type СТЕК specification is СОЗДАТЬ: function () return (@); ВСТАВИТЬ: function (integer; @) return (@); УДАЛИТЬ: function (@) return (@); ВЕРШИНА: function (@) return (integer); ПУСТ: function (@) return (boolean); end specification; Здесь операция СОЗДАТЬ выдает в качестве результата пустой стек, ВСТАВИТЬ - стек с добавленным на "верх" его элементом, УДАЛИТЬ - стек с удаленным "верхним" элементом, ВЕРШИНА - значение "верхнего" элемента стека, ПУСТ - признак пустоты стека. Элементами стека здесь могут быть только целые числа. 27
РЕАЛИЗАЦИЯ АБСТРАКТНОГО ТИПА ДАННЫХ Реализацию удобнее делать с помощью объектноориентированных языков программирования, таких как C++ или Java, в которых абстрактные типы данных поддерживаются с помощью классов Реализация АТД включает конкретное описание объектов определяемого типа и реализацию операций этого типа. Это означает, что объекты описываются либо как данные простых типов, либо как массивы, записи или объединения. Причем используются предопределенные типы данных или АТД, определенные ранее. Реализация операций состоит в описании подпрограмм, выполняющих необходимые действия с указанными объектами. Например операции +, *, =. . и т. п, но при этом скрывается сама реализация этих операций. 28
Абстрактным принято называть тип данных, в явном виде не имеющийся в языке программирования, в этом смысле это понятие относительное - тип данных, отсутствующий в одном языке программирования, может присутствовать в другом.
Абстрактный тип данных (АТД) определяется независимо от способа его реализации:
множеством возможных значений этого типа,
и набором операций со значениями этого типа.
Использование АТД может быть ограничено этапом разработки программного обеспечения, но для его явного использования в программе надо иметь его реализацию на основе уже имеющихся (и ранее реализованных) типов данных в языке программирования:
способ представления значений этого типа,
и реализацию операций со значениями этого типа.
АТД не является предопределенным в языке программирования, и даже более того – операции конструирования таких типов, предопределенные в языке, перекладывают на разработчика-программиста вопрос о способе представления значений такого типа и реализации операций со значениями этого типа. А потому, для таких типов данных вопрос о выборе определений и способов реализации операций вида конструктор (значений и хранилищ данных) такого типа, селектор и модификатор компонентов (значений и хранилищ данных) такого типа возлагается на разработчика-программиста.
В концепции АТД особый статус имеют понятия интерфейс , открытый пользователю, и реализация , скрытая от него. Особая роль этих понятий в концепции АТД связана с основополагающим положением о независимости понятия АТД от способа его реализации.
В современных «практических языках программирования» для конструирования АТД обычно используется предопределенная операция конструирования типов class , которая дает разработчику-программисту не только средства группировки данных и операций (с этими данными) в единое целое, но и средства инкапсуляции, наследования и полиморфизма для управления способами конструирования и доступа к таким данным. Отметим, что класс описывает одну возможную реализацию АТД, отображение класса в АТД выражается функцией абстракции, но обратное отношение, обычно, не является функциональным, реализаций одного и того же АТД может быть несколько.
В исследованиях по абстрактным типам данных уже на раннем этапе была осознана важная роль понятия «параметризация типа ». Действительно, например АТД «Стек» не зависит от типа элементов стека, но реализовать этот АТД указанием на «элементы какого-то одинакового типа» невозможно. В язык программирования Ada соответствующие средства конструирования параметризованных типов данных были включены изначально, а в современных «практических языках программирования» какие средства появились только со времен появления разработки по STL-библиотеке . На сегодня понятие «обобщенное программирование» занимает значимое положение в практическом программировании благодаря включению в «практические языки программирования» средств конструирования параметризованных типов данных (шаблоны, template , generic) .
Всё вышесказанное означает, что с методологической и теоретической точки зрения необходимо более детальное точное определение понятия «абстрактный тип данных». В теории понятие «абстрактный тип данных» обычно определяется как многосортная (многоосновная) алгебраическая система , в которой дополнительно к множеству возможных значений (носителю) и набору операций над такими значениями выделены понятия:
Сорт и сигнатура – эти понятия позволяют расклассифицировать и элементы носителя и операции с ними по их типам (для операций - по типам их аргументов и возвращаемого значения).
Предикаты – отношения на элементах носителя. Это позволяет определять область возможных значений наложением ограничений (требований) на допустимые значения, а также в естественной трактовке работать с произвольными логическими выражениями, не принуждая интерпретировать их как функции принадлежности для множеств или как многозначные операции.
На такой основе можно рассматривать абстрактные типы данных с единой целостной логико-алгебраической точки зрения, включая вопросы о конструкторах (типов и значений), селекторах и модификаторах свойств для объектов такого типа .
Понятия «структура данных» и «абстрактный тип данных» в чем-то очень близкие. Можно конечно считать, что эти понятия - просто два взгляда на одно и то же. Способ представления значений АТД всегда основан на некоторой структуре данных, менее или более сложной, и реализация операций с такими значениями естественно зависит от этой выбранной структуры данных. С другой стороны, заинтересовавшую нас структуру данных при большом желании мы всегда можем оформить как АТД.
Но все же мы будем различать эти два понятия, учитывая:
Абстрактный тип данных - подразумевает определенный уровень абстрагирования с целью фиксации прикладного (предметно-ориентированного) типа данных безотносительно к способам его реализации, и возможно включения этого типа данных в прикладную библиотеку, ну хотя бы для конкретной разработки конкретной программной системы. АТД может иметь несколько альтернативных реализаций, основанных на различных структурах данных.
Структура данных - скорее некоторая схема организации данных и управления ими, которая предполагает соответствующие конкретизации при ее использовании в конкретных ситуациях при решении конкретных задач.
К абстрактным типам данных прежде всего естественно относятся математические базовые алгебраические системы – последовательности, множества, отношения и отображения (функциональные отношения, функции) . Но в программировании на переднем плане не исследование общих свойств этих математических понятий, а возможности их использования в разработке моделей решения задач предметной области, алгоритмов решения этих задач и эффективной реализации разработанных алгоритмов. А потому в программировании в виде АТД обычно оформляются с одной стороны ограниченные варианты этих базовых алгебраических систем, а с другой стороны расширенные специализированными наборами операций, представляющими прагматический интерес с точки зрения области применения.
Доброго времени суток, хабравчане!
Следующий пост является изложением моих размышлений на тему природы классов и АТД. Эти размышления дополнены интересными цитатами из книг гуру разработки программного обеспечения
Введение
Начнем с того, что плавно подойдем к определению АТД. АТД, в первую очередь, представляет собой тип данных, что означет следущее:наличие определенных доступных операций над элементами этого типа;
а также данные, относительно которых эти операции выполняются (диапазон значений).
Что же означает слово “абстрактный”? В первую очередь понятие “абстрактность” означет сосредоточение внимания на чем-то важном и, при этом, нам нужно отвлечься от неважных, на данный момент, деталей. Определение абстрактности хорошо раскрыто в книге Гради Буча (“Grady Booch”). Звучит определение так:
Абстракция – это выделение и придание совокупности объектов общих свойств, которые определяют их концепутальные границы и отличают от всех других видов объектов.
Иными словами, абстракция позволяет “пролить свет” на нужные нам данные объектов и, при этом, “затенить” те данные, которые нам не важны.
Итак, что же будет, если слить понятия “тип данных” и “абстракция” воедино? Мы получим тип данных, который предоставляет нам некий набор операций, обеспечивающих поведение объектов этого типа данных, а также этот тип данных будет скрывать те данные, с помощью которых реализовано данное поведение. Отсюда, приходим к понятию АТД:
АТД – это такой тип данных, который скрывает свою внутреннюю реализацию от клиентов.
Удивительно то, что путем применения абстракции АТД позволяет нам не задумываться над низкоуровневыми деталями реализации, а работать с высокоуровневой сущностью реального мира (Стив Макконнелл).
Я считаю, что при разработке АТД сначала нужно определить интерфейс, так как интерфейс не должен зависеть от внутреннего представления данных в АТД. После определения операций, сотставляющих интерфейс, нужно сосредоточиться на данных, которые и будут реализовать заданное поведение АТД. В итоге мы получим некую структуру данных – механизм позволяющий хранить и обрабатывать данные. При этом, прелесть АТД в том, что если нам захочется изменить внутренне представление данных, то нам не придется блуждать по всей программе и менять каждую строку кода, которая зависит от данных, которые мы хотим поменять. АТД инкапсулирует эти данные, что позволяет менять работу объектов этого типа, а не всей программы.
Преимущества АТД
Использование АТД имеет массу преимуществ (все описанные преимущества можно найти в книге Стива Макконнелла «Совершенный код”):
- Инкапсуляция деталей реализации.
Это означает, что единожды инкапсулировав детали реализации работы АТД мы предоставляем клиенту интерфейс, при помощи которого он может взаимодействовать с АТД. Изменив детали реализации, представление клиентов о работе АТД не изменится.
- Снижение сложности.
Путем абстрагирования от деталей реализации, мы сосредатачиваемся на интерфейсе, т.е на том, что может делать АТД, а не на том как это делается. Более того, АТД позволяет нам работать с сущностью реального мира.
- Ограничение области использования данных.
Используя АТД мы можем быть уверены, что данные, представляющие внутреннюю структуру АТД не будут зависеть от других участков кода. При этом реализуется “независимость” АТД.
- Высокая информативность интерфейса.
АТД позволяет представить весь интерфес в терминах сущностей предметной области, что, согласитесь, повышает удобочитаемость и информативность интерфейса.
Стив Макконнелл рекомендует представлять в виде АТД низкоуровнеые типы данных, такие как стек или список. Спросите себя, что представляет собой этот список. Если он представляет список сотрудников банка, то и рассматривайте АТД как список сотрудников банка.
Итак, мы разобрались, что такое АТД и назвали преимущества его применения. Теперь стоит отметить, что при разработке классов в ООП следует думать, в первую очередь, об АТД. При этом, как сказал Стив МакКоннелл, Вы программируете не на языке, а с помощью языка. Т.е Вы будете программировать выходя за рамки языка, не ограничиваясь мыслями в терминах массивов или простых типов данных. Вместо этого Вы будете думать на высоком уровне абстракции (например, в терминах электронных таблицах или списков сотрудников). Класс – это не что иное как дополнение и способ реализации концепции АТД. Мы можем даже представить класс в виде формулы:
Класс = АТД + Наследование + Полиморфизм.
Так почему же следут думать об АТД, при разработке классов. Потому что, сперва мы должны решить какие операции будут составлять интерфейс будущего класса, какие данные скрыть, а к каким предоставить открытый доступ. Мы должны подумать об обеспечении высокой информативности интерфейса, легкости оптимизации и проверки кода, а также о том, как бы нам предоставить правильную абстракцию, чтобы можно было думать о сущностях реального мира, а не о низкоуровнеых деталях реализации. Я считаю, что именно после определения АТД мы должны думать о вопросах наследования и полиморфизма.
Стоит отметить, что концепция АТД нашла гирокое применение в ООП, т.к именно эта концепция дополняет ООП и позволяет уменшить сложность программ в быстроменяющемся мире требований к ПО.
Данную статью я писал для того, что бы обратить внимание разработчиков на АТД с целью повышения качества работы и разработки программного обеспечения.
Использованные источники:
Стив Макконнелл – “Совершенный код”;
Роберт Седжвик – «Алгоритмы на Java».
Все встроенные типы данных, являются абстрактными, хотя так их называют редко.
Понятие абстракции
Абстракция - это суждение или представление о некотором объекте, которое содержит только свойства, являющиеся существенными в данном контексте. Абстракция позволяет объединять экземпляры объектов в группы, внутри которых общие свойства объектов можно не рассматривать, т.е. абстрагироваться от них. Абстракция - это эффективное средство против сложности программирования, позволяющее программисту сосредоточиться на существенных свойствах объектов. Виды абстракций: абстракция процесса и абстракция данных .
Абстракция процесса. Все подпрограммы являются абстракциями процессов, они определяют способ, с помощью которого программа устанавливает, что необходимо выполнить некоторый процесс, без уточнения деталей того, как именно это следует сделать. Возможность абстрагироваться от многочисленных деталей алгоритма, который выполняется подпрограммой, позволяет создавать, читать и понимать большие программы. Любой абстракции данных являются операции, определяемые как абстракции процессов.
Абстракция данных. Абстрактный тип данных - это инкапсуляция, которая содержит только представления данных одного конкретного типа и подпрограммы, которые выполняют операции с данными этого типа. С помощью управления доступом несущественные детали описания типа можно скрыть от внешних модулей, которые используют такой тип. Программные модули, которые используют абстрактный тип данных, могут объявлять переменные этого типа, даже несмотря на то, что реальное представление типа скрыто от них. Экземпляр абстрактного типа данных называется объектом.
Причина создания абстракции типа данных и абстракции процесса - это средство против сложности, способ сделать большие и/или сложные программы более управляемыми.
Инкапсуляция
Разделение программы на синтаксические контейнеры, которые содержат группы логически связанных подпрограмм и данных. Эти синтаксические контейнеры называются модулями, а процесс их разработки- модуляризацией.
Составление программы из наборов подпрограмм и данных, каждый из которых можно компилировать отдельно, без повторной компиляции остальной части программы. Такой набор называется единицей компиляции.
Инкапсуляция - это способ объединения в единое целое подпрограмм и данных, которые они обрабатывают. Инкапсуляция, которая компилируется либо отдельно, либо независимо от других, является основой абстрактной системы и логической организации набора соответствующих вычислений.
Абстрактные типы данных, определяемые пользователем
Абстрактные типы данных, определяемые пользователем, должны иметь следующие свойства:
1) определение типа, позволяющее программным модулям объявлять переменные этого типа, создавая при этом реальное представление этих переменных в памяти.
2) набор операций для манипуляций с объектами данного типа.
Формальное определение абстрактного типа данных в контексте типов, определенных пользователем: абстрактный тип данных - это тип данных, который удовлетворяет следующим двум условиям.
Представление (определение типа) и операции над объектами данного типа содержатся в одной синтаксической единице, переменные данного типа можно создавать и в других модулях.
Представление объектов данного типа скрыто от программных модулей, использующих этот тип, над объектами можно производить операции, которые прямо предусмотрены в определении типа.
Упаковка представления типа и операций в отдельную синтаксическую единицу, позволяет организовывать программу в виде логических единиц, которые можно компилировать отдельно. Во-вторых, появляется возможность модифицировать представления объектов данного типа или операции с ними в отдельной части программы. У сокрытия деталей представления типа есть преимущества. Клиенты не могут "видеть" детали представления объектов, и их код не зависит от этого представления. Таким образом, представления объектов можно изменять в любое время, не требуя при этом вносить изменения в код клиентов. Другим очевидным и важным преимуществом сокрытия информации является повышенная надежность. Клиенты не могут непосредственно изменять основные представления объектов ни преднамеренно, ни случайно, следовательно, возрастает целостность таких объектов. Объекты можно изменять только с помощью предусмотренных для этого операций.
Вопросы разработки типов
Должна существовать возможность делать имя типа и заголовки подпрограмм видимыми в клиентах абстракции. Это позволяет клиентам объявлять переменные абстрактного типа и манипулировать их значениями. Несмотря на то что имя типа должно быть видимым извне, его определение должно быть скрыто.
Существует очень мало общих встроенных операций, которые можно выполнять с объектами абстрактных типов, в отличие от операций, предусмотренных определением типа. К таким операциям относятся присваивания, а также проверки равенства и неравенства. Если язык не позволяет пользователям перегружать операцию присваивания, то она должна быть встроенной. Проверки равенства и неравенства в одних случаях должны быть заранее определены, а в других - нет. Разработчик типа должен определить операции для большинства абстрактных типов данных сам.
Языки Smalltalk, C++ и Java непосредственно поддерживают абстрактные типы данных.
Абстрактные типы данных в языке C++
Языки Ada и Modula-2 обеспечивают инкапсуляцию, которая может использоваться при моделировании абстрактных типов данных, в языке C++ введено понятие класса, который непосредственно поддерживает абстрактные типы данных. В языке C++ классы - это типы, а пакеты языка Ada и модули языка Modula-2 типами не являются. Пакеты и модули импортируются, позволяя импортирующей программной единице объявлять переменные любого типа, определенного в пакете или модуле. В программе на языке C++ переменные объявляются как сущности, имеющие тип данного класса. Таким образом, классы гораздо больше похожи на встроенные типы, чем пакеты или модули. Программная единица, которая видит пакет в языке Ada или модуль в языке Modula-2, имеет доступ к любым открытым сущностям просто по их именам. Программная единица на языке C++, которая объявляет экземпляр класса, также имеет доступ к любым открытым сущностям в этом классе, но только через экземпляр этого класса.
Доброго времени суток, хабравчане!
Следующий пост является изложением моих размышлений на тему природы классов и АТД. Эти размышления дополнены интересными цитатами из книг гуру разработки программного обеспечения
Введение
Начнем с того, что плавно подойдем к определению АТД. АТД, в первую очередь, представляет собой тип данных, что означет следущее:наличие определенных доступных операций над элементами этого типа;
а также данные, относительно которых эти операции выполняются (диапазон значений).
Что же означает слово “абстрактный”? В первую очередь понятие “абстрактность” означет сосредоточение внимания на чем-то важном и, при этом, нам нужно отвлечься от неважных, на данный момент, деталей. Определение абстрактности хорошо раскрыто в книге Гради Буча (“Grady Booch”). Звучит определение так:
Абстракция – это выделение и придание совокупности объектов общих свойств, которые определяют их концепутальные границы и отличают от всех других видов объектов.
Иными словами, абстракция позволяет “пролить свет” на нужные нам данные объектов и, при этом, “затенить” те данные, которые нам не важны.
Итак, что же будет, если слить понятия “тип данных” и “абстракция” воедино? Мы получим тип данных, который предоставляет нам некий набор операций, обеспечивающих поведение объектов этого типа данных, а также этот тип данных будет скрывать те данные, с помощью которых реализовано данное поведение. Отсюда, приходим к понятию АТД:
АТД – это такой тип данных, который скрывает свою внутреннюю реализацию от клиентов.
Удивительно то, что путем применения абстракции АТД позволяет нам не задумываться над низкоуровневыми деталями реализации, а работать с высокоуровневой сущностью реального мира (Стив Макконнелл).
Я считаю, что при разработке АТД сначала нужно определить интерфейс, так как интерфейс не должен зависеть от внутреннего представления данных в АТД. После определения операций, сотставляющих интерфейс, нужно сосредоточиться на данных, которые и будут реализовать заданное поведение АТД. В итоге мы получим некую структуру данных – механизм позволяющий хранить и обрабатывать данные. При этом, прелесть АТД в том, что если нам захочется изменить внутренне представление данных, то нам не придется блуждать по всей программе и менять каждую строку кода, которая зависит от данных, которые мы хотим поменять. АТД инкапсулирует эти данные, что позволяет менять работу объектов этого типа, а не всей программы.
Преимущества АТД
Использование АТД имеет массу преимуществ (все описанные преимущества можно найти в книге Стива Макконнелла «Совершенный код”):
- Инкапсуляция деталей реализации.
Это означает, что единожды инкапсулировав детали реализации работы АТД мы предоставляем клиенту интерфейс, при помощи которого он может взаимодействовать с АТД. Изменив детали реализации, представление клиентов о работе АТД не изменится.
- Снижение сложности.
Путем абстрагирования от деталей реализации, мы сосредатачиваемся на интерфейсе, т.е на том, что может делать АТД, а не на том как это делается. Более того, АТД позволяет нам работать с сущностью реального мира.
- Ограничение области использования данных.
Используя АТД мы можем быть уверены, что данные, представляющие внутреннюю структуру АТД не будут зависеть от других участков кода. При этом реализуется “независимость” АТД.
- Высокая информативность интерфейса.
АТД позволяет представить весь интерфес в терминах сущностей предметной области, что, согласитесь, повышает удобочитаемость и информативность интерфейса.
Стив Макконнелл рекомендует представлять в виде АТД низкоуровнеые типы данных, такие как стек или список. Спросите себя, что представляет собой этот список. Если он представляет список сотрудников банка, то и рассматривайте АТД как список сотрудников банка.
Итак, мы разобрались, что такое АТД и назвали преимущества его применения. Теперь стоит отметить, что при разработке классов в ООП следует думать, в первую очередь, об АТД. При этом, как сказал Стив МакКоннелл, Вы программируете не на языке, а с помощью языка. Т.е Вы будете программировать выходя за рамки языка, не ограничиваясь мыслями в терминах массивов или простых типов данных. Вместо этого Вы будете думать на высоком уровне абстракции (например, в терминах электронных таблицах или списков сотрудников). Класс – это не что иное как дополнение и способ реализации концепции АТД. Мы можем даже представить класс в виде формулы:
Класс = АТД + Наследование + Полиморфизм.
Так почему же следут думать об АТД, при разработке классов. Потому что, сперва мы должны решить какие операции будут составлять интерфейс будущего класса, какие данные скрыть, а к каким предоставить открытый доступ. Мы должны подумать об обеспечении высокой информативности интерфейса, легкости оптимизации и проверки кода, а также о том, как бы нам предоставить правильную абстракцию, чтобы можно было думать о сущностях реального мира, а не о низкоуровнеых деталях реализации. Я считаю, что именно после определения АТД мы должны думать о вопросах наследования и полиморфизма.
Стоит отметить, что концепция АТД нашла гирокое применение в ООП, т.к именно эта концепция дополняет ООП и позволяет уменшить сложность программ в быстроменяющемся мире требований к ПО.
Данную статью я писал для того, что бы обратить внимание разработчиков на АТД с целью повышения качества работы и разработки программного обеспечения.
Использованные источники:
Стив Макконнелл – “Совершенный код”;
Роберт Седжвик – «Алгоритмы на Java».