Бертран Мейер - Основы объектно-ориентированного программирования

Рис. 11.5. Преобразования между абстрактными и конкретными объектами

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

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

Реализация корректна, если (для всех функций af из АТД и их реализаций cf ) диаграмма коммутативна, или, как говорят, имеет место:

Свойство согласованности Класс-АТД

(cf;a) = (a;af)

где символ " ; " обозначает композицию функций. Другими словами, для любых двух функций f и g , их композиция: f;g задает функцию h , такую что h(x) = g(f(x)) для каждого применимого x .

(Композицию f;g также записывают в виде: g ° f , с обратным порядком применения операндов.)

Свойство устанавливает, что для каждого конкретного объекта CONC_1 не имеет значения, в каком порядке применяются преобразования (функция абстракции, а затем af или вначале cf , а потом функция абстракции); оба пути, помеченные на рисунке штрихованными линиями, ведут к одному и тому же значению - абстрактному объекту ABST_2 . Результат будет одним и тем же, если:

[x].Применить конкретную функцию класса cf , а потом функцию абстракции а , получив a(cf(CONC_1)) .

[x].Применить функцию абстракции а , а потом функцию АТД - af , получив af(a(CONC_1)) .

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

count_non_negative: 0 <= count

count_bounded: count <= capacity

Такие утверждения составляют часть инварианта класса, известную как инвариант реализации (implementation invariant). Они позволяют задать соответствие представления реализации, выбранное в классе, (здесь это атрибуты count , capacity , representation ) - визави соответствующего АТД.

Рис. 11.5помогает понять концепцию инварианта реализации. Он иллюстрирует характеристические свойства функции абстракции, представленной вертикальной стрелкой на рисунке. Об этом стоит поговорить подробнее.

Прежде всего, корректно ли рассматривать а , как функцию? Напомним, что функция (тотальная или частичная) отображает каждый элемент исходного множества ровно в один элемент целевого множества, в противоположность общему случаю отношения, не имеющего такого ограничения. Рассмотрим обратное преобразование (сверху - вниз) от абстрактного объекта к конкретному. Будем называть его отношением представления (representation relation); как правило, это отношение не является функцией, так как существует множество представлений одного и того же абстрактного объекта. В реализации стека массивом, где каждый стек задан парой , абстрактный стек имеет много различных представлений, иллюстрируемых следующим рис. 11.6. Все они имеют одно и то же значение count и одинаковые элементы массива representation для всех индексов в пределах от 1 до count , но размер массивов - capacity - может быть любым значением, большим или равным count ; элементы массива с индексом, большим count могут содержать произвольные значения.

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

count := count - 1

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