Invariants of the cycle (in particular, Ch.3 "Accelerated C ++")

Question

I am currently going through Accelerated C ++ and just came across this in chapter 3:

// invariant: // we have read count grades so far, and // sum is the sum of the first count grades while (cin >> x) { ++count; sum += x; } 

The authors follow this, explaining that the invariant needs special attention to it, because when the input is read at x , we will read the estimates count + 1 and, therefore, the invariant will be incorrect. Similarly, when we increase the count, sum will no longer be the sum of the latest grades (if you haven’t guessed, this is a traditional program for calculating student grades).

I do not understand why this matters. Of course, for any other loop such a statement would be true? For example, here is the first cycle of the while book (the output is filled later):

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

Once we have written the appropriate output line, of course, the invariant will be false until we increase r , as in another example?

How do these two conditions differ?

EDIT: Thanks for all your answers. I think I have this, but I'm going to leave it a little longer before choosing “Accepted Answer” to be sure. So far, all answers basically agree, so it hardly seems fair, but worth doing, I think.

Original paragraph as follows:

“Understanding the invariant for this cycle requires special attention because the condition at the time has side effects. These side effects affect the truth of the invariant: successful execution of cin → x does the first part of the invariant - the part that says that we read the estimates of the estimates is false. Accordingly, we must modify our analysis to explain the effect that this condition may have on the invariant.

We know that the invariant was true before evaluating the condition, so we know that we have already read the graphs of estimates. If cin → x succeeds, we now read the count + 1 classes. We can turn this part of the invariant back on by increasing the counter. However, this does falsify the second part of the invariant - the part that says that the sum is the sum of the first estimates of the graph, because after we increase the score, the sum now represents the sum of the first count - 1 estimate, not the first count. Fortunately, we can make the second part of the invariant true by doing the sum + = x; so that the whole invariant will be true during subsequent outages after a while.

If the condition is false, this means that our input attempt failed, so we have not received more data, and therefore the invariant is still true. As a result, we do not need to consider the side effects of the condition after completion. "

Answer 1

From your description, it sounds like the author says nonsense. Yes, the invariant is temporarily interrupted between instructions, but this will happen when you have non-atomic operations like this. As long as there are no clear breakpoints that can lead to incorrect invariant, and the program is in an inconsistent state, you are fine.

In this case, the only way that this can happen is if std :: cout throws an exception while the invariant is incorrect, then you will catch this exception somewhere, but continue to execute in a bad state. It seems to me that the author is too pedantic. So if you do not have any statements about breaking / continuing in the wrong place or exceptions are excluded, you are fine. I doubt many people will be interested in your code example because it is so simple.

Answer 2

In general, invariants are understood only in relation to loop iterations. (At least as I read them!)

The general case looks like this:

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

But during state conversion, your invariant is not necessarily satisfied.

And as a separate note of style: if you want to be a supercoder, instead of leaving your invariants in the comments, make their statements!

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

This way you have a self-test code.

Answer 3

I believe the book relates to a method for stopping loops. In the second case, it is very easy to see that the cycle stops as soon as the "r" is increased so as to equal the "rows". Since most counts in C ++ are based on a zero value, this most likely displays a line for each line.

On the other hand, the first example uses operator overloading for "→" on the cin object. The while loop will continue until this function returns zero. This operator overload will not return this value until the input is closed.

What key can you press so that "cin →" returns 0? Otherwise, the cycle will never end. You need to make sure that you are not creating such a loop.

You must add a line to stop the loop unconditionally. See the "break" and "continue" instructions.

Answer 4

This is really interesting / important in the context of exception safety.

Consider the following scenario:

• "count" is a custom class with operator++ overloaded
• Overloading operator++ throws an exception.
• The exception is caught later outside the loop (i.e. the loop looks like it is now, there is no try / catch)

In this case, the cycle invariant is no longer satisfied, and the state of everything that happens in the cycle is in question. Has a series been written? Has the account been updated? Is the amount correct?

Some additional protection (in the form of temporary variables for storing intermediate values ​​and some attempts / catches) should be used to ensure that everything remains consistent even when an exception is thrown.

Answer 5

The book seems to complicate things a lot more than necessary. I really don't think that explaining cycles with invariants is good. It’s kind of like an explanation with quantum physics.

The authors follow this, explaining that the invariant requires special attention to it, because when the input is read into the variable x, we will read the number + 1 class and, therefore, the invariant will be incorrect. Similarly, when we increment the meter, the variable amount will no longer be the sum of the latest grades (if you haven’t guessed, this is a traditional program for calculating student grades).

First of all, the invariant is not clear. If the invariant is "at the end of the iteration of the while , we read the count estimates with the sum sum ", then this looks right for me. The invariant is not clearly defined, so it makes no sense to even talk about when it is, and it is not respected.

If the invariant is "at any point in the iteration of the while , we read ...", then, strictly speaking, this invariant will not be true. As for cycles, I think the invariant should relate to the state that exists at the beginning, at the end, or at a fixed point in the cycle.

I do not have this book, and I do not know if things are being clarified or not, but it seems that invariants are being used incorrectly. If their invariant is incorrect, why use it in the first place?

I do not think you should worry too much about this. As long as you understand how these loops work, you're fine. If you want to understand them using invariants, you can, but you should pay attention to the invariant you choose. Do not choose the bad one, or he defeats the goal. You must choose an invariant for which it is easy to write code that respects it, and not choose random, and then try to write code that respects it, and definitely not choose indefinite and write code that has nothing to do with it and then say: "you need to pay attention, because it really does not respect the foggy invariant that I chose."

I do not understand why this matters. Of course, for any other loop such a statement would be true?

It depends on the invariant used (the book is rather vague from what you said), but yes, you seem to be right in this case.

For this code:

 // 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; } 

The invariant “At the end of the iteration of the while we wrote r rows” is certainly true.

I don’t have a book, so I don’t know if all this is all considered later. From what you said, this seems like a really lousy way to explain cycles.

Answer 6

I agree that you should know what an invariant is. Say I'm writing a good old BankAccount. I can say that always and always all transaction amounts in the transaction history will be added up to the account balance. That sounds reasonable. It would be nice if that were true. But during several lines, when I process the transaction, this is not true. Either I update the balance first, or add the transaction to the history and update the balance. For a moment, the invariant is false.

I can imagine a book that wants you to understand that an invariant is something that you always and always always, but sometimes it’s not, and it’s good to know when it’s not, because if you come back or throw it away an exception or give way to concurrency, or something else, when that is not true, your system will be corrupted. It’s a little harder to imagine that your paraphrase is what the authors intended to say. But I think that if I turn my head sideways and squint, I can rephrase it, because “the sum is the sum of the first grades” is always and always, with the exception of the law, while we are busy reading and adding them - maybe this is not so true during this process. It makes sense?

Answer 7

After your update, the author correctly describes how the loop invariant should be “restored” at each iteration of the loop.

I do not understand why this matters. Of course, for any other cycle a similar statement would be true?

Yes, thats true - there is nothing special in this loop (OK, the loop condition has a side effect, but it can be easily rewritten).

But I think that the important fact that the author would like to point out is the following: after the action performed inside the loop, the loop invariant is no longer true. This, of course, is a problem for the invariant, if the subsequent statements do not correct it by taking appropriate action.

Answer 8

In the first example, the variable count is not used for anything other than just increasing for each input cycle. The loop will continue until → returns NULL.

In the second example, the lines must be initialized by the number of lines to write. The cycle will continue until the number of specified lines is indicated.

 while (cin >> x) { ++count; } rows = NROWS; r = 0; while (r != rows) { // write a row of output std::cout << std::endl; ++r; }