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

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

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

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

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

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

Критерии

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

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

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

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

Различные реализации

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

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

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

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

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

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

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

• МАССИВ_ВВЕРХ: представляет стек посредством массива representation и целого числа count, с диапазоном значений от 0 (для пустого стека) до capacity - размера массива representation, элементы стека хранятся в массиве и индексируются от 1 до count.
• МАССИВ_ВНИЗ: похож на МАССИВ_ВВЕРХ, но элементы помещаются в конец стека, а не в начало. Здесь число, называемое free, является индексом верхней свободной позиции в стеке или 0, если все позиции в массиве заняты и изменяется в диапазоне от capacity для пустого стека до 0 для заполненного. Элементы стека хранятся в массиве и индексируются от capacity до free+1.
• СПИСОЧНОЕ: при списочном представлении каждый элемент стека хранится в ячейке с двумя полями: item, содержащем сам элемент, и previous, содержащем указатель на ячейку с предыдущим элементом. Для этого представления нужен также указатель last на ячейку, содержащую вершину стека.

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

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

if count " capacity then ...
if free " 0 then ...,

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

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

• создания новой ячейки n (здесь оно выполняется с помощью процедуры Паскаля new, которая выделяет память для нового объекта);
• присваивания x полю item новой ячейки;
• присоединения новой ячейки к вершине стека путем присвоения ее полю previous текущего значения указателя last;
• изменения 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 ему была прислана другая карточка, в которой был лишь второй инициал "Е". Он пишет:

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

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

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

К абстрактному взгляду на объекты

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

Использование операций

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

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

• Команда вталкивания некоторого элемента на вершину стека. Назовем эту операцию put.
• Команда удаления верхнего элемента стека. Назовем ее remove.
• Запрос элемента, находящегося на вершине стека (если стек не пуст). Назовем его item.
• Запрос на проверку пустоты стека. (Он позволит клиентам заранее проверить возможность операций remove и item.)

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

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

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

count: INTEGER
representation: array [1 .. capacity] of STACK_ELEMENT_TYPE

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

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

Политика невмешательства в обществе модулей

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

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

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

Согласованность имен

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

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

Стандартное имя операции над стеком	Имя, используемое здесь
Push (втолкнуть)	Put (поместить)
Pop (вытолкнуть)	Remove (удалить)
Top (вершина)	Item (элемент)
New (новый)	Make (создать)

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

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

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

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

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

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

Можно ли обойтись без абстракций?

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

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

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

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

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

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

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

Формализация спецификаций

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

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

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

• ТИПЫ
• ФУНКЦИИ
• АКСИОМЫ
• ПРЕДУСЛОВИЯ

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

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

Специфицирование типов

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

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

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

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

Типы

• STACK[G]

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

Универсализация (Genericity)

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

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

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

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

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

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

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

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

Перечисление функций

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

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

Функции

• put: STACK [G] × G → STACK [G]
• remove: STACK [G] STACK [G]
• item: STACK [G] G
• empty: STACK [G] → BOOLEAN
• 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:

• Функция put возвращает новое состояние стека с одним новым элементом, помещенным на его вершину. Рисунок на предыдущей странице иллюстрирует операцию put(s, x), выполняемую над стеком s и элементом x.
• Функция remove возвращает новое состояние стека с вытолкнутым верхним элементом, если таковой был. Как и put, эта функция при проектировании и реализации должна превращаться в команду (операцию, изменяющую объект, обычно реализуемую как процедура). Мы увидим далее, как учесть возможность пустого стека, с вершины которого нечего удалять.
• Функция item возвращает верхний элемент стека, если таковой имеется.
• Функция empty выявляет пустоту стека, ее результатом является логическое значение (истина или ложь). Предполагается, что АТД BOOLEAN, задающий логические значения, определен отдельно.
• Функция 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:

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

• Функция, в сигнатуре которой T появляется лишь справа от стрелки, например new, является функцией-конструктором. Она моделирует операцию, создающую экземпляры T из экземпляров других типов или вообще не использующую аргументов, например как в случае константного конструктора new.
• Такие функции как item и empty, у которых T появляется только слева от стрелки, являются функциями-запросами. Они моделируют операции, которые устанавливают свойства T, выраженные в терминах экземпляров других типов (в наших примерах - это BOOLEAN и параметр типа G).
• Такие функции как 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],

• (A1) item (put (s, x)) = x
• (A2) remove (put (s, x)) = s
• (A3) empty (new)
• (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

Две или три вещи, которые мы знаем о стеках

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

• Метод АТД определяет неявно некоторое множество объектов, задавая применимые к ним функции. Из этого определения никогда не следует, что в нем перечислены все операции; часто, на пути к представлению, будут добавлены и другие.
• Сами функции также определяются неявно. Вместо явных определений используются аксиомы, задающие свойства этих функций. Здесь тоже ничего не утверждается о полноте: когда вы, в конце концов, дойдете до реализации этих функций, они приобретут дополнительные свойства.

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

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

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

Частичные функции

Спецификация всякого реалистичного примера, даже такого простого как стеки, необходимо сталкивается с проблемами не всюду определенных операций: некоторые операции применимы не ко всем возможным элементам исходных множеств. Например, это имеет место для функций 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)

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

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

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

С точки зрения математики предусловие функции f - это характеристическая функция области f. Характеристической функцией подмножества Aмножества X называется полная функция ch: X → BOOLEAN такая, что ch(x) истинна, если x принадлежит A, и ложна в противном случае.

Полная спецификация

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

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

ТИПЫ (TYPES)

• STACK [G]

ФУНКЦИИ (FUNCTIONS)

• put: STACK [G] × G → STACK [G]
• remove: STACK [G] STACK [G]
• item: STACK [G] G
• empty: STACK [G] → BOOLEAN
• new: STACK [G]

АКСИОМЫ (AXIOMS)

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

• (A1) item (put (s, x)) = x
• (A2) remove (put (s, x)) = s
• (A3) empty (new)
• (A4) not empty (put (s, x))

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

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

Ничего кроме правды

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

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

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

item (remove (put (remove (put (put (
remove (put (put (put (new, x1), x2), x3)),
item (remove (put (put (new, x4), x5)))), x6)), x7)))

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

s1 = new
s2 = put (put (put (s1, x1), x2), x3)
s3 = remove (s2)
s4 = new
s5 = put (put (s4, x4), x5)
s6 = remove (s5)
y1 = item (s6)
s7 = put (s3, y1)
s8 = put (s7, x6)
s9 = remove (s8)
s10 = put (s9, x7)
s11 = remove (s10)
stackexp = item (s11)

Какой бы вариант определения вы ни выбрали, по нему несложно восстановить вычисление, математической моделью которого является stackexp: создать новый стек; втолкнуть в него элементы x1, x2, x3 (в указанном порядке); удалить верхний элемент (x3), назвав получившийся стек s3; создать другой пустой стек и т. д. Этот процесс графически представлен на рис. 6.5.

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

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

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

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

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

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