Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

# Asymmetric Bounds, Part 2: Overrun Is Hard to Avoid

June 14, 2012

Some programming languages allow programmers to say explicitly what range an integer variable is allowed to take on. So, for example, if you want to be able to define a type that represents the ordinal number of a month, you might do so in such a language (which we'll make up for the purpose of this article) by writing something like

```
type month = 1..12;
```

Such a declaration might define `month` as another name for a type that encompasses the values from 1 through 12, inclusive. One might then be able to write

```
var m: month;
```

and be confident that the value of `m` will always be in the inclusive range from 1 through 12.

Such a language might let you iterate over the months by writing something like

```
for m: month { /* … */ }
```

Each time through the loop, `m` would take on a different value in its range.

This neat iteration scheme runs into trouble as soon as we want to switch from a `for` statement to a more general `while` statement:

```
m = 1;
while (m <= 12) {
// …
m = m + 1;
}
```

This example has a self-contradictory condition in its `while` statement: If the type of `m` is such that its value is always in the range `1..12`, then the comparison `m <= 12` will always succeed. Putting it another way, the last trip through this loop will cause `m` to take on an invalid value.

Apparently, then, in our imaginary language, we must write such a loop along these lines:

```
m = 1;
while (true) {
// …
if (m == 12) break;
m = m + 1;
}
```

This technique ensures that `m` will never take on an invalid value. However, it also ensures that the loop will always execute at least once (because the test for loop termination comes after the computation represented by the comment), which in turn is difficult to square with the possibility that the range might be empty.

This difficulty is more than just theoretical. If types correspond to ranges in our hypothetical language, we must figure out the properties of the type that corresponds to an empty range. In particular, if such a type does not encompass any values at all, we have the curious situation of a type that makes it impossible ever to have a variable of that type. Moreover, such a type would be appropriate to represent the range of indices for an empty array, so the type's behavior would have more than passing interest.

It seems, then, that there are at least two reasons why it might be useful to permit variables to take on values outside their nominal range:

• It is easier to define iteration over a range if it is possible for a variable to stray outside its nominal range at the end of the last trip through a loop;
• If a type corresponds to an empty range — that is, a range with no values at all — it is impossible to have variables of that type unless those variables have out-of-range values. The reason, of course, is that all values are out of range.

These theoretical-looking considerations have the practical implication that it is useful to allow a variable's value to stray outside its specific bounds — at least under the right conditions. Next week, I'll talk about how to allow variables to stray in such a way while still making it possible to check whether a variable is in bounds.

### 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.