калинин.ru / программирование / c и c++ /

<< 18.09.00 >>

Инварианты внутри программы

Вы когда-нибудь задумывались, над тем, как вы пишите программы? Если нет, то, я думаю, сегодняшняя заметка будет вам полезна.

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

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

Первое, отсутствие детерминированности, в свое время очень страшило программистов. Например, Дейкстра в своей "Дисциплине программирования" (кстати, рекомендую найти и прочитать) писал следующее:

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

С тех прошло уже много лет, и современного программиста вряд ли можно удивить вызовом select() по открытым файловым дескрипторам и ожидания прихода данных в первый из них.

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

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

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

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

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

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

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

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

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

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

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

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

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

Поэтому проверку таких условий надо выделять так, что бы их предназначение было бы видно сразу: при таких условиях работа функции будет корректной. Например, в старой библиотеке ClassLib фирмы Borland были предусмотрены специальные макросы PRECONDITION и POSTCONDITION, которые визуально выделяли предусловия и постусловия.

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

#ifdef NDEBUG
#define assert(p) ((void)0)
#else
#define assert(p) ((p) ? (void)0 : _assert(#p, __FILE__, __LINE__))
#endif

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

Соответсвенно, если определен макрос NDEBUG, то проверка условий не выполняется.

Расставленные по исходному коду assert'ы являются признаком профессионального программиста.

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

template<class X, class A>
inline void Assert(A assertion)
{
    if(!assertion) throw X();
}

Которая должна использоваться как-то так:

Assert<exception>(x > 0);

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

Тем не менее, на практике это редко удается сделать. А теперь возвращаюсь к тому вопросу, который я задал в начале этой заметки. Как вы пишите программы?

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

Резюме

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

Версия для печати

Ссылки по теме:

Э. Дейкстра    Дисциплина программирования. Бъерн Страуструп    Язык программирования C++, 3 издание.

/comment/books/27_08_00.shtml    C и C++. Правила программирования.

Рядом в разделе: Библиотека консорциума W3, libwww (20.09.00)    Популярный нынче термин "веб-программирование" обычно подразумевает под собой программирование, в лучшем случае, на perl, в худшем --- на PHP, в совсем...   >>>> volatile (12.09.00)    И опять я публикую здесь текст из конференции SU.C_CPP. Впору заводить для этого отдельный раздел ;) Автор этого письма, Александр Кротов,...   >>>>

Рядом по дате: Памятка завхозу (19.09.00)    Шла уже третья неделя. Мы выходили из района. Восемьдесят километров тайги, по уши снега среди бурелома и на кончике азимута маленький...   >>>> Кундун / Kundun, 1997 (17.09.00)    С момента предыдущего моего комментария на какой-либо фильм прошло уже недели три и это не из-за того, что я как-то охладел...   >>>>

Содержание:

Заглавная страница Мой блог Мое резюме Дайджест Программирование    C&C++ Сети Unix Алгоритмы Оптимизация Соревнования Отвлеченно XML TeX Просто так

Студенческое Туризм   Байки Фотографии Комментарии    Книги Web-ресурсы Фильмы Интернет Программное обеспечение Жизнь Благодарности Форум Хронология