Java Reference
In-Depth Information
A possible loop invariant P can be created by making a copy of postcondition R
and replacing the last integer 2 in it by a fresh variable:
invariant P: 9 , 8 , , down to k have been printed
How does it start? Initially, nothing has been printed. If k is set to 10 , then the
invariant implies that
9 , 8 , , down to 10 have been printed
i.e. no numbers have been printed. Therefore, setting k to 10 truthifies P .
When does it stop? Looking at the invariant and the postcondition, we see that
the loop should stop when k is 2 , so it should continue as long as k!=2 .
How does it make progress? By decreasing k .
How does it fix the invariant? By printing the next integer, which is integer k
-1 .
Putting it all together, we get this loop:
// Print 9 , 8 , , down to 2
// { invariant P: 9 , 8 , , down to k have been printed }
for ( int k= 10; k != 2; k= k - 1)
{ System.out.println(k - 1); }
// { R: 9 , 8 , , down to 2 have been printed }
A different invariant, a different loop.
The loop just developed may feel a bit odd: why not start k at 9 , print k , and
stop when k is 1 ? That would work, but it would require a different invariant. A
different invariant P can be created by making a copy of postcondition R and
replacing the last integer 2 in it by k+1 (instead of k ); a self-review exercise in
Sec. 7.5.5 asks you to develop a loop using this invariant.
invariant P: 9 , 8 , , down to k+1 have been printed
7.5.4
A for-loop schema
Earlier, we presented this schema for processing the first n natural numbers:
// Process natural numbers 0..n-1 , for n≥0
int k= 0;
// { invariant: 0..k-1 have been processed }
while (k != n) {
Process k;
k= k + 1;
Lesson
page 7-4
}
// {0..n-1 have been processed }
Search WWH ::

Custom Search