Correct For Loop Design

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!

-
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. – umlcat Jan 27 '12 at 3:38
The code snippet at the top of the question implies that they start at zero. – Blrfl Jan 27 '12 at 11:21
If you're in danger of going over the bounds of your datatype you need to set the compiler to give overflow errors. – Pieter B Apr 26 '12 at 8:14

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:

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.

-

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.

-
Pet peave: do NOT use postincrement in this situation, it's semantically the wrong choice. – Joris Timmermans Dec 12 '11 at 14:10
@MadKeithV Yet if you'll notice, all the answers are using postincrement, because that's the idiom inside a for loop in C. Besides which, the compiler should be able to optimize it into a preincrement since the value is just being thrown away. – Izkata Dec 12 '11 at 21:26
@Paul: You understand the problem is that the expansion of the syntax isn't type dependent. And yes, Felix has a "for element in array" function: iter, as well as folds etc. They're implemented with the for loop, see: felix-lang.org/\$/usr/local/lib/felix/felix-latest/lib/std/… – Yttrill Dec 12 '11 at 23:57
@MadKeithV Sorry, I learned C before we knew about correctness and Standards :) – Paul Jan 26 '12 at 13:30
@MadKeithV: How so? In this particular context, i++ and ++i are identical; they both increment i, and the result is discarded. (There are reasons to prefer preincrement in C++ for non-elementary types, neither of which applies here.) – Keith Thompson Feb 26 '12 at 6:37

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; } } }

-
Felix supports break/continue with labels too (you can break an outer loop). The problem is basically that I am writing the tutorial (felix-lang.org/web/tut_13.fdoc) and the code doesn't look clean. It should. Perhaps I need an exclusive loop too but I can't think of a syntax (distinct from the inclusive loop). – Yttrill Dec 12 '11 at 23:50

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?

-
sorry, the "argument" I presented in the last paragraph is supposed to be an argument in favour of an exclusive loop, it basically says that there's always a value one greater than the last valid loop index anyone might use "in practice". I'm trying to decide whether to provide an inclusive loop (current design) or switch to an exclusive loop, or perhaps something else. Ideally a loop would be "for i in sequence do .. done", so would work for any ordered set, not just integer subranges (see Python iterators). C for loop is too powerful to verify easily. – Yttrill Dec 13 '11 at 0:06
@Yttrill: I've edited my answer as an answer for your comment. – Secure Dec 13 '11 at 6:21
Re your edit, YES, I think I am looking at the problem from the wrong direction. The for loops are there because they're more restricted than the rather open-ended C for() loop, which is hard to check for correctness. I wanted something "more obviously correct" but I didn't really get it. [The purpose of Felix: it's a systems and application language designed to replace most C and all C++. I'm an ex-member of C++ committee so I have a good idea what's wrong with C++ :] – Yttrill Dec 14 '11 at 9:58

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).

-
C's for loop does not universally handle all cases with a fixed comparison in the predicate. If you use < you cannot stop a loop which reaches the maximum value of the control variable type (for some types). If you use <= you cannot skip the body of the loop for zero cases. There is therefore no formulation for an arbitrary integral type which works correctly for 0 upto and including maximum value of the type. You need to understand my problem: I am generating code (not hand writing it) for unknown type with unknown bounds. – Yttrill May 12 '12 at 23:59