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

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

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

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

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

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

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

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

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

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

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

index:= index + 1previous:= activeactive:= 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. Так что стоило заплатить за ее оптимизацию, поскольку она обеспечивает кардинальное улучшение производительности, будучи свободной от тестов.

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

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

· Связные деревья (см. лекцию 15 курса "Основы объектно-ориентированного программирования") представляют более серьезную проблему. Практически важным является класс TWO_WAY_TREE, задающий удобное представление деревьев с двумя ссылками (на родителя и потомка). Построенный на идеях, описываемых при представлении множественного наследования, класс объединяет понятия узла и дерева, так что он является наследником TWO_WAY_LIST и BI_LINKABLE. Но тогда каждый узел является списком, может быть двунаправленным и хранить обоих стражей.

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

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

Рис. 5.12. Заголовок и страж

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

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

Рис. 5.13. Заголовок как страж (на непустом списке)

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

Рис. 5.14. Заголовок как страж (на пустом списке)

На пустом списке следует присоединить 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. Прежде чем закончить наш полет, еще несколько наблюдений:

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

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

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

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

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

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

· В интересах текущих пользователей: это означает продолжать жить с устаревшим дизайном, чьи неприятные эффекты будут по прошествии времени становиться все более тяжкими. В индустрии это называется восходящей совместимостью (upward compatibility). Совместимость, как много преступлений совершается во имя твое, как писал Виктор Гюго (правда, говоря о свободе).

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

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

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

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

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

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

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

Дата добавления: 2014-12-07