Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.
 


Video