Correct For Loop Design
- by Yttrill
What is the correct design for a for loop?
Felix currently uses
if len a > 0 do
for var i in 0 upto len a - 1 do
println a.[i];
done
done
which is inclusive of the upper bound. This is necessary to support the full range of values of a typical integer type. However the for loop shown does not support zero length arrays, hence the special test, nor will the subtraction of 1 work convincingly if the length of the array is equal to the number of integers.
(I say convincingly because it may be that 0 - 1 = maxval: this is true in C for unsigned int, but are you sure it is true for unsigned char without thinking carefully about integral promotions?)
The actual implementation of the for loop by my compiler does correctly handle 0 but this requires two tests to implement the loop:
continue:
if not (i <= bound) goto break
body
if i == bound goto break
++i
goto continue
break:
Throw in the hand coded zero check in the array example and three tests are needed.
If the loop were exclusive it would handle zero properly, avoiding the special test, but there'd be no way to express the upper bound of an array with maximum size.
Note the C way of doing this:
for(i=0; predicate(i); increment(i))
has the same problem. The predicate is tested after the increment, but the terminating increment is not universally valid!
There is a general argument that a simple exclusive loop is enough: promote the index to a large type to prevent overflow, and assume no one will ever loop to the maximum value of this type.. but I'm not entirely convinced: if you promoted to C's size_t and looped from the second largest value to the largest you'd get an infinite loop!
