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

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

Математический тип данных является компонентой многоосновной алгебры данных, а абстракция означает, что алгебра данных рассматривается с точностью до изоморфизма. Например, данные, которые мы представляем как "комплексное число", могут быть определены с помощью операций +, – , x, /, im, re, mod, arg, в то время как сами числа могут представляться различным образом с помощью обычных типов. Одним из таких представлений будет пара вещественных чисел, определяющих вещественную и мнимую часть, другим – пара чисел, определяющих модуль и аргумент.

Основную роль абстрактные типы данных играют в методологии программирования, основанной на пошаговой разработке программ

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

В теории абстрактных типов данных исследуются различные способы определения независимо от способов их реализации. Известны три основных подхода:

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

Инструменты