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

В предыдущей части было сделано утверждение относительно роли абстракций типов данных в программировании. Для того, чтобы в этом убедиться, следует вернуться к понятию “переменная”, но теперь уже – в контексте программирования. Кто-то может сказать, что переменная – это имя в программе. Что будет не совсем точно, потому что “имя”, обладает единственным свойством – его уникальностью. Очевидно, что переменные обладают и другими свойствами. Кто-то скажет, что это “хранилище”, которое принимает различные значения. Это опять не совсем точно в отношении переменных в программах, так как часто переменная не хранит значение, которое ей присваивается, при этом значение не может существовать в программе само по себе, ведь оно тоже абстрактно. Оно будет иметь некоторое конкретное представление.

Например, число $42$ является значением, оно будет представлено в памяти компьютера в виде двоичного:

2^{5} + 2^{3} + 2^{1}

;

а в программе – еще и в виде десятичного:

4 * 10^{1} + 2 * 10^{0}

;

или шестнадцатеричного:

2 * 16^{1} + 10 * 16^{0} ㅤилиㅤ 2 A_{16}

набора данных.

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

Так как математические абстракции принято классифицировать по каким-либо признакам для удобства (например, переменные разделяются на такие, которые представляют целые или дробные числа), такой подход применяется и в языках программирования. Классификация производится по свойствам, перечисленным выше, а именно: какое множество значений принимают данные, какую форму принимают значения из этого множества, какие операции возможны для значений из этого множества [Wirth]. То есть, тип данных – это совокупность представления какого-то значения в программе и в памяти компьютера, которая позволяет работать с конкретным значением в программе с помощью соответствующих операций. Внутри самой программы также есть “конкретные” сущности и абстрактные сущности. Первые ассоциируются с объектами, вторые – со значениями [McJones]. В общем смысле, объект – это некоторое отношение между типом данных и самими данными в памяти компьютера. Свойства объекта определяются его типом.

Второе значение слова “абстрактный” – удаленный, то есть, рассматриваемый в отрыве от своего источника. Так разделение подходов в программировании на парадигмы (программирование может быть структурное, объектно-ориентированное, функциональное и т.д.) является абстракцией, потому что с точки зрения целевого устройства все эти парадигмы производят один и тот же машинный код, который исполняется независимо от того, какую идею вкладывал в него программист. Предназначение абстракций в программировании заключается в том, чтобы проектировать программы, понимать их и проверять их логику на правильность на основании законов, которые управляют абстракциями (например, на основании законов математики), не отвлекаясь на подробности реализации этих абстракций в конкретном компьютере.

Рассмотрим несложный пример. Предположим, что перед вами поставлена задача разработать тип данных в языке С, который будет использоваться для представления рациональных² чисел в различных программах. Например, такое число можно было бы хранить в виде структуры:


struct rational {
    int p;
    int q;
};

Тогда атрибут $p$ – это числитель, а $q$ – знаменатель. В этом случае создание рационального числа в программе могло бы выглядеть так:


rational a = {1, 2};

rational b;
b.p = 5;
b.q = 6;

rational c;

Все три способа являются правильными с точки зрения компилятора (в данном примере используется gcc³). Но внимательный читатель может заметить, что тут есть проблемы. Во-первых, в качестве числителя и знаменателя можно передавать любые значения, в том числе $0$ . Это, конечно, противоречит правилам работы с рациональными числами, так как $0$ в числителе должен обнулять все число, а в знаменателе $0$ недопустим. Во-вторых, и числитель, и знаменатель можно свободно менять уже после создания переменной, что чревато всеми проблемами, перечисленными выше. В-третьих, оба атрибута можно оставить без значений, что делает такую переменную бесполезной, а поведение программы, которая ее использует, непредсказуемым.

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


rational cons(int x, int y) {
    assert(y != 0);
    if(x == 0) return {0, 0};
    rational r;
    if(y < 0) {
        r.p = -x;
        r.q = -y;
    }
    else {
        r.p = x;
        r.q = y;
    }
    return r;
}

Функция проверяет: числитель на нулевое значение (тогда вся дробь обнуляется), знаменатель на нулевое значение (тогда даже нет смысла продолжать, и работа программы прерывается c помощью макроса assert из соответствующей библиотеки; в одной из следующих глав есть более элегантный способ справляться с этой ситуацией), знаменатель на отрицательное значение (тогда отрицание переносится на числитель).


rational a = cons(1, 2);

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

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

Упражнения

Абстрактные типы данных будут составлять основу большинства концепций, обсуждаемых в этом тексте, поэтому с ними нужно освоиться как можно лучше. Для этого читателю предлагается дополнить тип данных, описанный выше, несколькими операциями. Во-первых, было бы неплохо поддерживать сокращенную форму всех создаваемых в программе рациональных чисел (при заданных числителе и знаменателе, которые кратны одному и тому же числу, делить их на это число по умолчанию: $\frac{5}{10}$ превращать в $\frac{1}{2}$ , $\frac{9}{6}$ – в $\frac{3}{2}$ ). Во-вторых, было бы удобно отображать такие числа в текстовом виде как дроби, а не пару целых чисел. Пример этих дополнений будет ниже, но настоятельно рекомендуется сделать их самостоятельно, и только в случае полной неудачи посмотреть реализацию.

Пример решения

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


void reduce(rational &r) {
    if(r.q == 1 || r.p == 0) return;
    else {
        int d = gcd(abs(r.p), r.q);
        r.p /= d;
        r.q /= d;
    }
}

Обратите внимание на то, что тип данных для переменной d указан явно, что можно сделать только с несколькими допущениями: результат функции gcd имеет значение типа int или без потерь приводится к нему; числитель и знаменатель аргумента r оба могут участвовать в выражениях вместе со значениями типа int. Этот дефект алгоритма в последствии придется исправить. Обобщенное программирование является одним из инструментов для этого и подробно обсуждается в соответствующей главе. Реализация нахождения наибольшего общего делителя могла бы выглядеть так.


int gcd(int m, int n) {
    while(n != 0) {
        int t = m % n;
        m = n;
        n = t;
    }
    if(m < 0) m = -m;
    return m;
}

Здесь используется модифицированный алгоритм Евклида [Степанов]. Данный алгоритм легко переписывается с помощью рекурсии для тех языков, которые не имеют встроенных циклов. У многих реализаций этого алгоритма есть некоторые недостатки. Алгоритм зависит от операции деления, которая является недостаточно эффективной. Алгоритм также зависит от типов данных его аргументов, что привязано к архитектуре процессора и используемому компилятору, поэтому неудачная реализация может нарушать важные математические свойства алгоритма [Cormen]. На практике часто можно встретить использование расширенной версии алгоритма Евклида или двоичного алгоритма, разработанного Д. Штайном [Knuth]. Поэтому лучшим выбором для среднестатистического разработчика будет использование встроенного в стандартную библиотеку алгоритма, реализация которого остается на совести авторов компилятора. Например, в С++:


template<class M, class N> constexpr std::common_type_t<M, N> gcd(M m, N n);

Стандартная функция использует шаблоны типов для того, чтобы в качестве аргументов можно было передавать любые целые числа. С этого момента будем предполагать, что все упоминания функции gcd используют эту версию, поставляемую с языком С++.

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


char *rstr(const rational &r, char *ret) {
    int i = 0;
    auto f = [&] (int n) {
        char *start = ret + i;
        while(n) {
            ret[i++] = (n % 10) + '0';
            n /= 10;
        }
        char *end = ret + i - 1;
        while(start < end) {
            char tmp = *start;
            *start = *end;
            *end = tmp;
            start++;
            end--;
        }
    };
    f(r.p);
    if(r.q > 1) {    
        ret[i++] = '/';
        f(r.q);
    }
    return ret;
}

Тонкий момент в коде выше связан с включением в функцию другой функции. Это сделано исходя из того факта, что внутренняя функция никогда не будет использоваться отдельно от родительской функции, соответственно нет причины захламлять пространство имен, связанное с этим файлом, именем еще одной функции. Сама внутренняя функция f сделана с помощью лямбда-выражения [Вики-конспекты(г)]. Эта функция определяет цифры, составляющие числитель и знаменатель, с помощью остатка от деления на $10$ и записывает эти цифры в виде печатных символов в предоставленный для этого массив. Сами печатные символы получаются прибавлением ASCII-кода [ANSI] символа $"0"$ к числовому значению, что даст ASCII-код искомой цифры (так как все коды в таблице идут по порядку, начиная с $0$ ).

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

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

Во-вторых, функция возвращает строку, которая передается в нее изначально, что может показаться бесполезным. Причина состоит в том, что строки в С и С++ являются указателями, что подразумевает отсутствие процесса “конструирования” объекта внутри функции. Это значит, что данная функция не создает новых объектов, а только лишь дублирует адрес строки, в которой были произведены необходимые манипуляции с данными. Другими словами, можно считать, что у функции нет возвращаемого значения:


rational a = cons(10, 20);
reduce(a);
char tmp[100]{};
rstr(a, tmp);
assert(!strcmp("1/2", tmp));

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


char tmp[100]{};
assert(!strcmp(“1/2”, rstr(a, tmp)));

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


tmp = rstr(a);

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

Сноски

¹Программирование можно считать одной из областей математики, языки программирования можно называть абстрактными компьютерами [Strachey].

²Действительное число, которое можно представить как пару целых чисел, записанных одно над другим через прочерк, в виде дроби.

³GCC, the GNU Compiler Collection, gcc.gnu.org.