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

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

Является ли вызов start допустимым, если список пуст; если да, то каков эффект вызова?
Что случится с курсором после remove, если курсор был в последней позиции? Неформально мы к этому подготовились, позволяя курсору передвигаться на одну позицию левее и правее списка. Но нам нужны более точные утверждения, недвусмысленно описывающие все случаи.

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

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

0 <= index; index <= count + 1

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

Рис. 5.8. Список со стражами

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

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

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). В граничном случае пустого списка картина выглядит так:

Рис. 5.9. Пустой список со стражами

Итак, пустой список имеет два возможных состояния: 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 курса "Основы объектно-ориентированного программирования"), АТД и, как следствие, реализация класса является теорией, в данном случае теорией связных списков.Утверждения инварианта выражают аксиомы теории, но любая полезная теория имеет также и интересные теоремы.

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

Содержание раздела