Основы объектно-ориентированного программирования
Шрифт:
Сила спецификаций АТД проистекает из их способности отражать только существенные свойства структур данных без лишних деталей. Приведенная выше спецификация стеков выражает все, что нужно по существу знать о понятии стека, и не включает ничего, что относилось бы к каким-либо конкретным реализациям стеков. Это вся правда о стеках, и ничего кроме правды.
Такие спецификации задают общую модель вычислений на соответствующих структурах данных. Определенные в спецификации абстрактного типа данных функции позволяют строить сложные выражения, а аксиомы АТД позволяют упрощать такие выражения и получать более простые результаты. Сложное стековое выражение является
Вот пример. Рассмотрим для приведенной выше спецификации АТД STACK следующее выражение stackexp:
По-видимому, выражение stackexp будет проще понять, если мы представим его как последовательность вспомогательных выражений:
Какой бы вариант определения вы ни выбрали, по нему несложно восстановить вычисление, математической моделью которого является stackexp: создать новый стек; втолкнуть в него элементы x1, x2, x3 (в указанном порядке); удалить верхний элемент (x3), назвав получившийся стек s3; создать другой пустой стек и т. д. Этот процесс графически представлен на рис. 6.5 .
Можно легко найти значение такого АТД выражения, нарисовав последовательно несколько таких рисунков. (Здесь найдено x4). Но теория позволяет нам получить этот результат формально, не обращаясь к рисункам, а только последовательно применяя аксиомы для упрощения выражения, до тех пор, пока дальнейшее упрощение станет невозможным. Например:
[x]. Применить A2 для упрощения s3– т. е. заменить remove(put (put (put (s1, x1), x2), x3)) на выражение put (put (s1, x1), x2)). (Согласно A2 всякую пару remove-put можно выбросить).
Рис. 6.5. Манипуляции со стеком
[x]. По той же аксиоме s6
И так далее. Последовательность таких упрощений, выполненная механически так же легко и как последовательность упрощений в элементарной арифметике, приведет к значению выражения stackexp, которое действительно равно x4 (попробуйте проверить это сами, аккуратно проведя весь процесс упрощения).
Этот пример позволяет отметить одну из важнейших теоретических ролей абстрактных типов данных: они предоставляют формальную модель для понятий программы и выполнения программы. Эта модель чисто математическая: в ней нет императивных понятий состояния программы, переменных с изменяемыми во времени значениями, последовательности выполняемых действий. Она основана на обычных математических методах преобразования выражений.
От абстрактных типов данных к классам
Итак, у нас имеется отправная точка - элегантная математическая теория для моделирования структур данных и, как мы только что видели, в целом - программ. Но наша цель - это архитектура ПО, а не математическая или даже теоретическая информатика! Не сбились ли мы с нашего пути? Отнюдь. При поиске подходящей модульной структуры, основанной на типах объектов, АТД предоставляют механизм описания высокого уровня, не связанный с особенностями реализации. Это приведет нас к фундаментальным структурам ОО-технологии.
Классы
В поиске, начатом в лекции 3, АТД будут служить непосредственной основой модулей. Точнее, ОО-система будет строиться (на уровне анализа, проектирования и реализации) как совокупность взаимодействующих, частично или полностью реализованных АТД. Основное понятие здесь - класс:
Определение: класс
Класс - это абстрактный тип данных, снабженный некоторой (возможно частичной) реализацией
Таким образом, чтобы получить класс, мы должны построить АТД и решить, как его реализовывать. АТД - это математическое понятие, а реализация - это его версия, ориентированная на компьютер. Приведенное определение, однако, утверждает, что реализация может быть частичной. Введенные ниже термины позволяют отделить этот случай от полностью реализованного класса:
Определение: отложенный и эффективный классы
Полностью реализованный класс называется эффективным (effective). Класс, который реализован лишь частично или совсем не реализован, называется отложенным (deferred). Всякий класс является либо отложенным, либо эффективным.
Чтобы получить эффективный класс, требуется предусмотреть все детали реализации. Для отложенного класса можно выбрать определенный уровень реализации, но при этом оставить некоторые аспекты реализации незавершенными. В самом крайнем случае при частичной реализации можно вообще отказаться от принятия каких-либо решений о ее уточнении. В этом случае получившийся класс будет полностью отложенным и будет эквивалентен АТД.