Loop Invariants and Class Invariants

A loop is easy to write and surprisingly hard to get right. Most loop bugs are not visible in the loop header. They hide in the way a few variables change from one pass to the next. This article works through two small array-processing methods written with while loops. Each one is short enough to trace by hand, which makes them good practice for a skill that matters throughout programming: stating what the loop has done so far and checking that it still matches what you expect.

The first method computes the sum of every element in an integer array. It uses two variables besides the array itself. The variable total holds the running sum, and the variable i is the index of the element being processed. The loop continues as long as i is less than the array length, so every valid index is visited exactly once.

The sum starts total at 0. Starting from 0 is the identity for addition: adding elements to 0 produces exactly the sum of those elements. Each pass through the body adds one element to total, and the index then advances to the next position. Because the condition is checked before every pass, the loop stops on its own once i reaches the length of the array.

Read the diagram as a sequence of states. Every arrow is one pass through the body, and every box is the record of what the loop has done up to that moment. The idea of recording state between passes is what the rest of this article depends on.

Hand tracing means recording the value of every variable before each check of the loop condition, then applying the loop body once per pass. The table of states is the record of what the loop has actually done. The worked example below uses a three-element array, [3, 7, 2], so you can follow the procedure on concrete numbers.

Two details in the trace are worth checking every time. First, the condition is evaluated before each pass, including the check that would begin a pass at index 3. That check is false, which is why the loop stops and does not run a fourth pass. Second, each check must use the value of i from the end of the previous pass, never a value remembered from earlier. In the table, the i before check column always copies the i after pass column from the row above it.

Inside the sum loop body there are three statements. The addition uses A[i] while i still refers to the current element. Only afterward does i = i + 1 move the index forward. The order is part of the logic, not a stylistic choice. Order inside a loop body is one of the most common places where a result diverges from expectation.

The return statement in the sum method sits after the loop, not inside it. The method therefore returns only once the condition i < A.length has become false, which means every index has been processed. Returning from inside the loop would stop the traversal after the first element.

Consider what happens if the return is moved into the body. On the array [3, 7, 2], the first pass would add 3 and then return 3. The method would look like it works on that first element, but it would silently ignore the other two. This kind of bug is easy to miss because the code runs without error.

The second method finds the largest value in an array. It keeps a candidate for the maximum, called max, and compares each remaining element against it. Whenever an element is larger than the current max, that element becomes the new max. When the traversal ends, max holds the largest value seen.

This version differs from the sum loop in its starting values. The method initializes max to A[0], the first element, and starts the index at 1 so that the first element is not compared with itself. The starting value of max must be an element that is actually in the array, because the loop only ever replaces max with an element it has seen.

Use the hand-tracing procedure on an array you have not seen yet. Before each condition check, write down total or max, i, and the condition result. Then answer the questions below.