Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In this Stackoverflow anwer I dimly recall being taught that it's better to use as "wide" a condition as possible to terminate a loop, rather than testing for an exact termination condition.

i.e. use:

while (x < 10) 

rather than

while (x != 10)

however I cannot recall (or find) any formal basis or rationale for this.

Is this actually written down anywhere as best current practise?

share|improve this question
add comment

4 Answers

Edsger Dijkstra made a note about != vs. < in chapter 8 of his "Discipline of Programming", page 56:

Prior to my getting used to these formal developments I would always have used "j < n" as the guard for this repetitive construct, a habit I still have to unlearn, for in case like this, the guard "j != n" is certainly to be preferred. The reason for the preference is twofold. The guard "j != n"allows us to conclude "j = n" upon termination without an appeal to the invariant relation P and thus simplifies the argument about what the whole construct achieves for us compared with the guard "j < n". Much more important, however, is that the guard "j != n" makes termination dependent upon (part of) the invariant relation, viz. "j <= n", and is therefore to be preferred for reasons of robustness. If the addition "j := j + 1" would erroneously increase j too much and would establish "j > n", then the guard "j < n" would give no alarm, while the guard "j != n" would at least prevent proper termination. Even without taking machine malfunctioning into account, this argument seems valid.

I promptly stopped using < in my loop termination conditions after reading this note some 25 years ago.

EDIT This note follows a discussion of a program that finds a maximum of a function f(k) in the range [0..n):

k, j := 0, 1;
do j != n --> if f(k) >= f(j) --> j := j + 1
              [] f(k) <= f(j) --> k, j := j, j + 1 fi od

This unusual notation adopted in his book roughly corresponds to this program:

int k = 0, j = 1;
while (j != n) {
    if (f(k) <= f(j)) k = j;
    j++;
}
share|improve this answer
    
curious - he's making that recommendation for exactly the opposite reason I would. –  Alnitak Apr 16 '12 at 19:07
    
@Alnitak I'm with him on this argument: widest continuation conditions make it for tightest termination conditions, simplifying my reasoning about the loop and its termination. I would much rather see my code hang at the place where I have a logical mistake right away than debug an unintended consequences in unrelated parts of the code. This argument gains even more importance in C and C++, where writing past the end of an array is merely an undefined behavior, not a guaranteed crash. –  dasblinkenlight Apr 16 '12 at 19:19
    
@dasblinkenlicht Can you give us some context about what Dijkstra meant with "this repetitive construct"? Simple for loops? –  scarfridge Apr 16 '12 at 19:29
2  
Sometimes you want your program to carry on, giving, perhaps, less-than-perfect answers as a result of less-than-perfect data. Other times, as here, you want your program to crash the instant something is wrong. Certainly if you are depending on j equaling n after the loop, you need to check it with j == n. If you just need to stop the loop and can't depend on j being n because there's a few extra j++'s in the loop or j is a floating point number, j <= n works better. I think there's a right answer for each case, but each case may have a different right answer. –  RalphChapin Apr 16 '12 at 20:07
1  
I find it odd that he lists, as a reason to prefer !=, the fact that j == n is guaranteed when the loop terminates, but the example algorithm has no use for j or n beyond the end of the loop. Also, this algorithm as stated finds the max of a function over the lower-inclusive range [0..n). The terminating condition is then that j is no longer in that range, which given that j is incremented, means j >= n; thus the continuing condition is logically the inverse, j < n. As much as I respect Dijkstra as a computational theorist, I fundamentally disagree with his argument here. –  KeithS Apr 16 '12 at 20:27
show 3 more comments

The rationale could be, that in the second version in case of some bug (say x is incremented by 3 instead of 1) the loop will never terminate, once x jumped from 9 to 12. The first version will at least stop in all cases where x is incremented at all (though would still fail in many other cases).

share|improve this answer
    
yes, that's the informal reasoning - I was hoping for some sort of authority to back that up. –  Alnitak Apr 16 '12 at 15:00
3  
@Alnitak - for practical purposes the concept has to make sense to you. Referencing an "authority" seems more like an academic need. –  JeffO Apr 16 '12 at 15:16
    
@JeffO yes, it's an academic need to put a decent citation in my answer ;-) –  Alnitak Apr 16 '12 at 15:46
3  
I'm not decent enough? I have 1xGuru badge and 4xEnlightened badges on SE ;) –  thorsten müller Apr 16 '12 at 16:01
    
nah, not decent enough - I have 5x Guru and 27x Enlightened on Stackoverflow and I don't know the answer ;-) –  Alnitak Apr 16 '12 at 19:06
add comment

if you use floating point variables chances are that you will never have x==10 this is due to rounding

for example (if constants are not folded) 0.3!=0.1+0.1+0.1 om most machines

share|improve this answer
    
You may want to include another answer in case the OP is using integers. –  FrustratedWithFormsDesigner Apr 16 '12 at 17:24
    
+1 (back to zero). This is a key point for anyone yet to be burned by floating point arithmetic. –  RalphChapin Apr 16 '12 at 19:59
add comment

Here's a StackOverflow question that illustrates the reasoning perfectly. He had i != bytes_read as the loop condition, but had more than one place inside the loop that incremented i, which created an infinite loop under certain conditions. Using <= makes the infinite loop finite instead. That's all there is to it, nothing so involved that someone's going to write a paper on it.

It also makes it more clear to someone reading the program what values are valid for that variable. i != bytes_read on its own implies that that values greater than bytes_read are valid. You have to read several other lines of code to know that they aren't. This particular example might be blindingly obvious, but it still adds clarity to the code. From a more formal perspective, it relieves you of the need to prove that the other statements further restrict i to be less than bytes_read.

Whether it qualifies as a "best practice" or not really depends on if there's a better way to do it. For example, you should use an iterator to loop through items in a container rather than an integer counter based on the container size. Adding an assert to catch values outside a valid range might be more useful if it's a real possibility.

share|improve this answer
1  
Loop termination is not a universal good: faced with a possibility of an infinite loop vs. a terminating one that skips indexes and leaves uninitialized junk in half of my array, I'll take an infinite loop. Infinite loops are easy to discover and fix, as opposed to writing past the end of the array or leaving parts of the array uninitialized. Languages with array index checking greatly alleviate this problem, but they do not make it disappear. –  dasblinkenlight Apr 16 '12 at 20:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.