Correct For Loop Design

Question

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!

Answer 1

You forgot to mention wheter your string variables in Felix start with index 0 or 1. Searching for that in the web, its additional job for readers. And affects the way your example is evaluated.

Anyway. Are you sure that:

for(i=0; predicate(i); increment(i))

In C: "The predicate is tested after the increment, but the terminating increment is not universally valid!"

Traslates to this:

i=0
continue:
  body
  increment(i)
  if not predicate(i) goto break
  goto continue
break:

Instead of this:

continue:
  i=0
  if not predicate(i) goto break
  body
  increment(i)
  goto continue
break:

Since your for loop its more specific like pascal, you may consider how should be translated and evaluated in case the index value is equal or lesser to the initial value.

Usually, if the initial value, and final value are the same, the loop is executed once, if the final value is greater that the initial value, the loop is not executed.

Answer 2

In C it would be for (int i = 0 ; i < (len a) ; i++ ) { }. This would not execute any iterations since 0 is not < 0 (i < (len a)).

If you are going to use an unsigned then yes, you need to surround with the condition check.

Does it have a for element in array {} type function?

If it's considered functional there is a way to do with with recursion.

Answer 3

Does Felix support break/continue? Implementing them correctly might affect how you approach things.

My C approach would start thus:

for(int i = 0; i<len(a); i++) { // do stuff }

As you have noted, this breaks when a hits the int limit. A possible answer is to check before the increment, so we avoid increments that overflow, but we need to check before the increment, because if len(a) == 0, we do not want to execute the body. The following solves the problem:

id: for(int i = 0; i<len(a); i++) { // do stuff if(i == len(a) - 1) { break id; } }

, where id is a unique label. However this is inefficient, because the for check is redundant for all iterations except the first. At this step, it's tempting to use a while loop, but note that a C for loop is not exactly equivalent to a while loop, as breaks/continues work differently (wrt. to execution of the increment). The simplest transformation I can think that preserves these semantics is

if( len(a) > 0 ) { id: for(int i = 0; ; i++) { // do stuff if(i == len(a) - 1) { break id; } } }

Answer 4

Your last paragraph doesn't make much sense to me. If you use a signed int in the first place, then you make the assumption that your largest possible upper loop bound is the largest positive signed int value. If you use a larger type for your loop, then there won't be an overflow. If there could be an overflow, then by an upper loop bound larger than the maximum positive signed int value, which invalidates your initial assumption.

Additionally, do not assume that no one will ever do this or that. If you are in doubt for a specific loop, then test for it and explicitly express what you assume here.

assert(UINT_MAX > INT_MAX);

if ((unsigned int)len(a) <= INT_MAX) {
    for (unsigned int i = 0; i < len(a); i++)
}
else {
    Handle an unexpected situation here.
}

EDIT (a bit too long for a comment to your comment):

Maybe you're looking at the problem from the wrong direction? Note that C's for loop isn't exclusive by itself. It is just often used this way because of the 0-based array indexing. Nothing stops you from using it inclusive:

for (i = 0; i <= len(a)-1; i++)

In fact, nearly any expression can be used for the three parts, because it is more syntactic sugar than its own command, so you can as well use it to iterate through a linked list:

for (p = start; p != NULL; p = p->next)

So you could first define what you expect from your for loops? Should they be strictly bound to numerical operations? Then you could as well provide them with "growing" ints that never overflow and are automatically scaled up to bigints, according to the needs. Or you could define that 0-1 is always treated as -1, so you have for i in 0 upto -1 which won't execute at all and saves you the additional check for 0.

What's the intended purpose of your language? Is there really a need for me as a programmer to care about the exact types used in the for loop?

Answer 5

C in fact does not have the same problem. The C for loop does not execute the iteration step before checking the predicate. See section 6.8.5.3 of the ISO C standard, which states this clearly.

The argument about promotion you are referring to is as you say, incorrect, but for a more direct reason: there may be no widening promotion. For example, nothing in the C standard guarantees that there is any type wider than unsigned char (that is, implementations in which all unsigned types are the same width are allowed).