В информатике абстрактный тип данных ( ADT ) — это математическая модель типов данных , определяемая ее поведением ( семантикой ) с точки зрения пользователя данных , в частности, с точки зрения возможных значений, возможных операций над данными. этот тип и поведение этих операций. Эта математическая модель контрастирует со структурами данных , которые являются конкретными представлениями данных и являются точкой зрения разработчика, а не пользователя. Например, в стеке есть операции push/pop, которые следуют правилу «Последним пришел — первым вышел» и могут быть конкретно реализованы с использованием либо списка, либо массива. Другим примером является набор , в котором хранятся значения без какого-либо определенного порядка и без повторяющихся значений. Сами значения не извлекаются из наборов, скорее, значение проверяется на членство, чтобы получить логическое значение «входит» или «не входит».
ADT — это теоретическая концепция, используемая в формальной семантике и верификации программ , а также, в менее строгом смысле, при проектировании и анализе алгоритмов , структур данных и программных систем . Большинство основных компьютерных языков напрямую не поддерживают формальное определение ADT. Однако различные функции языка соответствуют определенным аспектам реализации АТД, и их легко спутать с собственно АТД; к ним относятся абстрактные типы , непрозрачные типы данных , протоколы и проектирование по контракту . Например, в модульном программировании модуль объявляет процедуры, соответствующие операциям ADT, часто с комментариями , описывающими ограничения. Эта стратегия сокрытия информации позволяет изменять реализацию модуля, не нарушая работу клиентских программ, но модуль лишь неформально определяет ADT. Понятие абстрактных типов данных связано с концепцией абстракции данных , важной в объектно-ориентированном программировании и проектировании по контрактным методологиям разработки программного обеспечения . [ нужна цитата ]
ADT были впервые предложены Барбарой Лисков и Стивеном Н. Зиллесом в 1974 году как часть разработки языка CLU . [1] Алгебраическая спецификация была важным предметом исследований в CS примерно в 1980 году и почти синонимом абстрактных типов данных в то время. [2] Оно имеет математическую основу в универсальной алгебре . [3]
Формально АТД аналогичен алгебраической структуре в математике [4] , состоящей из области определения, набора операций и набора ограничений, которым должны удовлетворять операции. [5] Домен часто определяется неявно, например, свободный объект в наборе операций ADT. Интерфейс ADT обычно относится только к предметной области и операциям и, возможно , к некоторым ограничениям операций, таким как предварительные и постусловия; но не на другие ограничения, такие как отношения между операциями, которые считаются поведением. Существует два основных стиля формальных спецификаций поведения: аксиоматическая семантика и операционная семантика . [6]
Несмотря на то, что ограничения не являются частью интерфейса, они по-прежнему важны для определения ADT; например, стек и очередь имеют схожие интерфейсы добавления/удаления элемента, но именно ограничения отличают поведение «последним пришел — первым обслужен» от режима «первым пришел — первым обслужен». Ограничения состоят не только из таких уравнений, как , fetch(store(S,v))=vно и из логических формул .
В духе функционального программирования каждое состояние абстрактной структуры данных представляет собой отдельную сущность или значение. С этой точки зрения каждая операция моделируется как математическая функция без побочных эффектов . Операции, изменяющие ADT, моделируются как функции, которые принимают старое состояние в качестве аргумента и возвращают новое состояние как часть результата. Порядок, в котором оцениваются операции, не имеет значения, и одна и та же операция, примененная к одним и тем же аргументам (включая одни и те же входные состояния), всегда будет возвращать одни и те же результаты (и выходные состояния). Ограничения определяются как аксиомы или алгебраические законы, которым должны удовлетворять операции.
В духе императивного программирования абстрактная структура данных понимается как изменяемая сущность — это означает, что существует понятие времени, и АТД может находиться в разных состояниях в разное время. Затем операции со временем меняют состояние ADT; поэтому порядок, в котором оцениваются операции, важен, и одна и та же операция с одними и теми же объектами может иметь разные последствия, если она выполняется в разное время. Это аналогично инструкциям компьютера или командам и процедурам императивного языка. Чтобы подчеркнуть эту точку зрения, принято говорить, что операции выполняются или применяются , а не оцениваются , подобно императивному стилю, часто используемому при описании абстрактных алгоритмов. Ограничения обычно описываются в прозе.
Представления ADT часто ограничиваются только ключевыми операциями. Более подробные презентации часто описывают вспомогательные операции над АТД, такие как:
create(), что создает новый экземпляр ADT;compare( s , t ), который проверяет, эквивалентны ли состояния двух экземпляров в некотором смысле;hash( s ), который вычисляет некоторую стандартную хеш-функцию на основе состояния экземпляра;print( s ) или show( s ), что создает удобочитаемое представление состояния экземпляра.Эти названия носят иллюстративный характер и могут различаться у разных авторов. В определениях АТД в императивном стиле часто также можно встретить:
initialize( s ), который подготавливает вновь созданный экземпляр s для дальнейших операций или сбрасывает его в некое «исходное состояние»;copy( s , t ), который переводит экземпляр s в состояние, эквивалентное состоянию t ;clone( t ), который выполняет s ← create(), copy( s , t ) и возвращает s ;free( s ) или destroy( s ), который освобождает память и другие ресурсы, используемые s .Обычно эта freeоперация не имеет значения и смысла, поскольку АТД являются теоретическими объектами, которые «не используют память». Однако это может быть необходимо, когда необходимо проанализировать память, используемую алгоритмом, использующим ADT. В этом случае необходимы дополнительные аксиомы, определяющие, сколько памяти использует каждый экземпляр ADT в зависимости от его состояния и какая ее часть возвращается в пул с помощью free.
Определение ADT часто ограничивает хранимые значения для его экземпляров членами определенного набора X , называемого диапазоном этих переменных. Например, абстрактная переменная может быть ограничена хранением только целых чисел. Как и в языках программирования, такие ограничения могут упростить описание и анализ алгоритмов , а также улучшить их читабельность.
В стиле эксплуатации часто неясно, как обрабатываются несколько экземпляров и может ли изменение одного экземпляра повлиять на другие. Общий стиль определения ADT записывает операции так, как будто во время выполнения алгоритма существует только один экземпляр, и все операции применяются к этому экземпляру. Например, стек может иметь операции push( x ) и pop(), которые работают с единственным существующим стеком. Определения ADT в этом стиле можно легко переписать, чтобы допустить несколько сосуществующих экземпляров ADT, добавив явный параметр экземпляра (например, S в примере стека ниже) к каждой операции, которая использует или изменяет неявный экземпляр. Некоторые АТД невозможно определить без разрешения нескольких экземпляров, например, когда одна операция принимает в качестве параметров два разных экземпляра АТД, например операция unionс множествами или compareоперация со списками.
Стиль множественных экземпляров иногда сочетается с аксиомой псевдонимов , а именно, что результат create() отличается от любого экземпляра, уже используемого алгоритмом. Реализации ADT по-прежнему могут повторно использовать память и позволять реализациям create() возвращать ранее созданный экземпляр; однако определить, что такой экземпляр даже «повторно используется», сложно в формализме ADT.
В более общем смысле, эту аксиому можно усилить, чтобы исключить также частичное наложение псевдонимов с другими экземплярами, так что составные АТД (такие как деревья или записи) и АТД ссылочного типа (такие как указатели) можно считать полностью непересекающимися. Например, при расширении определения абстрактной переменной для включения абстрактных записей операции над полем F записывающей переменной R явно включают F , которое отличается от R , но также является его частью . Аксиома частичного псевдонимирования гласит, что изменение поля одной переменной записи не влияет на другие записи.
Некоторые авторы также включают вычислительную сложность («стоимость») каждой операции как с точки зрения времени (для вычислительных операций), так и с точки зрения пространства (для представления значений), чтобы помочь в анализе алгоритмов . Например, можно указать, что каждая операция занимает одинаковое время и каждое значение занимает одно и то же пространство независимо от состояния АТД, или что существует «размер» АТД, и операции являются линейными, квадратичными и т. д. в размер АТД. Александр Степанов , разработчик стандартной библиотеки шаблонов C++ , включил гарантии сложности в спецификацию STL, утверждая:
Причиной введения понятия абстрактных типов данных было обеспечение взаимозаменяемости программных модулей. У вас не может быть взаимозаменяемых модулей, если только эти модули не имеют одинакового сложного поведения. Если я заменю один модуль другим модулем с таким же функциональным поведением, но с другим компромиссом по сложности, пользователь этого кода будет неприятно удивлен. Я мог бы рассказать ему все, что мне нравится об абстракции данных, но он все равно не захотел бы использовать этот код. Утверждения сложности должны быть частью интерфейса.
— Александр Степанов [7]
Другие авторы с этим не согласны, утверждая, что стековой АТД один и тот же независимо от того, реализован ли он с помощью связанного списка или массива, несмотря на разницу в операционных затратах, и что спецификация АТД должна быть независимой от реализации.
Абстрактную переменную можно рассматривать как простейший нетривиальный АТД с семантикой императивной переменной. Он допускает две операции, 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 , х ) }.Это определение ничего не говорит о результате вычисления fetch( V ), когда V не инициализирован , то есть перед выполнением какой-либо операции storeнад V. Извлечение перед сохранением можно запретить, определить для получения определенного результата или оставить неуказанным. Существуют некоторые алгоритмы, эффективность которых зависит от предположения, что это fetchдопустимо, и возвращают произвольное значение в диапазоне переменной.
Абстрактный стек — это структура «последним пришел — первым вышел». Обычно он определяется тремя ключевыми операциями: push, которая вставляет элемент данных в стек; pop, который удаляет из него элемент данных; и peekили top, который обращается к элементу данных на вершине стека без его удаления. Полное определение абстрактного стека включает также логическую функцию empty( S ) и createоперацию (), которая возвращает исходный экземпляр стека.
В аксиоматической семантике, если это тип состояний состояния и тип значений, содержащихся в стеке, они могут иметь типы , , , и . В аксиоматической семантике создание исходного стека является «тривиальной» операцией и всегда возвращает одно и то же выделенное состояние. Поэтому его часто обозначают специальным символом, например Λ или «()». Тогда предикат операции можно записать просто как или . empty
Тогда ограничения таковы pop(push(S,v))=(S,v): , top(push(S,v))=v, [8] 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бесконечно, каждый раз приводя в другое состояние) или круговых стопок (которые возвращаются в одно и то же состояние через конечное число popсекунд). В частности, они не исключают состояния 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 , Икс ); push( С , у ); У ← pop( С ); push( С , з ); В ← pop( С ); W ← pop( S ) }где x , y и z — любые значения, а U , V , W — попарно различные переменные, эквивалентно:
В отличие от аксиоматической семантики, операционная семантика может страдать от псевдонимов. Здесь неявно предполагается, что операции над экземпляром стека не изменяют состояние любого другого экземпляра ADT, включая другие стеки; то есть:
push( S , x ); push( T , y ) } эквивалентно { push( T , y ); push( S , х ) }.Более сложный пример — иерархия Boom с абстрактными типами данных двоичного дерева , списка , сумки и множества . [9] Все эти типы данных могут быть объявлены с помощью трех операций: null , которая создает пустой контейнер, Single , которая создает контейнер из одного элемента, и Append , которая объединяет два контейнера одного и того же типа. Полную спецификацию для четырех типов данных затем можно получить путем последовательного добавления к этим операциям следующих правил:
Доступ к данным может быть определен путем сопоставления с образцом трех операций, например, функции- члена для этих контейнеров следующим образом:
Необходимо позаботиться о том, чтобы функция была инвариантной относительно соответствующих правил для типа данных. Внутри каждого из классов эквивалентности, подразумеваемых выбранным подмножеством уравнений, он должен давать один и тот же результат для всех своих членов.
Некоторые распространенные ADT, которые оказались полезными в самых разных приложениях:
Каждый из этих ADT может быть определен многими способами и вариантами, не обязательно эквивалентными. Например, абстрактный стек может иметь или не иметь countоперацию, которая сообщает, сколько элементов было помещено, но еще не извлечено. Этот выбор имеет значение не только для клиентов, но и для реализации.
Расширение ADT для компьютерной графики было предложено в 1979 году: [10] абстрактный тип графических данных (AGDT). Его представили Надя Магненат Тельманн и Даниэль Тельманн . AGDT предоставляют преимущества ADT и возможности структурированного построения графических объектов.
Абстрактные типы данных — это теоретические сущности, используемые (помимо прочего) для упрощения описания абстрактных алгоритмов, классификации и оценки структур данных, а также для формального описания систем типов языков программирования. Однако ADT может быть реализован . Это означает, что каждый экземпляр или состояние АТД представлен некоторым конкретным типом данных или структурой данных , и для каждой абстрактной операции существует соответствующая процедура или функция , и эти реализованные процедуры удовлетворяют спецификациям и аксиомам АТД до определенного стандарта. На практике реализация не идеальна, и пользователи должны знать о проблемах, связанных с ограничениями представления и реализованных процедур.
Например, целые числа могут быть заданы как АТД, определяемый выделенными значениями 0 и 1, операциями сложения, вычитания, умножения, деления (с учетом деления на ноль), сравнения и т. д., которые ведут себя в соответствии со знакомыми математическими правилами. аксиомы абстрактной алгебры, такие как ассоциативность, коммутативность и т. д. Однако в компьютере целые числа чаще всего представляются как 32-битные или 64-битные двоичные числа фиксированной ширины . Пользователи должны знать о проблемах с этим представлением, таких как арифметическое переполнение , когда ADT указывает допустимый результат, но представление не может разместить это значение. Тем не менее, во многих целях пользователь может игнорировать эти неточности и просто использовать реализацию, как если бы это был абстрактный тип данных.
Обычно существует множество способов реализовать один и тот же ADT, используя несколько разных конкретных структур данных. Так, например, абстрактный стек может быть реализован посредством связанного списка или массива . Различные реализации АТД, обладающие одинаковыми свойствами и возможностями, можно считать семантически эквивалентными и в некоторой степени взаимозаменяемыми в коде, использующем АТД. Это обеспечивает форму абстракции или инкапсуляции и обеспечивает большую гибкость при использовании объектов ADT в различных ситуациях. Например, разные реализации ADT могут быть более эффективными в разных ситуациях; можно использовать каждый в той ситуации, когда он предпочтителен, повышая тем самым общую эффективность. Код, использующий реализацию ADT в соответствии с его интерфейсом, продолжит работать, даже если реализация ADT будет изменена.
Чтобы клиенты не зависели от реализации, ADT часто упаковывается как непрозрачный тип данных или какой-либо дескриптор [11] в один или несколько модулей , интерфейс которых содержит только сигнатуру (количество и типы параметров и результаты) операций. Реализация модуля, а именно тела процедур и конкретная используемая структура данных, может быть затем скрыта от большинства клиентов модуля. Это дает возможность изменять реализацию, не затрагивая клиентов. Если реализация раскрыта, она называется прозрачным типом данных.
Современные объектно-ориентированные языки, такие как C++ и Java , поддерживают абстрактные типы данных. Когда класс используется в качестве типа, это абстрактный тип, который ссылается на скрытое представление. В этой модели АТД обычно реализуется как класс , и каждый экземпляр АТД обычно является объектом этого класса. Интерфейс модуля обычно объявляет конструкторы как обычные процедуры, а большинство других операций ADT — как методы этого класса. Многие современные языки программирования, такие как C++ и Java, поставляются со стандартными библиотеками, реализующими многочисленные ADT в этом стиле. Однако такой подход нелегко инкапсулировать несколько вариантов представления, обнаруженных в ADT. Это также может подорвать расширяемость объектно-ориентированных программ. В чисто объектно-ориентированной программе, использующей интерфейсы в качестве типов, типы относятся к поведению, а не к представлениям.
Спецификации некоторых языков программирования намеренно расплывчаты в отношении представления определенных встроенных типов данных, определяя только операции, которые можно над ними выполнять. Следовательно, эти типы можно рассматривать как «встроенные ADT». Примерами являются массивы во многих языках сценариев, таких как Awk , Lua и Perl , которые можно рассматривать как реализацию абстрактного списка.
В языке формальной спецификации АТД могут быть определены аксиоматически, а затем язык позволяет манипулировать значениями этих АТД, обеспечивая тем самым простую и немедленную реализацию. Например, семейство языков программирования OBJ позволяет определять уравнения для спецификации и переписывать их для их выполнения. Однако такие автоматические реализации обычно не так эффективны, как специализированные реализации.
В качестве примера приведем реализацию абстрактного стека, приведенного выше, на языке программирования C.
Интерфейс императивного стиля может быть:
typedef struct stack_Rep stack_Rep ; // тип: представление экземпляра стека (непрозрачная запись) typedef stack_Rep * stack_T ; // тип: дескриптор экземпляра стека (непрозрачный указатель) typedef void * stack_Item ; // тип: значение, хранящееся в экземпляре стека (произвольный адрес) stack_T stack_create ( недействительный ); // создает новый пустой экземпляр стека 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 )) { } // что-то делает, если стек пуст Этот интерфейс может быть реализован разными способами. Реализация может быть сколь угодно неэффективной, поскольку приведенное выше формальное определение АТД не определяет, сколько места может использовать стек или сколько времени должна занимать каждая операция. Он также не определяет, продолжает ли состояние стека 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 ( недействительный ); // возвращает состояние пустого стека stack_T stack_push ( stack_T s , stack_Item x ); // добавляет элемент на вершину состояния стека и возвращает полученное состояние стека stack_T stack_pop ( stack_T s ); // удаляет верхний элемент из состояния стека и возвращает полученное состояние стека stack_Item stack_top ( stack_T s ); // возвращает верхний элемент состояния стека 
СМИ, связанные с абстрактными типами данных, на Викискладе?