Correct For Loop Design

cfelixprogramming-languages

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!

Best Answer

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.

Related Topic