Абстрактный тип данных

Абстрактные типы данных в программировании

Автор: Лапшин Владимир Анатольевич

Введение Использование АТД в языках программирования АТД как алгебраические системы Языки алгебраических спецификаций Заключение Список литературы

Введение

В данной работе рассматривается концепция абстрактных типов данных (АТД). Со времени формулирования этой концепции в 1974 году [1] абстрактные типы данных играют важную роль в теории программирования. Концепция АТД является, наряду с объектно-ориентированным подходом, наиболее популярной в настоящее время методологией для составления программ. В процессе декомпозиции программы на составляющие компоненты доступ к ним организуется посредством т.н. кластера операций, который представляет собой конечный список операций, которые могут быть использованы для модификации данных, предоставляемых данным компонентом.
Отличительной особенностью абстрактных типов данных как механизма абстракции является тот факт, что функциональность компонента программы, описываемая кластером операций, может быть реализована различными способами. Различные реализации абстрактных типов данных взаимозаменяемы благодаря механизму абстракции АТД, позволяющему скрыть детали реализации с помощью набора предопределенных операций.
Концепция абстрактных типов данных хорошо описывается с помощью математической теории алгебраических систем [2]. Алгебраическую систему или, проще говоря, алгебру (абстрактную алгебру), неформально можно определить как множество с набором операций, действующих на элементах данного множества. Операции реализуются как функции от одного или более параметров, действующие на элементах данного множества (для операции с одним аргументом) или на декартовых произведениях множества (для операций с несколькими аргументами). Описание операций, включающее в себя описание типов аргументов (рассуждение имеет смысл только для статически типизированных языков – прим.ред.) и возвращаемых значений, называется сигнатурой алгебраической системы. Сигнатуры, очевидно, представляют математическую модель абстрактного типа данных. Это обстоятельство дает возможность описывать программные сущности, заданные посредством АТД, как алгебраические системы. Этот подход будет подробнее рассмотрен ниже.
Типы данных впервые были описаны Д. Кнутом в его книге «Искусство программирования» [3]. В главе 2, «Информационные структуры», Кнут описывает т.н. структуры данных, определяемые как способы организации данных внутри программы. Кнут описывает такие типы данных, как списки, деревья, стеки, очереди, деки и т.д. Рассмотрим, например, как Кнут описывает тип данных «стек».
Кроме собственно описания самой структуры данных, Кнут описывает «алгоритмы обработки» этой структуры с помощью словаря специальных терминов [3, стр. 281]. Для стека этот словарь содержит термины: push (втолкнуть), pop (вытолкнуть) и top (верхний элемент стека). Таким образом, типы данных описываются Кнутом с помощью специального языка, задающего определенную терминологию и толкование этой терминологии. Эта особенность описания была замечена Стивеном Жиллем в работе [4] и, таким образом, явилась одним из побудительных мотивов для осознания важности концепции АТД.
В 1972 году была напечатана работа Дэвида Парнаса (David Parnas) [5], в которой впервые был сформулирован принцип разделения программы на модули. Модули – это компоненты программы, которые имеют два важных свойства:

1. 
   Модули скрывают в себе детали реализации.
   
2. 
   Модули могут быть повторно использованы в различных частях программы.
   

Парнас представлял модули как абстрактные машины, хранящие внутри себя состояния и позволяющие изменять это состояние посредством определенного набора операций. Эта концепция является базовой, как для концепции абстрактных типов данных, так и для объектно-ориентированного программирования.
Понятие абстрактного типа данных впервые в явном виде было сформулировано в совместной работе Стивена Жиля и Барбары Лисков [1]. В разделе «Смысл понятия абстракции» авторы обсуждают, каким образом понятие абстракции может быть применимо к программному коду. Абстракция – это способ отвлечься от неважных деталей и, таким образом, выбрать наиболее важные признаки для рассмотрения. В процессе создания программы разработчик строит программную модель решаемой задачи. В процессе построения программной модели разработчик оперирует элементами этой модели. Программный код структурируется соответствующим образом. Для выделения программных сущностей в коде программы естественно использовать механизм абстракции. В работе Жиля и Лисков рассматривался механизм т.н. поведенческой абстракции или, в терминологии авторов, функциональной абстракции.
Функциональная абстракция подразумевает выделение набора операций (функций) для работы с элементами программной модели. Таким образом, сущности программной модели представляются с помощью набора операций. Так осуществляется поведенческая абстракция сущности в программном коде. Сами авторы использовали термин «operational cluster», т.е. набор операций, и назвали такой набор операций абстрактным типом данных (АТД).
Рассмотрим определение абстрактного типа данных на языке, синтаксис которого унаследован преимущественно от языка PASCAL (детали можно найти в оригинальной работе). Этот язык поддерживает абстракцию модулей, доступ к которым задается посредством набора операций. Итак, определение типа «стек».

stack: cluster(element_type: type) is push, pop, top, erasetop, empty; rep(type_param: type) = (tp: integer; e_type: type; stk: array[1..] of type_param; create s: rep(element_type); s.tp := 0; s.e_type := element_type; return s; end push: operation(s: rep, v: s.e_type); s.tp := s.tp+1; s.stk[s.tp] := v; return; end pop: operation(s: rep) returns s.e_type; if s.tp = 0 then error; s.tp := s.tp-1; return s.stk[s.tp]; end top: operation(s: rep) returns s.e_type; if s.tp = 0 then error; return s.stk[s.tp]; end erasetop: operation(s: rep); if s.tp = 0 then error; s.tp := s.tp-1; return; end empty: operation(s: rep) returnsboolean; return s.tp = 0; endend stack

Здесь задается модуль с именем «stack» и для него определяется набор (cluster) операций: push, pop, top, erasetop, empty. От привычного всем программистам нашего времени набора операций со стеком этот кластер отличается только наличием операции erasetop, которая аналогична операции pop, но не возвращает значения. В библиотеке STL языка C++ операция pop шаблонного класса stack определена как erasetop, т.е. не возвращает удаляемого значения. Таким образом, это определение, сделанное в 1974 году, практически аналогично используемым сейчас определениям типа стек.
Для представления типа содержимого стека используется параметрический тип rep. Название унаследовано от термина «object representation» (представление объекта). По идее авторов, пользователи не имеют доступа к внутренним «объектам» модуля, но работают только с его «представлением», т.е. с типом rep. В данном случае rep является представлением внутренней реализации объектов «стека». Для каждого объекта стека фиксируется тип его элементов (e_type), поддерживается счетчик числа элементов в стеке (tp) и хранилище элементов в виде массива (stk).
Заметим, что процедура create не входит в набор операций АТД stack. Это специальная операция, используемая исключительно для целей конструирования объектов абстрактного типа данных stack. Таким операции в теории АТД называются конструкторами. Чуть более строго определим терминологию, для чего опишем операции в математической нотации:

create: -> Stack[Elem] push: Stack[Elem] x Elem -> Stack[Elem] pop: Stack[Elem] -> Elem top: Stack[Elem] -> Elem erasetop: Stack[Elem] -> Stack[Elem] empty: Stack[Elem] -> Bool

Операции без аргументов, возвращающие объекты стека, как это делает create, называются конструкторами АТД. В теории алгебраических систем такие операции называют еще константами. Операции вида push и erasetop, возвращающие в качестве результата объекты стека, называют командами. Операции, в которых справа от стрелки не встречается представление АТД, как pop, top и empty, называют запросами.
Таким образом, согласно классическому определению, абстрактный тип данных представляется как кластер операций. Операции получают и возвращают аргументы определенных типов, поэтому для полноценного описания АТД необходимо еще эти типы определить. В большинстве случаев этого вполне достаточно, но можно было бы описать еще условия, которым должны удовлетворять все правильные реализации данного абстрактного типа данных. Эти условия легко можно сформировать в виде композиции операций, применяемых к объектам стека. Например, совершенно ясно, что вставив элемент в стек с помощью операции push, а затем, взяв элемент с вершины стека с помощью операции top, мы должны получить тот же элемент. Это утверждение можно сформулировать следующим образом:

top(push(s,x))=x

Аналогичным образом можно сформулировать другие условия:

pop(push(s,x))=x empty(create())=true not empty(push(s,x))=true

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

pop(s) require not empty(s) top(s) require not empty(s)

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