Блинков Ю.А., Месянжин В.В. (сост) Основы объектно-ориетнированного программирования. Саратовский Государственный университет, механико-математический факультет

Подождите немного. Документ загружается.

– new: STACK [G]

• АКСИОМЫ (AXIOMS)

– Для всех x: G, s: STACK [G],

A1 item (put (s, x)) = x

A2 remove (put (s, x)) = s

A3 empty (new)

A4 not empty (put (s, x))

• ПРЕДУСЛОВИЯ (PRECONDITIONS)

– remove (s: STACK [G]) require not empty (s)

– item (s: STACK [G]) require not empty (s)

Сила спецификаций АТД проистекает из их способности отражать только существенные свойства

структур данных без лишних деталей. Приведенная выше спецификация стеков выражает все, что

нужно по существу знать о понятии стека, и не включает ничего, что относилось бы к каким-либо

конкретным реализациям стеков. Это вся правда о стеках, и ничего кроме правды.

Такие спецификации задают общую модель вычислений на соответствующих структурах данных.

Определенные в спецификации абстрактного типа данных функции позволяют строить сложные вы-

ражения, а аксиомы АТД позволяют упрощать такие выражения и получать более простые резуль-

таты. Сложное стековое выражение является математическим эквивалентом программы, а процесс

упрощения является математическим эквивалентом вычисления или выполнения этой программы.

Вот пример. Рассмотрим для приведенной выше спецификации АТД STACK следующее выражение

stackexp:

item (remove (put (remove (put (put (

remove (put (put (put (new, x1), x2), x3)),

item (remove (put (put (new, x4), x5)))), x6)), x7)))

По-видимому, выражение stackexp будет проще понять, если мы представим его как последова-

тельность вспомогательных выражений:

s1 = new

s2 = put (put (put (s1, x1), x2), x3)

s3 = remove (s2)

s4 = new

s5 = put (put (s4, x4), x5)

s6 = remove (s5)

y1 = item (s6)

s7 = put (s3, y1)

s8 = put (s7, x6)

s9 = remove (s8)

s10 = put (s9, x7)

s11 = remove (s10)

stackexp = item (s11)

Какой бы вариант определения вы ни выбрали, по нему несложно восстановить вычисление, мате-

матической моделью которого является stackexp: создать новый стек; втолкнуть в него элементы x1,

x2, x3 (в указанном порядке); удалить верхний элемент (x3), назвав получившийся стек s3; создать

другой пустой стек и т. д. Этот процесс графически представлен на рис.6.5.

Рис. 6.5: Манипуляции со стеком

6.3 От абстрактных типов данных к классам

Классы

АТД будут служить непосредственной основой разбиения системы на модули. Точнее, ОО-система

будет строиться (на уровне анализа, проектирования и реализации) как совокупность взаимодей-

ствующих, частично или полностью реализованных АТД. Основное понятие здесь - класс:

Класс - это абстрактный тип данных, снабженный некоторой (возможно частичной) реа-

лизацией

Таким образом, чтобы получить класс, мы должны построить АТД и решить, как его реализовывать.

АТД - это математическое понятие, а реализация - это его версия, ориентированная на компьютер.

Приведенное определение, однако, утверждает, что реализация может быть частичной. Введенные

ниже термины позволяют отделить этот случай от полностью реализованного класса:

Полностью реализованный класс называется эффективным (effective). Класс, который

реализован лишь частично или совсем не реализован, называется отложенным (deferred).

Всякий класс является либо отложенным, либо эффективным.

Чтобы получить эффективный класс, требуется предусмотреть все детали реализации. Для отло-

женного класса можно выбрать определенный уровень реализации, но при этом оставить некоторые

аспекты реализации незавершенными. В самом крайнем случае при частичной реализации можно

вообще отказаться от принятия каких-либо решений о ее уточнении. В этом случае получившийся

класс будет полностью отложенным и будет эквивалентен АТД.

Как создавать эффективный класс

Рассмотрим вначале эффективные классы. Что нужно сделать для реализации АТД? Результирую-

щий эффективный класс будет формироваться из элементов трех видов:

E1 Спецификации АТД (множество функций с соответствующими аксиомами и предусловиями, опи-

сывающими их свойства).

E2 Выбора представления.

E3 Отображения из множества функций (E1) в представление (E2) в виде множества механизмов

(или компонентов (features)), каждый из которых реализует одну из функций в терминах пред-

ставления и при этом удовлетворяет аксиомам и предусловиям. Многие из этих компонентов

будут методами - обычными процедурами, но некоторые могут появляться в качестве полей

данных или "атрибутов"(это будет показано в следующих лекциях).

Роль отложенных классов

В определении эффективного класса должна присутствовать полная информация о реализации

(пункты E2 и E3). Если она хоть в чем-то неполна, то класс является отложенным.

Чем более "отложенным"является класс, тем он ближе к АТД, одетому в некоторую синтаксиче-

скую одежду, которая скорее поможет завоевать признание разработчиков ПО, чем математиков.

Отложенные классы особенно полезны при анализе и проектировании:

• При ОО-проектировании многие аспекты реализации будут опущены, проектирование должно

сосредотачиваться на архитектурных свойствах высокого уровня - на том, какую функциональ-

ность обеспечивает каждый модуль системы, а не на том, как он это делает.

• При постепенном продвижении к полной реализации будут добавляться все новые и новые ее

свойства до тех пор, пока не будет получен эффективный класс.

Но на этом роль отложенных классов не завершается, даже в полностью реализованной системе

можно часто обнаружить много таких классов. Кое-что следует из только что перечисленных при-

менений: когда из отложенных классов получаются эффективные, то появляется желание сохранить

их в качестве предков (в смысле наследования) эффективных классов как живую память о процессе

анализа и проектирования.

Очень часто при разработке ПО с помощью не ОО-подходов система в окончательном виде не со-

держит никаких записей о тех значительных усилиях, которые были затрачены на ее получение. Для

тех, кто вынужден будет обслуживать такую систему - расширять, переносить, отлаживать - понять

ее без этих записей будет так же трудно, как трудно геологу понять видимый ландшафт, не имея

доступа к осадочным слоям. Один из лучших способов обеспечить необходимую для сопровождения

системы информацию - это сохранить отложенные классы в ее окончательной форме.

У отложенных классов имеется также применение, полностью связанное с реализацией. Они

служат для классификации групп связанных типов объектов, предоставляют некоторые наиболее

важные многократно используемые модули высокого уровня, фиксируют общие свойства поведения

многих вариантов и играют ключевую роль (вместе с полиморфизмом и динамическим связыванием)

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

Абстрактные типы данных и скрытие информации

Особенно интересным следствием ОО-политики, в которой модули основаны на реализациях АТД

(классах), является то, что она дает ясный ответ на вопрос, который остался нерешенным при обсуж-

дении скрытия информации: как нам следует разделять общедоступные и скрытые свойства модуля -

видимую и невидимую части айсберга? Если модуль является классом, полученным из АТД, то ответ

Рис. 6.6: АТД вид модуля при скрытии информации

ясен. Из трех частей, вовлеченных в эту эволюцию, E1- спецификация АТД, является открытой, а E2

и E3 - выбор представления и реализация функций АТД в терминах этого представления - должны

быть закрытыми (секретными). Когда мы начнем строить классы, то столкнемся еще с четвертой

частью, также секретной, - вспомогательными свойствами, необходимыми только для внутренних

нужд этих программ.

Таким образом, использование абстрактных типов данных в качестве источника модулей дает нам

практичное, однозначное указание для применения скрытия информации в наших проектах.

Конструирование объектно-ориентированного ПО

Мы уже давали определение конструирования ОО-ПО: будучи весьма общим, оно представляет

метод следующим образом: "основывать архитектуру всякой программной системы на модулях, полу-

ченных из типов объектов, с которыми оперирует система". Придерживаясь рамок этого определения,

мы можем дополнить его теперь более техническим определением:

Конструирование ОО-ПО - это построение программной системы как структурирован-

ной совокупности реализаций (возможно частичных) абстрактных типов данных.

Это определение будет нашим рабочим определением. Все его компоненты являются важными:

• В основе лежит понятие абстрактного типа данных.

• Для конструирования программ нам нужны не сами по себе АТД (как математическое понятие),

а реализации АТД - программистское понятие.

• При этом эти реализации не обязаны быть полными, оговорка "возможно частичные"позволяет

использовать и отложенные классы, включая, как крайний случай, полностью отложенный

класс без какой-либо реализации.

• Система представляет собой совокупность классов без выделения какого-либо главного или

ответственного класса или головной программы.

• Эта совокупность является структурированной благодаря двум отношениям между классами:

"быть клиентом"и наследованию.

6.4 Ключевые концепции

• Теория абстрактных типов данных (АТД) примиряет необходимость в точности и полноте спе-

цификаций с желанием избежать лишних деталей в спецификации.

• Спецификация абстрактного типа данных является формальным математическим описанием, а

не текстом программы. Она аппликативна, т.е. не включает в явном виде изменений.

• АТД может быть родовым, и он задается функциями, аксиомами и предусловиями. Аксиомы

и предусловия выражают семантику данного типа и важны для полного и однозначного его

описания.

• Частичные функции образуют удобную математическую модель для описания не всюду опре-

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

при котором она будет выдавать результат для заданного конкретного аргумента.

• ОО-система - это совокупность классов. Каждый класс основан на некотором абстрактном типе

данных и задает частичную или полную реализацию этого АТД.

• Класс является эффективным, если он полностью реализован, в противном случае он называ-

ется отложенным.

• Классы должны разрабатываться в наиболее общем виде, допускающем повторное использова-

ние; процесс их объединения в систему часто идет снизу-вверх.

• Абстрактные типы данных являются скорее неявными, чем явными описаниями. Эта неявность,

которая также означает открытость, переносится на весь ОО-метод.

• Не существует формального определения интуитивно ясного понятия "полноты"спецификации

абстрактного типа данных. Строго определяемое понятие достаточной полноты как правило

обеспечивает удовлетворительный ответ. Хотя не существует метода, устанавливающего до-

статочную полноту произвольной спецификации, часто удается ее доказать для конкретных

спецификаций; приведенное в этой лекции доказательство достаточной полноты для специфи-

кации стеков может служить образцом и для других случаев.

Контрольные вопросы

1. Какими критериями следует руководствоваться при описании типов объектов?

описания должны быть точными и недвусмысленными

описания должны быть полностью специфицированы

описания могут быть неточными

описания не должны быть излишне специфицированы

2. Спецификация АТД включает разделы