В информатике абстрактный тип данных ( ADT ) — это математическая модель для типов данных , определяемая его поведением ( семантикой ) с точки зрения пользователя данных , в частности, с точки зрения возможных значений, возможных операций над данными этого типа и поведения этих операций. Эта математическая модель контрастирует со структурами данных , которые являются конкретными представлениями данных и являются точкой зрения реализатора, а не пользователя. Например, стек имеет операции push/pop, которые следуют правилу Last-In-First-Out, и могут быть конкретно реализованы с использованием либо списка, либо массива. Другим примером является набор , который хранит значения без какого-либо определенного порядка и без повторяющихся значений. Сами значения не извлекаются из наборов; вместо этого проверяется значение на принадлежность, чтобы получить логическое «in» или «not in».
ADT — это теоретическая концепция, используемая в формальной семантике и проверке программ , а также, менее строго, в проектировании и анализе алгоритмов , структур данных и программных систем . Большинство основных языков программирования напрямую не поддерживают формальное указание ADT. Однако различные языковые особенности соответствуют определенным аспектам реализации ADT и их легко спутать с собственно ADT; к ним относятся абстрактные типы , непрозрачные типы данных , протоколы и проектирование по контракту . Например, в модульном программировании модуль объявляет процедуры, соответствующие операциям ADT, часто с комментариями , описывающими ограничения. Эта стратегия сокрытия информации позволяет изменять реализацию модуля, не нарушая клиентские программы, но модуль только неформально определяет ADT. Понятие абстрактных типов данных связано с концепцией абстракции данных , важной в объектно-ориентированном программировании и методологиях проектирования по контракту для разработки программного обеспечения . [1]
ADT были впервые предложены Барбарой Лисков и Стивеном Н. Зиллесом в 1974 году в рамках разработки языка CLU . [2] Алгебраическая спецификация была важным предметом исследований в области компьютерных наук около 1980 года и почти синонимом абстрактных типов данных в то время. [3] Она имеет математическую основу в универсальной алгебре . [4]
Формально ADT аналогичен алгебраической структуре в математике, [5] состоящей из домена, набора операций и набора ограничений, которым должны удовлетворять операции. [6] Домен часто определяется неявно, например, свободный объект над набором операций ADT. Интерфейс ADT обычно относится только к домену и операциям, и, возможно, к некоторым ограничениям на операции, таким как предварительные условия и постусловия; но не к другим ограничениям, таким как отношения между операциями, которые считаются поведением. Существует два основных стиля формальных спецификаций поведения: аксиоматическая семантика и операционная семантика . [7]
Несмотря на то, что они не являются частью интерфейса, ограничения по-прежнему важны для определения ADT; например, стек и очередь имеют похожие интерфейсы добавления элемента/удаления элемента, но именно ограничения отличают поведение «последний пришел — первый ушел» от поведения «первый пришел — первый ушел». Ограничения состоят не только из уравнений, таких как , fetch(store(S,v))=vно и из логических формул .
В духе функционального программирования каждое состояние абстрактной структуры данных является отдельной сущностью или значением. В этом представлении каждая операция моделируется как математическая функция без побочных эффектов . Операции, которые изменяют ADT, моделируются как функции, которые принимают старое состояние в качестве аргумента и возвращают новое состояние как часть результата. Порядок, в котором оцениваются операции, несущественен, и одна и та же операция, примененная к одним и тем же аргументам (включая одни и те же входные состояния), всегда будет возвращать одни и те же результаты (и выходные состояния). Ограничения указываются как аксиомы или алгебраические законы, которым должны удовлетворять операции.
В духе императивного программирования абстрактная структура данных рассматривается как сущность, которая является изменяемой — это означает, что существует понятие времени, и АТД может находиться в разных состояниях в разное время. Затем операции изменяют состояние АТД с течением времени; поэтому важен порядок, в котором оцениваются операции, и одна и та же операция над одними и теми же сущностями может иметь разные эффекты, если выполняется в разное время. Это аналогично инструкциям компьютера или командам и процедурам императивного языка. Чтобы подчеркнуть эту точку зрения, принято говорить, что операции выполняются или применяются , а не оцениваются , подобно императивному стилю, часто используемому при описании абстрактных алгоритмов. Ограничения обычно указываются в прозе.
Презентации ADT часто ограничиваются только ключевыми операциями. Более подробные презентации часто определяют вспомогательные операции ADT, такие как:
create(), что дает новый экземпляр ADT;compare( s , t ), который проверяет, эквивалентны ли состояния двух экземпляров в некотором смысле;hash( s ), которая вычисляет некоторую стандартную хеш-функцию из состояния экземпляра;print( s ) или show( s ), что создает понятное для человека представление состояния экземпляра.Эти названия иллюстративные и могут различаться у разных авторов. В определениях ADT в императивном стиле часто можно встретить также:
initialize( s ), который подготавливает вновь созданный экземпляр s для дальнейших операций или сбрасывает его в некоторое «начальное состояние»;copy( s , t ), который переводит экземпляр s в состояние, эквивалентное состоянию t ;clone( t ), который выполняет s ← create(), copy( s , t ) и возвращает s ;free( s ) или destroy( s ), который восстанавливает память и другие ресурсы, используемые s .Операция freeобычно не является релевантной или значимой, поскольку ADT являются теоретическими сущностями, которые не «используют память». Однако она может быть необходима, когда нужно проанализировать хранилище, используемое алгоритмом, который использует ADT. В этом случае нужны дополнительные аксиомы, которые определяют, сколько памяти использует каждый экземпляр ADT, как функцию его состояния, и какая ее часть возвращается в пул free.
Определение ADT часто ограничивает хранимое значение(я) для его экземпляров членами определенного множества X, называемого диапазоном этих переменных. Например, абстрактная переменная может быть ограничена только хранением целых чисел. Как и в языках программирования, такие ограничения могут упростить описание и анализ алгоритмов и улучшить их читаемость.
В операционном стиле часто неясно, как обрабатываются несколько экземпляров и может ли изменение одного экземпляра повлиять на другие. Распространенный стиль определения ADT записывает операции так, как будто во время выполнения алгоритма существует только один экземпляр, и все операции применяются к этому экземпляру. Например, стек может иметь операции push( x ) и pop(), которые работают с единственным существующим стеком. Определения ADT в этом стиле можно легко переписать, чтобы допустить несколько сосуществующих экземпляров ADT, добавив явный параметр экземпляра (например, S в примере стека ниже) к каждой операции, которая использует или изменяет неявный экземпляр. Некоторые ADT невозможно осмысленно определить, не разрешив несколько экземпляров, например, когда одна операция принимает два различных экземпляра ADT в качестве параметров, например, операция unionнад множествами или compareоперация над списками.
Стиль множественных экземпляров иногда сочетается с аксиомой псевдонимизации , а именно, что результат create() отличается от любого экземпляра, уже используемого алгоритмом. Реализации ADT могут по-прежнему повторно использовать память и позволять реализациям create() выдавать ранее созданный экземпляр; однако определение того, что такой экземпляр даже «используется повторно», затруднительно в формализме ADT.
В более общем смысле эта аксиома может быть усилена, чтобы исключить также частичное совмещение с другими экземплярами, так что составные АТД (такие как деревья или записи) и АТД ссылочного стиля (такие как указатели) могут считаться полностью непересекающимися. Например, при расширении определения абстрактной переменной для включения абстрактных записей операции над полем F переменной записи R явно включают F , которое отличается от R , но также является его частью . Аксиома частичного совмещения будет утверждать, что изменение поля одной переменной записи не влияет ни на какие другие записи.
Некоторые авторы также включают вычислительную сложность («стоимость») каждой операции, как с точки зрения времени (для вычислительных операций), так и пространства (для представления значений), чтобы помочь в анализе алгоритмов . Например, можно указать, что каждая операция занимает одинаковое время и каждое значение занимает одинаковое пространство независимо от состояния ADT, или что существует «размер» ADT, и операции являются линейными, квадратичными и т. д. по размеру ADT. Александр Степанов , разработчик библиотеки стандартных шаблонов C++ , включил гарантии сложности в спецификацию STL, утверждая:
Причиной введения понятия абстрактных типов данных было разрешение взаимозаменяемых программных модулей. У вас не может быть взаимозаменяемых модулей, если только эти модули не разделяют схожее поведение сложности. Если я заменю один модуль другим модулем с тем же функциональным поведением, но с другими компромиссами сложности, пользователь этого кода будет неприятно удивлен. Я мог бы рассказать ему все, что угодно об абстракции данных, и он все равно не захотел бы использовать этот код. Утверждения сложности должны быть частью интерфейса.
— Александр Степанов [8]
Другие авторы не согласны, утверждая, что стековый АТД одинаков, независимо от того, реализован ли он с помощью связанного списка или массива, несмотря на разницу в эксплуатационных затратах, и что спецификация АТД должна быть независимой от реализации.
Абстрактную переменную можно рассматривать как простейший нетривиальный АТД с семантикой императивной переменной. Она допускает две операции fetchи store. Операционные определения часто записываются в терминах абстрактных переменных. В аксиоматической семантике, позволяя быть типом абстрактной переменной и быть типом ее содержимого, является функцией и является функцией типа . Основное ограничение состоит в том, что всегда возвращает значение x, использованное в последней операции над той же переменной V , то есть . Мы также можем потребовать, чтобы полностью перезаписывало значение, .fetchstorefetchstorefetch(store(V,x)) = xstorestore(store(V,x1),x2) = store(V,x2)
В операционной семантике fetch( V ) — это процедура, которая возвращает текущее значение в ячейке V , а store( V , x ) — это процедура с voidвозвращаемым типом, которая сохраняет значение x в ячейке V . Ограничения описываются неформально, так как чтение согласуется с записью. Как и во многих языках программирования, операция store( V , x ) часто записывается как V ← x (или какая-то похожая запись), а fetch( V ) подразумевается всякий раз, когда переменная V используется в контексте, где требуется значение. Так, например, V ← V + 1 обычно понимается как сокращение для store( V , fetch( V ) + 1).
В этом определении неявно предполагается, что имена всегда различны: сохранение значения в переменной U не влияет на состояние отдельной переменной V. Чтобы сделать это предположение явным, можно добавить ограничение, что:
store( U , x ); store( V , y ) } эквивалентна { store( V , y ); store( U , x ) }.Это определение ничего не говорит о результате вычисления fetch( V ), когда V не инициализировано , то есть до выполнения какой-либо storeоперации над V . Извлечение перед сохранением может быть запрещено, определено как имеющее определенный результат или оставлено неопределенным. Существуют некоторые алгоритмы, эффективность которых зависит от предположения, что такое a fetchявляется допустимым, и возвращает некоторое произвольное значение в диапазоне переменной.
Абстрактный стек — это структура типа «последний пришел — первый вышел». Обычно она определяется тремя ключевыми операциями: push, которая вставляет элемент данных в стек; pop, которая удаляет элемент данных из него; и peekили top, которая обращается к элементу данных на вершине стека без удаления. Полное определение абстрактного стека также включает в себя булеву функцию empty( S ) и createоперацию (), которая возвращает начальный экземпляр стека.
В аксиоматической семантике, если быть типом состояний стека, а быть типом значений, содержащихся в стеке, они могут иметь типы , , , , и . В аксиоматической семантике создание начального стека является «тривиальной» операцией и всегда возвращает одно и то же выделенное состояние. Поэтому его часто обозначают специальным символом, например Λ или «()». Тогда предикат операции можно записать просто как или . empty
Ограничения тогда таковы pop(push(S,v))=(S,v): , top(push(S,v))=v, [9] empty ( create) = T (вновь созданный стек пуст), empty( push( S , x )) = F (помещение чего-либо в стек делает его непустым). Эти аксиомы не определяют эффект top( s ) или pop( s ), если только s не является состоянием стека, возвращаемым a push. Поскольку pushоставляет стек непустым, эти две операции можно определить как недействительные, когда s = Λ. Из этих аксиом (и отсутствия побочных эффектов) можно вывести, что push(Λ, x ) ≠ Λ. Кроме того, push( s , x ) = push( t , y ) тогда и только тогда, когда x = y и s = t .
Как и в некоторых других разделах математики, принято также предполагать, что состояниями стека являются только те, существование которых может быть доказано из аксиом за конечное число шагов. В этом случае это означает, что каждый стек представляет собой конечную последовательность значений, которая становится пустым стеком (Λ) после конечного числа pops. Сами по себе приведенные выше аксиомы не исключают существования бесконечных стеков (которые можно popперебирать вечно, каждый раз получая другое состояние) или циклических стеков (которые возвращаются в то же самое состояние после конечного числа pops). В частности, они не исключают состояния s такие, что pop( s ) = s или push( s , x ) = s для некоторого x . Однако, поскольку невозможно получить такие состояния стека из начального состояния стека с помощью заданных операций, предполагается, что они «не существуют».
В операциональном определении абстрактного стека push( S , x ) ничего не возвращает, а pop( S ) выдает значение в качестве результата, но не новое состояние стека. Тогда есть ограничение, что для любого значения x и любой абстрактной переменной V последовательность операций { push( S , x ); V ← pop( S ) } эквивалентна V ← x . Поскольку присваивание V ← x по определению не может изменить состояние S , это условие подразумевает, что V ← pop( S ) восстанавливает S в состояние, которое оно имело до push( S , x ). Из этого условия и из свойств абстрактных переменных следует, например, что последовательность:
push( S , x ); push( S , y ); U ← pop( S ); push( S , z ); V ← pop( S ); W ← pop( S ) }где x , y и z — любые значения, а U , V , W — попарно различные переменные, эквивалентно:
В отличие от аксиоматической семантики, операционная семантика может страдать от псевдонимов. Здесь неявно предполагается, что операции над экземпляром стека не изменяют состояние любого другого экземпляра ADT, включая другие стеки; то есть:
push( S , x ); push( T , y )} эквивалентна { push( T , y ); push( S , x )}.Более сложным примером является иерархия Boom бинарного дерева , списка , сумки и набора абстрактных типов данных. [10] Все эти типы данных могут быть объявлены тремя операциями: null , которая создает пустой контейнер, single , которая создает контейнер из одного элемента, и append , которая объединяет два контейнера одного типа. Полная спецификация для четырех типов данных может быть затем задана путем последовательного добавления следующих правил к этим операциям:
Доступ к данным можно задать путем сопоставления с образцом по трем операциям, например, функцию- член для этих контейнеров:
Необходимо позаботиться о том, чтобы функция была инвариантной относительно соответствующих правил для типа данных. В пределах каждого из классов эквивалентности, подразумеваемых выбранным подмножеством уравнений, она должна давать тот же результат для всех своих членов.
Некоторые распространенные ADT, которые оказались полезными в самых разных приложениях, это
Каждый из этих ADT может быть определен многими способами и вариантами, не обязательно эквивалентными. Например, абстрактный стек может иметь или не иметь countоперацию, которая сообщает, сколько элементов было помещено и еще не извлечено. Этот выбор имеет значение не только для его клиентов, но и для реализации.
Расширение ADT для компьютерной графики было предложено в 1979 году: [11] абстрактный графический тип данных (AGDT). Он был введен Надей Магненат Тальманн и Даниэлем Тальманном . AGDT предоставляют преимущества ADT с возможностями для построения графических объектов структурированным образом.
Абстрактные типы данных — это теоретические сущности, используемые (помимо прочего) для упрощения описания абстрактных алгоритмов, классификации и оценки структур данных и формального описания систем типов языков программирования. Однако ADT может быть реализован . Это означает, что каждый экземпляр или состояние ADT представлен некоторым конкретным типом данных или структурой данных , и для каждой абстрактной операции существует соответствующая процедура или функция , и эти реализованные процедуры удовлетворяют спецификациям и аксиомам ADT до некоторого стандарта. На практике реализация не идеальна, и пользователи должны знать о проблемах, связанных с ограничениями представления и реализованных процедур.
Например, целые числа могут быть указаны как ADT, определяемые различающимися значениями 0 и 1, операциями сложения, вычитания, умножения, деления (с учетом деления на ноль), сравнения и т. д., ведущими себя в соответствии с известными математическими аксиомами абстрактной алгебры, такими как ассоциативность, коммутативность и т. д. Однако в компьютере целые числа чаще всего представляются как 32-битные или 64-битные двоичные числа фиксированной ширины . Пользователи должны знать о проблемах с этим представлением, таких как арифметическое переполнение , когда ADT указывает допустимый результат, но представление не может вместить это значение. Тем не менее, для многих целей пользователь может игнорировать эти неточности и просто использовать реализацию, как если бы это был абстрактный тип данных.
Обычно существует множество способов реализовать один и тот же ADT, используя несколько различных конкретных структур данных. Так, например, абстрактный стек может быть реализован с помощью связанного списка или массива . Различные реализации ADT, имеющие все те же свойства и возможности, могут считаться семантически эквивалентными и могут использоваться в некоторой степени взаимозаменяемо в коде, использующем ADT. Это обеспечивает форму абстракции или инкапсуляции и дает большую гибкость при использовании объектов ADT в различных ситуациях. Например, различные реализации ADT могут быть более эффективными в различных ситуациях; можно использовать каждую из них в ситуации, когда они предпочтительны, тем самым повышая общую эффективность. Код, использующий реализацию ADT в соответствии с его интерфейсом, продолжит работать, даже если реализация ADT будет изменена.
Чтобы предотвратить зависимость клиентов от реализации, ADT часто упаковывается как непрозрачный тип данных или дескриптор некоторого рода [12] в одном или нескольких модулях , интерфейс которых содержит только сигнатуру (количество и типы параметров и результатов) операций. Реализация модуля, а именно тела процедур и конкретная используемая структура данных, затем может быть скрыта от большинства клиентов модуля. Это позволяет изменять реализацию, не затрагивая клиентов. Если реализация раскрыта, она известна как прозрачный тип данных.
Современные объектно-ориентированные языки, такие как C++ и Java , поддерживают форму абстрактных типов данных. Когда класс используется как тип, это абстрактный тип, который ссылается на скрытое представление. В этой модели ADT обычно реализуется как class , и каждый экземпляр ADT обычно является объектом этого класса. Интерфейс модуля обычно объявляет конструкторы как обычные процедуры, а большинство других операций ADT как методы этого класса. Многие современные языки программирования, такие как C++ и Java, поставляются со стандартными библиотеками, которые реализуют многочисленные ADT в этом стиле. Однако такой подход не позволяет легко инкапсулировать несколько вариантов представления, найденных в ADT. Он также может подорвать расширяемость объектно-ориентированных программ. В чистой объектно-ориентированной программе, которая использует интерфейсы как типы, типы ссылаются на поведения, а не на представления.
Спецификация некоторых языков программирования намеренно неопределенна в отношении представления некоторых встроенных типов данных, определяя только операции, которые могут быть выполнены с ними. Поэтому эти типы можно рассматривать как «встроенные ADT». Примерами являются массивы во многих языках сценариев, таких как Awk , Lua и Perl , которые можно рассматривать как реализацию абстрактного списка.
В формальном языке спецификации ADT могут быть определены аксиоматически, и язык затем позволяет манипулировать значениями этих ADT, тем самым обеспечивая простую и немедленную реализацию. Семейство языков программирования OBJ , например, позволяет определять уравнения для спецификации и переписывать их для их выполнения. Однако такие автоматические реализации обычно не так эффективны, как специализированные реализации.
В качестве примера приведем реализацию абстрактного стека, представленного выше, на языке программирования C.
Интерфейс в императивном стиле может быть следующим:
typedef struct stack_Rep stack_Rep ; // тип: представление экземпляра стека (непрозрачная запись) typedef stack_Rep * stack_T ; // тип: дескриптор экземпляра стека (непрозрачный указатель) typedef void * stack_Item ; // тип: значение, хранящееся в экземпляре стека (произвольный адрес) stack_T stack_create ( void ); // создает новый пустой экземпляр стека void stack_push ( stack_T s , stack_Item x ); // добавляет элемент наверх стека stack_Item stack_pop ( stack_T s ); // удаляет верхний элемент из стека и возвращает его bool stack_empty ( stack_T s ); // проверяет, пуст ли стек Этот интерфейс можно использовать следующим образом:
#include <stack.h> // включает интерфейс стека stack_T s = stack_create (); // создает новый пустой экземпляр стека int x = 17 ; stack_push ( s , & x ); // добавляет адрес x наверх стека void * y = stack_pop ( s ); // удаляет адрес x из стека и возвращает его if ( stack_empty ( s )) { } // что-то делает, если стек пуст Этот интерфейс может быть реализован многими способами. Реализация может быть произвольно неэффективной, поскольку формальное определение ADT, приведенное выше, не указывает, сколько места может использовать стек, и как долго должна выполняться каждая операция. Оно также не указывает, продолжает ли существовать состояние стека s после вызова x ← pop( s ).
На практике формальное определение должно указывать, что пространство пропорционально количеству элементов, помещенных и еще не извлеченных; и что каждая из операций выше должна завершаться за постоянное время, независимо от этого числа. Чтобы соответствовать этим дополнительным спецификациям, реализация может использовать связанный список или массив (с динамическим изменением размера) вместе с двумя целыми числами (количеством элементов и размером массива).
Определения ADT в функциональном стиле больше подходят для функциональных языков программирования, и наоборот. Однако можно предоставить интерфейс в функциональном стиле даже в императивном языке, таком как C. Например:
typedef struct stack_Rep stack_Rep ; // тип: представление состояния стека (непрозрачная запись) typedef stack_Rep * stack_T ; // тип: дескриптор состояния стека (непрозрачный указатель) typedef void * stack_Item ; // тип: значение состояния стека (произвольный адрес) stack_T stack_empty ( void ); // возвращает пустое состояние стека stack_T stack_push ( stack_T s , stack_Item x ); // добавляет элемент наверх состояния стека и возвращает результирующее состояние стека stack_T stack_pop ( stack_T s ); // удаляет верхний элемент из состояния стека и возвращает результирующее состояние стека stack_Item stack_top ( stack_T s ); // возвращает верхний элемент состояния стека 
Медиа, связанные с абстрактными типами данных на Wikimedia Commons