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

Конечно, абстрактные типы данных не ограничиваются вопросами скрытия информации, хотя многие их элементарные изложения дальше этого не идут. Собственно АТД были введены Лисков и Зиллеса [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] как часть теории описания структур данных в терминах трех разных уровней (физического, структурного, неявного).

Написать спецификацию, задающую абстрактный тип данных ТОЧКА (POINT), моделирующий точки на плоскости в планиметрии. Эта спецификация должна отражать следующие аспекты: декартовы и полярные координаты, повороты, параллельные переносы, расстояние от начала координат, расстояние до другой точки.

Члены Ассоциации Боевых Петухов - боксерской лиги - регулярно встречаются в поединках, чтобы установить их относительную силу. В поединке встречаются два боксера, и его результатом является победа одного и поражение другого боксера или ничья. Если выявлен победитель, то результат поединка используется для изменения рангов боксеров лиги: объявляется, что победитель превосходит побежденного и каждого боксера b , которого до поединка превосходил проигравший. Остальные соотношения остаются без изменений.

Опишите эту проблему как набор абстрактных типов данных: АТД_ЛИГА, БОКСЕР, ПОЕДИНОК. (Указание: не вводите явно понятие "ранг", а промоделируйте его с помощью функции "превосходит", выражающей отношение превосходства на множестве боксеров лиги.)

Написать спецификацию АТД "счет в банке" с такими операциями как "положить на счет", "снять со счета", "текущий баланс", "владелец", "смена владельца".

Каким образом добавить функции, представляющие операции открытия и закрытия счета? (Указание: эти функции являются функциями другого АТД).

Рассмотрите знакомую вам систему электронной почты. Определите в духе этой лекции абстрактный тип данных ПОЧТОВОЕ_СООБЩЕНИЕ. Включите в него не только функции-запросы, но и команды и конструкторы.

Разработайте абстрактный тип данных ИМЯ, в котором учитывались бы различные компоненты полного имени человека.

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

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

Модифицируйте спецификацию АТД для стеков, включив в нее операции count (возвращает число элементов стека), change_top (заменяет верхний элемент стека заданным элементом) и wipe_out (удаляет все элементы). Не забудьте включить необходимые аксиомы и предусловия.

Измените приведенную в этой лекции спецификацию стеков так, чтобы она описывала стеки ограниченной емкости. (Указание: введите емкость как явную функцию-запрос и сделайте функцию put частичной).