Если вам не терпится окунуться в глубины объектной технологии и подробно изучить множественное наследование, динамическое связывание и другие игрушки, то, на первый взгляд, эта лекция может показаться лишней задержкой на этом пути, поскольку она в основном посвящена изучению некоторых математических понятий (хотя вся используемая в ней математика элементарна).

Но так же, как самый талантливый музыкант извлечет пользу из изучения основ музыкальной теории, знания об абстрактных типах данных помогут вам понять и получить удовольствие от практики ОО-анализа, проектирования и программирования, хотя привлекательность этих понятий, возможно, уже проявилась и без помощи теории. Поскольку абстрактные типы данных являются теоретическим базисом для всего метода, следствия идей, вводимых в этой лекции, будут ощущаться во всей оставшейся части курса.

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

Это открыло мне глаза, я начал понимать, что значит использовать инструмент, называемый алгеброй. Черт возьми, никто никогда не говорил мне ничего подобного раньше. Мсье Дюпюи [учитель математики] произносил напыщенные фразы об этом предмете, но ни разу не сказал этих простых слов: это разделение труда, которое, как и всякое другое разделение труда производит чудеса и позволяет уму сконцентрировать все свои силы только на одной стороне объектов, только на одном из их качеств.

Насколько другим это предстало бы перед нами, если бы мсье Дюпюи сказал нам: "Этот сыр мягкий или твердый, он белый, он синий, он старый, он молодой, он твой, он мой, он легкий или он тяжелый. Из всех его многочисленных качеств давайте рассматривать только вес. Каким ни был этот вес, давайте назовем его A. А теперь, не думая больше о весе, давайте применять к А все, что мы знаем о количестве."

Такая простая вещь, но до сих пор никто не говорил нам о ней в этой отдаленной провинции...

Стендаль, "Жизнь Анри Брюлара"

Что касается абстракции, то она состоит в отделении ощутимых свойств тел либо от других их свойств, либо от самих тел, которые ими обладают. Когда это отделение делается неудачно или неверно применяется, возникают ошибки, что возможно как в философских вопросах, так и в физических и математических вопросах. Прямой путь к ошибке в философии - недостаточно упростить изучаемые объекты, и верный путь к получению ошибочных результатов в физике и математике - это считать объекты менее сложными, чем они есть на самом деле.

Дени Дидро, "Письмо слепого на благо тех, кто может видеть"

Чтобы получить надлежащие описания объектов, наш метод должен удовлетворять трем условиям:

[x]. Описания должны быть точными и недвусмысленными.

[x]. Они должны быть полными - или, по крайней мере, иметь в каждом конкретном случае нужную нам полноту (некоторые детали можно намеренно опускать).

[x]. Они не должны быть излишне специфицированы.

Последний пункт делает ответ нетривиальным. В конце концов, легко сделать описание точным, недвусмысленным и полным, если мы готовы "выдать все секреты", указав все детали объектного представления. Но такое описание, как правило, будет включать чересчур много информации для авторов программ, которым требуется доступ к таким объектам.

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

Чтобы лучше понять всю важность описаний абстрактных типов данных, исследуем глубже потенциальные последствия использования физической реализации в качестве основы описания объектов.

Удобным и хорошо изученным примером является описание объектов типа стек. Объект стек служит для того, чтобы накапливать и доставать другие объекты в режиме "последним пришел - первым ушел" ("LIFO"), элемент, вставленный в стек последним, будет извлечен из него первым. Стек повсеместно используется в информатике и во многих программных системах, в частности, компиляторы и интерпретаторы усыпаны разными видами стеков.

Существует несколько физических представлений стеков:

Рис. 6.1.  Три возможных представления стеков

Этот рисунок иллюстрирует три наиболее популярных представления стеков. Для удобства ссылок дадим каждому из них свое имя:

[x]. МАССИВ_ВВЕРХ: представляет стек посредством массива representation и целого числа count, с диапазоном значений от 0 (для пустого стека) до capacity - размера массива representation, элементы стека хранятся в массиве и индексируются от 1 до count.

[x]. МАССИВ_ВНИЗ: похож на МАССИВ_ВВЕРХ, но элементы помещаются в конец стека, а не в начало. Здесь число, называемое free, является индексом верхней свободной позиции в стеке или 0, если все позиции в массиве заняты и изменяется в диапазоне от capacity для пустого стека до 0 для заполненного. Элементы стека хранятся в массиве и индексируются от capacity до free+1.

[x]. СПИСОЧНОЕ: при списочном представлении каждый элемент стека хранится в ячейке с двумя полями: item, содержащем сам элемент, и previous, содержащем указатель на ячейку с предыдущим элементом. Для этого представления нужен также указатель last на ячейку, содержащую вершину стека.

Рядом с каждым представлением на рисунке приведен фрагмент программы (в духе Паскаля), с соответствующей реализацией основной стековой операции: втолкнуть элемент x на вершину стека (push).

Для представлений с помощью массивов МАССИВ_ВВЕРХ и МАССИВ_ВНИЗ команды увеличивают или уменьшают указатель на вершину (count или free) и присваивают x соответствующему элементу массива. Так как эти представления поддерживают стеки с не более чем capacity элементами, то корректные реализации должны содержать защищающие от переполнения тесты соответствующего вида:

if count " capacity then ...

if free " 0 then ...,

(на рисунке они для простоты опущены).

Для представления СПИСОЧНОЕ вталкивание элемента требует четырех действий:

[x]. создания новой ячейки n (здесь оно выполняется с помощью процедуры Паскаля new, которая выделяет память для нового объекта);

[x]. присваивания x полю item новой ячейки;

[x]. присоединения новой ячейки к вершине стека путем присвоения ее полю previous текущего значения указателя last;

[x]. изменения last так, чтобы он ссылался на только что созданную ячейку.

Хотя эти представления встречаются чаще всего, существует и много других представлений стеков. Например, если вам нужны два стека с однотипными элементами и память для их представления ограничена, то можно использовать один массив с двумя метками вершин count как в представлении МАССИВ_ВВЕРХ и free как в МАССИВ_ВНИЗ. При этом один стек будет расти вверх, а другой - вниз. Условием полного заполнения этого представления является равенство count= free.

Преимущество такого представления состоит в уменьшении риска переполнить память: при двух массивах размера n, представляющих стеки способом МАССИВ_ВВЕРХ или МАССИВ_ВНИЗ, память исчерпается, как только любой из стеков достигнет n элементов. А в случае одного массива размера 2n, содержащего два стека лицом к лицу, работа продолжается до тех пор, пока их общая длина не превысит 2n, что менее вероятно, если стеки растут независимо друг от друга. (Для любых переменных p и q, max (p +q) "= max (p) + max (q)).

Рис. 6.2.  Представление двух стеков лицом к лицу

Каждое из этих и другие возможные представления полезны в разных ситуациях. Выбор одного из них в качестве эталона для определения стека был бы типичным примером излишней спецификации. Почему мы должны, например, предпочесть МАССИВ_ВВЕРХ представлению СПИСОЧНОЕ? Большинство видимых свойств представления МАССИВ_ВВЕРХ - массив, число count, верхняя граница - несущественны для понимания представляемой ими структуры.

Почему так плохо использовать конкретное представление в качестве спецификации?

Можно напомнить результаты изучения Линцем (Lientz) и Свенсоном (Swanson) стоимости сопровождения. Было установлено, что более 17% стоимости ПО приходится на изменения в форматах данных. Ясно, что метод, который ставит анализ и проектирование в зависимость от физического представления структур данных, не обеспечит разработку достаточно гибкого ПО.

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

Как бы стеки не заставили нас забыть, что кроме излюбленных специалистами по информатике примеров имеются структуры данных, тесно связанные с объектами реальной жизни. Вот забавный пример, взятый из почты форума Риски (Risks) (группа новостей Usenet comp.risks), который иллюстрирует опасности взгляда на данные, чересчур сильно зависящего от их конкретных свойств. Некто Даррелл Д. Е. Лонг, которого родители наградили двумя инициалами второго имени, получил кредитную карточку, в которой был указан лишь первый из них "Д". После обращения к менеджеру фирмы TRW ему была прислана другая карточка, в которой был лишь второй инициал "Е". Он пишет:

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

Автор приведенного выше письма, в основном, беспокоился из-за ненужной почты, что неприятно, но не смертельно, архивы форума Риски (Risks) полны случаями вызванной компьютерами неразберихи с гораздо более серьезными последствиями. Уже отмечавшаяся выше "проблема миллениума" является другим примером опасности, возникающей при организации доступа к данным на основе их физического представления, ее последствия обошлись в сотни миллионов долларов.

Как нам сохранить полноту, точность и однозначность, не заплатив за это излишней спецификацией?

Представления стека при всех их различиях объединяет то, что они описывают структуру "хранения" (т.е. структуру, используемую для хранения других объектов), к которой применяются определенные операции, обладающие определенными свойствами. Сосредоточившись не на выборе конкретного представления структуры, а на этих операциях и свойствах, можно получить достаточно абстрактное, но, тем не менее, полезное описание понятия стек.

Обычно для стеков рассматриваются следующие операции:

[x]. Команда вталкивания некоторого элемента на вершину стека. Назовем эту операцию put.

[x]. Команда удаления верхнего элемента стека. Назовем ее remove.

[x]. Запрос элемента, находящегося на вершине стека (если стек не пуст). Назовем его item.

[x]. Запрос на проверку пустоты стека. (Он позволит клиентам заранее проверить возможность операций remove и item.)

Кроме того, нам понадобится операция-конструктор для создания пустого стека. Назовем ее make.

При традиционном взгляде на структуры данных мы рассматривали бы понятие стека, заданное с помощью некоторого объявления данных, соответствующего одному из вышеуказанных представлений, например для представления МАССИВ_ВВЕРХ. В стиле Паскаля это выглядит как

count: INTEGER

representation: array [1 .. capacity] of STACK_ELEMENT_TYPE

где константа capacity - это максимальное число элементов в стеке. Тогда put, remove, item, empty и make будут подпрограммами, которые работают на структурах, определенных этим объявлением объектов.

Чтобы сделать главный шаг в направлении абстракции данных, нужно стать на противоположную точку зрения: забыть на некоторое время о конкретном представлении и взять в качестве определения структуры данных операции сами по себе. Иначе говоря, стек - это любая структура, к которой клиенты могут применять перечисленные выше операции.

Только что намеченный метод описания структур данных выглядит довольно эгоистичным подходом в мире структур данных. Нас не столько интересует то, что они собой представляют внутренне, как то, что они могут друг другу предложить. В этом мы похожи на экономиста - пылкого приверженца теорий приоритета производства и невидимой руки, воспитанного в духе школы "пусть-все-решит-свободный-рынок". Мир объектов (а, следовательно, и архитектуры ПО) будет миром взаимодействующих объектов, общающихся на основе точно определенных протоколов.

Аналогия с экономикой будет сопровождать наше изложение и дальше, агенты - программные модули - называются поставщиками и клиентами, протоколы будут называться контрактами, и большая часть ОО-разработки, на самом деле, может рассматриваться как "Проектирование по Контракту" - это заголовок одной из следующих лекций.

Не следует чересчур увлекаться этой аналогией (как и всякой другой): эта работа не учебник по экономике и она не содержит даже намеков на точку зрения автора в этой области. Сейчас нам достаточно отметить поразительные аналогии подхода абстрактных типов данных с некоторыми теориями о взаимодействии агентов-людей.

Давайте убедимся в том что, приведенная выше спецификация и ее детали являются достаточно удобными. Для того, кто раньше сталкивался со стеками, избранные при обсуждении стека имена операций могут показаться странными или даже шокирующими. Каждому уважающему себя специалисту по информатике операции со стеком известны под другими именами:

Таблица 6.1.Имена операций над стеком

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

Стеки это просто один из видов контейнеров, точнее они относятся к категории контейнеров, которые можно назвать распределителями. Распределитель предоставляет своим клиентам механизм для хранения (put), извлечения (item) и удаления (remove) объектов, но не дает им возможности управлять тем, какой объект будет извлекаться или удаляться. Например, метод доступа LIFO, используемый в стеках, позволяет извлекать или удалять только тот элемент, который был сохранен последним. Другой вид распределителей - очередь, которая использует метод доступа "первым в, первым из" (FIFO): элементы добавляются в один конец очереди, а извлекаются и удаляются - с другого конца. Пример контейнера, не являющегося распределителем, - это массив, в нем вы сами выбираете целочисленные номера позиций, в которые вставляются или из которых извлекаются объекты.

Поскольку схожесть разных видов контейнеров (распределителей, массивов и т.п.) более важна, чем различия между тем, как они хранят, извлекают или удаляют объекты, эта книга твердо придерживается стандартизованной терминологии, которая сглаживает различия между вариантами структур данных и, наоборот, подчеркивает их общность. Поэтому базисная операция извлечения элемента будет всегда называться item, базисная операция удаления элемента будет всегда называться remove, и т.д.

Вопросы именования могут вначале показаться поверхностными - "косметическими", как иногда говорят программисты. Но не забывайте, что одна из наших конечных целей - создать основу для мощных, профессиональных библиотек программных компонент, допускающих повторное использование. Такие библиотеки будут содержать десятки тысяч доступных операций. Без их систематической и ясной номенклатуры и разработчики, и пользователи этих библиотек быстро потонут в потоке специальных и несравнимых имен, что создаст сильное (и не имеющее оправдания) препятствие к масштабному повторному использованию.

Таким образом, вопросы именования - это не косметика. Хорошее, допускающее повторное использование ПО - это ПО, которое предоставляет пользователям соответствующий набор функций и предоставляет их под правильными именами.

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

В разработке программного обеспечения, как и в других научных и технических дисциплинах, плодотворная идея после того, как ее раскрыли, может показаться очевидной, даже если потребовалось много времени, чтобы она возникла. Сначала зачастую появляются плохие и запутанные (что часто одно и то же) идеи, и требуется время, чтобы более простые и элегантные заняли их место.

Это замечание справедливо и для абстрактных типов данных. Хотя хорошие разработчики ПО всегда с пользой применяли абстракцию (вследствие хорошего образования или просто интуитивно), многие из существующих ныне систем были разработаны без учета этой цели.

В предыдущих разделах нам удалось сделать первые шаги по дороге к АТД. Их достаточно для понимания того, что программа, написанная в соответствии с самыми элементарными представлениями об абстракции данных, должна была бы рассматривать MAIL_MESSAGE (ПОЧТОВОЕ_СООБЩЕНИЕ) как точно определенное абстрактное понятие. Одной из операций сообщения мог быть запрос, называемый, например, sender (отправитель), возвращающий информацию об отправителе сообщения. Любой элемент почтовой программы, которому была бы нужна эта информация, получал бы ее только через этот запрос sender. Если бы почтовая программа была разработана в соответствии с этим, кажущимся очевидным, принципом, то для моего небольшого упражнения достаточно было бы изменить только код запроса sender. Более того, весьма вероятно, что в этом случае программа предоставляла бы также и операцию set_sender (установить_отправителя), которая позволила бы выполнить требуемую работу еще проще.

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

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

Приведенные содержательные описания явно недостаточны - put вталкивает элемент на "вершину" стека, remove выталкивает элемент, находящийся на вершине. Нам нужно точно знать, как клиенты могут использовать эти операции и что они для этого должны делать.

Спецификация АТД предоставит эту информацию. Она состоит из четырех разделов, разъясняемых в следующих разделах:

[x]. ТИПЫ

[x]. ФУНКЦИИ

[x]. АКСИОМЫ

[x]. ПРЕДУСЛОВИЯ

Для спецификации АТД в этих разделах будут использоваться простая математическая нотация.

В разделе ТИПЫ указываются специфицируемые типы. В общем случае, может оказаться удобным определять одновременно несколько АТД, хотя в нашем примере имеется лишь один тип STACK(СТЕК). Между прочим, что такое тип? Ответ на этот вопрос объединит все положения, развиваемые далее в этой лекции: тип - это совокупность объектов, характеризуемая функциями, аксиомами и предусловиями. Не будет большой ошибкой рассматривать пока тип как множество объектов в математическом смысле слова "множество" - тип STACK как множество всех возможных стеков, тип INTEGER как множество всех целых чисел и т.д.

Однако при этом не должно быть никакой путаницы: АТД, такой как STACK, - это не объект (один конкретный стек), а совокупность объектов (множество всех стеков). Напомним, в чем состоит наша главная цель: найти подходящую основу для модулей наших программных систем. Очевидно, не имеет смысла делать основой для модуля один конкретный объект - один стек, один самолет, один счет в банке. ОО-проектирование даст нам возможность строить модули, отражающие свойства всех стеков, всех самолетов, всех банковских счетов, или, по крайней мере, значительной их части.

Объект, принадлежащий множеству объектов, описываемых спецификацией АТД, называется экземпляром этого АТД. Например, конкретный стек, обладающий свойствами абстрактного типа данных STACK, будет экземпляром АТД STACK. Понятие экземпляра проходит через все ОО-проектирование и программирование, и будет играть важную роль в объяснении поведения программ во время исполнения.

В разделе ТИПЫ просто перечисляются типы, вводимые в данной спецификации. Здесь:

Типы

[x]. STACK[G]

Таким образом, наша спецификация относится к одному абстрактному типу данных - STACK, задающему стеки объектов произвольного типа G.

В описании STACK[G] именем G обозначен произвольный, не определяемый тип. G называется формальным родовым параметром для типов элементов АТД STACK, а сам STACK называется родовым или универсальным АТД. Механизм, допускающий такие параметризованные спецификации, известен как универсализация, мы уже сталкивались с аналогичным понятием в обзоре конструкций пакетов.

Можно писать спецификации АТД без параметризации, но ценой будут неоправданные повторения. Кроме того, возможность повторного использования желательна не только для программ, но и для спецификаций! Благодаря механизму универсализации, можно выполнять параметризацию типов в явном виде, выбрав для параметра некоторое произвольное имя (здесь - G), представляющее переменную для типа элементов стека.

В результате такой АТД как STACK - это не просто тип, а скорее образец типа. Для получения непосредственно используемого типа стека нужно определить тип элементов стека, например ACCOUNT, и передать его в качестве фактического родового параметра, соответствующего формальному параметру G. Поэтому, хотя сам по себе STACK это образец типа, обозначение STACK[ACCOUNT] задает полностью определенный тип. Про такой тип, полученный с помощью передачи фактических параметров типов в родовой тип, говорят, что он порожден из общего по образцу.

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

Как показывает этот пример, предыдущее определение "экземпляра" нуждается в некоторой модификации. Строго говоря, конкретный стек является экземпляром не типа STACK (который, как мы заметили, является скорее образцом типа, а не типом), а некоторого типа, порожденного типом STACK, например, образцом типа STACK[ACCOUNT]. Тем не менее, нам удобно и далее говорить об экземплярах типа S и других образцов типов, понимая при этом, что речь идет об экземплярах порожденных ими типов.

Аналогично, не очень правильно говорить о типе STACK как об АТД: правильный термин в этом случае - "образец АТД". Но для простоты в данном обсуждении мы будем и далее, если это не приведет к путанице, опускать слово "образец".

Это отличие перенесется и на ОО-проектирование и программирование, но там нам не потребуется два разных термина:

[x]. Основным понятием будет класс, который может иметь родовые параметры.

[x]. Описание реальных данных требует типов. Класс без параметров является также и типом, но класс с параметрами - только образец типа. Чтобы получить конкретный тип из такого класса, нужно передать ему фактические параметры типов, точно так, как мы это делали при получении АТД STACK[ACCOUNT], исходя из образца АТД STACK[G].

Вслед за разделом ТИПЫ идет раздел ФУНКЦИИ, в котором перечисляются операции, применяемые к экземплярам данного АТД. Как уже говорилось, эти операции будут главными компонентами определения типа, с их помощью описывается, что могут предложить его экземпляры, а не то, чем они являются.

Ниже приведен раздел ФУНКЦИИ для абстрактного типа данных STACK. Если вы разработчик ПО, то этот стиль описания вам знаком: строки этого раздела напоминают декларации типизированных языков программирования таких, как Pascal или Ada. Строка для операции new похожа на объявление переменной, остальные - на заголовки процедур.

Функции

[x]. put: STACK [G] × G STACK [G]

[x]. remove: STACK [G] STACK [G]

[x]. item: STACK [G] G

[x]. empty: STACK [G] BOOLEAN

[x]. new: STACK [G]

В каждой строке вводится определенная математическая функция, моделирующая соответствующую операцию над стеком. Например, функция put представляет операцию, которая вталкивает элемент на вершину стека.

Почему функции? Большая часть программистов не посчитает такую операцию как put функцией. Когда во время работы программной системы операция put применяется к стеку, она, как правило, изменяет этот стек, добавляя к нему элемент. Вследствие этого в приведенной выше классификации операций put была "командой" - операцией, которая может модифицировать объекты. (Две другие категории операций - это конструкторы и запросы).

Однако спецификация АТД - это математическая модель и в ее основании должны быть корректные математические методы. В математике понятие команды или, более общно, изменение чего-либо как таковое отсутствует: вычисление квадратного корня из числа 2 не изменяет само это число. Математические выражения просто определяют одни математические объекты в терминах некоторых других математических объектов. В отличие от вычисления программы на компьютере, они никогда не изменяют никакие математические объекты. Но поскольку мы нуждаемся в некотором математическом объекте для моделирования операций компьютера, то понятие функции представляется наиболее близким приближением. Функция - это механизм для получения некоторого результата, принадлежащего некоторому результирующему множеству по любому допустимому входу, принадлежащему некоторому исходному множеству. Например, если R обозначает множество вещественных чисел, то определение функции

square_plus_one: R R

square_plus_one(x)= x2 + 1 (для каждого x из R)

вводит функцию square_plus_one, для которой R является и исходным и результирующим множеством и которая выдает для любого входа в качестве результата квадрат этого входа, увеличенный на 1.

Спецификации абстрактных типов данных используют именно это понятие. Например, операция put определяется как

put: STACK [G] × G STACK [G]

и означает, что put будет брать два аргумента: STACK экземпляров типа G и экземпляр типа G и возвращать в качестве результата новый STACK [G]. (Более формально, множеством определения функции put является множество STACK [G] _ G, являющееся декартовым произведением множеств STACK [G] и G, т.е. множеством пар <s, x>, в которых первый элемент s принадлежит STACK [G] , а второй элемент x принадлежит G.) Вот рисунок, иллюстрирующий это:

Рис. 6.3.  Применение функции put

АТД имеют дело только с математическими функциями, у которых нет никаких побочных эффектов и которые, на самом деле, ничего не изменяют. Когда мы покинем утонченную сферу спецификации и попадем в неразбериху проектирования и реализации программ, нам придется восстановить понятие изменения, так как из-за накладных расходов мало кто одобрит программное окружение, в котором каждое выполнение операции "втолкнуть" в стек начинается с копирования этого стека. Мы рассмотрим позже переход от лишенного изменений мира АТД к полному изменений миру разработки ПО. Но поскольку сейчас мы хотим понять, как лучше всего определять типы, то математический взгляд на вещи нас вполне устраивает.

Из нашего обсуждения следуют роли операций, моделируемых каждой из функций спецификации STACK:

[x]. Функция put возвращает новое состояние стека с одним новым элементом, помещенным на его вершину. Рисунок на предыдущей странице иллюстрирует операцию put(s, x), выполняемую над стеком s и элементом x.

[x]. Функция remove возвращает новое состояние стека с вытолкнутым верхним элементом, если таковой был. Как и put, эта функция при проектировании и реализации должна превращаться в команду (операцию, изменяющую объект, обычно реализуемую как процедура). Мы увидим далее, как учесть возможность пустого стека, с вершины которого нечего удалять.

[x]. Функция item возвращает верхний элемент стека, если таковой имеется.

[x]. Функция empty выявляет пустоту стека, ее результатом является логическое значение (истина или ложь). Предполагается, что АТД BOOLEAN, задающий логические значения, определен отдельно.

[x]. Функция new создает пустой стек.

В разделе ФУНКЦИИ эти функции определяются не полностью, вводятся только их сигнатуры - списки типов их аргументов и результата. Сигнатура функции put

STACK [G] × G STACK [G]

показывает, что put берет в качестве аргумента пару вида <s,x>, в которой s - экземпляр типа STACK [G], а x - экземпляр типа G, и возвращает в качестве результата экземпляр типа STACK [G]. Вообще говоря, множество значений функции (его тип указывается в сигнатуре правее стрелки, здесь это STACK [G]) может само быть декартовым произведением. Это можно использовать при описании операций, возвращающих два или более результатов.

В сигнатуре функций remove и item вместо обычной стрелки используется перечеркнутая стрелка . Это означает, что эти функции применимы не ко всем элементам множества входов. Описание функции new выглядит просто как

new: STACK

без всякой стрелки в сигнатуре. Фактически, это сокращение для записи

new: STACK,

определяющей функцию без аргументов. Здесь аргументы не нужны, поскольку new должна всегда возвращать один и тот же результат - пустой стек. Поэтому для простоты мы убрали здесь стрелку. Результат применения этой функции (т. е. пустой стек) будет записываться new, как сокращение для new(), обозначающего результат применения new к пустому списку аргументов.

В начале этой лекции операции над типами были разделены на конструкторы, запросы и команды. В спецификации АТД для нового типа T, например для STACK [G] в нашем примере можно определить эту классификацию более строго. Эта классификация просто проверяет, где по отношению к стрелке расположен в сигнатуре каждой функции тип T:

[x]. Функция, в сигнатуре которой T появляется лишь справа от стрелки, например new, является функцией-конструктором. Она моделирует операцию, создающую экземпляры T из экземпляров других типов или вообще не использующую аргументов, например как в случае константного конструктора new.

[x]. Такие функции как item и empty, у которых T появляется только слева от стрелки, являются функциями-запросами. Они моделируют операции, которые устанавливают свойства T, выраженные в терминах экземпляров других типов (в наших примерах - это BOOLEAN и параметр типа G).

[x]. Такие функции как put и remove, у которых T появляется с обеих сторон стрелки, являются функциями-командами. Они моделируют операции, которые по существующим экземплярам T и, возможно, экземплярам других типов выдают новые экземпляры типа T.

Мы уже видели, как типы данных (например, STACK) описываются посредством задания списка функций, применимых к их экземплярам. Все, что известно об этих функциях, - это их сигнатуры.

Чтобы указать, что речь идет о стеке, а не какой-либо другой структуре данных, имеющейся пока спецификации АТД совершенно недостаточно. Всякий распределитель, например очередь: "первым вошел - первым вышел", также будет удовлетворять этой спецификации.

Это, конечно, не должно удивлять, поскольку в разделе ФУНКЦИИ сами функции только объявляются (так же, как в программе объявляются переменные), но полностью не определяются. В ранее рассмотренном примере математического определения:

square_plus_one: R R

square_plus_one (x)= x2 + 1 (для каждого x из R)

первая строка играет роль сигнатуры, но есть еще и вторая строка, в которой определяется значение функции. Как можно достичь того же для функций АТД?

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

Только чтобы убедиться в том, что мы понимаем, как может выглядеть явное определение, давайте напишем одно такое определение для приведенного ранее представления стека МАССИВ_ВВЕРХ. С точки зрения математики выбор этого представления означает, что экземпляр типа STACK - это пара <count, representation> , где representation - это массив, а count - это число помещенных в стек элементов. Тогда явное определение функции put (для любого экземпляра x типа G) выглядит так:

put (<count, representation>, x)= <count + 1, representation [count+1: x]>

где a [n: v] обозначает массив, полученный из a путем изменения значения элемента с индексом n на v (все остальные элементы не изменяются).

Это определение функции put является просто математической версией реализации операции put, набросок которой в стиле Паскаля приведен вслед за представлением МАССИВ_ВВЕРХ на рисунке с возможными представлениями стеков в начале этой лекции.

Но это не то определение, которое бы нас устроило. "Освободите нас от рабства представлений!" - этот лозунг Фронта Освобождения Объектов и его военного крыла (бригады АТД) является также и нашим. (Отметим, что его политическая ветвь специализируется на тяжбах: класс - действие).

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

Они формулируются в разделе АКСИОМЫ (AXIOMS). Для типа STACK он выглядит следующим образом.

Аксиомы

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

[x]. (A1) item (put (s, x)) = x

[x]. (A2) remove (put (s, x)) = s

[x]. (A3) empty (new)

[x]. (A4) not empty (put (s, x))

Первые две аксиомы выражают основные свойства стеков (последним пришел - первым ушел) LIFO. Чтобы понять их, предположим, что у нас есть стек s и экземпляр x, и определим s' как результат put(s, x) , т. е. как результат вталкивания x в s. Приспособим один из предыдущих рисунков:

Рис. 6.4.  Применение функции put

Здесь аксиома A1, говорит о том, что вершиной s' является x - последний элемент, который мы втолкнули, а аксиома A2 объясняет, что при удалении верхнего элемента s' мы снова получаем тот же стек s, который был до вталкивания x. Эти две аксиомы дают лаконичное описание главного свойства стеков в чисто математических терминах без всякой помощи императивных рассуждений или ссылок на свойства представлений.

Аксиомы A3 и A4 говорят о том, когда стек пуст, а когда - нет: стек, полученный в результате работы конструктора new пустой, а всякий стек, полученный после вталкивания элемента в уже существующий стек (пустой или непустой) не является пустым.

Эти аксиомы, как и остальные, являются предикатами (в смысле логики), выражающими истинность некоторых свойств для всех возможных значений s и x. Некоторые предпочитают рассматривать A3 и A4 в другой эквивалентной форме как определение функции empty индукцией по размеру стеков:

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

A3' · empty (new) = true

A4' · empty (put (s, x)) = false

Спецификации АТД являются неявными. Имеются два вида "неявности":

[x]. Метод АТД определяет неявно некоторое множество объектов, задавая применимые к ним функции. Из этого определения никогда не следует, что в нем перечислены все операции; часто, на пути к представлению, будут добавлены и другие.

[x]. Сами функции также определяются неявно. Вместо явных определений используются аксиомы, задающие свойства этих функций. Здесь тоже ничего не утверждается о полноте: когда вы, в конце концов, дойдете до реализации этих функций, они приобретут дополнительные свойства.

Эта неявность является ключевым аспектом абстрактных типов данных и, как следствие, - их будущих аналогов в построении ОО-ПО - классов. Когда мы определяем абстрактный тип данных или класс, мы всегда сообщаем кое-что об этом типе или классе, просто перечисляя те их свойства, которые знаем, и берем их в качестве определения. При этом никогда не предполагается, что других применимых свойств нет.

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

Этот "неявный" подход имеет далеко идущие последствия. В пункте "дополнительные темы" в конце этой лекции помещены еще некоторые комментарии о неявности.

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

Решение этой проблемы, использованное в приведенной выше спецификации, состоит в том, чтобы определить эти функции как частичные. Функция из исходного множества X в результирующее множество Y является частичной, если она определена не для всех элементов X. Функция, не являющаяся частичной, называется полной. Простым примером частичной функции в обычной математике является функция обращения действительных чисел inv, значение которой на действительном числе x равно

inv(x)= 1/x.

Поскольку inv не определена при x = 0, мы можем определить ее как частичную функцию на множестве R всех действительных чисел:

Inv: R R

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

Областью (определения) частичной функции типа X Y является подмножество тех элементов X, для которых эта функция имеет некоторое значение. В нашем примере областью функции inv является R - {0}, т.е. множество действительных чисел, отличных от 0.

В спецификации АТД STACK эти идеи использованы для стеков при объявлении remove и item как частичных функций в разделе ФУНКЦИИ - это указано с помощью перечеркнутых стрелок в их сигнатуре. При этом возникает новая проблема, обсуждаемая в следующем пункте: как задавать области таких функций?

В некоторых случаях функцию put тоже желательно описывать как частичную, например, это требуется в таких реализациях как МАССИВ_ВВЕРХ и МАССИВ_ВНИЗ, которые поддерживают выполнение лишь конечного числа подряд идущих операций put для каждого заданного стека. Это на самом деле полезное упражнение - приспособить спецификацию STACK к тому, чтобы она описывала ограниченные стеки конечного объема, поскольку в приведенном выше виде она не содержит никаких ограничений на размеры стеков.

Это будет новым применением частичных функций, отражающим ограничения реализации. В отличие от этого, объявление функций remove и item как частичных отражает абстрактное свойство этих операций, относящееся ко всем реализациям.

Частичные функции являются неустранимым фактом процесса проектирования ПО, отражающим очевидное наблюдение: не каждая операция применима ко всем объектам. Но они также являются и потенциальным источником ошибок: если функция f из X в Y является частичной, то нельзя быть уверенным в том, что выражение f(e) имеет смысл, даже если e принадлежит X - требуется гарантировать, что это значение принадлежит области f.

Для этого всякая спецификация АТД, содержащая частичные функции, должна задавать их области. В этом и состоит роль раздела ПРЕДУСЛОВИЯ (PRECONDITIONS). Для АТД STACK этот раздел выглядит так:

Предусловия (preconditions)

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

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

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

Булевское выражение, которое определяет область функции, называется предусловием соответствующей частичной функции. В нашем случае предусловия обеих функций remove и item утверждают, что стек должен быть непустым. Перед "требует" помещается имя функции с именами ее аргументов (в примере для аргумента-стека использовано s), так что предусловие может ссылаться на эти аргументы.

BOOLEAN такая, что ch(x) истинна, если x принадлежит A, и ложна в противном случае.

Раздел ПРЕДУСЛОВИЯ (PRECONDITIONS) завершает простую спецификацию абстрактного типа данных STACK. Для удобства ссылок полезно собрать вместе разные компоненты спецификации, приведенные выше. Вот полная спецификация.

Спецификация стеков как АТД

ТИПЫ (TYPES)

[x]. STACK [G]

ФУНКЦИИ (FUNCTIONS)

[x]. put: STACK [G] × G STACK [G]

[x]. remove: STACK [G] STACK [G]

[x]. item: STACK [G] G

[x]. empty: STACK [G] BOOLEAN

[x]. new: STACK [G]

АКСИОМЫ (AXIOMS)

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

[x]. (A1) item (put (s, x)) = x

[x]. (A2) remove (put (s, x)) = s

[x]. (A3) empty (new)

[x]. (A4) not empty (put (s, x))

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

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

[x]. 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.

Можно легко найти значение такого АТД выражения, нарисовав последовательно несколько таких рисунков. (Здесь найдено x4). Но теория позволяет нам получить этот результат формально, не обращаясь к рисункам, а только последовательно применяя аксиомы для упрощения выражения, до тех пор, пока дальнейшее упрощение станет невозможным. Например:

[x]. Применить A2 для упрощения s3 - т. е. заменить remove(put (put (put (s1, x1), x2), x3)) на выражение put (put (s1, x1), x2)). (Согласно A2 всякую пару remove-put можно выбросить).

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

[x]. По той же аксиоме s6 равно put(s4, x4) . Затем можно применить аксиому A1 и вывести, что y1, т. е. item(put(s4, x4)) на самом деле равно x4, установив тем самым (как указано стрелкой на рисунке), что s7 получается в результате вталкивания x4 на верщину стека s3.

И так далее. Последовательность таких упрощений, выполненная механически так же легко и как последовательность упрощений в элементарной арифметике, приведет к значению выражения stackexp, которое действительно равно x4 (попробуйте проверить это сами, аккуратно проведя весь процесс упрощения).

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

Итак, у нас имеется отправная точка - элегантная математическая теория для моделирования структур данных и, как мы только что видели, в целом - программ. Но наша цель - это архитектура ПО, а не математическая или даже теоретическая информатика! Не сбились ли мы с нашего пути? Отнюдь. При поиске подходящей модульной структуры, основанной на типах объектов, АТД предоставляют механизм описания высокого уровня, не связанный с особенностями реализации. Это приведет нас к фундаментальным структурам ОО-технологии.

В поиске, начатом в лекции 3, АТД будут служить непосредственной основой модулей. Точнее, ОО-система будет строиться (на уровне анализа, проектирования и реализации) как совокупность взаимодействующих, частично или полностью реализованных АТД. Основное понятие здесь - класс:

Определение: класс

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

Таким образом, чтобы получить класс, мы должны построить АТД и решить, как его реализовывать. АТД - это математическое понятие, а реализация - это его версия, ориентированная на компьютер. Приведенное определение, однако, утверждает, что реализация может быть частичной. Введенные ниже термины позволяют отделить этот случай от полностью реализованного класса:

Определение: отложенный и эффективный классы

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

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

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

[x]. (E1) Спецификации АТД (множество функций с соответствующими аксиомами и предусловиями, описывающими их свойства).

[x]. (E2) Выбора представления.

[x]. (E3) Отображения из множества функций (E1) в представление (E2) в виде множества механизмов (или компонентов (features)), каждый из которых реализует одну из функций в терминах представления и при этом удовлетворяет аксиомам и предусловиям. Многие из этих компонентов будут методами - обычными процедурами, но некоторые могут появляться в качестве полей данных или "атрибутов" (это будет показано в следующих лекциях).

Например, для АТД STACK можно выбрать в качестве представления (шаг E2) решение, названное выше МАССИВ_ВВЕРХ, при котором каждый стек реализуется парой

<representation, count>,

где representation - это массив, а count - это целое число. При реализации функций (E3) у нас будут процедуры для функций put, remove, item, empty и new, выполняющие соответствующие действия. Например, функцию put можно реализовать программой вида

put (x: G)

is -- Втолкнуть x в стек.

-- (без проверки стека на возможное переполнение.)

do

count := count + 1

representation [count]:= x

end

Объединение элементов, полученных в пунктах (E1), (E2) и (E3), приведет к классу - модульной структуре объектной технологии.

В определении эффективного класса должна присутствовать полная информация о реализации (пункты E2 и E3). Если она хоть в чем-то неполна, то класс является отложенным.

Чем более "отложенным" является класс, тем он ближе к АТД, одетому в некоторую синтаксическую одежду, которая скорее поможет завоевать признание разработчиков ПО, чем математиков. Отложенные классы особенно полезны при анализе и проектировании:

[x]. При ОО-проектировании многие аспекты реализации будут опущены, проектирование должно сосредотачиваться на архитектурных свойствах высокого уровня - на том, какую функциональность обеспечивает каждый модуль системы, а не на том, как он это делает.

[x]. При постепенном продвижении к полной реализации будут добавляться все новые и новые ее свойства до тех пор, пока не будет получен эффективный класс.

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

Очень часто при разработке ПО с помощью не ОО-подходов система в окончательном виде не содержит никаких записей о тех значительных усилиях, которые были затрачены на ее получение. Для тех, кто вынужден будет обслуживать такую систему - расширять, переносить, отлаживать - понять ее без этих записей будет так же трудно, как трудно геологу понять видимый ландшафт, не имея доступа к осадочным слоям. Один из лучших способов обеспечить необходимую для сопровождения системы информацию - это сохранить отложенные классы в ее окончательной форме.

У отложенных классов имеется также применение, полностью связанное с реализацией. Они служат для классификации групп связанных типов объектов, предоставляют некоторые наиболее важные многократно используемые модули высокого уровня, фиксируют общие свойства поведения многих вариантов и играют ключевую роль (вместе с полиморфизмом и динамическим связыванием) в обеспечении децентрализации и расширяемости программной архитектуры.

Несколько следующих лекций, в которых вводятся основные ОО-методы, будут сосредоточены на эффективных классах. Но при этом следует помнить о понятии отложенного класса, чья важность будет расти по мере овладения всей мощью ОО-метода.

Особенно интересным следствием ОО-политики, в которой модули основаны на реализациях АТД (классах), является то, что она дает ясный ответ на вопрос, который остался нерешенным при обсуждении скрытия информации: как нам следует разделять общедоступные и скрытые свойства модуля - видимую и невидимую части айсберга?

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

Если модуль является классом, полученным из АТД, то ответ ясен. Из трех частей, вовлеченных в эту эволюцию, E1- спецификация АТД, является открытой, а E2 и E3 - выбор представления и реализация функций АТД в терминах этого представления - должны быть закрытыми (секретными). Когда мы начнем строить классы, то столкнемся еще с четвертой частью, также секретной, - вспомогательными свойствами, необходимыми только для внутренних нужд этих программ.

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

Переход от АТД к классам включает существенное изменение стилистики: введение изменений и императивных аргументов.

Как вы помните, спецификация абстрактных типов данных не описывает явно изменений, т. е., используя термин из теоретической информатики, является аппликативной. Все свойства АТД моделируются как математические функции, это относится к конструкторам, запросам и командам. Например, операция вталкивания для стеков моделируется функцией-командой:

put: STACK [G] × G STACK [G],

задающей операцию, которая возвращает новый стек, а не изменяет существующий.

Классы отказываются от чисто аппликативной точки зрения на функции и переопределяют команды как операции, которые могут изменять объекты. Например, операция put будет определена как процедура, которая получает некоторый элемент типа G (формальный параметр) и модифицирует стек, вталкивая новый элемент на его вершину, не создавая нового стека.

Такое изменение стиля отражает императивные настроения, преобладающие при разработке ПО. (В качестве синонима слова "императивный" иногда используется термин "операционный"). При этом потребуется изменять аксиомы АТД. Аксиомы стеков A1 и A4, которые имели вид

[x]. (A1) item (put (s, x)) = x

[x]. (A4) not empty (put (s, x))

превратятся в императивной форме в предложение, называемое постусловием программы (routine postcondition), вводимое ключевым словом ensure (обеспечивает):

put (x: G) is

-- Втолкнуть x на вершину стека

require

... Предусловие (если таковое имеется) ...

do

... Соответствующая реализация (если известна) ...

ensure

item = x

not empty

end

Здесь постусловие объясняет, что результатом вызова программы put значение item будет равно x (втолкнутому элементу), а значение empty будет ложно.

Другие аксиомы спецификации АТД приводят к утверждению, известному как инвариант класса. Постусловия, инварианты класса и другие перевоплощения предусловий и аксиом АТД мы рассмотрим во время обсуждения утверждений и проектирования по контракту (п. 11.10 "Связь с АТД").

Если вы внимательно следили, начиная с лекции о модульности, за главной линией рассуждений, которая привела нас к абстрактным типам данных, а затем и к классам, то сейчас, быть может, вы будете удивлены. Поставив целью получить по возможности наилучшую модульную структуру, мы пришли к тому, что объекты, точнее - типы объектов, будут лучшей основой для модулей, чем их традиционные соперники - функции. Это привело к следующему вопросу: как описать эти типы объектов. Но, когда мы на него ответили: описывать нужно в виде абстрактных типов данных (и их заменителей на практике - классов), то оказалось, что нужно основывать описание данных на ... применяемых к ним функциях! Не получился ли у нас порочный круг?

Нет. Типы объектов, представлямые АТД и классами, остаются неизменной основой модуляризации.

Неудивительно, что и объектный, и функциональный аспект должен проявиться в окончательной архитектуре системы: никакое описание вопросов ПО не может считаться полным, если в нем опущена одна из этих компонент. Фундаментальное различие ОО-методов и старых подходов состоит в распределении ролей: типы объектов - безусловные победители при выборе критериев для построения модулей. Функциям достается только роль их слуг.

При ОО-декомпозиции никакая функция не существует сама по себе - каждая функция прикреплена к некоторому типу объектов. Это относится и к уровню проектирования, и к уровню разработки: никакое свойство не существует само по себе, каждое из них прикреплено к некоторому классу.

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

Конструирование объектно-ориентированного ПО (определение 2)

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

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

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

[x]. Для конструирования программ нам нужны не сами по себе АТД (как математическое понятие), а реализации АТД - программистское понятие.

[x]. При этом эти реализации не обязаны быть полными, оговорка "возможно частичные" позволяет использовать и отложенные классы, включая, как крайний случай, полностью отложенный класс без какой-либо реализации.

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

[x]. Эта совокупность является структурированной благодаря двум отношениям между классами: "быть клиентом" и наследованию.

Подчеркнем теперь важность понятия АТД для областей, лежащих вне непосредственной области его предполагаемого применения.

Подход, основанный на АТД, говорит нам, что серьезное интеллектуальное исследование должно отвергать всякую попытку понять суть вещей изнутри как бесполезную, и вместо этого должно сосредотачиваться на понимании используемых свойств этих вещей. Не объясняйте мне, что вы собой представляете, скажите мне, что у вас есть - что я могу от вас получить. Если потребуется дать имя этой эпистемологической дисциплине, мы скажем, что это принцип разумного эгоизма.

Если я испытываю жажду, то апельсин - это то, из чего я могу выдавить сок, если художник, то цвет - это то, что может воодушевить мою палитру, если фермер, то это - продукт, который я могу продать на рынке, если архитектор, то это - чертежи, показывающие мне, как спроектировать новый оперный театр, но если я - ни один из них, и никак не использую апельсин, то я не должен говорить о нем, поскольку понятие "апельсин" для меня даже не существует.

Принцип эгоизма, утверждающий, что вы - это то, что у вас есть, является крайним выражением идеи, играющей центральную роль в развитии науки: идеи абстракции или важности разделения понятий. Две цитаты, приведенные в начале этой лекции, каждая из которых по-своему замечательна, выражают важность этой идеи. Их авторы Дидро и Стендаль были писателями, а не учеными, хотя очевидно, что у обоих имелось хорошее понимание сути научного метода. (Дидро был пылким вдохновителем Большой энциклопедии, а Стендаль готовился к поступлению в Политехническую школу, хотя затем решил, что может найти более подходящие занятия). Просто поразительно, насколько обе цитаты применимы к использованию абстракции при конструировании программ.

Но в принципе эгоизма есть и кое-что помимо абстракции - это, кажущаяся с первого взгляда шокирующей, идея о том, что ни о каком свойстве не стоит говорить, если от него нет никакой прямой пользы говорящему.

Это приводит к мысли рассмотреть общее интеллектуальное значение нашей области.

На протяжении ряда лет во многих статьях и выступлениях предлагалось проверить, как разработчики ПО могут извлечь выгоду от изучения философии, общей теории систем, "когнитивных наук", психологии. Но для практикующих разработчиков программ результаты оказываются разочаровывающими. Если исключить из рассмотрения универсально применимые законы рационального (разумного) исследования, известные просвещенным умам уже в течение многих веков (по крайней мере, с Декарта), которые, разумеется, применимы к информатике, как и ко всему прочему, то иногда кажется, что специалисты в вышеуказанных дисциплинах могут получить больше, обучаясь у специалистов по программному обеспечению, чем наоборот.

Конструкторы программ брались - с различной степенью успеха - за решение ряда самых сложных из когда-либо рассматриваемых интеллектуальных задач. Немногие из инженерных проектов могут сравниться по сложности с программными проектами, содержащими много миллионов строк, которые регулярно производятся в наши дни. Приложив немало амбициозных усилий, программистское сообщество достигло точного понимания таких предметов и понятий, как размер, сложность, структура, абстракция, таксономия, параллельность, рекурсивный вывод, различие между описанием и предписанием, язык, изменение и инварианты. Все это произошло так недавно и настолько интуитивно, что сама эта профессиональная среда еще не осознала эпистемологических последствий собственной деятельности.

В конце концов, появится кто-нибудь, кто объяснит, какие уроки весь интеллектуальный мир может извлечь из опыта конструирования ПО. Нет сомнений в том, что абстрактные типы данных будут играть в них выдающуюся роль.

Представленное выше описание абстрактных типов данных вполне достаточно для использования АТД в рамках данной книги. (Чтобы дополнить его, выполните упражнения, которые помогут уточнить ваше понимание этого понятия).

Если же, как я надеюсь, АТД уже завоевали вас своей элегантностью, простотой и мощью, то не исключено, что вам захочется узнать побольше об их свойствах, даже о таких, которые не будут использоваться в обсуждении ОО-методов. Далее на нескольких страницах рассмотрены следующие дополнительные темы, которые можно опустить при первом чтении:

[x]. неявность и ее связь с процессом конструирования ПО;

[x]. различие между спецификацией и проектированием;

[x]. различие между классами и записями;

[x]. возможные альтернативы использованию частичных функций;

[x]. решение о полноте или неполноте спецификации.

Библиографические ссылки к этой лекции указывают на более специальную литературу по АТД.

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

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

x: POINT REAL

y: POINT REAL

и объявлением типа в таком традиционном языке программирования, как Pascal:

type

POINT =

record

x, y: real

end

На первый взгляд эти два объявления представляются эквивалентными: оба утверждают, что с типом POINT связаны два значения x и y типа REAL. Но между ними имеется существенная, хотя и тонкая разница:

[x]. Запись в языке Pascal является законченной и явной: она показывает, что объект POINT включает два данных поля и ничего кроме них.

[x]. Объявление функций АТД не несут такого смысла. Они показывают, что объект типа POINT можно запрашивать о значениях его x и y, но не исключают других запросов, например, о массе и скорости точки в кинематическом приложении.

С упрощенной математической точки зрения можно считать, что приведенное выше объявление в Паскале является определением математического множества POINT как декартова произведения:

POINT REAL × REAL,

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

Если имеются спецификации некоторого понятия, то может появиться желание переместить ее из неявного мира в явный, идентифицируя понятие с декартовым произведением применимых к нему простых запросов, например захочется идентифицировать точки с парами <x, y>. Такой процесс идентификации можно рассматривать как определение перехода от анализа и спецификации к проектированию и реализации.

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

В литературе по разработке программ обычно объясняется, что это различие между "определением задачи" и "построением ее решения". Будучи в принципе правильным, такое объяснение не всегда применимо на практике и иногда бывает трудно понять, где заканчивается спецификация и начинается проектирование. Даже в среде исследователей люди запросто критикуют друг друга в связи с этой темой: "вы рекламируете язык x как язык спецификаций, но на самом деле он предназначен для проектирования". Наивысшим оскорблением считается обвинение некоторой системы обозначений в обслуживании реализации (подробнее об этом в одной из следующих лекций).

Приведенное выше определение дает более точный критерий: пересечь Рубикон между спецификацией и проектированием - это перейти от неявного к явному, другими словами:

Определение: переход от анализа (спецификации) к проектированию

Перейти от спецификации к проектированию - это идентифицировать каждую абстракцию с декартовым произведением ее простых запросов.

Последующий переход - от проектирования к реализации - это просто движение от одного явного вида к другому: форма при проектировании более абстрактна и ближе к математическим понятиям, а при реализации более конкретна и ближе к компьютеру, но обе они являются явными. Этот переход менее драматичен, чем предыдущий - действительно, при дальнейшем чтении станет понятно, что объектная технология почти стирает различие между проектированием и реализацией. При хорошей системе ОО-нотации нашими компьютерами непосредственно выполняется (с помощью компиляторов) то, что в не ОО-мире часто рассматривалось бы как проекты.

Другим замечательным свойством объектной технологии является то, что при ней можно сохранять неявные описания гораздо дольше, чем при других подходах. В последующих лекциях будет введена система обозначений, позволяющая определять класс в виде:

class POINT feature

x, y: REAL

end

Это выглядит подозрительно похожим на приведенное выше определение записи в Паскале. Но, несмотря на внешнее сходство, определение класса другое - оно неявное! Эта неявность проявляется при наследовании: автор класса или (что еще более интересно) кто-либо другой может в любой момент определить новый класс, например:

class MOVING_POINT inherit

POINT

feature

mass: REAL

velocity: VECTOR [REAL]

end

который расширяет исходный класс совершенно незапланированным способом. Тогда переменная (или сущность, если использовать вводимую далее терминологию) типа POINT, объявленная как

p1: POINT

может быть связана с объектом не только типа POINT, но и с каждым потомком этого типа, например с объектом типа MOVING_POINT. Это может получиться, в частности, с помощью "полиморфных присваиваний" вида:

p1 := mp1

где mp1 имеет тип MOVING_POINT.

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

Способность определять элементы программ (классы), которые немедленно используются (посредством наследования), оставаясь неявными, является одним из главных нововведений объектной технологии, непосредственно отвечающему принципу Открыт-Закрыт. В последующих лекциях будут раскрыты все вытекающие из нее следствия.

Один из технических приемов, используемый в этой лекции, мог вызвать удивление, - применение частичных функций. Он связан с неустранимой проблемой применения в некоторой спецификации не всюду определенных операций. Но являются ли частичные функции лучшим решением этой проблемы?

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

Каждый тип T дополняется значением "ошибка". Обозначим его через w_T . Тогда для всякой функции f сигнатура

f: ... Типы входов ... T

определяет, что всякое применение f к объекту, для которого соответствующее вычисление не может быть выполнено, выдаст значение w_T.

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

Предположим, например, что рассматриваются стеки целых чисел - экземпляры типа STACK [INTEGER], где INTEGER - это АТД, экземпляры которого - целые числа. Хотя для нашего примера не требуется полностью выписывать спецификацию INTEGER, этот АТД должен моделировать основные операции (сложение, вычитание, "меньше чем" и т. п.), определенные на математическом множестве целых чисел. Аксиомы этого АТД должны выражать обычные свойства целых чисел. Вот одно из таких типичных свойств: для всякого целого n:

[Z1]

n + 1 n

Пусть теперь n будет результатом запроса верхнего элемента пустого стека, т. е. значением выражения item (new), где new - это пустой стек целых чисел. При этом запросе n должно получить специальное значение w_INTEGER . Что же тогда должно быть значением выражения n+1? Если у нас в распоряжении имеются в качестве значений только обычные целые числа и w_INTEGER , то в качестве ответа мы вынуждены выбрать w_INTEGER:

wINTEGER + 1 = wINTEGER.

Это единственный допустимый выбор. Если присвоить w_INTEGER+1 любое другое значение, "нормальное" число q, то это означает, что после попытки доступа к вершине пустого стека и получения в качестве результата ошибочного значения мы можем волшебным образом устранить всякую память об этой ошибке, просто прибавив к результату единицу!

Но, при выборе w_INTEGER в качестве значения n + 1 при n равном w_INTEGER, нарушается указанное выше свойство Z1. В общем случае, выражение w_INTEGER+p будет равно w_INTEGER для любого p. Это означает, что для измененного типа данных (INTEGER, дополненные ошибочным элементом) требуется новая система аксиом, объясняющая, что всякая операция над целыми числами возвращает значение w_INTEGER, если хоть один из ее аргументов равен w_INTEGER. Аналогичные изменения потребуются для каждого типа.

Получившееся усложнение не кажется обоснованным. Мы не можем изменять спецификацию целых чисел только для того, чтобы промоделировать каждую отдельную структуру данных (в нашем случае - стеки). При использовании частичных функций ситуация более простая. Конечно, для всякого выражения, содержащего частичные функции, приходится проверять, что их аргументы удовлетворяют соответствующим предусловиям. После завершения такой проверки, можно беспрепятственно применять аксиомы. При этом не требуется изменять существующие системы аксиом.

Другой вопрос, который может вас тревожить: есть ли какой-нибудь способ убедиться в том, что спецификация описывает все нужные свойства объектов, для которых она предназначена? Студенты, которым требуется написать их первые спецификации (например, проделать упражнения в конце этой лекции), часто приходят с аналогичным вопросом: "Как узнать, что я уже специфицировал достаточно свойств и могу остановиться?"

В более общей форме вопрос звучит так: существует ли метод, позволяющий определять полноту спецификации АТД?

Если непосредственно задать вопрос в такой форме, то ответ будет простой - нет. Понятно, что для формальной спецификации сказать, что она полна - это утверждать, что она покрывает все необходимые свойства, но это имеет смысл только по отношению к некоторому эталонному документу, в котором все эти свойства перечислены. Тогда мы сталкиваемся с двумя равно неутешительными ситуациями:

[x]. Если эталонный документ является неформальным (например, документом с требованиями на естественном языке или просто текстом упражнения), то отсутствие формальности предотвращает всякую попытку систематической проверки соответствия спецификации всем требованиям, описанным в этом документе.

[x]. Если же эталонный документ является формальным, и мы можем, используя его, проверить полноту нашей спецификации, то это просто отодвигает проблему дальше: как можно убедиться в полноте самого эталонного документа?

Таким образом, в этой тривиальной форме вопрос о полноте неинтересен. Но имеется и более полезное понятие полноты, соответствующее значению этого слова в математической логике. Для математика некоторая теория является полной, если ее аксиомы и правила вывода являются достаточно мощными, чтобы доказать истинность или ложность любой формулы, выразимой в языке данной теории. Хотя такое понятие полноты является более ограниченным, но оно интеллектуально вполне удовлетворительно, поскольку показывает, что если теория позволяет нам выражать некоторое свойство, то она также дает возможность определить имеет ли это свойство место.

Как можно перенести эту идею на спецификации АТД? Здесь "язык теории" - это множество правильно построенных выражений, т.е. тех выражений, которые можно построить, используя функции АТД, применяемые к аргументам соответствующих типов. Например, используя спецификацию АТД STACK и считая, что x является правильно построенным выражением типа G, можно указать следующие правильно построенные выражения:

new

put (new, x)

item (new) - если это кажется странным, то см. комментарии ниже.

empty (put (new, x))

stackexp - ранее определенное сложное выражение.

Однако выражения put (x) и put (x, new) не являются правильно построенными, так как они не соответствуют правилу: put всегда должно иметь два аргумента - первый типа STACK [G] и второй типа G.

Третий пример в рамке item (new) не задает никакого осмысленного вычисления, поскольку аргумент new не удовлетворяет предусловию для item. Хотя это выражение и правильно построено, оно не является корректным. Вот точное определение этого понятия.

Определение: корректное выражение АТД

Пусть f(x1 , ... , xn) - правильно построенное выражение, содержащее одну или более функций некоторого АТД. Это выражение является корректным тогда и только тогда, когда все его аргументы xi являются (по рекурсии) корректными и их значения удовлетворяют предусловию f, если оно имеется.

Не следует путать "корректное" и "правильно построенное". "Правильно построенное" - это структурное свойство, указывающее на то, что функции, входящие в выражение, имеют правильное число аргументов соответствующих типов, а корректность, которой могут обладать лишь правильно построенные выражения, означает, что данное выражение задает осмысленное вычисление. Как мы видели, выражение put (x) не является правильно построенным (и поэтому бессмысленно спрашивать, корректно ли оно), а выражение item (new) правильно построено, но некорректно.

Правильно построенное, но некорректное выражение похоже на программу, которая компилируется (поскольку построена в соответствии с требованиями синтаксиса языка программирования и удовлетворяет ограничениям, накладываемым в нем на типы), но аварийно завершается во время выполнения из-за выполнения некоторой недопустимой операции, например, деления на 0 или выталкивания элемента из пустого стека.

Особый интерес с точки зрения полноты представляют выражения-запросы, у которых самая внешняя функция является запросом. Вот примеры таких выражений:

empty (put (put (new, x1), x2))

item (put (put (new, x1), x2))

stackexp

Выражение-запрос задает значение, которое (если оно определено) принадлежит не определяемому АТД, а некоторому другому ранее определенному типу. Так, первое приведенное выше выражение имеет значение типа BOOLEAN, а второе и третье - тип G формального параметра для элементов стека, например если мы рассматриваем АТД STACK [INTEGER], то это будет тип INTEGER.

Выражения-запросы представляют внешние наблюдения, которые можно сделать о результатах некоторого вычисления, использующего экземпляры нового АТД. Если спецификация этого АТД хорошая, то она должна позволить нам установить определены ли эти результаты, и если да, то каковы они. Представляется, что спецификация стека обладает этим свойством, по крайней мере, для трех представленных в примере выражений, поскольку она позволяет установить, что все эти выражения определены, и с помощью аксиом можно получить их значения:

empty (put (put (new, x1), x2)) = False

item (put (put (new, x1), x2)) = x2

stackexp = x4

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

Приведем точное определение достаточной полноты. (Не расположенные к математике читатели могут пропустить остаток этого раздела).

Определение: достаточная полнота

Спецификация АТД T является достаточно полной тогда и только тогда, когда аксиомы ее теории позволяют для каждого выражения expr решить следующие задачи:

[x]. (S1) Определить, является ли expr корректным.

[x]. (S2) Если expr - выражение-запрос и в пункте S1 установлена его корректность, то представить значение expr в виде, не включающем никаких значений типа T.

В S2 выражение expr имеет вид f(x1 , ..., xn), где f - функция вида запрос такая, как empty и item для стеков. S1 говорит о том, что у expr есть значение, но этого недостаточно, нам хотелось бы знать, каково это значение, представленное в терминах значений других типов (в примере со стеком это значения типов BOOLEAN и G). Если аксиомы настолько сильны, что всегда позволяют ответить на этот вопрос, то спецификация является достаточно полной.

Достаточная полнота свидетельствует о том, что никакое важное свойство не осталось вне нашей спецификации. Поэтому ее можно считать ответом на поставленный выше вопрос: как понять, что можно прекратить поиски новых свойств при построении спецификации? На практике хорошо бы проводить такую проверку, по крайней мере неформально, для любой спецификации АТД, которую вы пишете - начните с решений упражнений, приведенных в этой лекции. Часто, можно получить формальное доказательство достаточной полноты; приведенное ниже доказательство для спецификации STACK является образцом, которому во многих случаях можно следовать.

Пункт S2 оптимистически говорит об одном значении expr, а что, если аксиомы приводят к двум или более значениям? Это сделало бы спецификацию бесполезной. Чтобы устранить такую ситуацию нам нужно еще одно свойство, называемое в математической логике непротиворечивостью:

Определение: непротиворечивость АТД

Спецификация АТД является непротиворечивой тогда и только тогда, когда для всякого правильно построенного выражения expr ее аксиомы позволяют вывести не более одного значения.

Эти два свойства являются взаимно дополнительными. Нам хотелось бы для каждого выражения-запроса выводить ровно одно значение: хотя бы одно (достаточная полнота), но не более одного (непротиворечивость).

(Этот раздел и остаток этой лекции содержат дополнительный материал и их результаты не нужны для остальной части книги).

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

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

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

[x]. (S1) Определить, является ли e корректным.

[x]. (S2) Если в пункте S1 установлена корректность e и его внешними функциями являются item или empty (т.е. функции-запросы), то представить значение e с помощью значений типов BOOLEAN и G без ссылок на значения типа STACK [G] или на функции из спецификации STACK.

Для начала мы рассмотрим только правильно построенные выражения, не включающие ни одну из двух функций-запросов item и empty, т. е. выражения, построенные только из функций new, put и remove. Таким образом, на этом этапе нас будет интересовать лишь задача S1 (установить определено ли выражение). Функции-запросы и S2 будут рассмотрены далее.

Правило для решения задачи S1 задается следующим свойством:

Правило корректного веса

Правильно построенное стековое выражение e, не содержащее ни item, ни empty, является корректным тогда и только тогда, когда его вес неотрицателен и каждое его подвыражение является (по индукции) корректным.

Здесь "вес" выражения представляет число элементов в соответствующем стеке, это значение также совпадает с разностью между числом вложенных вхождений функций put и remove. Приведем точное определение этого понятия:

Определение: вес

Вес правильно построенного стекового выражения, не содержащего ни item, ни empty, определяется по индукции следующим образом:

[x]. (W1) Вес выражения new равен 0.

[x]. (W2) Вес выражения put (s, x) равен ws + 1, где ws - это вес s.

[x]. (W3) Вес выражения remove (s) равен ws- 1, где ws - это вес s.

Содержательно, правило корректного веса утверждает, что стековое выражение корректно тогда и только тогда, когда в нем самом и в каждом из его подвыражений имеется не меньше операций put (вставляющих элементы в стек), чем операций remove (выталкивающих элементы с вершины стека). Если рассмотреть такое выражение как представление некоторого вычисления над стеком, то это означает, что мы никогда не будем пытаться вытолкнуть больше элементов, чем втолкнули. Напомним, что на этом этапе мы сосредоточились на функциях put и remove, оставив в стороне запросы item и empty.

Интуитивно сформулированное правило выглядит верным, но нам следует все же доказать, что оно имеет место. Удобно ввести еще одно вспомогательное правило и одновременно доказывать справедливость обоих этих правил:

Правило нулевого веса

Пусть e - это правильно построенное и корректное стековое выражение, не содержащее item или empty. Тогда empty (e) истинно тогда и только тогда, когда вес e равен 0.

Доказательство использует индукцию по уровню вложенности (максимальному числу вложенных пар скобок) выражения. Для удобства ссылок напомним аксиомы, относящиеся к функции empty:

Аксиомы стека

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

[x]. (A3) empty (new)

[x]. (A4) not empty (put (s, x))

При уровне вложенности 0 (без скобок) выражение e должно совпадать с new, поэтому его вес равен 0 и оно корректно, так как у new нет никаких предусловий. Аксиома A3 утверждает, что empty (new) истинно. Это обеспечивает базис индукции как для правила корректного веса, так и для правила нулевого веса.

Индукционный шаг: предположим, что оба правила выполняются для всех выражений с уровнем вложенности не более n. Нужно доказать, что тогда они выполняются и для любого выражения e с уровнем вложенности n+1. Поскольку наши выражения сейчас не содержат функций-запросов, то e должно иметь один из следующих двух видов:

E1 · e = put (s, x)

E2 · e = remove (s)

где x имеет тип G, а уровень вложенности у s равен n. Пусть ws - это вес s.

В случае E1, поскольку put - всюду определенная функция, e корректно тогда и только тогда, когда s корректно, т. е. (по предположению индукции) тогда и только тогда, когда s и все его подвыражения имеют неотрицательные веса. Но это эквивалентно тому, что e и все его подвыражения имеют неотрицательные веса, что и доказывает правило корректного веса в этом случае. Кроме того, e имеет положительный вес ws+1, и (по аксиоме A4) является непустым, что доказывает правило нулевого веса.

В случае E2 выражение e корректно тогда и только тогда, когда выполняются два следующих условия:

EB1 _ s и все его подвыражения являются корректными.

EB2 _ not empty (s) (это предусловие для функции remove).

По предположению индукции условие EB2 означает, что вес s ws положителен или, что эквивалентно, вес e, равный ws - 1, является неотрицательным. Следовательно, e удовлетворяет Правилу корректного веса. Чтобы доказать, что оно также удовлетворяет правилу нулевого веса, нужно показать, что e пусто тогда и только тогда, когда его вес равен 0. Так как вес s положителен, то s должно содержать по крайней мере одно вхождение put, которое также входит и в e. Рассмотрим самое внешнее вхождение put в e, это вхождение находится непосредственно внутри remove (так как remove находится на самом внешнем уровне у e). Это означает, что у e имеется подвыражение (быть может, совпадающее с самим e) вида

remove (put (stack_expression, g_expression)),

которое по аксиоме A2 можно сократить просто до stack_expression. После выполнения этой замены вес e уменьшится на 2, и получившееся выражение, имеющее то же значение, что и e, удовлетворяет по предположению индукции правилу нулевого веса. Это доказывает утверждение индукции в случае E2.

Это доказательство попутно показывает, что во всяком правильно построенном выражении, не содержащем функций-запросов item и empty, можно устранить все вхождения remove, т.е. получить, применяя всюду, где это возможно, аксиому A2, некоторую каноническую форму, в которую будут входить только put и new. Например, выражение:

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

имеет то же значение, что и каноническая форма:

put (put (new, x1), x5).

Давайте дадим этому механизму имя и приведем его определение:

Правило канонического сокращения

Всякое правильно построенное и корректное стековое выражение, не содержащее функций-запросов item и empty, имеет эквивалентную каноническую форму, которая не содержит функции remove (т.е. состоит только из функций put и new>). Эта каноническая форма получается путем применения аксиомы стека A2 всегда, пока это возможно.

Таким образом, мы завершили доказательство достаточной полноты, но только для выражений, не содержащих функции-запросы, и, следовательно, только свойства S1 (проверка корректности выражения). Для завершения доказательства нужно рассмотреть выражения, включающие функции-запросы, и обсудить задачу S2 (нахождение значений для выражений-запросов). Это означает, что нам нужно некоторое правило для определения корректности и значения всякого правильно построенного выражения вида f(s), где s - это правильно построенное выражение, а f - это либо item, либо empty.

Это правило и доказательство его корректности также используют индукцию по уровню вложенности. Пусть n - это уровень вложенности s. Если n=0, то s может быть только new, поскольку остальные функции требуют аргументов и, следовательно, содержат хоть одну пару скобок. Тогда для обеих функций-запросов ситуация ясна:

[x]. empty (new) корректно и имеет значение истина (true) (по аксиоме A3);

[x]. item (new) некорректно, так как предусловие item требует выполнения not empty (s) .

Индукционный шаг: предположим, что s имеет уровень вложенности n не менее 1. Если у какого-либо подвыражения u выражения s внешняя функция есть item или empty, то уровень вложенности u не превосходит n-1, что по предположению индукции позволяет определить корректность u и, если u корректно, получить его значение, применяя аксиомы. Выполнив замены всех таких подвыражений, получим для s эквивалентную форму, в которую входят только функции put, remove и new.

Далее используем идею введенной выше канонической формы, чтобы избавиться от всех вхождений remove, так что результирующая форма для s будет включать только функции put и new. Случай, когда s это просто new уже был рассмотрен, остался случай, когда s имеет вид put(s', x) . В этом случае для двух рассматриваемых выражений имеем:

[x]. empty (s) корректно и по аксиоме A3 значение этого выражения есть ложь (false);

[x]. item (s) корректно, так как предусловие not empty (s) для item выполнено; из аксиомы A1 следует, что значение этого выражения равно x.

Это завершает доказательство достаточной полноты, так как мы показали справедливость множества правил - правила корректного веса и правила канонического сокращения, позволяющего нам выяснять корректность заданного стекового выражения, а для корректного выражения-запроса - определять его значение в терминах значений типов BOOLEAN и G.

[x]. Теория абстрактных типов данных (АТД) примиряет необходимость в точности и полноте спецификаций с желанием избежать лишних деталей в спецификации.

[x]. Спецификация абстрактного типа данных является формальным математическим описанием, а не текстом программы. Она аппликативна, т.е. не включает в явном виде изменений.

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

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

[x]. ОО-система - это совокупность классов. Каждый класс основан на некотором абстрактном типе данных и задает частичную или полную реализацию этого АТД.

[x]. Класс является эффективным, если он полностью реализован, в противном случае он называется отложенным.

[x]. Классы должны разрабатываться в наиболее общем виде, допускающем повторное использование; процесс их объединения в систему часто идет снизу-вверх.

[x]. Абстрактные типы данных являются скорее неявными, чем явными описаниями. Эта неявность, которая также означает открытость, переносится на весь ОО-метод.

[x]. Не существует формального определения интуитивно ясного понятия "полноты" спецификации абстрактного типа данных. Строго определяемое понятие достаточной полноты как правило обеспечивает удовлетворительный ответ. Хотя не существует метода, устанавливающего достаточную полноту произвольной спецификации, часто удается ее доказать для конкретных спецификаций; приведенное в этой лекции доказательство достаточной полноты для спецификации стеков может служить образцом и для других случаев.

Несколько работ, опубликованных в начале 1970-х, сделали возможным появление абстрактных типов данных. Среди них наиболее известны статья Хоара о "доказательстве корректности представлений данных" [Hoare 1972a], в которой было введено понятие абстракции функций, и работа Парнаса по скрытию информации, отмеченная в библиографических заметках к лекции 3.

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

Описать в виде АТД очереди (первым пришел - первым ушел) в том же стиле, что и стеки. Обратите внимание на общие и отличительные черты этих АТД. (Указание: аксиомы для item и remove должны отличаться, при описании put (s,x) рассмотрите случаи, когда очередь s пуста и непустая).

(Это упражнение предполагает, что вы выполнили предыдущее).

Определите общий АТД РАСПРЕДЕЛИТЕЛЬ, покрывающий и стеки и очереди.

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

Определите абстрактный тип данных BOOLEAN так, чтобы его можно было использовать в определениях других АТД из этой лекции. Можно считать, что операции равенства и неравенства (= и ) автоматически определены для каждого АТД.

(Это упражнение предполагает, что вы выполнили одно или несколько предыдущих упражнений).

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

Докажите, что приведенная в этой лекции спецификация стеков является непротиворечивой.