Модель с АТД

Последний раз обновлено 27.06.01

Содержание

Можно составить модель таким образом, чтоб она была не структурной. Забегая вперед, назовем интересующую нас модель объектной. Для начала надо ввести одно новое понятие. Я думаю, что его хорошее понимание является ключом к объектной модели.

АТД – ключ к объектной модели

Модель с АТД

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

АТД – ключ к объектной модели

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

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

Сравнение с модулем

АТД – ключ к объектной модели

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

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

Функции АТД, как и функции модуля, исполняются в контексте реализации отличном от контекста их вызова. Для модуля такой контекст реализации один. Для АТД каждая переменная имеет свой контекст реализации, возможно разделяя часть его между всеми переменными. В модуле можно поддерживать несколько контекстов искусственно, как в примере "Реализация модуля с несколькими контекстами в структурной программе" (Пример 1) в разделе "Структурная программа:Модуль", но это происходит не автоматически. Если в программе есть только одна переменная АТД, то преимущества АТД не так очевидны. С таким же успехом можно вызывать функции модуля.

Сравнение с обычным типом

АТД – ключ к объектной модели

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

Противоположное: в Паскале есть встроенный тип "строка". Кто работал со строками на С, тот может быстро вспомнить что нужно сделать, чтобы сложить две произвольные динамические строки (char*):

  1. убедиться что обе строки одновременно не NULL
  2. убедиться что сумма длин не 0
  3. выделить память для не NULL новой строки
  4. скопировать туда не NULL строки не 0 длины
  5. плюс очистить если надо складываемые строки

Такие подробности в вызывающем строку коде не относятся к сути задачи, которая этим кодом решается, код может быть отображает текст и ему все равно, нулевая ли длина строки и как и где выделена память. "Природой" для строки в контексте этого вызывающего кода будет все, кроме операции сложения: длина, расположение в памяти, содержимое. Тип "строка" в С, которого там, кстати, и нет, его заменитель (char*) не является АТД относительно операции сложения.

Перегрузка функций

АТД – ключ к объектной модели

Модель с АТД обладает интересной особенностью: можно применять к разным АТД функции с одинаковыми именами. Примером таких функций являются арифметические операции для встроенных типов. При одинаковом обозначении, эти операции имеют разный код для int и double. В языке с поддержкой АТД это распространяется на любую функцию АТД. Это хорошо не только с точки зрения легкости задания имен функций (см. далее шаблоны кода).

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

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

Перегрузить функцию можно по любому типу, не только по АТД. Пример (Пример 1) с перегрузкой, где перегруженная функция сlear() принимает разные типы параметров. Можно видеть, что коду (1) соответствует эквивалентный код на структурном языке ( правая половина ), если дополнить структуру полем тип_АТД type;

Пример 1
Реализация АТД с перегрузкой функций и без
с перегрузкойбез перегрузки 
T1      var_1[50];
void    clear(T1* v, int n);

T2      var_2[50];
void    clear(T2* v, int n);

    //(1)
    for(int i=0; i < 5; i++)
     {
      if(i&1) clear(&var_1[i], i);
      else clear(&var_2[i], i);
     }
 
/*(2)*/
#define clear(v,n)\
        switch((v)–>type)\
         {\
          case C_T1:\
           T1_clear( (T1*)((void*)(v)), (n) );\
          break;\
          \
          case C_T2:\
           T2_clear( (T2*)((void*)(v)), (n) );\
          break;\
          \
          default: assert(0);\
         }

    /*(1)*/
int    i;
    for(i=0; i < 5; i++)
     {
      var_1[i].type=C_T1;
      var_2[i].type=C_T2;

      if(i&1) clear(&var_1[i], i)
      else clear(&var_2[i], i) 
     }

Раннее и позднее связывание

АТД – ключ к объектной модели

Жульничество в (Пример 1) в (2): ( #define…(T1*)((void*)(v))… ) к которому приходится прибегать, показывает, что такой метод на структурном языке никогда бы не прижился, и еще он показывает, что перегрузка может быть реализована компилятором "автоматическим switch" по некому скрытому полю структуры содержащему индекс типа. Подобный вид перегрузки, реальный подбор функции при которой происходит во время выполнения называют поздним связыванием.

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

Раннее связывание дает выигрыш в скорости работы, но не всегда применимо. Нельзя модифицировать код (1) из (Пример 1) так

Пример 2
Позднее связывание
for(int i=0; i < 25; i++)сlear2( (i&1)? (void*)&var_1[i]: (void*)&var_2[i] , i );

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

Шаблоны кода

АТД – ключ к объектной модели

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

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

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

Реализация АТД на структурном языке

АТД – ключ к объектной модели

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

В чистом структурном языке, без модернизации, тоже возможен почти автоматический подбор функции и шаблоны кода. Это можно сделать так (Пример 3). Пример похож на пример из "Структурная программа: модуль", но имеет ряд отличий. Ссылка на себя при вызове функции повторяется в первом параметре.

Неуклюжесть конструкций объясняется именно тем, что в структурном языке нет поддержки АТД. Использование первой ссылки, при вызове, заменяет "автоматический switch" компилятора, а использование ссылки в параметре нужно для доступа к данным. При такой организации АТД, в пределах одного типа АТД, для каждой переменной АТД будет общий код и своя структура данных. Функции будут иметь позднее связывание.

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

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

Проблемы модели с АТД

Модель с АТД

Задание модели с АТД

Проблемы модели с АТД

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

Можно сразу выделить этапы, необходимые для создания программы:

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

Язык, поддерживающий АТД, должен:

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

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

Другие примеры АТД

Проблемы модели с АТД

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

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

Можно реализовать это на С, подобно (Пример 3), несмотря на косность конструкций, это позволит заметить ряд особенностей и привыкнуть к АТД лучше.

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

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

Готовые результаты есть в листингах приложений.

Пример 3
Реализация АТД на структурном языке
Интерфейс АТД 
typedef struct complex *t_complex_p;
typedef struct complex
{
    /*сами данные структуры*/
    double    re,im;

    /*указатели на операции над данными*/

    /*арифметические операции*/
    void    (*add)(t_complex_p this,t_complex_p c);
    void    (*sub)( t_complex_p this,t_complex_p c);

    /*сравнение (комплексные числа
      сравнивают на равно/неравно)*/
    char    (*compare)(t_complex_p this,t_complex_p c);

}t_complex;

/*создание переменной*/
void    t_complex_constructor(t_complex_p this);
Реализация АТД 
static void    t_complex_add(t_complex_p this,t_complex_p c);
static void    t_complex_sub(t_complex_p this,t_complex_p c);
static char    t_complex_compare(t_complex_p this,t_complex_p c);

void    t_complex_constructor(t_complex_p c)
{
    assert(c);
    c->add=t_complex_add;
    c->sub=t_complex_sub;
    c->compare=t_complex_compare;
    c->im=c->re=.0;
}

void    t_complex_add(t_complex_p this,t_complex_p c)
{
    assert(this); assert(c);
    this->re+=c->re; this->im+=c->im;
}

char    t_complex_compare(t_complex_p this,t_complex_p c)
{
    assert(this); assert(c);
    return ( (this->re == c->re)&&(this->im == c->im) );
}
Использование АТД 
t_complex    complex[2];

    t_complex_constructor(&complex[0]); 
    t_complex_constructor(&complex[1]);

    complex[0].re=.34;
    complex[1].im=.43;

    /*сравнить и если не равно, то сложить*/
    if(! (*(complex[0].compare)) (&complex[0],complex[1]) )
     {
      (*(complex[0].add))( &complex[0],&complex[1]); 
     }

Таблица 1
Варианты задач для создания АТД
ДанныеФункции
Строка
указатель на строку \0( он же на выделенную память): char_p str
размер выделенной памяти: u_int mem_size
 присвоить: void set(char*);
прибавить(+=): void add(char*);
сохранить в поток "wb": void save(FILE*fi);
загрузить из потока "rb": void load(FILE*fo);
Список указателей на структуры: элемент
typedef struct plist_item * t_plist_item_p;
typedef struct plist_item{
t_plist_item_p next;/*связь списка*/
char_p obj_pointer; /*данные хранения*/
}t_plist_item;		.
Список указателей на структуры: список
всего элементов списка: u_int items;
начало списка: t_plist_item list;
текущий элемент: u_int number; 		вставить данные за текущим элементом:
void insert(void*);
удалить данные и элемент списка:
void remove();
получить данные элемента n:
void* index(int);
очистить список:
void zap();

Недостатки модели с АТД

Проблемы модели с АТД

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

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

Таблица 2
Уровни абстракций элементов АТД модели
Абстракции от структурной модели
Перегруженная функция (раннее связывание)
АТД Шаблоны кода (позднее связывание)

Модель с АТД

Сайт создан в системе uCoz