Бертран Мейер - Основы объектно-ориентированного программирования
Конечно, абстрактные типы данных не ограничиваются вопросами скрытия информации, хотя многие их элементарные изложения дальше этого не идут. Собственно АТД были введены Лисков и Зиллеса [Liskov 1974]; более алгебраические представления были приведены в [M1976] и [Guttag 1977]. Так называемая группа ADJ (Гоген, Тэтчер, Вагнер) исследовали алгебраические основания абстрактных типов данных, используя теорию категорий. В частности, см. их важную статью [Goguen 1978], опубликованную в коллективной монографии.
На основе абстрактных типов данных основано несколько языков спецификаций. Двумя результатами группы ADJ являются CLEAR [Burstall 1977] [Burstall 1981] и OBJ-2 [Futatsugi 1985]. См. также Larch, предложенный Гуттагом, Хорнингом и Вингом [Guttag 1985].
Идеи АТД повлияли на такие языки формальных спецификаций как Z в ряде его воплощений [Abrial 1980] [Abrial 1980a] [Spivey 1988] [Spivey 1992] и VDM [Jones 1986]. Недавние расширения Z обнаружили тесную связь с ОО-идеями, см. например, Object Z [Duke 1991] и дальнейшие ссылки в гл. 11.
Фраза "разделение интересов" является центральной в работе Дейкстры, см. в частности, его "Дисциплину программирования" [Dijkstra 1976].
Понятие достаточной полноты было впервые опубликовано Гуттагом и Хорнингом [Guttag 1978] (оно основано на диссертации Гуттага 1975г.)
Идея о том, что переход от спецификации к проектированию означает переключение с неявного на явное путем отождествления АТД с декартовым произведением его простых запросов, была предложена в [M 1982] как часть теории описания структур данных в терминах трех разных уровней (физического, структурного, неявного).
Упражнения
У6.1 Точки
Написать спецификацию, задающую абстрактный тип данных ТОЧКА (POINT), моделирующий точки на плоскости в планиметрии. Эта спецификация должна отражать следующие аспекты: декартовы и полярные координаты, повороты, параллельные переносы, расстояние от начала координат, расстояние до другой точки.
У6.2 Боксеры
Члены Ассоциации Боевых Петухов - боксерской лиги - регулярно встречаются в поединках, чтобы установить их относительную силу. В поединке встречаются два боксера, и его результатом является победа одного и поражение другого боксера или ничья. Если выявлен победитель, то результат поединка используется для изменения рангов боксеров лиги: объявляется, что победитель превосходит побежденного и каждого боксера b, которого до поединка превосходил проигравший. Остальные соотношения остаются без изменений.
Опишите эту проблему как набор абстрактных типов данных: АТД_ЛИГА, БОКСЕР, ПОЕДИНОК. (Указание: не вводите явно понятие "ранг", а промоделируйте его с помощью функции "превосходит", выражающей отношение превосходства на множестве боксеров лиги.)
У6.3 Банковские счета
Написать спецификацию АТД "счет в банке" с такими операциями как "положить на счет", "снять со счета", "текущий баланс", "владелец", "смена владельца".
Каким образом добавить функции, представляющие операции открытия и закрытия счета? (Указание: эти функции являются функциями другого АТД).
У6.4 Сообщения
Рассмотрите знакомую вам систему электронной почты. Определите в духе этой лекции абстрактный тип данных ПОЧТОВОЕ_СООБЩЕНИЕ. Включите в него не только функции-запросы, но и команды и конструкторы.
У6.5 Имена
Разработайте абстрактный тип данных ИМЯ, в котором учитывались бы различные компоненты полного имени человека.
У6.6 Текст
Рассмотрите понятие текста, обрабатываемого текстовым редактором. Задайте это понятие в виде АТД. (Это задание оставляет достаточно много свободы спецификатору, не забудьте включить содержательное описание тех свойств текста, которые вы избрали для моделирования в АТД).
У6.7 Покупка дома
Напишите спецификацию абстрактного типа данных для задачи покупки дома, описанной в предыдущей лекции. Уделите особое внимание определению логических ограничений, выраженных в виде предусловий и аксиом спецификации АТД.
У6.8 Дополнительные операции для стеков
Модифицируйте спецификацию АТД для стеков, включив в нее операции count (возвращает число элементов стека), change_top (заменяет верхний элемент стека заданным элементом) и wipe_out (удаляет все элементы). Не забудьте включить необходимые аксиомы и предусловия.
У6.9 Ограниченные стеки
Измените приведенную в этой лекции спецификацию стеков так, чтобы она описывала стеки ограниченной емкости. (Указание: введите емкость как явную функцию-запрос и сделайте функцию put частичной).
У6.10 Очереди
Описать в виде АТД очереди (первым пришел - первым ушел) в том же стиле, что и стеки. Обратите внимание на общие и отличительные черты этих АТД. (Указание: аксиомы для item и remove должны отличаться, при описании put (s,x) рассмотрите случаи, когда очередь s пуста и непустая).
У6.11 Распределители
(Это упражнение предполагает, что вы выполнили предыдущее).
Определите общий АТД РАСПРЕДЕЛИТЕЛЬ, покрывающий и стеки и очереди.
Рассмотрите механизм для задания более специальных спецификаций АТД (таких как стеки и очереди) с помощью ссылок на общие спецификации такие, как спецификация распределителей. (Указание: посмотрите на механизм наследования, изучаемый в следующих лекциях).
У6.12 Булевский -- BOOLEAN
Определите абстрактный тип данных BOOLEAN так, чтобы его можно было использовать в определениях других АТД из этой лекции. Можно считать, что операции равенства и неравенства (= и ) автоматически определены для каждого АТД.
У6.13 Достаточная полнота
(Это упражнение предполагает, что вы выполнили одно или несколько предыдущих упражнений).
Изучите спецификацию АТД, написанную вами в качестве решения одного из предыдущих упражнений, и попытайтесь доказать, что она является достаточно полной. Если она не достаточно полная, то объясните, почему и покажите, как ее можно исправить или расширить, чтобы сделать достаточно полной.
У6.14 Непротиворечивость
Докажите, что приведенная в этой лекции спецификация стеков является непротиворечивой.
Лекция 7. Статические структуры: классы
Анализируя основы программной инженерии, мы поняли причины, требующие совершенствования модульного подхода - повторное использование и расширяемость кода. Мы осознали, что традиционные методы исчерпали себя, - централизованная архитектура ограничивает гибкость. Мы выявили хорошую теоретическую основу ОО-подхода - абстрактные типы данных. Теперь, когда проблемам уделено достаточно внимания, вперед к их решению! Раздел содержит введение в фундаментальные методы ОО-анализа, проектирования и программирования. Необходимые обозначения (элементы описания) будут вводиться по мере необходимости. Сначала необходимо рассмотреть базовые строительные блоки - классы.
Классы, а не объекты - предмет обсуждения
Какова центральная концепция объектной технологии? Необходимо дважды подумать, прежде чем ответить "объект". Объекты полезны, но в них нет ничего нового.
С тех пор, как структуры используются в Cobol, с тех пор, как в Pascal существуют записи, с тех пор как программист написал на C первое определение структуры, человечество располагает объектами.
Объекты важны при описании выполнения ОО-систем. Но базовым понятием объектной технологии является класс. Обратимся вновь к его определению. (Детальное обсуждение объектов содержится в следующей лекции.)
Определение класса
Класс - это абстрактный тип данных, поставляемый с возможно частичной реализацией.
Абстрактные типы данных (АТД) являются математическим понятием, пригодным на этапе подготовки спецификации - в процессе анализа. Понятие класса, предусматривая частичную или полную реализацию, обеспечивает необходимую связь с разработкой ПО на этапах проектирования и программирования. Напомним, класс называется эффективным, если его реализация полна, и отложенным - при частичной реализации.
Аналогично АТД, класс - это тип, описывающий множество возможных структур данных, называемых экземплярами (instances) класса. Экземпляры АТД являются абстракциями - элементами математического множества. Экземпляр класса конкретен - это структура данных, размещаемая в памяти компьютера и обрабатываемая программой.
