Что такое инвариант в программировании

Использование программами компьютерной памяти

Полезный материал на эту тему в четком изложении имеется также здесь

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

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

Дополнительно, о том, что такое процесс в вычислительной системе, можно посмотреть, например, здесь

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

Использование концепции виртуальной памяти в вычислительной сиситеме дает следующие преимущества

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

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

Виртуальное адресное пространство любого процесса подразделяется на:

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

вот

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

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

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

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

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

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

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

В языке Julia (как и в Python, но только не в C/C++) реализован механизм так называемой автоматической сборки мусора, который автоматически освобождает фрагменты динамической памяти, после того как программа утрачивает ссылки на на эти фрагменты. Например,

здесь после второго присваивания ссылка на объект типа Robot будет утрачена.

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

Простейшие приемы доказательства и контроля правильности программного кода

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

Каждая подпрограмма или даже просто участок кода предполагаю свое условие «ДАНО» и условие «РЕЗУЛЬТАТ». Поэтому если программный код включает последовательный вызов подпрограмм (или просто логически законченных участков код), то в промежутки между ними целесообразно включать комментарии, содержащие соответствующие утверждения.

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

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

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

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

Циклы

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

Cвойство цикла с предусловием

Для любого цикла с предусловием верно:

Инвариант цикла и метод доказательства правильности цикллического алгоритма

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

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

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

Имеем доказательство правильности алгоритма:

ИНВАРИАНТ && УТВ => весь ряд замаркирован от начала до конца

Имеем тоже самое доказательство правильности алгоритма: ИНВАРИАНТ && УТВ => весь ряд замаркирован от начала до конца

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

ЗАМЕЧАНИЕ. Если в теле цикла с предусловием имеются операторы break или return , то они могут нарушать «естественный» порядок выполнения операторов, составляющих тело этого цикла, и, следовательно, метод доказательства правильности такого цикла на основе инварианта цикла будет не применим. Точно также для цикла с постусловием понятие инварианта цикла не работает.

Опасность и нежелательность цикла с постусловием*

В языке Julia, как и в языке Python специальной конструкции «цикл с постусловием», нет, но вот, например, в языке C/C++ она есть:

Но в Julia такой цикл тоже можно организовать

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

С помощью цикла с предусловием решение запищется так:

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

то получимм код, который правильно работает во вех случаях КРОМЕ одного, а именно, кроме случая, когда Робот изначально стоит рядом с перегородкой. Опасность такого кода состоит в том, что его многократно можно тестировать и не обнаружить никакой ошибки, но она есть (!), и может проявиться в самый не подходящий момент.

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

С помощью цикла с предусловием это запишется так:

А вот использование цикла с постусловием и в этом случае может породить ошибку:

При n=0 вместо требуемой 1 получится 2 (!).

Вывод: циклом с постусловием лучше всего никогда не пользоваться.

Пример: алгоритм подсчёта числа перегородок в ряду

Пусть требуется решить следующую задачу.

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

РЕЗУЛЬТАТ: Робот — противоположной грагицы поля и функция возвращает число горизонтальных перегородок, находящихся непосредственно над рядом с роботом

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

Метод переменной состояния

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

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

Альтернативный способ

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

Что такое инвариант в ООП?

Очень часто в статьях по ООП встречается такое слово, как инвариант:

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

Что имеется ввиду под этим термином? Как выглядят инварианты в коде?

Я нашёл описание термина «инвариант цикла»:

Инвариант цикла – это соотношение, которое истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла. Все это описано у Дейкстры в книге «Дисциплина программирования», и детально разжевано у Гриса в книге «Наука программирования».

А хотелось бы понять, что понимают под инвариантом

в программировании по контракту и
чистом ООП (я так понял, это имеет отношение к инкапсуляции)

Инвариант в математике — это выражение которое сохраняет свое значение. В программировании инвариантом также называют предикат который всегда истинный.

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

В коде инварианты чаще всего никак не выражены, но иногда ставятся защитные проверки которые их проверяют.

Бьерн Страуструп — Язык программирования С++. Главы 11-13
Страница 37. Инварианты

Значение членов или объектов, доступных с помощью членов класса,
называется состоянием объекта (или просто значением объекта).
Главное при построении класса — это: привести объект в полностью
определенное состояние (инициализация), сохранять полностью определенное
состояние обЪекта в процессе выполнения над ним различных операций,
и в конце работы уничтожить объект без всяких последствий. Свойство,
которое делает состояние объекта полностью определенным, называется
инвариантом.
Поэтому назначение инициализации — задать конкретные значения,
при которых выполняется инвариант объекта. Для каждой операции класса
предполагается, что инвариант должен иметь место перед выполнением
операции и должен сохраниться после операции. В конце работы
деструктор нарушает инвариант, уничтожая объект. Например,
конструктор String::String(const char*) гарантирует,
что p указывает на массив из, по крайней мере, sz элементов, причем
sz имеет осмысленное значение и v[sz-1]==0. Любая строковая операция
не должна нарушать это утверждение.
При проектировании класса требуется большое искусство, чтобы
сделать реализацию класса достаточно простой и допускающей
наличие полезных инвариантов, которые несложно задать. Легко
требовать, чтобы класс имел инвариант, труднее предложить полезный
инвариант, который понятен и не накладывает жестких ограничений
на действия разработчика класса или на эффективность реализации.
Здесь "инвариант" понимается как программный фрагмент,
выполнив который, можно проверить состояние объекта. Вполне возможно
дать более строгое и даже математическое определение инварианта, и в
некоторых ситуациях оно может оказаться более подходящим. Здесь же
под инвариантом понимается практическая, а значит, обычно экономная,
но неполная проверка состояния объекта.
Понятие инварианта появилось в работах Флойда, Наура и Хора,
посвященных пред- и пост-условиям, оно встречается во всех важных
статьях по абстрактным типам данных и верификации программ за
последние 20 лет. Оно же является основным предметом отладки в C++.
Обычно, в течение работы функции-члена инвариант не сохраняется.
Поэтому функции, которые могут вызываться в те моменты, когда
инвариант не действует, не должны входить в общий интерфейс класса.
Такие функции должны быть частными или защищенными.
Как можно выразить инвариант в программе на С++? Простое решение —
определить функцию, проверяющую инвариант, и вставить вызовы этой
функции в общие операции. Например:

class String <
int sz;
int* p;
public:
class Range <>;
class Invariant <>;

String(const char* q);

void String::check()
<
if (p==0 || sz<0 || TOO_LARGE<=sz || p[sz-1])
throw Invariant;
>

char& String::operator[](int i)
<
check(); // проверка на входе
if (i<0 || i<sz) throw Range; // действует
check(); // проверка на выходе
return v[i];
>

Этот вариант прекрасно работает и не осложняет жизнь программиста.
Но для такого простого класса как String проверка инварианта будет
занимать большую часть времени счета. Поэтому программисты обычно
выполняют проверку инварианта только при отладке:

inline void String::check()
<
if (!NDEBUG)
if (p==0 || sz<0 || TOO_LARGE<=sz || p[sz])
throw Invariant;
>

Мы выбрали имя NDEBUG, поскольку это макроопределение, которое
используется для аналогичных целей в стандартном макроопределении
С assert(). Традиционно NDEBUG устанавливается с целью указать,
что отладки нет. Указав, что check() является подстановкой, мы
гарантировали, что никакая программа не будет создана, пока константа
NDEBUG не будет установлена в значение, обозначающее отладку.
С помощью шаблона типа Assert() можно задать менее регулярные
утверждения, например:

template<class T, class X> inline void Assert(T expr,X x)
<
if (!NDEBUG)
if (!expr) throw x;
>

вызовет особую ситуацию x, если expr ложно, и мы не отключили
проверку с помощью NDEBUG. Использовать Assert() можно так:

Шаблон типа Assert() подражает макрокоманде assert() языка С.
Если i не находится в требуемом диапазоне, возникает особая
ситуация Bad_f_arg.
С помощью отдельной константы или константы из класса проверить
подобные утверждения или инварианты — пустяковое дело. Если же
необходимо проверить инварианты с помощью объекта, можно определить
производный класс, в котором проверяются операциями из класса, где нет
проверки, см. упр.8 в $$13.11.
Для классов с более сложными операциями расходы на проверки могут
быть значительны, поэтому проверки можно оставить только для "поимки"
трудно обнаруживаемых ошибок. Обычно полезно оставлять по крайней
мере несколько проверок даже в очень хорошо отлаженной программе.
При всех условиях сам факт определения инвариантов и использования
их при отладке дает неоценимую помощь для получения правильной
программы и, что более важно, делает понятия, представленные
классами, более регулярными и строго определенными. Дело в том, что
когда вы создаете инварианты, то рассматриваете класс с другой
точки зрения и вносите определенную избыточность в программу.
То и другое увеличивает вероятность обнаружения ошибок, противоречий
и недосмотров.
Мы указали в $$11.3.3.5, что две самые общие формы преобразования
иерархии классов состоят в разбиении класса на два и в выделении
общей части двух классов в базовый класс. В обоих случаях хорошо
продуманный инвариант может подсказать возможность такого
преобразования. Если, сравнивая инвариант с программами операций,
можно обнаружить, что большинство проверок инварианта излишни,
то значит класс созрел для разбиения. В этом случае подмножество операций
имеет доступ только к подмножеству состояний объекта. Обратно,
классы созрели для слияния, если у них сходные инварианты, даже
при некотором различии в их реализации.

Что такое инвариант в программировании