Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

There's one important use case for Dijkstra's alternative (c), that is, an interval closed at both ends. That is when your set has a maximum element and you want to be able to express an interval including the maximum. This is, of course, important in any programming language whose basic integer types have a bounded range. For instance, the following loop in C never halts:

    for(uint8_t i = 0; i < 256; i++) { ... }
What's even worse, the following loop has undefined behavior because signed integer overflow is not defined:

    for(int8_t i = 0; i < 128; i++) { ... }


In fact, there's no way to make a C for loop run 256 times using only an 8-bit counter, because there aren't enough states. Looping N times requires N+1 evaluations of the termination condition, and with only 256 states of the index variable you can't have more than 255 iterations.

You can do it with a do { } while loop, which only needs N evaluations of the termination condition for N iterations.


This is arguably a limitation of C-style for loops.

For example, Python:

   for i in range(0, 256):
Rust:

   for i in 0..256 {
and many other languages have similar things.

Proper ranges also mean that the compiler never needs to do complicated reasoning that may depend on signed integer overflow having undefined behavior in order to prove that the loop has a finite number of iterations or that `i` doesn't wrap around.


Yes, I considered mentioning Rust as a more modern example. But even in Rust, ranges such as `0..max+1` are awkward enough that a closed range syntax was added to the language. With a range like `0u8..=255u8` you can also ensure that your induction variable can directly be passed to things expecting a u8 without a cast that might hide an accidental overflow.


These would be peculiarities of the C programming language, not issues of typed integers or of expression ranges. Other, actually-strictly-typed languages will complain that 256 doesn't fit in a byte, or if 256 is a larger sized integer, that automatic comparisons between differently sized integer types is not allowed.


Yes, but my point was that the solution is to use a closed range instead; in this case, use `i <= 255` as the loop condition. Another solution, of course, is to widen the type of your induction variable.


But that doesn't work here either -- 255 + 1 = 0, and 0 <= 255, so you still loop forever.


I expect most counting for loops are one of two types: 'count from A to B inclusive' and 'count N numbers starting from M'.

We commonly have syntax for the first, or sometimes some variant of it designed to avoid the `-1' in the common case, at the cost of complicating some other cases. It's also common to have some rather over-general iterating mechanism called "for" that covers both, or tries to.

But I don't think I've ever seen anything special for the second, for some reason. And the iteration counter and the loop value could have different types - so you could count 128 int8_t values if you wanted. Though in most cases you'd just use it as a replacement for "for(i=m;i<m+n;++i) {do stuff with i}" or "(for i=0;i<n;++i) {do stuff with m+i}".

(One possible exception: the ancient 1980s computer I used as a boy had two syntaxes for saving blocks of memory. You could enter the range as "A B" (save from A to B inclusive), or as "M+N" (save N bytes starting from M).)


I don't quite understand what you're saying. If you change the code to

    for(uint8_t i = 0; i <= 255; i++) { ... }
then it still doesn't halt.


You're right, of course. Apparently my brain doesn't work well today.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: