A Simple Invariant

October 24, 2012

Last week, I said that I would discuss how to use class invariants and data-structure audits to make software more reliable. I'll start with invariants.

An invariant is a claim about a program that we expect to be true at specific points during the program's execution. With each invariant comes the benefit that code can assume that the invariant is true, and the responsibility that code must never cause the invariant to become false at any point at which it is expected to be true.

Programmers often use invariants without realizing it. For example, consider this comment

// At this point, the vector v is sorted.

If the comment is correct, it is describing an invariant: Every time control passes through the comment, the elements of `v` are in sequence. Accordingly, the invariant's benefit is that, for example, it is safe to use a binary search on `v`. The invariant's responsibility is that code that changes the value of `v`'s elements must then put those elements back in sequence before the next time the program reaches this comment.

For example, if we execute a statement such as

```
v.push_back(n);
```

we have probably broken the invariant (unless `n` happens to have a value that keeps `v` in order). Accordingly, we have the responsibility of putting `v` back into order before the next point in the program at which the invariant is expected to be true.

One way of fulfilling this responsibility is to sort `v` after we've inserted `n`:

```
sort(v.begin(), v.end());
```

Once we have done so, `v`'s is once again in order, so the invariant is valid. Of course, sorting can take a while, but this approach might sense if we were putting many new elements into `v` instead of just one. The first call to `push_back` makes the invariant false, but once we're done appending elements to `v`, calling `sort` makes the invariant true again.

Another way to fulfill our responsibility is not to append `n` to `v`, but rather to insert `n` into `v` at a point that maintains `v`'s ordering. When we do this insertion, we can take advantage of the invariant. For example, we might write code such as

```               v.insert(upper_bound(v.begin(), v.end(), n), n);
```

The call to `upper_bound` does a binary search in `v` (i.e., in the range starting at `v.begin()` and ending just before `v.end()`). It returns an iterator that refers to the first element that is strictly greater than `n`, or an off-the-end iterator if no such element exists. The call to `insert` places a copy of `n` immediately before the position to which the result of `upper_bound` refers. In effect, the call to `insert` inserts a copy of `n` at the last position in `v` at which it is possible to do so while preserving `v`'s sequence. We note in passing that if we had called `lower_bound` instead of `upper_bound`, `v`'s sequence would still be preserved, and the copy of `n` would have been inserted at the first position at which it was possible to do so. These two positions are usually identical, but not if `v` contains multiple elements with values equal to `n`.

These examples are typical of how programmers can use invariants to help think about their programs. The main idea is to ensure that the invariant is true whenever it is supposed to be true, and we can do that either by causing it to be true (by calling `sort`) or by arranging that it never becomes false (by using `upper_bound` and `insert`). Next week, I'll talk about how we can use invariants such as this one to make our programs more reliable.

More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>