Инварианты цикла (Конкретно Ch.3 “Ускоренного C++”)

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

Общий случай выглядит так:

[invariant true];
while (keep going) {
    [state transformation];
    [invariant true];
}

Но во время преобразования состояния ваш инвариант не обязательно выполняется.

И отдельное примечание по стилю: если вы хотите быть суперкодером, вместо того, чтобы оставлять свои инварианты в комментариях, сделайте их утверждения!

// Loop invariant: x+y = -4
for (int x = 0; x < 10; x++) {
    [do something];
    assert(x+y == -4);  // Loop invariant here!
}

Таким образом, у вас будет код самопроверки.

Я считаю, что в книге говорится о способе остановки циклов while. Во втором случае очень легко увидеть, что цикл остановится, когда «r» будет увеличено достаточно, чтобы равняться «строкам». Поскольку большинство счетчиков в C ++ отсчитываются от нуля, это, скорее всего, выведет строку для каждой строки.

С другой стороны, в первом примере используется перегрузка оператора для ">>" объекта cin. Цикл while будет продолжаться до тех пор, пока эта функция не вернет ноль. Эта перегрузка оператора не вернет это значение, пока вход не закроется.

Какую клавишу можно нажать, чтобы "cin >>" вернул 0? В противном случае цикл никогда не закончится. Вам нужно убедиться, что вы не создаете такой цикл.

Необходимо добавить строку для остановки цикла вне условия. Посмотрите утверждения "break" и "continue".

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

Я могу представить книгу, которая хочет, чтобы вы поняли, что инвариант - это то, что вы утверждаете как истинное всегда и во все времена, но иногда это не так, и что хорошо знать, когда это не так, потому что, если вы вернетесь, или выбросите исключение, или уступите параллелизму, или что-то еще, когда это не так, ваша система будет полностью испорчена. Немного сложнее представить, что вы перефразировали то, что намеревались сказать авторы. Но я думаю, что если я поверну голову в сторону и прищуриюсь, я смогу перефразировать это так: «сумма - это сумма первых подсчитанных оценок» верно всегда и всегда, кроме тех случаев, когда мы заняты чтением и добавлением их - это может быть не так. правда во время этого процесса. Имеет смысл?

В первом примере переменная count не используется ни для чего другого, кроме как просто увеличиваться для каждого цикла ввода. Цикл будет продолжаться до тех пор, пока >> не вернет NULL.

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

while (cin >> x) {
    ++count;
}


rows = NROWS;
r = 0;

while (r != rows) {
    // write a row of output 
    std::cout << std::endl;
    ++r;
}

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

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

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

Если инвариант равен «в любой точке итерации цикла while , мы прочитали ...`, то, строго говоря, этот инвариант не будет истинным. Я думаю, что инвариант должен относиться к состоянию, которое существует в начале, конце или в фиксированной точке цикла.

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

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

Я не понимаю, почему это важно. Конечно, для любого другого цикла подобное утверждение было бы верным?

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

Для этого кода:

// invariant: we have written r rows so far
int r = 0; // this is also important!
while (r != rows) {
    // write a row of output 
    std::cout << std::endl;
    ++r;
}

Инвариант «В конце итерации цикла while мы написали r строк» ​​определенно истинен.

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

Это действительно интересно / важно в контексте безопасности исключений.

Рассмотрим следующий сценарий:

• «count» - это определяемый пользователем класс с перегруженным оператором ++
• Этот перегруженный оператор ++ вызывает исключение.
• Исключение перехватывается позже вне цикла (т. Е. Цикл выглядит так же, как и сейчас, нет try / catch)

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

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

После вашего обновления автор правильно описывает, как инвариант цикла должен «восстанавливаться» на каждой итерации цикла.

Я не понимаю, почему это важно. Конечно, практически для любого другого цикла подобное утверждение было бы верным?

Да, это правда - в этом цикле нет ничего особенного (хорошо, условие цикла имеет побочный эффект, но его можно легко переписать).

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