About middle-test loops

Ordinary program loops can be cathegorized into the following two cathegories: pre-test loops and post-test loops. For example, in C++ for loops and while loops are pre-test loops, do-while loops are post-test loops. (It isn’t very hard to find out whether a concrete loop construction is pre-test or post-test. If you can define a such loop using this concrete construction which body isn’t invoked at all, then this loop construction must be pre-test. Just try it: for(0;0;0) doSomething(); and while (0) doSomething(); show immediately that for and while constructions are absolutely pre-test.)

These facts are simple and well-known. Why is it interesting? Because newbies can ask weird questions related to this topic. Yesterday I’ve found the following thread on Stack overflow. (For your information, gentle reader, stack overflow is one of my stamping grounds. When I am a big and strong real programmer, I will collect some gold medals.) Here is it: http://stackoverflow.com/questions/1807110/is-it-possible-to-have-a-while-loop-in-c-that-makes-the-check-in-the-middle-of. I like the pure naivety of the question „is it possible to have a while loop in c++ that makes the check in the middle of the loop instead of the beginning or end?”, especially because it isn’t dummy at all. A typical reaction for a question like this is always something like „there is no (and can’t be) language constructs for every possible use case you can imagine”.  (Note: If you are a Perl programmer, you never answer something like that. In Perl, actually we have language constructs for every possible use case. 😉 )

Before we start thinking about the theoretical problem of  middle-test loops by ourself, it is better to make some researches first. The idea of „loop with test in the middle” is a pretty old idea, it was proposed by Dahl in 1972, see the relevant articles on Wikipedia, for example, this: http://en.wikipedia.org/wiki/Control_flow. Dahl invented a new loop construction and he wrote his loop in the following form:

loop
   ...
while condition;
   ...
repeat;

The first remarkable thing, that pre-test loops and post-test loops can be emulated with Dahl’s loop. If the tag ‘loop’ is omitted, we get a pre-test loop. If the tag ‘repeat’ is omitted, we get a post-test loop. If the tag ‘while’ is omitted, we get an infinite loop. This connection between infinite loops and Dahl’s super loop is especially interesting, because, if we use our imagination, Dahl’s loop seem like an infinite loop with a conditional break. (The instruction „break” helps us to leave the current loop in C++. So while is something like a  „conditional break” in this case, because it terminates the loop only when its condition is true.) In C++, we don’t have loop-while-repeat loop, but we can emulate it with an infinite loop and with a conditional break:

for (;;) {
   ...
   if ( !condition ) break;
   ...
}

or

while (true) {
   ...
   if ( !condition ) break;
   ...
 }

Of course there is not a such reason which is in the way of inserting more than one conditional break into this lovely construction. We can do it: 

while (true) {
   ...
   if ( !condition1 ) break;
   ...
   if ( !condition2 ) break;
   ...
   if ( !condition3 ) break;
 }

And frankly, we do it all the time. If you examine main loops of big software projects, you will see that they are infinite loops in the most of cases, and you will find much of conditional breaks in these infinite loops. For example in OpenGL, glutMainLoop() uses an infinite loop and about the same construction.


do {
   ...
   exit if (condition1);
   ...
   exit if(condition2);
   ...
 }

Sad, but it is not so elegant like Dahl’s loop, because we cannot omit the keyword ‘do’ and the main block of the infinite loop, if we want to. That’s why the following notation is more cool than the previous:

do {
   ...
}  while (condition1) {
   ...
}  while (condition2) {
   ...
}

I feel that it is awsome, not just because of cascading while loops. If we omit some parts of it, we can specify all possible C –style conditional loops plus we can specify the infinite loop with my favourite do{} notation. The only problem that it is a bit hard to read. And the other problem that it is something like reinventing the wheel – I’m sure that this theoretical construction is well-known in certain circles.

Advertisements

About vrichard86

I'm Richard and I'm an enthusiastic coder. I want to be better and I think a professional journal is a great self improvement tool. Welcome to my blog, to my hq, to my home on the web!
This entry was posted in Theory and tagged , , , . Bookmark the permalink.