Loop-and-a-half: Difference between revisions
m Linkify loop. |
More correct explanation for the 'half'; note that Knuth was quoting Dijkstra; linkify Knuth and Dijkstra. |
||
Line 13: | Line 13: | ||
</source> |
</source> |
||
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: |
|||
<source lang="python"> |
<source lang="python"> |
||
Line 25: | Line 25: | ||
</source> |
</source> |
||
The 'half' refers to the fact that only part of the last loop iteration is performed <ref>{{cite web|url=http://www.kohala.com/start/papers.others/knuth.dec74.html|title=Structured Programming With GOTO Statements|author=[[Donald Knuth]] (quoting [[Edsger_W._Dijkstra]])}}</ref>. |
|||
Further solutions variants include fetching the next item and immediately testing for the sentinel (in [[C_(programming_language)|C]]): |
|||
<source lang="c"> |
<source lang="c"> |
Revision as of 18:31, 4 December 2018
The topic of this article may not meet Wikipedia's general notability guideline. (December 2018) |
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]. 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.