Jump to content

Loop-and-a-half

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by BarbarianAtTheGates (talk | contribs) at 18:43, 4 December 2018 (Add more refererences: one book and one CS paper.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Loop-and-a-half is a computer science term for a control flow construct where a loop is exited in the middle, instead of at the beginning or at the end. This kind of logic is needed for example when processing an unknown number of data items until a certain condition becomes true indicating that there are no more items to process. Usually the exit condition has to do with the data items, for example looking for a particular item called the sentinel which indicates the end of the items.

Writing a loop-and-a-half in a simplistic manner leads to code duplication which is a problem for software maintenance and hard to understand logic which again is a burden on software maintenance.

In the below examples we read data items from a file stream and test against a known sentinel value.

item = read()
while item is not sentinel:
   process(item)
   item = read()

The fetching of the next item is duplicated, and the two instances of it are separated by the potentially long processing for the data item. This leads into brittle and error-prone code.

The basic solution is to use a loop that looks like an infinite loop but is not, because in case of the sentinel we exit the loop:

while true:
   item = read()
   if item is sentinel:
       break
   process(item)

The 'half' refers to the fact that only part of the last loop iteration is performed [1][2][3]. Further solutions variants include fetching the next item and immediately testing for the sentinel (in C):

while ((item = read()) != sentinel) {
   process(item);
}

or using a pseudo-infinite do-while loop which is equivalent with the above pseudo-infinite while loop:

do {
   item = read();
   if (item == sentinel) {
       break;
   }
   process(item);
} while (true);

Some purists of structured programming object to leaving loops in the middle, but following that path means that the state of whether to stay in the loop or continue processing has to be maintained separately, again leading into brittle code.

References

  1. ^ Donald Knuth (quoting Edsger_W._Dijkstra) (1974). "Structured Programming With GOTO Statements".
  2. ^ Steve McConnell (1993). "Code Complete".
  3. ^ Owen Astrachan (1998). "Loop Patterns".