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

Не путать с абстрактным типом или алгебраическим типом данных .

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

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

История

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

Определение

Формально АТД аналогичен алгебраической структуре в математике: Состоит из домена, набора операций и набора ограничений, которым должны удовлетворять операции. Домен часто определяется неявно, например, свободный объект в наборе операций ADT. Интерфейс ADT обычно относится только к предметной области и операциям и, возможно , к некоторым ограничениям операций, таким как предварительные и постусловия; но не на другие ограничения, такие как отношения между операциями, которые считаются поведением. Существует два основных стиля формальных спецификаций поведения: аксиоматическая семантика и операционная семантика .

Несмотря на то, что ограничения не являются частью интерфейса, они по-прежнему важны для определения ADT; например, стек и очередь имеют схожие интерфейсы добавления/удаления элемента, но именно ограничения отличают поведение «последним пришел — первым обслужен» от режима «первым пришел — первым обслужен». Ограничения состоят не только из таких уравнений, как fetch(store(S,v))=v но и логические формулы .

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

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

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

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

Вспомогательные операции

Представления ADT часто ограничиваются только ключевыми операциями. Более подробные презентации часто описывают вспомогательные операции над АТД, такие как:

• create(), что создает новый экземпляр ADT;
• compare( s , t ), который проверяет, эквивалентны ли состояния двух экземпляров в некотором смысле;
• hash( s ), который вычисляет некоторую стандартную хеш-функцию на основе состояния экземпляра;
• print( с ) или show( s ), который создает удобочитаемое представление состояния экземпляра.

Эти названия носят иллюстративный характер и могут различаться у разных авторов. В определениях АТД в императивном стиле часто также можно встретить:

• initialize( s ), который подготавливает вновь созданный экземпляр s для дальнейших операций или сбрасывает его в некое «исходное состояние»;
• copy( s , t ), который переводит экземпляр s в состояние, эквивалентное состоянию t ;
• clone( t ), который выполняет s ← create(), copy( s , t ) и возвращает s ;
• free( с ) или destroy( s ), который освобождает память и другие ресурсы, используемые s .

The free операция обычно не имеет значения и смысла, поскольку АТД являются теоретическими объектами, которые «не используют память». Однако это может быть необходимо, когда необходимо проанализировать память, используемую алгоритмом, использующим ADT. В этом случае необходимы дополнительные аксиомы, определяющие, сколько памяти использует каждый экземпляр ADT в зависимости от его состояния и какая ее часть возвращается в пул free.

Ограниченные типы

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

Псевдонимы

В стиле эксплуатации часто неясно, как обрабатываются несколько экземпляров и может ли изменение одного экземпляра повлиять на другие. Общий стиль определения ADT записывает операции так, как будто во время выполнения алгоритма существует только один экземпляр, и все операции применяются к этому экземпляру. Например, стек может содержать операции push( х ) и pop(), которые работают с единственным существующим стеком. Определения ADT в этом стиле можно легко переписать, чтобы допустить несколько сосуществующих экземпляров ADT, добавив явный параметр экземпляра (например, S в примере стека ниже) к каждой операции, которая использует или изменяет неявный экземпляр. Некоторые АТД невозможно определить без разрешения нескольких экземпляров, например, когда одна операция принимает в качестве параметров два разных экземпляра АТД, например union операция над множествами или compare операции со списками.

Стиль множественных экземпляров иногда сочетается с аксиомой псевдонимов , а именно, что результат create() отличается от любого экземпляра, уже используемого алгоритмом. Реализации ADT по-прежнему могут повторно использовать память и позволять реализацию create() для получения ранее созданного экземпляра; однако определить, что такой экземпляр даже «повторно используется», сложно в формализме ADT.

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

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

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

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

—  Alexander Stepanov

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

Примеры

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

Абстрактную переменную можно рассматривать как простейший нетривиальный АТД с семантикой императивной переменной. Он допускает две операции, fetch и store. Операционные определения часто записываются в терминах абстрактных переменных. В аксиоматической семантике, допуская $V$ быть типом абстрактной переменной и $X$ быть типом его содержимого, fetch это функция $V\to X$ и store является функцией типа $V\to X\to V$. Основное ограничение заключается в том, что fetch всегда возвращает значение x, использованное в самом последнем store операцию над той же переменной V , т.е. fetch(store(V,x)) = x. Мы также можем потребовать, чтобы store полностью перезаписывает значение, store(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).

В этом определении неявно предполагается, что имена всегда различны: сохранение значения в переменной не влияет на состояние отдельной переменной V. U Чтобы сделать это предположение явным, можно добавить ограничение, которое:

• если U и V — разные переменные, последовательность { store( У , х ); store( V , y ) } эквивалентно { store( V , y ); store( U , х ) }.

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

Абстрактная стопка

Абстрактный стек — это структура «последним пришел — первым вышел». Обычно он определяется тремя ключевыми операциями: push, который вставляет элемент данных в стек; pop, который удаляет из него элемент данных; и peek или top, который обращается к элементу данных на вершине стека без его удаления. Полное определение абстрактного стека включает также булеву функцию. empty( S ) и create() операция, которая возвращает исходный экземпляр стека.

В аксиоматической семантике, допуская $S$ быть типом состояний стека и $X$ быть типом значений, содержащихся в стеке, они могут иметь типы $push:S\to X\to S$, $pop:S\to (S,X)$, $top:S\to X$, $create:S$, и $empty:S\to \mathbb {B}$. В аксиоматической семантике создание исходного стека является «тривиальной» операцией и всегда возвращает одно и то же выделенное состояние. Поэтому его часто обозначают специальным символом, например Λ или «()». empty Тогда предикат операции можно записать просто как $s=\Lambda$ или $s\neq \Lambda$.

Тогда ограничения pop(push(S,v))=(S,v), top(push(S,v))=v, empty( create) = T (вновь созданный стек пуст), empty( push( S , x )) = F (помещение чего-либо в стек делает его непустым). Эти аксиомы не определяют эффект top( с ) или pop( s ), если только s не является состоянием стека, возвращаемым push. С push оставляет стек непустым, эти две операции можно определить как недопустимые, когда s = Λ. Из этих аксиом (и отсутствия побочных эффектов) можно сделать вывод, что push(Λ, x ) ≠ Λ. push( s , х ) знак равно push( t , y ) тогда и только тогда, когда x = y и s = t .

Как и в некоторых других разделах математики, принято также предполагать, что состояниями стека являются только те состояния, существование которых можно доказать из аксиом за конечное число шагов. В данном случае это означает, что каждая стопка представляет собой конечную последовательность значений, которая становится пустой стопкой (Λ) после конечного числа popс. Сами по себе приведенные выше аксиомы не исключают существования бесконечных стеков (которые можно popпед всегда, каждый раз приводя к другому состоянию) или круговые стопки (которые возвращаются в одно и то же состояние после конечного числа popс). В частности, они не исключают состояния такие , что 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( С , х ). Из этого условия и свойств абстрактных переменных следует, например, что последовательность:

{ push( С , х ); push( С , у ); У ← pop( С ); push( С , з ); В ← pop( С ); Вт ← pop( С ) }

где x , y и z — любые значения, а U , V , W — попарно различные переменные, эквивалентно:

{ U ← у ; В ← г ; W ← х }

В отличие от аксиоматической семантики, операционная семантика может страдать от псевдонимов. Здесь неявно предполагается, что операции над экземпляром стека не изменяют состояние любого другого экземпляра ADT, включая другие стеки; то есть:

• Для любых значений x , y и любых различных стеков S и T последовательность { push( С , х ); push( T , y ) } эквивалентно { push( Т , у ); push( S , х ) }.

Иерархия стрел

Более сложный пример — иерархия Boom с абстрактными типами данных двоичного дерева , списка , сумки и набора . Все эти типы данных могут быть объявлены тремя операциями: null , которая создает пустой контейнер, Single , которая создает контейнер из одного элемента, и Append , которая объединяет два контейнера одного и того же типа. Полную спецификацию для четырех типов данных затем можно получить путем последовательного добавления к этим операциям следующих правил:

- null — это левая и правая нейтраль для дерева:	присоединить(нуль,А) = А, присоединить(А,нуль) = А.
- в списках добавлено, что добавление ассоциативно:	добавить(добавить(A,B),C) = добавить(A,добавить(B,C)).
- сумки добавляют коммутативности:	добавить(В,А) = добавить(А,В).
- наконец, множества также идемпотентны:	присоединить(А,А) = А.

Доступ к данным может быть определен путем сопоставления с образцом трех операций, например, функции- члена для этих контейнеров следующим образом:

- член(X,один(Y)) = eq(X,Y)

- член (X, ноль) = ложь

- член(X,append(A,B)) = или(член(X,A), член(X,B))

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

Общие ADT

Некоторые распространенные ADT, которые оказались полезными в самых разных приложениях:

• Коллекция
• Контейнер
• Список
• Нить
• Набор
• Мультисет
• Карта
• Мультикарта
• График
• Дерево
• Куча
• Очередь
• Приоритетная очередь
• Двусторонняя очередь
• Двусторонняя приоритетная очередь

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

Абстрактный графический тип данных

Расширение ADT для компьютерной графики было предложено в 1979 году: абстрактный графический тип данных (AGDT). Его представили Надя Магненат Тельманн и Даниэль Тельманн . AGDT предоставляют преимущества ADT и возможности структурированного построения графических объектов.

Выполнение

Абстрактные типы данных — это теоретические сущности, используемые (помимо прочего) для упрощения описания абстрактных алгоритмов, классификации и оценки структур данных, а также формального описания систем типов языков программирования. Однако ADT может быть реализован . Это означает, что каждый экземпляр или состояние АТД представлен некоторым конкретным типом данных или структурой данных , и для каждой абстрактной операции существует соответствующая процедура или функция , и эти реализованные процедуры удовлетворяют спецификациям и аксиомам АТД до определенного стандарта. На практике реализация не идеальна, и пользователи должны знать о проблемах, связанных с ограничениями представления и реализованных процедур.

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

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

Чтобы клиенты не зависели от реализации, ADT часто упаковывается как непрозрачный тип данных или дескриптор . какой-либо в одном или нескольких модулях , интерфейс которых содержит только сигнатуру (количество и типы параметров и результатов) операций. Реализация модуля, а именно тела процедур и конкретная используемая структура данных, может быть затем скрыта от большинства клиентов модуля. Это дает возможность изменять реализацию, не затрагивая клиентов. Если реализация раскрыта, она называется прозрачным типом данных.

Современные объектно-ориентированные языки, такие как C++ и Java , поддерживают абстрактные типы данных. Когда класс используется в качестве типа, это абстрактный тип, ссылающийся на скрытое представление. В этой модели АТД обычно реализуется как класс , и каждый экземпляр АТД обычно является объектом этого класса. Интерфейс модуля обычно объявляет конструкторы как обычные процедуры, а большинство других операций ADT — как методы этого класса. Многие современные языки программирования, такие как C++ и Java, поставляются со стандартными библиотеками, реализующими многочисленные ADT в этом стиле. Однако такой подход нелегко инкапсулировать несколько вариантов представления, обнаруженных в ADT. Это также может подорвать расширяемость объектно-ориентированных программ. В чисто объектно-ориентированной программе, использующей интерфейсы в качестве типов, типы относятся к поведению, а не к представлениям.

Спецификации некоторых языков программирования намеренно расплывчаты в отношении представления определенных встроенных типов данных, определяя только операции, которые можно над ними выполнять. Следовательно, эти типы можно рассматривать как «встроенные ADT». Примерами являются массивы во многих языках сценариев, таких как Awk , Lua и Perl , которые можно рассматривать как реализацию абстрактного списка.

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

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

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

Интерфейс в императивном стиле

Интерфейс императивного стиля может быть:

typedef struct stack_Rep stack_Rep;       // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T;               // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item;                 // type: value stored in stack instance (arbitrary address)

stack_T stack_create(void);               // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s);          // removes the top item from the stack and returns it
bool stack_empty(stack_T s);              // checks whether stack is empty

Этот интерфейс можно использовать следующим образом:

#include <stack.h>          // includes the stack interface

stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x);          // adds the address of x at the top of the stack
void* y = stack_pop(s);     // removes the address of x from the stack and returns it
if (stack_empty(s)) { }     // does something if stack is empty

Этот интерфейс может быть реализован разными способами. Реализация может быть сколь угодно неэффективной, поскольку приведенное выше формальное определение АТД не определяет, сколько места может использовать стек или сколько времени должна занимать каждая операция. Он также не определяет, продолжает ли состояние стека s существовать после вызова x ← pop( с ).

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

Функциональный интерфейс

Определения ADT в функциональном стиле больше подходят для функциональных языков программирования, и наоборот. Однако можно обеспечить интерфейс функционального стиля даже на таком императивном языке, как C. Например:

typedef struct stack_Rep stack_Rep;          // type: stack state representation (opaque record)
typedef stack_Rep* stack_T;                  // type: handle to a stack state (opaque pointer)
typedef void* stack_Item;                    // type: value of a stack state (arbitrary address)

stack_T stack_empty(void);                   // returns the empty stack state
stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack state and returns the resulting stack state
stack_T stack_pop(stack_T s);                // removes the top item from the stack state and returns the resulting stack state
stack_Item stack_top(stack_T s);             // returns the top item of the stack state

См. также

• Концепция (общее программирование)
• Формальные методы
• Функциональная спецификация
• Обобщенный алгебраический тип данных
• Начальная алгебра
• Принцип замены Лискова
• Теория типов
• Стены и Зеркала

Ссылки

• Лисков, Варвара ; Зиллес, Стивен (1974). «Программирование с абстрактными типами данных». Материалы симпозиума ACM SIGPLAN по языкам очень высокого уровня . Уведомления SIGPLAN. Том. 9. С. 50–59. CiteSeerX   10.1.1.136.3043 . дои : 10.1145/800233.807045 .
• Дейл, Нелл; Уокер, Генри М. (1996). Абстрактные типы данных: спецификации, реализации и приложения . Джонс и Бартлетт Обучение. ISBN  978-0-66940000-7 .

Дальнейшее чтение

• Митчелл, Джон С .; Плоткин, Гордон (июль 1988 г.). «Абстрактные типы имеют экзистенциальный тип» (PDF) . Транзакции ACM в языках и системах программирования . 10 (3): 470–502. дои : 10.1145/44501.45065 . S2CID   1222153 . Архивировано (PDF) из оригинала 9 октября 2022 г.

Внешние ссылки

• СМИ, связанные с абстрактными типами данных , на Викискладе?
• Абстрактный тип данных в NIST Словаре алгоритмов и структур данных