Design and Implementation of Iterative Loops
by Bradley A. Berg August 17, 2024
Copyright 2024, Bradley Berg. All rights are reserved.
Most programming languages include iterative loop constructs. In this paper a rationale is established for the loop constructs used in an experimental language called Gilda. The language was devised to explore several new concepts as they apply to writing commercial quality software. Alternative semantics for loop constructs and their implementation in translators are considered. The design goals are to establish loop constructs that are easy to use in programs, provide high performance, and consistent results.
DO V = From to End [by Step]
Note: Throughout this paper the iteration variable (V)
will be referred to as the iterator.
Integer iterative loops first initialize the iterator to the value, From. Then the loop is performed zero or more times as the iterator is incremented before performing the next loop. Looping stops when the next iteration value would exceed the End value.
Upon exit the iterator contains the initial value or it's value in the last loop executed. Some languages (e.g. the C for loop) leave the iterator's value with the terminal value plus the increment. This also happens when iteration is programmed using a simple While loop. Note that all values are signed integers.
V = From; Always initialize the iterator.
DO while V <= End: DO while performing the loop body,
:
V += Step; Increment the iterator.
-
Terminating a loop using a simple condition instead of an intrinsic iteration construct also requires that the sign of the increment be known. This is usually the case, but not always. Also conditional loops will fail if the termination values are near the maximum or minimum integer values. For example, the following loop written in C will cause an infinite loop.
char i; // An 8 bit signed integer.
for ( i = 125; i <= 127; i++ ) {} // Wraps from 127 to -128.
Iterative loops with a positive constant increment in Gilda use the following algorithm. Note the special case that limits the termination value (t) within the allowable range of signed integers.
Without this check the termination value could be lower than the smallest negative integer allowed (e.g. an 8 bit iterator where End= -126 and Step = 4). In this case the smallest negative integer is used to force the loop to exit after one iteration.
V = From; Always initialize the iterator.
IF V <= End: IF executing the loop at least once,
t = small; Smallest negative integer (does 1 loop).
IF End > t + Step: IF the terminal value does not underflow,
t = End - Step + 1; Termination value when over 1 loop.
.
DO always: DO over each loop iteration,
<Loop body>
UNDO IF V >= t; UNDO IF at the terminal value.
V += Step; Increment the iterator.
. -
Note: The constant, small, is the smallest negative integer.
A zero increment causes a compilation error.
Similar code is used for negative increments.
Arithmetic is done over integers the width of the iterator.
Example: DO I = 77 to 100 by 5 where I is a byte
V = 77; Always initialize the iterator.
IF 77 <= 100: IF executing the loop at least once,
t = -128; Smallest negative integer (does 1 loop).
IF 100 >= -128 + 5: IF the terminal value does not underflow,
t = 100 - 5 + 1; Termination value when over 1 loop.
.
DO always: DO over each loop iteration,
<Loop body>
UNDO IF V >= 96; UNDO IF at the terminal value.
V += 5; Increment the iterator.
. -
Here is similar logic to use when the Step is a negative constant.
V = From; Always initialize the iterator.
IF V >= End: IF executing the loop at least once,
t = small - 1; Wrap to the largest positive integer.
IF End <= t + Step: IF the terminal value does not underflow,
t = End - Step - 1; Termination value when over 1 loop.
.
DO always: DO over each loop iteration,
<Loop body>
UNDO IF V <= t; UNDO IF at the terminal value.
V += Step; Increment the iterator.
. -
If the loop's bounds are expressions, they may use the iterator. For this reason the expressions need to be evaluated before the assigning the initial iterator value. This way the value prior to the Do statement is used and not the inital value.
If the increment is a variable and it's sign can not be determined statically then the loop computations need to consider cases where the increment could be either positive or negative. The following code can be used to implement both cases without introducing additional branches. Instead in the case of a negative increment the inequality is reversed by complementing the operands (exclusive-or with -1). Adjustments are also made to the computations for the termination value.
assert Step fault; The loop increment is zero.
V = From; Always initialize the iterator.
s = sign( Step ); Extend the sign (arithmetic shift right).
IF V -- s <= End -- s: IF executing the loop at least once,
t = small; Smallest negative number.
IF End -- s >= &IF the terminal value does not underflow,
((t -- s) + Step) -- s
t = (End - Step + 1) -- s; Termination value when over 1 loop.
.
DO always: DO over each loop iteration,
<Loop body>
UNDO IF V -- s >= t; UNDO IF at the terminal value.
V += Step; Increment the iterator.
. -
Notes: Arithmetic is done over integers the width of the iterator.
The -- operator is an exclusive or.
The Sign function returns 0 for positive arguments and
-1 for negative arguments.
Using these algorithms, the programmer can reassign the iterator within the loop and the loop will still terminate properly. Some languages may prohibit this citing performance or program clarity issues. However, there is usually no performance penalty when this is done in a scalar loop.
The Step needs to be checked that it is non-zero to avoid an infinite loop. If it is known to be a constant by the compiler it can issue an error message. Otherwise a run time check will be needed.
If the increment is a variable, there may be a small performance penalty. The alternative implementation computes the number of iterations first and then terminates when the count decrements to zero. This implementation precludes the possibility of reassigning the iterator as the loop is executed a fixed number of times. Some processors include an instruction to optimally perform a decrement and branch.
Contemporary processor architectures and compilers preclude the performance benefit for iterating a fixed number of times. Processors now use branch prediction and execute multiple instructions concurrently. Compilers can usually schedule the additional logical operations needed to implement the algorithm for variable increments. Rarely is there now a performance degradation for allowing the iteration variable to be reassigned.
Reassigning the iterator does preclude parallel loop execution. Fortran (commonly used on parallel execution machines) prohibits reassignment. Programmers writing code intended for parallel execution are aware of this and simply need to avoid reassignment.
Reassigning the iterator also makes it a little harder to read code. A program maintainer has to examine the loop for possible iterator modifications to understand the loop operation. It is much simpler to just look at the top line to understand the loop constraints. For this reason programmers may want to avoid reassignment even if the language allows it. Pascal and the Gilda language do not allow the iterator to be modified to support guarded commands [Dijkstra].
DO V = From to End [by Step]
Floating point iteration may have unexpected results when determining the number of iterations and errors may accumulate in the iterator. The implementation described here emphasizes correctness over performance. Programmers can still write code for floating point iterators to achieve alternative implementations with higher performance or consistant results using other constructs.
Using a floating point inequality to terminate a loop may iterate a different number of times on various processors or even with different translators on the same processor. To avoid using a floating point comparison to terminate the loop, the number of loop iterations must be computed before each loop. The loop is executed a fixed number of times; precluding reassignment of the iterator.
assert Step fault; The loop increment is zero.
V = From
count = End - From
IF count = 0.0 or sign( count ) = sign( Step )
count = integer( count / Step )
loop = 0.0
DO always
<Loop body>
UNDO IF loop => count
loop += 1.0
V = From + loop * Step
. -
Note: The Integer function truncates the fractional part
of a floating point value.
The first test checks to see if any loops are to be performed. The test is made before the division. A small difference in the upper and lower bounds may be reduced to zero by the division. If this was to happen the loop would be executed once; which may be wrong. By comparing the signs of the difference to the increment, the loop will be skipped when it should.
As with integer loops the Step needs to be checked so that it is non-zero to avoid a division by zero. If it is known to be a constant by the compiler it can issue an error message. Otherwise a run time check will be needed.
If the loop is executed at least once, the number of loop iterations less one is determined next. Machines with different floating point representations could iterate a different number of times. With the widespread adoption of IEEE-754 floating point arithmetic [IEEE], this is less problematic these days.
Even so, programmers need to consider rounding issues when performing any floating point operations. If in the context of a program it is known that the increment evenly divides the difference of the upper and lower bounds, the programmer should add half the increment to the end bound. This can not by done by the compiler as it can not tell if the division is intended to be even.
From = K; K is an integer value. End = From + .5 * K Step = .0001 DO V = From to End + Step / 2 by Step
Loop computations are performed using 64 bit double precision floating point arithmetic. A sufficiently large count can be accurately computed. A double precision IEEE-754 floating point value can hold a 53 bit integer. If the count exceeds the maximum integer that can be accurately represented, an exception should be thrown. Of course, a 64 bit integer loop counter can also be used if it yields a performance advantage for a particular processor.
Floating point units can count by one and perform an integer comparison without rounding errors. The loop can be safely terminated using an integral floating point comparison. This lets the same variable to be used as a loop counter and to determine loop termination.
Another source of rounding error in loops is from the accumulation of addition errors each iteration. The total possible accumulated error is the number of iterations times the amount of error in each addition. To accurately set the iteration variable the increment is multiplied by a floating point loop counter.
Cross compilers run on one type of processor an generate code to run on another. Floating point computations may differ between the processors. To account for this floating point operations, including loop computations need to be performed at execution time. This way rounding will be performed consistantly throughout the program.
DO C in String [with Index]
Strings are frequently scanned in programs. Using an index to access each character is generally slow as the address of the character needs to be re-based each iteration. Programmers often use pointers to speed up the scan. When using a pointer to scan a string, a mechanism is needed to increment or decrement the iteration pointer.
Some languages allow unbounded operations on pointers. This is a common source of programming errors. Also, if the string is empty (has no characters) a pointer initialized to the string buffer will reference meaningless data.
Since strings are scanned so frequently in programs, a simple string iteration construct is provided. Each loop the iterator contains a character in the string from the first to the last. More complex constructs were considered such as a reverse scan. After examining a sizable code base, the one construct was found to be sufficient.
The iterator's type defaults to a byte unless it is declared otherwise. With a wider iterator the character is zero extended. If no loop iterations are run (the string is empty) the iterator is unchanged.
The loop generally would be implemented in a translator using a pointer. Since it is not visible in the program, problems with dangling pointers and buffer overruns are avoided. This saves a pointer declaration as well.
The optional With clause declares an integer index set to the position of the character in the string. It is initialized to zero so that when the string is empty the index will be zero after exiting the loop.
DO @P in Array [ subscript ] [to End] [by -1]
Another common use for pointers is to quickly iterate over an array. Using a pointer avoids having to use an index to access an array. The notation for a pointer reference is also simpler and cleaner than an array index [Lomet]. This loop construct is introduced to keep the pointer bounded. Otherwise a mechanism would be needed to bump up the pointer; which could overrun the array bounds. Buffer overruns can be exploited to thwart computer security [McGraw].
Unless explicitly declared the pointer is implicitly declared with the same type as the array. This allows the pointer declaration to be eliminated.
The increment is limited to plus or minus one so that only adjacent elements are scanned. Since this construct is included simply to avoid array indexing, it is limited to the most common cases. Higher dimensioned arrays still need to resort to traditional indexing.
Similarly, the subscript in the statement is limited to iterating over the rightmost dimension in multidimensional arrays. Note that these elements are stored in adjacent memory locations. To use this construct programs need to be written so that the inner loop processes the rightmost column.
DO ... UNDO [IF condition] -
The constructs used in a language can impact program complexity. Software metrics can be used to compare alternative language constructs. In the following examples constructs used to branch out of a loop are examined. In the first, the UNDO command is used conditionally transfer control past the end of the loop.
DO while condition1 <Code segment A> UNDO IF condition2 <Code segment B> -
The same code needed to implement this loop without an UNDO command is:
SET Flag True
DO while condition1 and Flag = True
<Code segment A>
IF condition2
SET Flag False
ELSE
<Code segment B>
- .
The cyclomatic complexity [McCabe] of both segments is 3. However there is a performance and reliability advantage to using the UNDO command. This can be determined using Halstead's measures of the number of operators, operands, unique operators, and unique operands. These are indicators of the effort needed to write a program.
In the first example the number of unique operators in increased by one (the addition of the UNDO command to the language). In the second example the number of unique operators is increased by one (the introduction of the Flag variable) and the total number of operations is increased by four (SET Flag True; AND Flag = True; SET Flag False; and ELSE).
The performance advantage results from not having to manipulate the flag. Program reliability is due to the simpler code. Introducing a flag to control the flow of execution is particularly error prone. The data space and code space are being made unnecessarily interdependent.
An operation similar to the UNDO is the CYCLE command. It conditionally branches to the top of a loop.
DO while condition1
<Code segment A>
CYCLE IF condition2
<Code segment B>
-
The equivalent code to implement the loop without the CYCLE command is:
DO while condition1
<Code segment A>
IF not condition2
<Code segment B>
- .
As before the Cyclomatic complexity of both examples is three. However, there is no performance advantage and the readability is also not enhanced. In the first example the number of unique operators is increased by one (the CYCLE command) over the second. There is no advantage to using the CYCLE command. It would only make the language more complex with no benefit to the programmer.
A sequential iterator produces a series of values by repeatedly calling an iteration method. Sequences are supported in a variety of programming languages; each with different semantics. In some cases sequences are treated as data objects that can be copied, have multiple references and can be stored in a data structure. Various operators such as suspend and resume are also declared.
The Gilda language supports sequencing that is comparatively simple. More complex semantics push a data management burdon on the programmer that may not be obvious. Since a sequence represents control state, treating it as a first class data object introduces control coupling. There may be subtle interactions with other language features such as exceptions. Depending on the implementation there may also be performance degradation that is not explicit. In any form of iteration performance matters to some users.
A sequence method contains multiple return points called continuations. The next time it is invoked control resumes after the continuation with the local state preserved from the previous call. A sequence method can optionally take arguments, but always returns a single value.
sequence File.Line: Read lines from a text file. entry Path string :Input the Path of a text file. exit Line string :Return each line in the file. OPEN`in File <> Path; Open the input file. DO until File`End: DO over each line in the file, INPUT Line; Read the next line. YIELD; Return the line; Resume here next call. - return; The final call does not return a line.
To use the sequence the programmer makes repeated calls. This can be done with either explicit calls or with a loop construct. In either case a local variable is implicitly declared that contains the state of the sequence. It preserves the sequence state between calls.
When explicitly retrieving values from a sequence the value must be known to exist. Otherwise a loop construct must be used. In order to know that there is a next element in a sequence it needs to be invoked and an element may or may not be returned. Due to this uncertain result a passive test for the end of a sequence can not be performed. In practice the length of the sequence is often known such as when iterating over a container with a known size.
DO Line from File.Line( Path ): Loop over an iterator. PRINT Line - YIELD E from C with It; Explicitly begin a non-empty sequence. YIELD E from It; Explicitly get the next element. YIELD end It; Explicitly end a sequence.
Since it is a local variable the iterator is deallocated in the same method where it is declared. This also means it is allocated on the stack; making it inherently thread safe.
Some sequence implementations require that the iterator be stored on the heap. That is, local variables in the sequence that are normally stack allocated are instead heap allocated. This introduces memory managment overhead that leads to more complex semantics that the programmer needs to be aware of. The stack allocation scheme has simple semantics that manage sequence state lexically and not a dynamic variable.
Remarkably, many popular languages have poorly conceived loop constructs. In such languages, translator writers need to carefully implement loops and provide error detection. It is not uncommon for errors in translators to persist, resulting in aberant program behavior.
These observations may be helpful when designing a programming language:
Consider these factors when implementing translators for any language:
Programmers should be aware of the limitations of the loop constructs they are using. Simply assuming a loop construct works as it appears to be intended can lead to errors. Programmers need to do boundary condition analysis on loops, particularly with constructs that can generate overflow by definition. Testing for boundary conditions is also needed as translators may not implement them properly.
Bibliography
1. Newey, Malcolm C. and Waite, William M. "The Robust Implementation of
Sequence-Controlled Iteration", Software Practice and Experience, Vol. 15,
July 1985, pp. 655 - 668.
2. Dijkstra, E. W. "A Discipline of Programming". Prentice-Hall,
Englewood Cliffs, N.J. 1976.
3. IEEE Computer Society (1985), IEEE Standard for Binary Floating-Point
Arithmetic, IEEE Std 754-1985.
4. Lomet, David B. "Making Pointers Safe in System Programming Languages",
IEEE Transactions on Software Engineering, Vol. SE-11, No. 1, January
1985 pp. 87-96.
5. McGraw, Gary and Viega, John "Make your software behave: Learning the
basics of buffer overflows". IBM web publication, March 1, 2000.
www-106.ibm.com/developerworks/security/library/s-overflows/?dwzone=security
6. Halstead, Maurice H. "Elements of Software Science", North Holland, 1977.
7. McCabe, Thomas J. "A Complexity Measure", IEEE Transactions on
Software Engineering, December 1976, pp. 308-320.
8. Flynn, Michael J. "Directions and Issues in Architecture and Language",
IEEE Computer, October 1980, pp. 5 - 22.