Принципы проектирования класса

Объекты как машины

Следующий принцип выражает этот запрет в более точной форме:

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

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

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

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

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

Наш рисунок основан на примере объекта list, интерфейс которого описан в предыдущих лекциях и будет еще обсуждаться подробнее в данной лекции. Команды включают start (курсор передвигается к первому элементу), forth (продвижение курсора к следующей позиции), search (передвижение курсора к следующему вхождению элемента, введенного в верхний левый слот). Запросы включают item (показ на дисплее панели значения элемента в позиции курсора), index (показ текущей позиции курсора). Заметьте разницу между понятием "курсора", связанного с внутренним состоянием и, следовательно, напрямую не наблюдаемым, и понятиями item или index, более абстрактными, задающими официально экспортируемую информацию о состоянии.

Функции, создающие объекты

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

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

Чистый стиль для интерфейса класса

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

Как вы могли заметить, этот стиль отличается от доминирующей сегодня практики, в частности от стиля программирования на языке C, предрасположенного к побочным эффектам. Игнорирование разницы между действием и значением - не просто свойство общего C-стиля (иногда кажется, что C-программисты не в силах противостоять искушению, получая значение, что-нибудь не изменить при этом). Все это глубоко встроено в язык, в такие его конструкции, как x++, означающую возвращение значения x, а затем его увеличение на 1 ; нимало не смущающую конструкцию ++x, увеличивающую x до возвращения значения; Эти конструкции сокращают несколько нажатий клавиш: y = x++ эквивалентно y = x; x := x+1. Целая цивилизация фактически построена на побочном эффекте.

Было бы глупо полагать бездумным стиль побочных эффектов. Его широкое распространение говорит о том, что многие находят его удобным, чем частично объясняется успех языка C и его потомков. Но то, что было привлекательным в прошлом веке, когда популяция программистов возрастала каждые несколько лет, когда важнее было сделать работу, не задумываясь о ее долговременном качестве, - не может подходить инженерии программ двадцать первого столетия. Мы хотим, чтобы ПО совершенствовалось вместе с нами, чтобы оно было понятным, управляемым, повторно используемым, и ему можно было бы доверять. Принцип Разделения Команд и Запросов является одним из требуемых условий достижения этих целей.

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

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

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

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

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

Принцип Разделения возвращает ссылочную прозрачность. Это означает, что мы будем отделять процедуру, передвигающую курсор к следующему элементу, и запрос, возвращающий значение элемента, на который указывает курсор. Пусть input имеет тип FILE ; инструкция чтения очередного целого из файла input будет выглядеть примерно так:

input.advance
    n := input.last_integer

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

Генераторы псевдослучайных чисел: упражнение

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

random_seed (seed)

Здесь seed задается клиентом, что позволяет при необходимости получать одну и ту же последовательность чисел. Каждое очередное число последовательности возвращается при вызове функции:

xx := next_random ()

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

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

Что является абстракцией данных?

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

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

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

Стоп - появился термин последовательность, или, более точно, последовательность псевдослучайных чисел. Это и есть разыскиваемая абстракция! Она вполне законна и напоминает рассмотренный ранее список с курсором, только является бесконечной. Ее свойства включают:

Для получения новой последовательности rand клиенты будут использовать create rand.make (seed), для получения следующего значения - rand.forth, для получения текущего значения - xx := rand.item.

Как видите, нет ничего специфического в интерфейсе последовательности случайных чисел за исключением аргумента seed в процедуре создания. Добавив процедуру start, устанавливающую курсор на первом элементе (которую процедура make может вызывать при создании последовательности), мы получаем каркас отложенного класса COUNTABLE_SEQUENCE, описывающего произвольную бесконечную последовательность. На его основе можно построить, например, последовательность простых чисел, определив класс PRIMES - наследника COUNTABLE_SEQUENCE, чьи последовательные элементы являются простыми числами. Другой пример - последовательность чисел Фибоначчи.

Класс COUNTABLE_SEQUENCE и его потомки, такие как PRIMES, являются частью универсальной иерархии ([M 1994]) информатики.

Абстрактное состояние, конкретное состояние

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

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

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

max is
        -- Максимальное значение элементов списка
    require
        not empty
    local
        original_index: INTEGER
    do
        original_index := index
        from
            start; Result := item
        until is_last loop
            forth; Result := Result.max (item)
        end
        go (original_index)
    end

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

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

Мы видели, что программный (конкретный) объект является реализацией абстрактного объекта и что два конкретных объекта могут быть реализациями одного и того же абстрактного объекта. Например, два различных представления стека могут задавать один и тот же стек. Конкретные стеки могут использовать массивы с маркером вершины count и одинаковыми элементами ниже count. Но они могут быть массивами разной размерности и иметь разные элементы, расположенные за count. С точки зрения математика каждый конкретный объект принадлежит области определения абстрактной функции a, и мы можем иметь $$c1 \ne c2$$ хотя a(c1) = a(c2).

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

representation.put (some_value, count + 1)

(с гарантией, что емкость массива, по меньшей мере, равна count + 1 ). Тогда побочный эффект затронет область выше той, что отведена стеку, и в этом нет ничего плохого.

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

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

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

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

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

Стратегия

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

Поэтому Принцип Разделения Команд и Запросов является методологическим предписанием, а не языковым ограничением. Это не снижает его важности.

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

Возражения

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

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

target.some_operation (...)
how_did_it_go := target.status

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

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

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

x := buffer.item; buffer.remove

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

buffer.remove; buffer.remove

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

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

Законные побочные эффекты: пример

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

Рассмотрим реализацию комплексных чисел. Как и в случае с точками, обсуждаемом в предыдущих лекциях, возможны два представления - декартово (с координатами x и y ) и полярное (с расстоянием r и углом q ). Какое из них выбрать? Простого ответа нет. Если, как обычно, обратиться к АТД, то разные применимые операции - сложение, вычитание, умножение и деление - и запросы для получения значений x, y, r и q эффективно выполняются для разных представлений (декартово представление лучше для сложения и умножения, полярное - для умножений и делений).

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

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

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

Пусть наш класс включает следующие операции:

class COMPLEX feature
    ... Объявления компонентов:
            infix "+", infix "-", infix "*", infix "/",
            add, subtract, multiply, divide,
            x, y, rho, theta, ...
end

Запросы x, y, rho и theta представляют экспортируемые функции, возвращающие вещественные значения. Они всегда определены (исключая theta для комплексного числа 0 ). Помимо инфиксных функций " + " и других предполагаем процедуру add и другие. Вызов: z1 + z2 дает новое комплексное число, вызов z1.add (z2) изменяет z1. На практике могут понадобиться только функции или только процедуры.

Наш класс включает следующие секретные (закрытые) атрибуты:

cartesian_ready: BOOLEAN
polar_ready: BOOLEAN
private_x, private_y, private_rho, private_theta: REAL

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

invariant
    cartesian_ready or polar_ready
    polar_ready implies (0 <= private_theta and private_theta <= Two_pi)
        -- cartesian_ready implies (private_x and private_y являются текущими)
        -- polar_ready implies (private_rho and private_theta являются текущими)

Последние два предложения выражены неформально в форме комментария.

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

Две закрытые процедуры доступны для проведения изменений представления:

prepare_cartesian is
            -- Сделать доступным декартово представление
    do
        if not cartesian_ready then
                check polar_ready end
                -- Поскольку инвариант требует, чтобы одно
                -- из двух представлений было текущим
            private_x := private_rho * cos (private_theta)
            private_y := private_rho * sin (private_theta)
            cartesian_ready := True
                -- Здесь cartesian_ready и polar_ready равны true:
                -- Оба представления являются текущими
        end
    ensure
        cartesian_ready
    end
prepare_polar is
            -- Сделать доступным полярное представление
    do
        if not polar_ready then
                    check cartesian_ready end
            private_rho := sqrt (private_x ^ 2 + private_y ^ 2)
            private_theta := atan2 (private_y, private_x)
            polar_ready := True
                -- Здесь cartesian_ready и polar_ready равны true:
                -- Оба представления являются текущими
        end
    ensure
        polar_ready
    end

Функции cos, sin, sqrt и atan2 берутся из стандартной математической библиотеки, atan2(y, x) вычисляет arctangent(y/x).

Нам также нужны процедуры создания - make_cartesian и make_polar:

make_cartesian (a, b: REAL) is
        -- Инициализация: abscissa a, ordinate b
    do
        private_x := a; private_y := b
        cartesian_ready := True; polar_ready := False
    ensure
        cartesian_ready; not polar_ready
    end

и симметрично для make_polar.

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

add (other: COMPLEX) is
        -- Добавляет значение other
    do
        prepare_cartesian; polar_ready := False
        private_x := x + other.x; private_y = y + other.y
    ensure
        x = old x + other.x; y = old y + other.y
        cartesian_ready; not polar_ready
    end

Заметьте, в постусловии важно использовать x и y, а не private_x и private_y, которые могут не быть текущими перед вызовом.

divide (z: COMPLEX) is
        -- Divide by z.
    require
        z.rho /= 0
        -- Численное выражение дает более реалистичное предусловие
    do
        prepare_polar; cartesian_ready := False
        private_rho := rho / other.rho
        private_theta = (theta - other.theta) \\ Two_pi
                        -- \\ - остаток от деления
    ensure
         rho = old rho / other.rho
         theta = (old theta - other.theta) \\ Two_pi
        polar_ready; not cartesian_ready
    end

Аналогично для вычитания и умножения - subtract и multiply. (Предусловие и постусловие могут быть слегка адаптированы для учета особенностей операций с плавающей точкой.) Варианты функций следуют тому же образцу:

infix "+" (other: COMPLEX): COMPLEX is
        -- Сумма текущего числа и other
    do
        create Result.make_cartesian (x + other.x, y + other.y)
    ensure
        Result.x = x + other.x; Result.y = y + other.y
        Result.cartesian_ready
    end
infix "/" (z: COMPLEX): COMPLEX is
        -- Частное от деления текущего комплексного числа на z
    require
        z.rho /= 0
    do
    create Result.make_polar (rho / other.rho, (theta - other.theta) \\ Two_pi)
    ensure
        Result.rho = rho / other.rho
        Result.theta = (old theta - other.theta) \\ Two_pi
        Result.polar_ready
    end

Аналогично для infix "-" и infix "**".

Но где здесь побочные эффекты? В последних двух функциях они непосредственно не видны. Все дело в x, y, rho и theta - они являются хитроумными создателями побочных эффектов. Вычисление x или y приведет к изменению представления (вызовется prepare_cartesian ), если не подготовлено декартово представление. Все симметрично для rho и theta. Вот примеры для x и theta:

x: REAL is
        -- Abscissa
    do
        prepare_cartesian; Result := private_x
    end
theta: REAL is
        -- Angle
    do
        prepare_polar; Result := private_theta
    end

Функции y и rho подобны. Все эти функции вызывают процедуру, которая может включить изменение состояния. В отличие от add и его собратьев, однако, они не делают предыдущее представление неверным, когда вычисляется новое представление. Например, если x вызывается в состоянии с ложным значением cartesian_ready, оба представления (все четыре вещественных атрибута) станут текущими. Все это потому, что функциям разрешается производить побочные эффекты только на конкретных объектах, но не на ассоциированных абстрактных объектах. Выразим это свойство более формально: вычисление z.x или другой функции может изменять конкретный объект, связанный с z, скажем от c1 до c2, но всегда с гарантией того, что

a(c1) = a(c2)

где a - абстрактная функция. Объекты c1 и c2 могут быть различными, но они представляют один и тот же математический объект - комплексное число.

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

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

Много ли аргументов должно быть у компонента?

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

Важность числа аргументов

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

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

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

nonlinear_ode
    (equation_count: in INTEGER;
     epsilon: in out DOUBLE;
    func: procedure    (eq_count: INTEGER; a: DOUBLE; eps: DOUBLE;
     b: ARRAY [DOUBLE]; cm: pointer Libtype)
    left_count, coupled_count: in INTEGER;
    ...)
    [И так далее. Всего 19 аргументов, включающих:
            - 4 in out значения;
            - 3 массива, используемы как входные и выходные;
        - 6 функций, каждая имеющая 6 - 7 аргументов, из которых
            2 или 3 являются массивами!]

Некоторые свойства делают эту процедуру особенно сложной в использовании:

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

Часть этой сложности, несомненно, связана со сложностью самой проблемы. Но все можно сделать лучше. ОО-библиотека для численных вычислений - Math ([Dubois 1997]) - предлагает совсем другой подход, согласованный с концепциями объектной технологии и принципами этой книги. Как ранее упоминалось, эта библиотека служит примером использования объектной технологии для упаковки старого программного обеспечения - ее ядром является не ОО-библиотека. Было бы абсурдно не использовать хорошо зарекомендовавшие себя алгоритмы, и прекрасно, когда им придается современный интерфейс, привлекательный для клиентов. Базисная подпрограмма nonlinear_ode имеет в ней форму:

solve
    -- Решить проблему, записав ответ в x и y

У нее теперь вообще нет аргументов! Просто создается экземпляр класса GENERAL_BOUNDARY_VALUE_PROBLEM, представляющий требуемую задачу, устанавливаются его свойства, отличные от значений, принятых по умолчанию. При этом могут вызываться подходящие процедуры, присоединенные к объекту, решающему проблему. Затем вызывается метод solve для этого объекта. Атрибуты класса x и y дают возможность анализа ответа.

Таким образом, применение ОО-техники дает существенный эффект по сокращению числа аргументов. Измерения, сделанные для библиотек ISE, показывают, что среднее число аргументов находится в пределах от 0,4 для базовых библиотек Base до 0,7 для графической библиотеки Vision. Для корректного сравнения с не ОО-библиотеками следует добавлять единицу, поскольку в объектном случае мы учитываем два аргумента в вызове x.f (a, b) против трех в необъектной программе - f (x, a, b). Но все равно сравнение явно в пользу объектной технологии, так как число аргументов, как мы видели, в необъектном случае достигает 19 аргументов и часто имеет значения 5, 10 или 15.

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

Операнды и необязательные параметры (опции)

Аргументы подпрограммы могут быть одного из двух возможных видов: операнды и опции.

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

my_document.print (printer_name, paper_size, color_or_not,
                 postscript_level, print_resolution)

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

Этот пример иллюстрирует разницу между операндами и опциями:

Это определение носит общий характер и оставляет место для неопределенности. Существуют два прямых критерия:

В соответствии с первым критерием аргументы print являются опциями. Заметьте, однако, что цель вызова - неявный аргумент my_document, как и все цели, должна быть операндом. Если не сказать, какой документ следует печатать, никто не сделает за вас этот выбор.

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

Принцип

Определение операндов и опций дает правило для аргументов:

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

my_document.set_printing_size ("A4")
my_document.set_color
my_document.print                     -- Совсем нет аргументов

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

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

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

Применение Принципа Операндов дает несколько преимуществ:

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

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

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

Преимущества, обеспечиваемые Принципом Операндов

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

Этот стиль вскоре становится естественным для разработчиков. (Мы сделали его частью стандарта в ISE.) Вы создаете требуемые объекты, устанавливаете любые значения, отличающиеся от принятых по умолчанию, затем применяете нужные операции. Эта схема была показана на примере solve в библиотеке Math. Она, конечно, предпочтительнее передачи 19 аргументов.

Исключения из Принципа Операндов?

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

Во-первых, можно получить преимущества от существования множества процедур создания. Класс поддерживает разные способы инициализации объектов, вызывая create x.make_specific (argument, ...), где make_specific - соответствующая процедура создания. Можно ослабить Принцип Операндов для таких процедур, облегчая задачу клиенту, предлагая различные способы установки значений, отличные от значений по умолчанию. Однако имеют место два ограничения:

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

my_document.set_printing_size ("...")
my_document.set_printer_name ("...")
my_document.print

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

print_with_size_and_printer (printer_name: STRING; size: SIZE_SPECIFICATION)

Это предполагает, конечно, что основная минимальная программа ( print в нашем примере) остается доступной и что новая программа является дополнением, упрощая задачу клиента в тех случаях, когда она действительно часто встречается.

Контрольный перечень

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

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

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

Размер класса: Подход списка требований

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

Следует ли подобным образом сосредоточиться на рассмотрении размеров класса как целого? Уверенного ответа здесь нет.

Определение размера класса

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

Все же остаются два вопроса:

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

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

Некоторые авторы, в том числе Поль Джонсон ([Johnson 1995]) настаивают на ограничении размеров класса:

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

Из опыта ISE следует другая точка зрения. Мы полагаем, что сам по себе размер класса не создает проблем. Хотя большинство классов относительно невелико (от нескольких компонентов до дюжины), встречаются и большие классы (от 60 до 80 компонентов, а иногда и больше), и с ними не возникает никаких особых проблем, если они хорошо спроектированы.

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

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

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

Класс STRING показывает, что большой не означает сложный. Некоторые абстракции по своей природе обладают многими компонентами. Процитирую Валдена и Нерсона ([Walden 1995]):

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

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

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

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

infix "+", infix "-", infix "*", infix "/"

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

Запреты и послабления

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

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

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

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

Активные структуры данных

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

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

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

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

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

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

Соответствующий класс должен быть универсальным (синонимы: родовым, параметризованным), так как структура должна быть применима к спискам с элементами любого типа. Значение звена, заданное компонентом item, имеет тип G - родовой параметр. Оно может быть непосредственно встроено, если фактический родовой параметр развернутого типа, например, для списка целых, или быть ссылкой в общем случае. Другой атрибут right типа LINKABLE[G] всегда представляет ссылку.

Сам список задается отдельной ячейкой - заголовком, содержащим ссылку first_element на первое звено, и, возможно, дополнительной информацией, например count - текущим числом элементов списка. Вот как выглядит связный список символов:

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

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

Технический момент: рисунок не фиксирует в деталях атрибуты LINKED_LIST кроме first_element, показывая просто затененную область. Хотя можно обойтись first_element, классы ниже включают атрибут count. Этот запрос может быть функцией, но неэффективно при каждом проходе по списку подсчитывать число элементов. Конечно, при использовании атрибута каждая операция вставки и удаления должна обновлять его значение. Здесь применим Принцип Унифицированного Доступа - можно менять реализацию, не нанося вреда клиентам класса.

Пассивные классы

Ясно, что нам нужны два класса: LINKED_LIST для списка (более точно, заголовка списка), LINKABLE для элементов списка - звеньев. Оба они являются универсальными.

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

indexing
    description: "Звенья, используемые в связном списке"
    note: "Частичная версия, только атрибуты"
class
    LINKABLE1 [G]
feature {LINKED_LIST}
    item: G
            -- Значение звена
    right: LINKABLE [G]
            -- Правый сосед
end

Тип right можно было бы задавать как like Current, но предпочтительнее на этом этапе сохранить больше свободы в переопределении, поскольку пока непонятно, что может потребовать изменений у потомков LINKABLE.

Для получения настоящего класса следует добавить подпрограммы. Что допустимо для клиентов при работе со звеньями? Они могут изменять поля item и right. Можно также ожидать, что многие из клиентов захотят при создании звена инициализировать его значение, что требует процедуры создания. Вот подходящая версия класса:

indexing
    description: "Звенья, используемые в связном списке"
class LINKABLE [G] creation
    make
feature {LINKED_LIST}
    item: G
            -- Значение звена
    right: LINKABLE [G]
            -- Правый сосед
    make (initial: G) is
            -- Инициализация item значением initial
        do put (initial) end
    put (new: G) is
            -- Замена значения на new
        do item := new end
    put_right (other: LINKABLE [G]) is
            -- Поместить other справа от текущего звена
        do right := other end
end

Для краткости в классе опущены очевидные постусловия процедуры (такие как ensure item = initial для make ). Предусловий здесь нет.

Ну, вот и все о LINKABLE. Теперь рассмотрим сам связный список, внутренне доступный через заголовок. Рассмотрим его экспортируемые компоненты: запрос на получение числа элементов ( count ), пуст ли список ( empty ), значение элемента по индексу i(item), вставка нового элемента в определенную позицию ( put ), изменение значения i -го элемента ( replace ), поиск элемента с заданным значением ( occurrence ). Нам также понадобится запрос, возвращающий ссылку на первый элемент ( void, если список пуст), который не должен экспортироваться.

Вот набросок первой версии. Некоторые тела подпрограмм опущены.

indexing
    description: "Односвязный список"
    note: "Первая версия, пассивная"
class
    LINKED_LIST1 [G]
feature -- Access
    count: G
    empty: BOOLEAN is
            -- Пуст ли список?
        do
            Result := (count = 0)
        ensure
            empty_if_no_element: Result = (count = 0)
        end
    item (i: INTEGER): G is
            -- Значение i-го элемента
        require
            1 <= i; i <= count
        local
            elem: LINKABLE [G]; j: INTEGER
        do
            from
                j := 1; elem := first_element
            invariant j <= i; elem /= Void variant i - j until
                j = i
            loop
                j := j + 1; elem := elem.right
            end
            Result := elem.item
        end
    occurrence (v: G): INTEGER is
            -- Позиция первого элемента со значением v (0, если нет)
        do ... end
feature -- Element change
    put (v: G; i: INTEGER) is
            -- Вставка нового элемента со значением v,
            -- так что он становится i-м элементом
        require
            1 <= i; i <= count + 1
        local
            previous, new: LINKABLE [G]; j: INTEGER
        do
                -- Создание нового элемента
            create new.make (v)
            if i = 1 then
                    -- Вставка в голову списка
                new.put (first_element); first_element := new
            else
                from
                    j := 1; previous := first_element
                invariant
                    j >= 1; j <= i - 1; previous /= Void
                    -- previous - это j-й элемент списка
                variant
                    i - j - 1
                until j = i - 1 loop
                    j := j + 1; previous := previous.right
                end
                    Вставить после previous
                previous.put_right (new)
                new.put_right (previous.right)
            end
            count := count + 1
        ensure
            one_more: count = old count + 1
            not_empty: not empty
            inserted: item (i) = v
            -- For 1 <= j < i,
            -- элемент с индексом j не изменил свое значение
            -- For i < j <= count,
                -- элемент с индексом j изменил свое значение
                -- на то, которое элемент с индексом j - 1
                -- имел перед вызовом
        end
    replace (i: INTEGER; v: G) is
            -- Заменить на v значение i-го элемента
        require
            1 <= i; i <= count
        do
            ...
        ensure
            replaced: item (i) = v
        end
feature -- Removal
    prune (i: INTEGER) is
            -- Удалить i-й элемент
        require
            1 <= i; i <= count
        do
            ...
        ensure
            one_less: count = old count - 1
        end
    ... Другие компоненты ...
feature {LINKED_LIST} -- Implementation
    first_element: LINKABLE [G]
invariant
    empty_definition: empty = (count = 0)
    empty_iff_no_first_element: empty = (first_element = Void)
end

Это хорошая идея попытаться самому закончить определение occurrence, replace и prune в этой первой версии. Убедитесь при этом, что поддерживается истинность инварианта.

Инкапсуляция и утверждения

До рассмотрения лучших версий несколько комментариев к первой попытке.

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

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

Утверждения для put полны, но из-за ограничений языка утверждений они не полностью формальны. Аналогично подробные предусловия следует добавить в другие подпрограммы.

Критика интерфейса класса

Удобно ли использование LINKED_LIST1? Давайте оценим наш проект.

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

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

Рассмотрим процедуру occurrence. Она возвращает индекс элемента, найденного в списке, или 0 в случае его отсутствия. Недостаток ее в том, что она дает только первое вхождение. Что, если клиент захочет получить последующие вхождения? Но есть и более серьезная трудность. Клиент, выполнивший поиск, может захотеть изменить значение найденного элемента или удалить его. Но любая из этих операций требует повторного прохода по списку!

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

Простые, напрашивающиеся решения

Как справиться с неэффективностью? На ум приходят два возможных решения:

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

Второе решение мы пытались реализовать в ранней версии ISE. Для вставки элемента непосредственно перед вхождением известного значения клиент вместо вызова search вызывал:

insert_before_by_value (v: G; v1: G) is
        -- Вставка нового элемента со значением v перед первым
        -- вхождением элемента со значением v1 или в конец списка,
        -- когда нет вхождений
    do
        ...
    end

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

Но вскоре мы осознали, на какой скользкий путь мы встали. Рассмотрим все потенциально полезные варианты: search_and_replace, insert_before_by_value, insert_ after_by_value, insert_after_by_position, insert_after_by_position, delete_before_by_value, insert_at_ end_if_absent и так далее.

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

Введение состояния

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

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

Как отмечалось в этой лекции, без колебаний можно рассматривать объекты как машины с внутренним состоянием и вводить как команды, изменяющие состояние, так и запросы на этом состоянии. В первом решении список уже имел состояние, определяемое его содержимым и модифицируемое командами, такими как put and remove ; но, добавив еще несколько компонентов, мы получим лучший интерфейс, делающий класс более простым и эффективным.

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

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

Примером команды, передвигающей курсор, является процедура search, заменяющая функцию occurrence. Вызов l.search(v) передвинет курсор к первому элементу со значением v справа от текущей позиции курсора, или передвинет его в позицию after, если таких элементов нет. Заметьте, помимо прочего, это решает проблему множественных вхождений, - просто повторяйте поиск столько раз подряд, сколь это необходимо. Для симметрии можно также иметь search_back.

Основные команды манипулирования курсором:

Кроме before и after запросы о позиции курсора включают index, целочисленный номер позиции, начинающийся с 1 для первой позиции, а также булевы запросы is_first и is_last.

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

Поддержка согласованности: инвариант реализации

При построении класса для фундаментальной структуры данных следует тщательно позаботиться обо всех деталях. Утверждения здесь обязательны. Без них велика вероятность пропуска важных деталей. Например:

Ответы на вопросы первого вида будут даны в виде предусловий и постусловий.

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

0 <= index; index <= count + 1

Что можно сказать о пустом списке? Необходима симметрия по отношению к левому и правому. Одно решение, принятое в ранних версиях библиотеки, состояло в том, что пустой список это тот единственный случай, когда before и after оба истинны. Это работает, но приводит в алгоритмах к частой проверке тестов в форме: if after and not empty. Это привело нас к концептуальному изменению точки зрения и введению в список двух специальных элементов - стражей (sentinel), изображаемых на рисунке в виде специальных картинок.

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

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

on_item (i: INTEGER): BOOLEAN is
            -- Есть ли элемент в позиции i?
    do
        Result := ((i >= 1) and (i <= count))
    ensure
        within_bounds: Result = ((i >= 1) and (i <= count))
        no_elements_if_empty: Result implies (not empty)
    end

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

Инвариант устанавливает истинность утверждения: not (after and before). В граничном случае пустого списка картина выглядит так:

Итак, пустой список имеет два возможных состояния: empty and before и empty and after, соответствующие двум позициям курсора на рисунке. Это кажется странным, но не имеет неприятных последствий и на практике предпочтительнее прежнего соглашения empty = (before and after), сохраняя справедливость empty implies (before or after).

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

0 <= index; index <= count + 1
before = (index = 0); after = (index = count + 1)
is_first = ((not empty) and (index = 1));
 is_last = ((not empty) and (index = count))
empty = (count = 0)
    -- Три следующих предложения являются теоремами,
    -- выводимыми из предыдущих утверждений:
empty implies (before or after)
not (before and after)
empty implies ((not is_first) and (not is_last))

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

Последние три предложения инварианта выводимы из предыдущих (см. У5.6). Для инвариантов минимализм не требуется, часто полезно включать дополнительные предложения, если они устанавливают важные, нетривиальные свойства. Как мы видели (см. лекцию 6 курса "Основы объектно-ориентированного программирования"), АТД и, как следствие, реализация класса является теорией, в данном случае теорией связных списков. Утверждения инварианта выражают аксиомы теории, но любая полезная теория имеет также и интересные теоремы.

С точки зрения клиента

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

l: LINKED_LIST [INTEGER]; m, n: INTEGER
...
l.search (m)
if not after then l.put_right (n) end

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

Для удаления третьего вхождения некоторого элемента клиент выполнит:

l.start; l.search (m); l.search (m); l.search (m)
if not after then l.remove end

Для вставки элемента в позицию i:

l.go (i); l.put_left (i)

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

Взгляд изнутри

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

В заголовке списка наряду со ссылкой на первый элемент first_element полезно хранить еще две ссылки на элемент в позиции курсора active и предшествующий ему элемент - previous. Это позволит эффективно выполнять вставку и удаление.

Клиенты могут узнать, каково состояние списка, имея доступ к открытым целочисленным атрибутам count и index и булевым запросам: before, after, is_first, is_last, item. Вот две типичные функции:

after: BOOLEAN is
        -- Находится ли курсор за списком?
    do Result := (index = count + 1) end
is_first: BOOLEAN is
        -- Установлен ли курсор на первом элементе?
    do Result := (index = 1) end

(Напишите самостоятельно функции before и is_last.) Для функции after высказывание "Стоит ли курсор справа от последнего элемента?" не совсем корректно, так как after может быть истинным, даже если в списке совсем нет элементов. Комментарии к заголовкам следует писать так, чтобы они были ясными; лаконичность и аккуратность - сестры таланта (см. лекцию 8).

Запрос item возвращает элемент в позиции курсора, если таковой имеется:

item: G is
       -- Элемент в позиции курсора
    require
        readable: readable
    do
        Result := active.item
    end

Напоминаю, readable указывает, установлен ли курсор на элементе списка ( index между 1 и count ). Также заметьте, item в active.item ссылается на атрибут в LINKABLE, а не на функцию из самого LINKED_LIST.

Рассмотрим теперь основные команды манипулирования курсором. Обращаться с ними нужно довольно деликатно, в утешение можно заметить, что лишь небольшая их часть - start, forth, put_right, put_left и remove, - выполняет нетривиальные операции над ссылками. Давайте начнем с команд start и forth. Процедура start должна работать как с пустым, так и с не пустым списком. Для пустого списка соглашение состоит в том, что start передвигает курсор ко второму стражу.

start1 is
        -- Передвигает курсор к первой позиции.
        -- (Предварительная версия.)
    do
        index := 1
        previous := Void
        active := first_element
    ensure
        moved_to_first: index = 1
        empty_convention: empty implies after
    end
forth1 is
            -- Передвигает курсор к следующей позиции.
            -- (Предварительная версия.)
    require
        not_after: not after
    do
        index := index + 1
        if before then
          active := first_element; previous := Void
        else
                    check active /= Void end
          previous := active; active := active.right
        end
    ensure
        moved_by_one: index = old index + 1
    end

Пора остановиться! Все становится слишком сложным и неэффективным. Производительность процедуры forth является критической, поскольку типично она используется клиентом в цикле from start until after loop ...; forth end. Можно ли избавиться от теста?

Можно, если всерьез рассматривать левого стража и всегда создавать его одновременно с созданием списка. (Процедура создания make для LINKED_LIST остается в качестве упражнения.) Заменим first_element ссылкой zeroth_element на левого стража:

Свойства zeroth_element /= Void и previous /= Void будут теперь частью инварианта (следует, конечно, убедиться, что процедура создания обеспечивает его выполнение). Они весьма ценны, поскольку позволяют избавиться от многих повторяемых проверок.

Процедура forth, запускаемая после обновленной процедуры start, теперь проще и быстрее (без проверок!):

start is
        -- Передвигает курсор к первой позиции
    do
        index := 1
        previous := zeroth_element
        active := previous.right
    ensure
        moved_to_first: index = 1
        empty_convention: empty implies after
        previous_is_zeroth: previous = zeroth_element
    end
forth is
        -- Передвинуть курсор к следующей позиции.
        -- (Версия пересмотрена в интересах эффективности. Без тестов!)
    require
        not_after: not after
    do
        index := index + 1
        previous := active
        active := active.right
    ensure
        moved_by_one: index = old index + 1
    end

Удобно определить go_before, устанавливающую курсор на левом страже:

go_before is
            -- Передвигает курсор к before
    do
        index := 0
        previous := zeroth_element
        active := zeroth_element
    ensure
        before: before
        previous_is_zeroth: previous = zeroth_element
        previous_is_active: active = previous
    end

Процедура go определяется в терминах go_before и forth:

go (i: INTEGER) is
           -- Передвигает курсор к i-й позиции
    require
        not_offleft: i >= 0
        not_offright: i <= count + 1
    do
        from
            if i < index then go_before end
        invariant index <= i variant i - index until index = i loop
            forth
        end
    ensure
        moved_there: index = i
    end

Мы старательно избегали проходов по списку. Процедуре go, единственной из рассмотренных, необходим цикл. Для симметрии следует добавить finish, перемещающую курсор к последней позиции, реализуемую вызовом go (count + 1).

Хотя и нет настоящей независимости, удобно (Принцип Списка Требований) экспортировать go_before. Тогда для симметрии следует включить и go_after, выполняющую go (count + 1), и экспортировать ее.

Также для симметрии добавлена процедура back, содержащая цикл, подобный go:

back is
            -- Передвинуть курсор к предыдущей позиции
    require
        not_before: not before
    do
                check index - 1 >= 0 end
        go (index - 1)
    ensure
        index = old index - 1
    end

Приятно иметь симметрию между back и forth, однако в ней таится угроза, поскольку клиент может беззаботно вызывать back, не думая, что ее реализация содержит цикл, в котором index - 1 раз вызывается forth. Если работа с левой частью списка проводится от случая к случаю, то однонаправленный список является подходящим, если же одинаково часто необходимо обращаться к элементам слева и справа от текущего, то необходимо перейти к двунаправленному списку. Соответствующий класс может быть построен как наследник LINKED_LIST (наследование используется корректно, так как двунаправленный список одновременно является и однонаправленным). Создание такого списка оставлено в качестве упражнения (см. У5.7). Следует его выполнить, если хотите достигнуть полного понимания концепций.

Ранние утверждения в инварианте не зависели от реализации. Добавим теперь утверждения, описывающие особенности реализации:

empty = (zeroth_element.right = Void)
        zeroth_element /= Void; previous /= Void
        (active = Void) = after; (active = previous) = before
        (not before) implies (previous.right = active)
        (previous = zeroth_element) = (before or is_first)
        is_last = ((active /= Void) and then (active.right = Void))

Большинство из запросов реализуются непосредственно - before возвращает булево значение (index = 0) и after - (index = count + 1). Элемент в позиции курсора дается:

item: G is
            -- Значение элемента в позиции курсора
        require
            readable: readable
        do
            Result := active.item
        end

Процедура search подобна go и оставлена читателю. Следует также написать процедуру i_th (i: INTEGER), возвращающую элемент в позиции i. Следует позаботиться об отсутствии абстрактного побочного эффекта, допуская конкретный побочный эффект.

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

remove is
-- Удаляет элемент в позиции курсора и передвигает курсор к правому соседу.
        -- (Если нет правого соседа, то становится истинным after).
    require
        readable: readable
    do
        active := active.right
        previous.put_right (active)
        count := count - 1
    ensure
        same_index: index = old index
        one_less_element: count = old count - 1
        empty_implies_after: empty implies after
    end

active := active.right
    if previous /= Void then previou.sput_right (active) end
    count := count - 1
    if count = 0 then
        first_element := Void
    elseif index = 1 then
        first_element := active
    -- Иначе first_element не изменяется
    end

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

АТД и абстрактные машины

Понятие активной структуры данных широко применимо и согласуется с ранее введенными принципами, в частности с Принципом Разделения Команд и Запросов. Явно вводя состояние структуры данных, зачастую приходим к простому интерфейсу документа.

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

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

Отделение состояния

Возможно развитие предыдущей техники. До сих пор курсор был лишь концепцией, реализованной атрибутами previous, active и index, но не был одним из классов. Можно определить класс CURSOR, имеющий потомков, вид которых зависит от структуры курсора. Тогда мы можем отделить атрибуты, задающие содержимое списка ( zeroth_element, count ), от атрибутов, связанных с перемещением по списку, хранимых в объекте курсора.

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

Слияние списка и стражей

(Этот раздел описывает улучшенную оптимизацию и может быть опущен при первом чтении.)

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

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

index := index + 1
previous := active
active := active.right

без дорогих проверок предыдущей версии. Мы избежали тестов, будучи уверенными, что active не равно Void, когда список не находится в состоянии after. Это следствие утверждения инварианта (active = Void) = after; верного потому, что у нас есть настоящее звено - страж, доступный как active, даже если список пуст.

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

from your_list.start until your_list.after loop ...; your_list.forth end

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

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

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

Для нахождения решения зададимся неожиданным вопросом.

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

Можем ли мы заставить заголовок списка играть роль стража? Оказывается, можем. Все, что имеет LINKABLE - это поле item и ссылку right. Для стража необходима только ссылка, указывающая на первый элемент, так что, если поместить ее в заголовок, то она будет играть ту же роль, как когда она называлась first_element в первом варианте со стражами. Проблема, конечно, была в том, что first_element мог иметь значение void для пустого списка, что принуждало во все алгоритмы встраивать тесты в форме if before then ...Мы точно не хотим возвращаться назад к этой ситуации. Но можем использовать концептуальную модель, показанную на рисунке, избавленную от стража

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

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

Сохраним все желательные утверждения инварианта предыдущей версии со стражами:

previous /= Void
        (active = Void) = after; (active = previous) = before
        (not before) implies (previous.right = active)
        is_last = ((active /= Void) and then (active.right = Void))

Предложения, включающие ранее zeroth_element:

zeroth_element /= Void
        empty = (zeroth_elemenеt.right = Void)
        (previous = zeroth_element) = (before or is_first)

теперь будут иметь вид:

first_element /= Void
        empty = (first_element = Current)
        (previous = Current) = (before or is_first)

Но чтобы все получилось так просто, необходимо (нас ждут опасные вещи, поэтому пристегните ремни) сделать LINKED_LIST наследником LINKABLE:

class LINKED_LIST [G] inherit
    LINKABLE [G]
        rename right as first_element, put_right as set_first_element end
...Остальное в классе остается как ранее с выше показанной заменой zeroth_element...

Не нонсенс ли это - позволить LINKED_LIST быть наследником LINKABLE? Совсем нет! Вся идея в том, чтобы слить воедино два понятия заголовка списка и стража, другими словами рассматривать заголовок списка как элемент списка. Поэтому мы имеем прекрасный пример отношения " is-a " ("является") при наследовании. Мы решили рассматривать каждый LINKED_LIST как LINKABLE, поэтому наследование вполне подходит. Заметьте, отношение "быть клиентом" даже не участвует в соревновании - не только потому, что оно не подходит по сути, но оно добавляет лишние поля к нашим объектам!

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

Последний шаг - класс TWO_WAY_TREE, по разумным причинам наследуемый от TWO_WAY_LIST и BI_LINKABLE. Достаточно для небольшого сердечного приступа, но нет - все прекрасно сложилось в нужном порядке и в нужном месте. Мы получили все необходимые компоненты, ненужных компонентов нет, концептуально все стражи на месте, так что forth, back и все связанные с ними циклы выполняются быстро, как это требуется, и стражи совсем не занимают памяти.

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

Выборочный экспорт

Отношение между классами LINKABLE и LINKED_LIST иллюстрируют важность поддержки у компонента более двух статусов экспорта - открытого (общедоступного) и закрытого (секретного).

Класс LINKABLE не должен делать свои компоненты - item, right, make, put, put_right - общедоступными, так как большинство клиентов не должно влезать во внутренности звеньев, они должны использовать только связные списки. Но их нельзя делать секретными, поскольку это спрятало бы их от LINKED_LIST, для которого они и предназначены, так как вызовы active.right, основа операций forth и других подпрограмм LINKED_LIST, были бы тогда невозможны.

Выборочный экспорт обеспечивает решение, позволяя LINKABLE отбирать то множество классов, которому и только которому экспортируются эти компоненты:

class
    LINKABLE [G]
feature {LINKED_LIST}
    item: G
    right: LINKABLE [G]
    -- и т.д.
end

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

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

(left /= Void) implies (left.right = Current)

Это требует, чтобы right было объявлено в предложении feature {... Другие классы ..., BI_LINKABLE} ; в противном случае вызов left.right будет неверным.

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

Как справляться с особыми ситуациями

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

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

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

if some_abnormal_situation_detected then
    raise some_exception;
end;
"Далее - нормальная обработка"

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

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

Априорная схема

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

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

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

operation (x:...) is
    require
        precondition (x)
    do
    ... Код, работающий только при условии выполнения предусловия...
    end

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

if precondition (y) then
    operation (y)
else
    ... Подходящие альтернативные действия...
end

(Для краткости этот пример использует неквалифицированный вызов, но, конечно же, большинство вызовов будут квалифицированными в форме: z.operation (y).) Чтобы избежать теста if...then...else, следует убедиться, что из контекста следует выполнение предусловия:

...Некоторые инструкции, которые, среди прочего, гарантируют выполнение предусловия...
        check precondition (y) end
operation (y)

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

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

Препятствия на пути априорной схемы

Из-за простоты и ясности априорная схема, в принципе, идеальна. По трем причинам она не является универсально применимой:

Примером случая А1 является решатель линейных уравнений. Функция, дающая решение системы линейных уравнений в форме a x = b, где a - матрица, а x и b - векторы, может быть взята из соответствующего библиотечного класса MATRIX:

inverse (b: VECTOR): VECTOR

Решение системы находится так: x := a.inverse(b). Единственное решение системы существует, только если матрица не "сингулярна". (Сингулярность здесь означает линейную зависимость уравнений, признаком которой является равенство 0 определителя матрицы.) Можно было бы ввести проверку на сингулярность в предусловие inverse, требуя, чтобы вызовы клиента имели вид:

if a.singular then
    ...Подходящие действия для сингулярной матрицы...
else
    x := a.inverse (b)
end

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

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

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

Апостериорная схема

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

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

a.invert (b)
if a.inverted then
    x := a.inverse
else
    ... Подходящие действия для сингулярной матрицы...
end

Функция inverse заменена процедурой invert, более аккуратным именем которой было бы attempt_to_invert. При вызове процедуры вычисляется атрибут inverted, истинный или ложный в зависимости от того, найдено ли решение. В случае успеха решение становится доступным через атрибут inverse. (Инвариант класса может быть задан в виде: inverted = (inverse /= Void).)

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

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

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

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

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

Роль механизма исключений

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

Остаются, однако, ситуации, когда обе схемы не являются адекватными. Возможны три таких категории:

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

Эволюция классов. Устаревшие классы

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

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

Иногда - но только иногда - есть другой выход. Мы вводим в нашу нотацию концепцию устаревших компонентов ( obsolete features ) или устаревших классов ( obsolete classes ). Вот пример подобной подпрограммы:

enter (i: INTEGER; v: G) is
        obsolete "Используйте put (value, index)"
    require
        correct_index (i)
    do
        put (v, i)
    ensure
        entry (i) = v
    end

Это реальный пример, хотя и неиспользуемый в настоящее время. Ранее при эволюции библиотек Base мы пришли к пониманию необходимости замены некоторых имен и соглашений (тогда еще принципы стиля, изложенные в лекции 8, не были сформулированы). Предполагалось изменить имя put на enter и item на entry и, что еще хуже, изменить порядок следования аргументов для совместимости с компонентами других классов в библиотеке.

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

Каковы следствия того, что компонента объявляется устаревшей? На практике они незначительны. Инструментарий окружения должен обнаружить это свойство и вывести соответствующее предупреждение, когда клиентская система использует класс. Компилятор, в частности, выведет сообщение, включающее строку, следующую за ключевым словом obsolete, такую как "Используйте put (value, index) " в нашем примере. Это все. Компонент, с другой стороны, продолжает нормально использоваться.

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

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

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

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

Документирование класса и системы

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

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

Показ интерфейса

Краткая форма непосредственно применяет правило Скрытия Информации, удаляя закрытую от клиента информацию, включающую:

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

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

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

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

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

Лекция 8, посвященная стилю, подробно рассмотрит два последних пункта.

Документирование на уровне системы

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

Инструментарий Case из окружения ISE, основанный на концепциях BON (Business Object Notation), обеспечивает такое видение. На рис.5.15 показана сессия, предназначенная для реверс-инженерии (reverse-engineering) библиотек Base.

Хотя детализация инструментария выходит за рамки этой книги (см. [M 1995c]), можно отметить, что это средство поддерживает анализ больших систем, позволяет изменять масштаб диаграммы, поддерживает возможность фокусироваться на кластерах (подсистемах), позволяет объединять графические снимки с текстовой информацией о подсистемах.

Все эти средства, являясь приложением Принципа Документирования, приближают нас к идеалу Самодокументирования. Все это достигается благодаря тщательно спроектированной нотации и современному окружению.

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

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

В работах Парнаса ([Parnas 1972], [Parnas 1972a]) вводится много похожих идей по проектированию интерфейса.

Различение операндов и опций и результирующий принцип взяты из работы [M1982a].

Понятие активной структуры данных поддерживается в некоторых языках программирования управляющими абстракциями, называемыми итераторами. Итератор представляет механизм, определенный совместно со структурой данных, описывающий, как применять некую операцию к каждому элементу структуры. Например, итератор, ассоциированный со списком, описывает циклический механизм прохода по списку, применяя данную операцию к каждому элементу списка, итератор дерева задает некую стратегию обхода дерева. В работах [Liskov 1981], [Liskov 1986] содержится подробное обсуждение концепции итераторов, доступных в языке программирования CLU. В объектной технологии итераторы могут быть определены в классах, не встраивая их в виде конструкций языка программирования [M 1994a].

Пример адаптивной реализации комплексных чисел взят из [M1979], где он описан на Simula.

Грамотное программирование (Literate programming) [Knuth 1984] утверждает, как и данная лекция, что программы должны содержать свою документацию. Его концепции, однако, существенно отличаются от концепций объектной технологии. Одно из упражнений предлагает сравнить два подхода.

Статьи Джеймса Мак-Кима и Ричарда Билака [Bielak 1993], [McKim 1992a] дают полезные советы по проектированию интерфейса, основанные на понятии Проектирования по Контракту.

Упражнения

У5.1 Функция с побочным эффектом

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

У5.2 Операнды и опции

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

У5.3 Возможные аргументы

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

У5.4 Число элементов как функция

Адаптируйте определение класса LINKED_LIST [G] так, чтобы count стал функцией, а не атрибутом, оставив неизменным интерфейс класса.

У5.5 Поиск в связных списках

Напишите процедуру search (x: G) для класса LINKED_LIST, разыскивающую следующее вхождение x.

У5.6 Теоремы в инварианте

Докажите истинность трех утверждений из первой части инварианта класса LINKED_LIST, отмеченных как теоремы (см. лекцию 5).

У5.7 Двунаправленные списки

Напишите класс, задающий двунаправленные списки с интерфейсом LINKED_LIST, но более эффективной реализацией таких операций, как back, go и finish.

У5.8 Альтернативный проект связного списка

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

У5.9 Вставка в связный список

Глядя на remove, напишите процедуры put_left и put_right для вставки элементов слева и справа от позиции курсора.

У5.10 Циклические списки

Объясните, почему класс LINKED_LIST не может использоваться для циклических списков. (Подсказка: покажите, что утверждения будут нарушаться.) Напишите класс CIRCULAR_LINKED, реализующий циклические списки.

У5.11 Функции ввода, свободные от побочных эффектов

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

У5.12 Документация

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

У5.13 Самодокументированное ПО

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