Введение

Математическая модель типов данных

В информатике абстрактный тип данных (АТД) — это математическая модель для типов данных, определяемая своим поведением (семантикой) с точки зрения пользователя данных, в частности, в терминах возможных значений, возможных операций над данными этого типа и поведения этих операций. Эта математическая модель противопоставляется структурам данных, которые являются конкретными реализациями данных и представляют точку зрения разработчика, а не пользователя. Например, стек имеет операции push/pop, которые следуют принципу "последним пришел — первым ушел" (LIFO) и могут быть конкретно реализованы с использованием списка или массива. Другой пример — множество, которое хранит значения без какого-либо определенного порядка и без повторений. Сами значения из множеств не извлекаются, вместо этого проверяется принадлежность значения множеству, чтобы получить логическое значение "принадлежит" или "не принадлежит". АТД — это теоретическая концепция, используемая в формальной семантике и верификации программ, а также, в меньшей степени, в разработке и анализе алгоритмов, структур данных и программных систем. Большинство распространенных языков программирования не поддерживают формальное определение АТД напрямую. Однако различные языковые средства соответствуют определенным аспектам реализации АТД и легко могут быть спутаны с самими АТД; к ним относятся абстрактные типы, непрозрачные типы данных, протоколы и проектирование по контракту. Например, в модульном программировании модуль объявляет процедуры, соответствующие операциям АТД, часто с комментариями, описывающими ограничения. Эта стратегия сокрытия информации позволяет изменять реализацию модуля, не нарушая работу клиентских программ, но модуль лишь неформально определяет АТД. Понятие абстрактных типов данных связано с концепцией абстракции данных, важной в объектно-ориентированном программировании и методологиях проектирования по контракту для разработки программного обеспечения.

История

Абстрактные типы данных (ADT) были впервые предложены Барбарой Лисков и Стивеном Н. Зиллесом в 1974 году в процессе разработки языка CLU. Алгебраическая спецификация была важной областью исследований в информатике примерно в 1980 году и в то время почти являлась синонимом абстрактных типов данных. Она имеет математическое обоснование в универсальной алгебре.

Определение

Формально, ADT аналогична алгебраической структуре в математике, состоящей из области (домена), набора операций и набора ограничений, которым должны удовлетворять эти операции. Домен часто определяется неявно, например, как свободный объект над набором операций ADT. Интерфейс ADT обычно определяет только домен и операции, а также, возможно, некоторые ограничения на операции, такие как предусловия и постусловия, но не другие ограничения, например, отношения между операциями, которые рассматриваются как поведение. Существует два основных стиля формальных спецификаций поведения: аксиоматическая семантика и операционная семантика. Несмотря на то, что ограничения не являются частью интерфейса, они все равно важны для определения ADT; например, стек и очередь имеют схожие интерфейсы добавления/удаления элементов, но именно ограничения отличают принцип "последним пришел – первым ушел" (LIFO) от принципа "первым пришел – первым ушел" (FIFO). Ограничения состоят не только из уравнений, но и из логических формул.

Семантика аксиоматическая

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

Операционная семантика

В духе императивного программирования абстрактная структура данных представляется как изменяемый объект – то есть, существует понятие времени, и АДТ может находиться в различных состояниях в разные моменты времени. Операции изменяют состояние АДТ с течением времени; следовательно, порядок выполнения операций имеет значение, и одна и та же операция над одними и теми же данными может приводить к разным результатам, если она выполняется в разное время. Это аналогично инструкциям компьютера или командам и процедурам императивного языка программирования. Чтобы подчеркнуть этот подход, принято говорить, что операции выполняются или применяются, а не вычисляются, подобно императивному стилю, часто используемому при описании абстрактных алгоритмов. Ограничения обычно задаются в текстовой форме.

Типы с ограничениями

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

Алиасинг

В операционном стиле часто неясно, как обрабатываются множественные экземпляры и может ли изменение одного экземпляра повлиять на другие. Распространенный стиль определения ADT записывает операции так, как будто во время выполнения алгоритма существует только один экземпляр, и все операции применяются к этому экземпляру. Например, стек может иметь операции (x) и , которые оперируют с единственным существующим стеком. Определения ADT, написанные в таком стиле, можно легко переписать, чтобы разрешить сосуществование нескольких экземпляров ADT, добавив явный параметр экземпляра (например, S в примере стека ниже) к каждой операции, которая использует или изменяет неявный экземпляр. Некоторые ADT не могут быть осмысленно определены без поддержки множественных экземпляров, например, когда одна операция принимает два различных экземпляра ADT в качестве параметров, такие как операция объединения над множествами или операция конкатенации над списками. Стиль множественных экземпляров иногда комбинируется с аксиомой об отсутствии псевдонимов, а именно, с утверждением, что результат операции отличается от любого экземпляра, уже используемого алгоритмом. Реализации ADT могут по-прежнему повторно использовать память и позволять реализации возвращать ранее созданный экземпляр; однако, определение того, что такой экземпляр даже "повторно используется", затруднительно в формализме ADT. В более общем смысле, эту аксиому можно усилить, чтобы исключить также частичное пересечение с другими экземплярами, так что составные ADT (такие как деревья или записи) и ADT ссылочного типа (такие как указатели) можно считать полностью независимыми. Например, при расширении определения абстрактной переменной для включения абстрактных записей, операции над полем F переменной записи R явно включают F, которое отличается от, но также является частью, R. Аксиома частичного отсутствия псевдонимов будет утверждать, что изменение поля одной переменной записи не влияет на другие записи.

Анализ сложности

Некоторые авторы также включают вычислительную сложность ("стоимость") каждой операции, как с точки зрения времени (для выполнения операций), так и пространства (для представления значений), чтобы облегчить анализ алгоритмов. Например, можно указать, что каждая операция занимает одинаковое время, а каждое значение – одинаковый объем памяти, независимо от состояния АДТ, или что существует "размер" АДТ, и операции выполняются за время, линейное, квадратичное и т.д. относительно этого размера. Александр Степанов, разработчик библиотеки стандартных шаблонов C++, включил гарантии сложности в спецификацию STL, утверждая:

Причина введения понятия абстрактных типов данных заключалась в обеспечении взаимозаменяемости программных модулей. Невозможно добиться взаимозаменяемости модулей, если они демонстрируют разное поведение с точки зрения сложности. Если я заменю один модуль другим, обладающим тем же функционалом, но отличающимся по компромиссам в сложности, пользователь этого кода будет неприятно удивлен. Я могу рассказывать ему все, что угодно об абстракции данных, но он все равно не захочет использовать этот код. Утверждения о сложности должны быть частью интерфейса. Александр Степанов

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

Абстрактная переменная

Абстрактная переменная может рассматриваться как самый простой нетривиальный АДТ с семантикой императивной переменной. Она допускает две операции, и операционные определения часто записываются с использованием абстрактных переменных. В аксиоматической семантике, если считать, что – это тип абстрактной переменной, а – тип её содержимого, то является функцией, а – функцией типа . Основное ограничение заключается в том, что всегда возвращает значение *x*, использованное в самой последней операции присваивания для той же переменной *V*, то есть . Мы также можем потребовать, чтобы присваивание полностью перезаписывало значение. В операционной семантике (V) – это процедура, возвращающая текущее значение в ячейке памяти *V*, а (V, x) – процедура с типом возвращаемого значения, которая сохраняет значение *x* в ячейке памяти *V*. Ограничения описываются неформально как согласованность операций чтения и записи. Как и во многих языках программирования, операция (V, x) часто записывается как V ← x (или в аналогичном виде), а (V) подразумевается всякий раз, когда переменная *V* используется в контексте, требующем значения. Например, V ← V + 1 обычно понимается как сокращение для (V, (V) + 1). В этом определении неявно предполагается, что имена переменных всегда различны: сохранение значения в переменной *U* не влияет на состояние отдельной переменной *V*. Чтобы сделать это предположение явным, можно добавить ограничение: если *U* и *V* – различные переменные, то последовательность { (U, x); (V, y) } эквивалентна { (V, y); (U, x) }. Данное определение ничего не говорит о результате вычисления (V), когда *V* не инициализирована, то есть до выполнения какой-либо операции присваивания для *V*. Чтение до записи может быть запрещено, определено как возвращающее определённый результат или оставлено неопределённым. Существуют алгоритмы, эффективность которых зависит от предположения, что такое чтение допустимо и возвращает некоторое произвольное значение из диапазона допустимых значений переменной.

Реализация

Абстрактные типы данных — это теоретические сущности, используемые (в частности) для упрощения описания абстрактных алгоритмов, классификации и оценки структур данных, а также для формального описания систем типов языков программирования. Однако абстрактный тип данных может быть реализован. Это означает, что каждый экземпляр или состояние АТД представлен некоторым конкретным типом данных или структурой данных, и для каждой абстрактной операции существует соответствующая процедура или функция, при этом эти реализованные процедуры удовлетворяют спецификациям и аксиомам АТД в соответствии с определенным стандартом. На практике реализация не всегда совершенна, и пользователи должны учитывать проблемы, связанные с ограничениями представления и реализованных процедур. Например, целые числа могут быть специфицированы как АТД, определяемый выделенными значениями 0 и 1, операциями сложения, вычитания, умножения, деления (с учетом деления на ноль), сравнения и т. д., поведение которых соответствует известным математическим аксиомам в абстрактной алгебре, таким как ассоциативность, коммутативность и так далее. Однако в компьютере целые числа чаще всего представляются в виде двоичных чисел фиксированной ширины 32 или 64 бита. Пользователи должны знать о проблемах, связанных с этим представлением, таких как арифметическое переполнение, когда АТД специфицирует допустимый результат, но представление не может вместить это значение. Тем не менее, во многих случаях пользователь может игнорировать эти неточности и просто использовать реализацию, как если бы это был абстрактный тип данных. Обычно существует множество способов реализации одного и того же АТД, используя различные конкретные структуры данных. Например, абстрактный стек может быть реализован с помощью связного списка или массива. Различные реализации АТД, обладающие всеми одинаковыми свойствами и возможностями, могут считаться семантически эквивалентными и могут быть в некоторой степени взаимозаменяемы в коде, использующем АТД. Это обеспечивает форму абстракции или инкапсуляции и предоставляет большую гибкость при использовании объектов АТД в различных ситуациях. Например, различные реализации АТД могут быть более эффективными в разных ситуациях; можно использовать каждую из них в ситуации, где она предпочтительнее, тем самым повышая общую эффективность. Код, использующий реализацию АТД в соответствии с его интерфейсом, продолжит работать, даже если реализация АТД будет изменена. Чтобы клиенты не зависели от реализации, АТД часто упаковывается в виде непрозрачного типа данных или дескриптора в одном или нескольких модулях, интерфейс которых содержит только сигнатуру (количество и типы параметров и результатов) операций. Реализация модуля — то есть тела процедур и конкретная структура данных, используемая в модуле — может быть скрыта от большинства клиентов модуля. Это позволяет изменять реализацию без влияния на клиентов. Если реализация раскрыта, она известна как прозрачный тип данных. Современные объектно-ориентированные языки, такие как C++ и Java, поддерживают форму абстрактных типов данных. Когда класс используется в качестве типа, это абстрактный тип, ссылающийся на скрытое представление. В этой модели АТД обычно реализуется как класс, а каждый экземпляр АТД обычно является объектом этого класса. Интерфейс модуля обычно объявляет конструкторы как обычные процедуры, а большинство других операций АТД — как методы этого класса. Многие современные языки программирования, такие как C++ и Java, поставляются со стандартными библиотеками, которые реализуют многочисленные АТД в этом стиле. Однако такой подход не позволяет легко инкапсулировать несколько вариантов представления, встречающихся в АТД. Он также может подорвать расширяемость объектно-ориентированных программ. В чисто объектно-ориентированной программе, использующей интерфейсы в качестве типов, типы относятся к поведению, а не к представлениям. Спецификация некоторых языков программирования намеренно расплывчата в отношении представления определенных встроенных типов данных, определяя только операции, которые могут быть выполнены над ними. Следовательно, эти типы можно рассматривать как «встроенные АТД». Примерами являются массивы во многих скриптовых языках, таких как Awk, Lua и Perl, которые можно рассматривать как реализацию абстрактного списка. В формальном языке спецификаций АТД могут быть определены аксиоматически, и язык позволяет манипулировать значениями этих АТД, обеспечивая тем самым прямолинейную и непосредственную реализацию. Семейство языков программирования OBJ, например, позволяет определять уравнения для спецификации и переписывания для их выполнения. Такие автоматические реализации обычно не так эффективны, как специализированные реализации.

Пример: реализация абстрактного стека

В качестве примера, приведена реализация абстрактного стека, описанного выше, на языке программирования C.