Design and Implementation of Iterative Loops

               by Bradley A. Berg      January 16, 2012

         Copyright 2012, 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 take into account
     boundary conditions.  Floating point iterators consider 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.

All values are signed integers.  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 programmers write
a simple While loop.

     V = From;                 Always initialize the iterator.

     DO WHILE  V <= End:       DO WHILE performing the loop body,
          :
        V += Step;                Increment the iterator.
     -


Using a simple condition to terminate a loop instead of an intrinsic
iteration construct requires that the sign of the increment be statically
known.  This is usually the case, but not always.  Also conditional loops
will fail if maximum or minimum termination values are used.  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.   */


The Gilda code (with pseudo code comments) below can be used to implement
an iterative loop construct with a positive constant increment.  Note the
special case that limits the termination value (t) within the allowable
range of signed integers.  Without the 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, even if the iterator
is reassigned in the loop body.


     V = From;                 Always initialize the iterator.

     IF From <= End:           IF executing the loop at least once,
        t = small;                Smallest negative number (always terminate).

        IF t + Step <= End:        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.
     .  -

          Notes:  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.


If the loop's bounds are expressions, then they need to be evaluated
before the iterator is assigned it's initial value.  The expressions
may contain a reference to the iterator.  In this case they need to
use it's value prior to the Do statement 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 the cases where
the increment is 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
complimenting the operands (exclusive or with -1).  Adjustments are
also made to the computations for the termination value.


     V = From;                      Always initialize the iterator.
     s = sign( Step );               Extend the sign (arithmetic shift right).
     assert  Step;                   ERROR:  The loop increment is zero.

     IF From -- s <= End -- s:      IF executing the loop at least once,
        t = small + s;                 Smallest negative or largest positive.

        IF (t + Step) -- s <= End -- s: IF the terminal value does not underflow,
           t = End - Step + 1 + 2 * s;     Termination value when over 1 loop.
        .

        DO ALWAYS:                     DO over each loop iteration,
             :
        UNDO IF  V -- s => t -- s;     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 due 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
            :
        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 16 bit Unicode character unless it
is declared otherwise.  If a character is extracted from a string
containing more narrow characters (e.g. extracting a 16 bit character
from a string containing 8 bit characters) it 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.



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


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,
       READ  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.
With such languages, translator writers need to carefully implement loops;
providing 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 prohibited 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 to iterate with 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.

   *  Assign the iterator after evaluating the bounds.

   *  Catch exception conditions from loop computations.  These are
      generally overflow and zero increments.

   *  Don't let float point iterators accumulate errors.

   *  The number of iterations in a floating point loop needs to be
      consistent across different processors.


Programmers need to 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.