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

Использование АТД в языках программирования

В большинстве современных императивных языков основной концепцией, используемой для описания абстракций в программном коде, является объектно-ориентированный подход. Объектно-ориентированное программирование (ООП) также, как и подход к программированию на основе АТД, является, в некоторой степени, развитием тех идей о модульном программировании, которые были заложены в упоминавшейся выше работе Дэвида Парнаса [4].
В ООП результатом абстракции являются объекты, представляющие собой абстрактные машины (устройства), обладающие внутренним состоянием, которое можно изменять посылкой сообщений через методы объекта. Объекты обмениваются сообщениями друг с другом и, таким образом, реализуется алгоритм программной модели. В этом смысле объект есть почти то, что подразумевал Парнас в своей работе, когда рассуждал о модульном программировании.
Одно из наиболее значимых отличий АТД от ООП заключается в том, что абстрактный тип не содержит данных и, тем более, каких либо состояний этих данных. Свойство абстракции АТД как раз и заключается в том, что абстрактный тип представляет собой поведенческую абстракцию, т.е. кластер операций, посредством которых производится взаимодействие с данными. Поведенческая абстракция целиком и полностью описывается спецификацией абстрактного типа данных. Реализация АТД должна соответствовать спецификации данного абстрактного типа, в этом и заключается абстракция на основе АТД. Подробнее о различиях концепций АТД и ООП можно прочитать в работе [6].
На практике, в языках программирования, которые поддерживают концепцию ООП, часто также реализуется и концепция АТД. Чтобы, согласно "бритве Оккама", не «множить сущее без необходимости», для реализации АТД используются средства ООП. Для этого абстрактный тип определяют как класс с определенным интерфейсом. После чего в качестве реализаций данного абстрактного типа выступают его объекты-наследники (в смысле наследования ООП). Работа с реализациями АТД ведется через интерфейс базового объекта, т.е. через операции данного АТД. Для этого обычно используется принцип подстановки Лисков [7], согласно которому объекты-наследники можно подставлять в аргументы, имеющие базовый тип.
Рассмотрим в качестве примера, как АТД реализуются в языке программирования C++. C++ является языком, поддерживающим ООП на основе т.н. механизма классов. Абстрактный тип данных определяется как класс, предоставляющий т.н. «чисто виртуальные методы». Для иллюстрации рассмотрим пример реализации АТД стека целочисленных значений на C++:

class Stack { public: virtualvoid push(unsigned int elem) = 0; virtualunsignedint top() = 0; virtualvoid pop() = 0; virtualbool empty() = 0; };

Здесь, ввиду особенностей реализации объектов на C++, объекты АТД Stack передаются в операции и возвращаются из них неявно, в виде скрытых параметров. Поэтому аргументы операций почти ничем не отличаются от тех, что описаны в спецификации АТД "стек" выше.
В языке C++ любой класс, объявляющий чисто виртуальный метод (т.е. приравненный нулю при объявлении), называется «абстрактным типом». Это, конечно, еще не абстрактный тип данных, но уже нечто методологически на него похожее. Экземпляры абстрактных типов создавать нельзя. Таким образом, абстрактные типы используются в C++ для определения интерфейсов (кластеров операций), т.е. реализуют в несколько усеченном виде концепцию АТД.
Для задания реализации абстрактных типов в языке C++ используется механизм наследования и переопределения, объявленных в базовом классе методов-операций. Вот, например, как будет выглядеть реализация стека на основе массива:

class ArrayStack : public Stack { // Массив реализуется на основе типа std::vector стандартной библиотеки C++ std::vector array_; public: void push(unsigned int elem) { array_.push_back(elem); } unsigned int top() { if (array_.empty()) { throw std::invalid_argument(“the stack is empty”); } return array_.back(); } void pop() { if (array_.empty()) { throw std::invalid_argument(“the stack is empty”); } array_.pop_back(); } bool empty() { return array_.empty(); } };

В реализации используется тип std::vector стандартной библиотеки языка C++. Это параметризованный тип, реализующий концепцию «динамического массива значений». Тип предоставляет методы для вставки/удаления значений в конец массива. Также имеются методы для доступа к последнему элементу массива и проверки массива на непустоту. При невыполнении предусловий на операции pop и top генерируется исключение.
В языке C++ принцип подстановки Лисков реализуется на типах «указателей на объекты классов» и на ссылках. Указатель представляет собой адрес объекта данного типа в памяти программы, но также является специфическим типов, с которым можно производить определенные операции. В частности, указатели на объекты классов-наследников можно приводить к указателям на их базовые классы. Рассмотрим на примере, каким образом это делается.
Для этого определим функцию, проверяющую одну из аксиом-равенств АТД "стек", а именно, аксиому

top(push(s,x))=x

Функция будет выглядеть так:

bool CheckFirstAxiom(Stack* stack) { stack->push(123); if (stack.top() != 123) returnfalse; returntrue; }

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

ArrayStack stack_impl; if (CheckFirstAxiom(&stack_impl)) std::cout << “first axiom works!\n”; else std::cerr << “first axiom does not works.\n”;

Здесь работает принцип подстановки Лисков, т.е. вместо типа Stack* был подставлен тип ArrayStack*. Кроме того, благодаря тому, что методы базового класса объявлены как виртуальные, производится вызов методов класса-наследника ArrayStack, т.е. работает реализация АТД Stack, выполненная на основе массива.
В описанном примере используется встроенная в язык C++ возможность реализации абстрактных типов данных. При этом реализации АТД подставляются динамически, во время исполнения программы. Однако, в C++ также можно реализовать концепцию АТД по другому, используя механизм шаблонов и, таким образом, связывая АТД с его реализацией на этапе компиляции.
Механизм, реализующий эту возможность, называется в C++ «сuriously recurring template pattern» (CRTP) [8]. Для реализации статического (на этапе компиляции) полиморфизма эта концепция выглядит следующим образом:

1. 
   Создается шаблонный класс B, который берет в качестве параметра шаблона некоторый тип T.
   
2. 
   При объявлении класса-наследника D этот класс наследуется от класса B и, кроме того, передается себя в качестве параметра шаблона класса B.
   

В виде C++ кода это будет выглядеть следующем образом:

template class B { … }; class D : public B { … };

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

template class Stack { public: void push(unsigned int elem) { static_cast(this)->push_impl(elem); }unsignedint top() { return static_cast(this)->top_impl(); } void pop() { static_cast(this)->pop_impl(); } bool empty() { returnstatic_cast(this)->empty_impl(); } };

Это, фактически, спецификация операций абстрактного типа данных Stack. Каждая операция вызывает внутри себя операцию класса-параметра шаблона, представляющего реализацию данного абстрактного типа.