Design and Implementation of Iterative Loops
by Bradley A. Berg April 22, 2022
Copyright 2022, Bradley Berg. All rights are reserved.
ABSTRACT
The rationale for iterative loop constructs in an experimental
programming language, Gilda, is presented. High performance
algorithms for implementing the constructs are derived. The
algorithms for integer and pointer iterators do not violate
boundary conditions. Floating point iterators avoid rounding
errors as well. The rationale for a construct to prematurely
exit a loop is also given.
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.
I. Iterative Integer Loop
A. Constant Increment
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 contain a reference to 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.
B. Variable Increment
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.
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].
II. Floating Point Iterative Loop
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.
V = From
count = End - From
IF 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.
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.
The loop can be safely terminated using an integral floating point
comparison. Floating point units can count by one and perform an integral
comparison without rounding errors. This lets the same variable 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.
III. Iterating With Pointers
A. Iterating Over Strings
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.
B. Iterating Over Arrays
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.
IV. Exiting a loop
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
UNDO IF condition2
-
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.
V. Sequences
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.
V. Conclusion
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:
* Reassignment of the iterator in integer loops has negligible or no
performance impact. Whether reassignment is left as an option for
the programmer to use or prohibit is up to the language designer.
* Consistent and accurate implementation of floating point loops may
result in a performance loss. Programmers can avoid this by rewriting
loops using integer iteration. Reassignment is not desirable as a
floating point iterator is best implemented using a fixed loop counter.
* Adding constructs that iterate using pointers can eliminate the
need to include unsafe pointer operators in a language.
* Using the Undo statement to exit a loop can simplify some programs.
The Cycle statment has no such utility.
Consider these factors when implementing translators for any language:
* Avoid unecessary overflow when computing integer loop bounds.
* Update the iterator after checking for termination.
* Catch exception conditions from loop computations. These are
generally overflow and zero increments.
* Don't let floating point iterators accumulate errors.
* The number of iterations in a floating point loop needs to be
consistent across different processors.
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.