Базисный треугольник

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

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

Рис. 5.1.  Три силы вычисления

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

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

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

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

Таким образом, остаются действия и объекты. Дуализм между действиями и объектами - тем, что система делает, и тем, с чем она это делает - это популярная тема в разработке ПО.

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

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

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

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

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

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

Библиографические замечания

Вопрос об ОО-декомпозиции рассматривается с использованием различных аргументов в [Cox 1990] (первоначально в 1986), [Goldberg 1981], [Goldberg 1985], [Page-Jones 1995] и [M 1978], [M 1979], [M 1983], [M 1987], [M 1988].

Метод проектирования сверху вниз отстаивается во многих книгах и статьях. Вирт [Wirth 1971] развил понятие пошагового уточнения.

Что касается других методов, то, по-видимому, наиболее близким является метод структурного проектирования Джексона JSD [Jackson 1983] и его расширение высокого уровня в [Jackson 1975]. См. также предложенный Варнье метод проектирования от данных [Orr 1977]. Для знакомства с методами, которые ОО-технология призвана заменить, смотрите книги по методу структурного проектирования Константина и Йордана [Yourdon 1979], по структурному анализу [DeMarco 1978], [Page-Jones 1980],[McMenamin 1984], [Yourdon 1989]; по методу Merise [Tardieu 1984], [Tabourier 1986].

Метод моделирования сущность-связь был введен Ченом [Chen 1976].

Декомпозиция, основанная на объектах

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

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

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

Функции и эволюция

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

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

Уточнение сверху вниз пакетной версии могло начаться следующим образом.

[B0] - Абстракция верхнего уровня "Решить полный экземпляр проблемы" [B1] - Первое уточнение "Прочесть входные данные" "Вычислить результаты" "Вывести результаты"

и т. д. Проектирование интерактивной версии сверху вниз может происходить в следующем стиле.

[I1] "Обработать одну транзакцию" [I2] if "Пользователь предоставил новую информацию" then "Ввести информацию" "Запомнить ее" elseif "Запрошена ранее данная информация" then "Извлечь запрошенную информацию" "Вывести ее" elseif "Запрошен результат" then if "Необходимая информация доступна" then "Получить запрошенный результат" "Вывести его" else "Запросить подтверждение запроса" if Да then "Получить требуемую информацию" "Вычислить запрошенный результат" "Вывести результат" end end end

(и т. д.)

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

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

Функциональная декомпозиция

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

Ингредиенты вычисления

При поиске правильной архитектуры ПО критическим является вопрос о модуляризации: какие критерии нужно использовать при выделении модулей наших программ?

Чтобы верно ответить на него, нужно сравнить соперничающих кандидатов.

Интерфейсы и проектирование ПО

Архитектура системы должна основываться на содержании, а не на форме. Но проектирование сверху вниз стремится использовать в качестве основы для структуры самый поверхностный аспект системы - ее внешний интерфейс.

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

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

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

Непрерывность

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

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

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

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

Не только одна главная функция

При эволюции системы то, что вначале воспринималось как ее главная функция, с течением времени может стать менее важным.

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

Рис. 5.3.  Структура простой системы расчета зарплаты

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

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

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

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

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

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

У нас уже накоплено достаточно оснований, чтобы попытаться определить ОО-конструирование ПО. Это будет лишь первый набросок, более конкретное определение последует в следующей лекции.

ОО-конструирование ПО (определение 1)

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

Содержательная характеристика этого подхода может служить лозунгом ОО-проектировщика:

Объектный девиз

Не спрашивай вначале, что система делает.

Спроси, кто в системе это делает!

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

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

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

Обнаружение вершины

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

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

"Обработать все запросы пользователя",

который далее можно уточнять примерно так:

from начальная загрузка системы until остановка или аварийный отказ loop "Прочесть запрос пользователя и поместить во входную очередь" "Взять запрос r из входной очереди" "Обработать r" "Поместить результат в выходную очередь" "Взять результат q из выходной очереди" "Выдать результат q получателю" end

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

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

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

У реальной системы нет "вершины"!

Описание отношений и структурирование ПО

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

B является клиентом A , если каждый объект типа B содержит информацию об одном или нескольких объектах типа A .

B является наследником A, если B представляет специализированную версию A .

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

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

Описания типов и объектов

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

При ответе на него следует руководствоваться двумя требованиями:

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

В следующей лекции развивается методика описания объектов, позволяющая достичь обе эти цели.

Преждевременное упорядочение

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

Напомним две альтернативных структуры для первого уточнения компилятора.

[C1] "Прочесть программу и породить последовательность лексем" "Разобрать последовательность лексем и построить абстрактное синтаксическое дерево" "Снабдить дерево семантической информацией" "Сгенерировать по полученному дереву код" [C'1] from "Инициализировать структуры данных" until "Определения всех функций обработаны" loop "Прочесть определение следующей функции" "Сгенерировать частичный код" end "Заполнить перекрестные ссылки"

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

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

Проектирование сверху вниз

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

Джонатан Свифт, "Путешествия Гулливера"

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

[C0] "Оттранслировать СИ-программу в машинный код"

или

[P0] "Обработать команду пользователя"

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

[C1] "Прочесть программу и породить последовательность лексем" "Разобрать последовательность лексем и построить абстрактное синтаксическое дерево" "Снабдить дерево семантической информацией" "Сгенерировать по полученному дереву код"

или, используя другую структуру (и сделав упрощающее предположение, что СИ-программа - это последовательность определений функций):

[C'1] from "Инициализировать структуры данных" until "Определения всех функций обработаны" loop "Прочесть определение следующей функции" "Сгенерировать частичный код" end "Заполнить перекрестные ссылки"

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

Процесс уточнения сверху вниз можно представить как построение дерева. Вершины представляют элементы декомпозиции, ветви показывают отношение "B есть уточнение A".

Рис. 5.2.  Разработка сверху вниз: структура дерева

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

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

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

Проектирование сверху вниз: общая оценка

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

Производство и описание

Одна из причин первоначальной привлекательности идей проектирования сверху вниз заключается в том, что этот стиль может быть удобен для объяснения каждого шага разработки. Но то, что хорошо для документации существующей разработки, не обязательно является наилучшим способом для ее проведения. Эта точка зрения была ярко представлена Майклом Джексоном в "Разработке систем" ([Jackson 1983], стр. 370-371):

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

Расширяемость

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

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

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

Совместимость

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

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

Упорядочивание и ОО-разработка

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

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

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

[H] найти_дом получить_ссуду подписать_контракт

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

[H1] найти_дом ensure дом_найден получить_ссуду ensure ссуда_получена подписать_контракт require дом_найден and ссуда_получена

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

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

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

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

Приведенное выше определение послужит отправной

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

Возможность повторного использования

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

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

Рис. 5.4.  Контекст модуля при разработке сверху вниз

Рисунок, показывающий часть дерева уточнений сверху вниз, иллюстрирует это свойство: C2 пишется, чтобы удовлетворить некоторой части требований C. Характеристики C2 полностью определяются его непосредственным контекстом, т.е. нуждами C. Например, C может быть модулем, отвечающим за анализ некоторых входных данных, а C2 может быть модулем, отвечающим за анализ одной строки (части всего длинного входа).

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

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

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

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

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

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

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

Выявление типов объектов

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

Многие объекты лежат на поверхности. Они непосредственно моделируют объекты физической реальности, к которой применяется ПО. ОО-технология является мощным средством моделирования, использующим типы программных объектов (классы) для моделирования типов физических объектов и отношения между типами объектов (клиент, наследование) для моделирования отношений между типами физических объектов таких, как агрегирование и специализация. Разработчику ПО не требуется изучать трактаты по ОО-анализу, чтобы в системе мониторинга для телекоммуникаций использовать класс CALL (ВЫЗОВ) и класс LINE (ЛИНИЯ), а в системе обработки документов - класс DOCUMENT (ДОКУМЕНТ), класс PARAGRAPH (АБЗАЦ) и класс FONT (ШРИФТ).Одним из источников типов объектов является повторное использование: классы, ранее определенные другими. Этот метод, не всегда бросающийся в глаза в литературе по ОО-анализу, на практике часто оказывается наиболее полезным. Мы должны противостоять соблазну что-либо изобретать, если задача уже была удовлетворительно решена другими. Наконец, опыт и копирование тоже играют важную роль. Ознакомившись с успешными ОО-разработками и образцами проектов, проектировщик может вдохновиться этими более ранними усилиями.

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

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

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

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

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

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

Альтернативы частичным функциям

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

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

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

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

T

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

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

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

[Z1] n + 1

n

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

wINTEGER + 1 = wINTEGER.

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

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

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

Библиографические замечания

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

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

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

Доказательство достаточной полноты

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

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

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

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

(S1) Определить, является ли e корректным.(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, определяется по индукции следующим образом:

(W1) Вес выражения new равен 0.(W2) Вес выражения put (s, x) равен ws + 1, где ws - это вес s.(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]

(A3) empty (new)(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, поскольку остальные функции требуют аргументов и, следовательно, содержат хоть одну пару скобок. Тогда для обеих функций-запросов ситуация ясна:

empty (new) корректно и имеет значение истина (true) (по аксиоме A3);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) . В этом случае для двух рассматриваемых выражений имеем:

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

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

Дополнительные темы

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

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

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

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

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

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

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

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

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

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

Еще раз о неявности

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

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

x: POINT

REAL y: POINT REAL

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

type POINT = record x, y: real end

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

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

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

POINT

REAL ? REAL,

где знак

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

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

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

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

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

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

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

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

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

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

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

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

Команда вталкивания некоторого элемента на вершину стека. Назовем эту операцию 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 будут подпрограммами, которые работают на структурах, определенных этим объявлением объектов.

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

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

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

Какова длина второго имени?

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

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

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

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

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

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

(E1) Спецификации АТД (множество функций с соответствующими аксиомами и предусловиями, описывающими их свойства).(E2) Выбора представления.(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), приведет к классу - модульной структуре объектной технологии.

Категории функций

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

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

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

Классы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Критерии

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

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

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

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

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

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

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

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

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

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

Назад к тому, с чего начали?

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

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

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

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

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

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

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

Вот пример. Рассмотрим для приведенной выше спецификации АТД 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). Но теория позволяет нам получить этот результат формально, не обращаясь к рисункам, а только последовательно применяя аксиомы для упрощения выражения, до тех пор, пока дальнейшее упрощение станет невозможным.
Например:

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

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

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

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

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

Опасность излишней спецификации

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

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

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

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

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

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

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

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

Функции

put: STACK [G] ? G

STACK [G]remove: STACK [G] STACK [G]item: STACK [G] Gempty: STACK [G] BOOLEANnew: 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 к пустому списку аргументов.

Переход к более императивной точке зрения

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

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

put: STACK [G] ? G

STACK [G],

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

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

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

(A1) item (put (s, 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 "Связь с АТД").

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

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

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

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

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

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

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

ТИПЫ (TYPES)

STACK [G]

ФУНКЦИИ (FUNCTIONS)

put: STACK [G] ? G

STACK [G]remove: STACK [G] STACK [G]item: STACK [G] Gempty: STACK [G] BOOLEANnew: 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 и считая, что 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 решить следующие задачи:

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



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

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

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

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

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

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

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

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

Рис. 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, верхняя граница - несущественны для понимания представляемой ими структуры.

Предусловия

Частичные функции являются неустранимым фактом процесса проектирования ПО, отражающим очевидное наблюдение: не каждая операция применима ко всем объектам. Но они также являются и потенциальным источником ошибок: если функция 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, и ложна в противном случае.

Раздел АКСИОМЫ

Мы уже видели, как типы данных (например, 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стандартное имя операции над стекомИмя, используемое здесь

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

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

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

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

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

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

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

Соотношение классов и записей

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

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, но и экземпляры всякого класса, описывающего понятия, выводимые из исходного класса.

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

Соотношение спецификации и проектирования

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

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

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

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

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

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

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

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

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

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

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

Типы

STACK[G]

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

У6.10 Очереди

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

У6.1 Точки

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

У6.2 Боксеры

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

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

У6.3 Банковские счета

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

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

У6.4 Сообщения

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

У6.5 Имена

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

У6.6 Текст

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

У6.7 Покупка дома

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

У6.8 Дополнительные операции для стеков

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

У6.9 Ограниченные стеки

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

У6.11 Распределители

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

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

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

У6.12 Булевский -- BOOLEAN

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

) автоматически определены для каждого АТД.

У6.13 Достаточная полнота

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

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

У6.14 Непротиворечивость

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

Универсализация (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].

За пределами программ

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

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

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

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

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

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

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

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

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

---

---