deferred
end
item: G is
-- Последний вставленный элемент.
require
not_empty: not empty
deferred
end
feature - Отчет о статусе
empty: BOOLEAN is
-- Стек пустой?
do
Result := (count = 0)
end
fulclass="underline" BOOLEAN is
-- Стек заполнен?
deferred
end
feature - Изменение элемента
put (x: G) is
-- Втолкнуть x на вершину.
require
not full
deferred
ensure
not_empty: not empty
pushed_is_top: item = x
one_more: count = old count + 1
end
remove is
-- Вытолкнуть верхний элемент.
require
not empty
deferred
ensure
not_fulclass="underline" not full
one_less: count = old count - 1
end
change_top (x: T) is
-- Заменить верхний элемент на x
require
not_empty: not empty
do
remove; put (x)
ensure
not_empty: not empty
new_top: item = x
same_number_of_items: count = old count
end
wipe_out is
-- Удалить все элементы.
deferred
ensure
no_more_elements: empty
end
invariant
non_negative_count: count >= 0
empty_count: empty = (count = 0)
end
Этот класс показывает, как можно реализовать эффективную процедуру, используя отложенные: например, процедура change_top реализована в виде последовательных вызовов процедур remove и put. (Такая реализация для некоторых представлений, например, для массивов, может оказаться не самой лучшей, но эффективные потомки класса STACK могут ее переопределить.)
Если сравнить класс STACK со спецификацией соответствующего АТД, приведенной в лекции 6, то обнаружится удивительное сходство. Подчеркнем, в частности, соответствие между функциями АТД и компонентами класса, и между пунктом PRECONDITIONS и предусловиями процедур. Аксиомы представлены в постусловиях процедур и в инварианте класса.
Добавление операций change_top, count и wipe_out в данном случае несущественно, так как они легко могут быть включены в спецификацию АТД (см. упражнение У6.8). Отсутствие явного эквивалента функции new из АТД также несущественно, так как созданием объектов будут заниматься процедуры-конструкторы в эффективных потомках этого класса. Остаются три существенных отличия.
Первое из них - это введение функции full, рассчитанной на реализации с ограниченным числом элементов стека, например, на реализацию массивами. Это типичный пример ограничения, которое несущественно на уровне спецификации, но необходимо для разработки практических систем. Отметим однако, что это отличие между АТД и отложенным классом можно легко устранить, включив в спецификацию АТД средства для охвата ограниченных стеков. При этом общность не будет потеряна, так как некоторые реализации (например, с помощью списков) могут реализовывать full тривиальными процедурами, всегда возвращающими ложь.
Второе отличие, отмеченное при обсуждении разработки по контракту, состоит в том, что спецификация АТД полностью аппликативна (функциональна), она включает функции без побочных эффектов. А отложенный класс, несмотря на его абстрактность, является императивным (процедурным), например put определена как процедура, изменяющая стек, а не как функция, которая берет в качестве аргумента один стек и возвращает другой.
Наконец, как тоже уже отмечалось, механизм утверждений недостаточно выразителен для некоторых аксиом АТД. Из четырех аксиом стеков
Для всех x: G, s: STACK [G],
1
item (put (s, x)) = x
2
remove (put (s, x)) = s
3
empty (new)
4
not empty (put (s, x))
все, кроме (2), имеют прямые эквиваленты среди утверждений. (Мы предполагаем, что для (3) процедуры-конструкторы у потомков обеспечат выполнение условия empty). Причины таких ограничений уже были объяснены и были намечены возможные пути их преодоления - языки формальных спецификаций IFL.
Отложенные классы как частичные интерпретации: классы поведения
Не все отложенные классы так близки к АТД как STACK. В промежутке между полностью абстрактным классом, таким как STACK, в котором все существенные компоненты отложены, и эффективным классом, таким как FIXED_STACK, описывающим единственную реализацию АТД, имеется место для реализаций АТД с различной степенью завершенности.
Типичным примером является иерархия реализаций таблиц, которая помогла нам понять роль частичной общности при изучении повторного использования. Первоначальный рисунок, показывающий отношения между вариантами, можно сейчас перерисовать в виде диаграммы наследования.
Рис. 14.13. Варианты понятия "таблица"
Наиболее общий класс TABLE является полностью или почти полностью отложенным, так как на этом уровне мы можем объявить несколько компонентов, но не можем предложить никакой существенной их реализации. Среди вариантов имеется класс SEQUENTIAL_TABLE, представляющий таблицы, в которые элементы вставляются последовательно. Примерами таких таблиц являются массивы, связанные списки и последовательные файлы. Соответствующие им классы в нижней части рисунка являются эффективными.
Особый интерес представляют такие классы как SEQUENTIAL_TABLE. Этот класс все еще отложенный, но его статус находится посредине между полностью отложенным статусом как у класса TABLE и полностью эффективным как у ARRAY_TABLE. У него достаточно информации, чтобы позволить себе реализацию некоторых специфических алгоритмов, например, в нем можно полностью реализовать последовательный поиск:
has (x: G): BOOLEAN is
-- x имеется в таблице?
do
from start until after or else equal (item, x) loop
forth
end
Result := not after
end