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

f : A × B × ... X

зависит от того, где имя АТД, скажем T , встречается среди типов A, B, ... X , включенных в эту сигнатуру:

[x].Если Т появляется только справа от стрелки, f является создателем; в классе это соответствует процедуре создания.

[x].Если Т появляется только слева от стрелки, f является запросом, обеспечивающим доступ к свойству экземпляра класса. Для класса запрос соответствует атрибуту или функции; термин запрос сохраняется и для класса, когда нет необходимости различать, как он реализован.

[x].Если Т появляется как слева, так и справа от стрелки, f является командой, вырабатывающей новый объект из одного или нескольких уже существующих. На этапе реализации f часто задается процедурой (также называемой командой), которая модифицирует существующий объект, не создавая новый, как это делают функции.

Из соответствия между АТД функциями и компонентами класса можно вывести соответствие между утверждениями класса и семантическими свойствами АТД.

[x].Предусловие для специфицированной в АТД функции появляется как предусловие программы, соответствующей данной функции.

[x].Аксиома, включающая команду, и, возможно, одну или более функций запросов, появится как постусловие соответствующей процедуры.

[x].Аксиомы, включающие только запросы, появятся как постусловия соответствующих функций или как инвариант. Последнее обычно имеет место, если более чем одна функция включена в аксиому, или, по меньшей мере, один из запросов реализован в виде атрибута.

[x].Аксиомы, включающие функцию создатель, появятся в постусловии соответствующей процедуры создания.

В этот момент следует вернуться назад и сравнить аксиомы АТД STACK с утверждениями класса STACK4 (включая и те, которые даны для класса STACK2 ).

Этот раздел требует от читателя определенной математической подготовки.

Полезно рассмотреть предшествующее обсуждение в терминах следующего рисунка, навеянного работой [Hoare 1972a], в которой описывается понятие " С является корректной реализацией А ".

Рис. 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) .