Breaking from the middle of a loop (C++)

[Alf P. Steinbach]

Note: this article is cross-posted to [comp.lang.c++] and
[comp.programming].

The subject of how to best express a logical "loop-and-a-half" has
popped up in a number of recent [clc++] threads.

The language, C++, is a bit important because in C++ all code must be
prepared for exceptions at any point, so that in this language the
possibility of missed cleanup due to early exit is not an issue.

Assume helpers

void throwX( char const s[] ) { throw std::runtime_error( s ); }

string commandStringFromUser()
{
using namespace std;
string line;

cout << "Command? ";
if( !getline( cin, line ) ) { throwX( "i/o failure" ); }
return line;
}

bool isValidCommandString( string const& s )
{
return (s.length() == 1 && isValidCommandChar( s[1] ));
}

Then, an example of "loop-and-a-half" expressed with exit in the middle:

// Variant 1, exit in middle.

char validUserCommand()
{
for( ;; )
{
std::string const line = commandStringFromUser();

if( isValidCommandString( line ) )
{
return line[1];
}

giveShortHelpAboutValidCommands();
}
}

Example of expressing the loop with redundant duplication of code:

// Variant 2, unrolled.

char validUserCommand()
{
std::string line;

line = commandStringFromUser();
while( !isValidCommandString( line ) )
{
giveShortHelpAboutValidCommands();
line = commandStringFromUser();
}
return line[1];
}

Example of expressing the loop with side-effect in the condition checking:

// Variant 3, side-effect in continuation condition checking.

char validUserCommand()
{
std::string line;

while( !isValidCommandString( line = commandStringFromUser() ) )
{
giveShortHelpAboutValidCommands();
}
return line[1];
}

It has been argued that the last two forms have a loop invariant whereas
the exit-in-middle lacks one, or more specifically, that its loop
invariant isn't established until halfway through the first iteration.

I think that's a bogus argument, and prefer variant 1, exit-in-middle.


Cheers (looking forward to comments! )

- Alf

 

[Alf P. Steinbach]

* Alf P. Steinbach:

[good article, but with a bug]

Don't know why, but I wrote 1 instead of 0 all the way.

Sorry.

Just assume 1 means 0... ;-)

Cheers,

- Alf

 

[owebeeone]

The subject of how to best express a logical "loop-and-a-half" has
popped up in a number of recent [clc++] threads.

The language, C++, is a bit important because in C++ all code must be
prepared for exceptions at any point, so that in this language the
possibility of missed cleanup due to early exit is not an issue.

....

What about this one ?

char validUserCommand()
{
for( std::string const line = ""; line =
commandStringFromUser(), ! isValidCommandString( line ); )
{
giveShortHelpAboutValidCommands();
}
return line[1];
}

 

[Lars Uffmann]

TBH I have no clue what you were talking about with the "loop invariant".

I often do an exit in the middle to ease code-understanding by avoiding
unnecessary nesting of scopes. Like in your example. The only difference
I make, for I consider it much easier to read the code, is to move the
break / continue / return / exit statement to the indentation level of
the scope that is interrupted. E.g.

int foo()
{
while (condition()) {
// do some stuff
if (somethingWrong())
break;

// do some more stuff
if (somethingRequiresFunctionEnd())
return someReturnCode;

// do even more things
}

return defaultReturnCode; // indented normal, because it's at the end
of the function ("normal" return)
}


However, if you want to to a loop-and-a-half without a break, what about
the extra scope nesting?

char validUserCommand()
{
for (int validInput = 0; !validInput; ) {
std::string const line = commandStringFromUser();

if( isValidCommandString( line ) ) {
validInput = 1;
}
else {
giveShortHelpAboutValidCommands();
}
}
return line[0];
}

 

[shazled]

   // Variant 1, exit in middle.

   char validUserCommand()
   {
       for( ;; )
       {
           std::string const line = commandStringFromUser();

           if( isValidCommandString( line ) )
           {
               return line[1];
           }

           giveShortHelpAboutValidCommands();
        }
    }

I use exit in the middle as suggested by the book "Code Complete". I
find "no repeating code" is easier to maintain. However, if
performance or formal verification is important I believe you need a
loop invariant:

std::string line;
bool valid = false;

do {
line = commandStringFromUser();
valid = isValidCommandString(line);
if (!valid) giveShortHelpAboutValidCommands();

} while(!valid);

return line[0];

Saul

 

[Gene]

Note: this article is cross-posted to [comp.lang.c++] and
[comp.programming].

The subject of how to best express a logical "loop-and-a-half" has
popped up in a number of recent [clc++] threads.

The language, C++, is a bit important because in C++ all code must be
prepared for exceptions at any point, so that in this language the
possibility of missed cleanup due to early exit is not an issue.

Assume helpers

   void throwX( char const s[] ) { throw std::runtime_error( s ); }

   string commandStringFromUser()
   {
       using namespace std;
       string line;

       cout << "Command? ";
       if( !getline( cin, line ) ) { throwX( "i/o failure" ); }
       return line;
   }

   bool isValidCommandString( string const& s )
   {
       return (s.length() == 1 && isValidCommandChar( s[1] ));
   }

Then, an example of "loop-and-a-half" expressed with exit in the middle:

   // Variant 1, exit in middle.

   char validUserCommand()
   {
       for( ;; )
       {
           std::string const line = commandStringFromUser();

           if( isValidCommandString( line ) )
           {
               return line[1];
           }

           giveShortHelpAboutValidCommands();
        }
    }

Example of expressing the loop with redundant duplication of code:

   // Variant 2, unrolled.

   char validUserCommand()
   {
       std::string line;

       line = commandStringFromUser();
       while( !isValidCommandString( line ) )
       {
           giveShortHelpAboutValidCommands();
           line = commandStringFromUser();
       }
       return line[1];
    }

Example of expressing the loop with side-effect in the condition checking:

   // Variant 3, side-effect in continuation condition checking.

   char validUserCommand()
   {
       std::string line;

       while( !isValidCommandString( line = commandStringFromUser() ) )
       {
           giveShortHelpAboutValidCommands();
       }
       return line[1];
    }

It has been argued that the last two forms have a loop invariant whereas
the exit-in-middle lacks one, or more specifically, that its loop
invariant isn't established until halfway through the first iteration.

I think that's a bogus argument, and prefer variant 1, exit-in-middle.

Cheers (looking forward to comments! )

- Alf

Loop invariants can include exit-in-middle if you design weakest
precondition relationships for returns and similar statements that
capture their effects. Roughly speaking, the invariant expression
needs a clause s.t. that the invariant remains true if the loop has
exited with a return value that meets specs.

 

[kwikius]

Note: this article is cross-posted to [comp.lang.c++] and
[comp.programming].

The subject of how to best express a logical "loop-and-a-half" has
popped up in a number of recent [clc++] threads.

The language, C++, is a bit important because in C++ all code must be
prepared for exceptions at any point, so that in this language the
possibility of missed cleanup due to early exit is not an issue.

Assume helpers

   void throwX( char const s[] ) { throw std::runtime_error( s ); }

   string commandStringFromUser()
   {
       using namespace std;
       string line;

       cout << "Command? ";
       if( !getline( cin, line ) ) { throwX( "i/o failure" ); }
       return line;
   }

   bool isValidCommandString( string const& s )
   {
       return (s.length() == 1 && isValidCommandChar( s[1] ));
   }

Then, an example of "loop-and-a-half" expressed with exit in the middle:

   // Variant 1, exit in middle.

   char validUserCommand()
   {
       for( ;; )
       {
           std::string const line = commandStringFromUser();

           if( isValidCommandString( line ) )
           {
               return line[1];
           }

           giveShortHelpAboutValidCommands();
        }
    }

FWIW I feel happiest with the above but switching the order, but am
unsure as to the technicalities:

char validUserCommand()
{
for( ;; ) {
std::string const line =commandStringFromUser();
if( ! isValidCommandString( line ) ) {
giveShortHelpAboutValidCommands();
}
else{
return line[..];
}
}
}

regards
Andy Little

 

[kwikius]

   char validUserCommand()
   {
       for( ;; )
       {
           std::string const line = commandStringFromUser();

           if( isValidCommandString( line ) )
           {
               return line[1];
           }

           giveShortHelpAboutValidCommands();
        }
    }

Actually IMO in this situation it is best to throw an exception at the
point the invalid command is detected.
There is no need for speed on unintelligable command, and is more
robust than relying on manually doing the check :

char validUserCommand()
{
for( ;; ) {
try{
std::string const line
= ValidCommandStringFromUser();
return line[..];
}
catch( InvalidCommandStringFromUser & e){
doShortHelpOnCommands();
continue;
}
}
}

 

[Gianni Mariani]

kwikius wrote:
......

Actually IMO in this situation it is best to throw an exception at the
point the invalid command is detected.
There is no need for speed on unintelligable command, and is more
robust than relying on manually doing the check :

char validUserCommand()
{
for( ;; ) {
try{
std::string const line
= ValidCommandStringFromUser();
return line[..];
}
catch( InvalidCommandStringFromUser & e){
doShortHelpOnCommands();
continue;
}
}
}

NO NO.

It's not easier to read.

It's not more efficient.

Input into the program must be anything and so it's not an "exception"al
thing to detect bad input.

I've tried writing code where exceptions are used more liberally and
they only make sense where the lower levels of code don't usually deal
with the problems - things like memory allocation, or unit test "failures".

IMHO that is..

 

[kwikius]

kwikius wrote:

.....

Actually IMO in this situation it is best to throw an exception at the
point the invalid command is detected.
There is no need for speed on unintelligable command, and is more
robust than relying on manually doing the check :

char validUserCommand()
{
    for( ;; ) {
      try{
          std::string const line
            = ValidCommandStringFromUser();
          return line[..];
      }
      catch( InvalidCommandStringFromUser & e){
          doShortHelpOnCommands();
          continue;
      }
    }
}

NO NO.

YES YES YES

It's not easier to read.

It's not more efficient.

How long will it take the user to figure out why their input is
invalid? Who needs microsecond efficiency here?

Note that the alternative is to manually check the data after its
arrived. Problem is that you have to remember the check. If you
"forget" the check then the function returns invalid data as if
nothing happened.

With the exception approach, if you dont catch then an error will be
transmitted . It may be ugly but it will not be missed. IOW its better
if missed error handling smacks the programmer in the face, not the
user.

Input into the program must be anything and so it's not an "exception"al
thing to detect bad input.

I've tried writing code where exceptions are used more liberally and
they only make sense where the lower levels of code don't usually deal
with the problems

In this case you have asked user for input. If you can't understand
the input you get - don't proceed.

regards
Andy Little

 

[David Tiktin]

Example of expressing the loop with side-effect in the condition
checking:

// Variant 3, side-effect in continuation condition checking.

char validUserCommand()
{
std::string line;

while( !isValidCommandString( line =
commandStringFromUser() ) ) {
giveShortHelpAboutValidCommands();
}
return line[1];
}

It has been argued that the last two forms have a loop invariant
whereas the exit-in-middle lacks one, or more specifically, that
its loop invariant isn't established until halfway through the
first iteration.

I think that's a bogus argument, and prefer variant 1,
exit-in-middle.

That argument *may* be bogus (I can't decide right now, but I do like
loop invariants when I can get them ;-), but why prefer variant 1
over variant 3? 3 seems very idiomatic to me (but I'm primarily a C
programmer). Using the assignment-in-conditional side effect lets
you turn all sorts of potential do loops (or "primed" while loops
with repeated code ala variant 2) into straightforward while loops.

My real argument for 3? The for(; in 1 says to me we're entering
an infinite loop. I see *later* inside the loop that we can leave
when we get a valid string. Not a big deal in this short function.
But in 3, the while condition tells me right away that we're entering
an input/validation loop (while (!isValidCommandString())). Since
that's what we're really doing here, it seems to me to express more
clearly what's actually going on in the code. Assuming you're used
to the assignment-in-conditional side effect idiom (which I am), it's
the variant with the least cruft, or put another way, the one reads
best for me.

Dave

 

[Gianni Mariani]

kwikius wrote:

.....

Actually IMO in this situation it is best to throw an exception at the
point the invalid command is detected.
There is no need for speed on unintelligable command, and is more
robust than relying on manually doing the check :
char validUserCommand()
{
for( ;; ) {
try{
std::string const line
= ValidCommandStringFromUser();
return line[..];
}
catch( InvalidCommandStringFromUser & e){
doShortHelpOnCommands();
continue;
}
}
}

NO NO.

YES YES YES

It's not easier to read.

It's not more efficient.

How long will it take the user to figure out why their input is
invalid? Who needs microsecond efficiency here?

Note that the alternative is to manually check the data after its
arrived. Problem is that you have to remember the check. If you
"forget" the check then the function returns invalid data as if
nothing happened.

With the exception approach, if you dont catch then an error will be
transmitted . It may be ugly but it will not be missed. IOW its better
if missed error handling smacks the programmer in the face, not the
user.

If you take that argument, all return values should be exceptions.

From my experience, C++ exceptions are too inflexible, don't work well
with threads (and most libraries today need to work with threads) and
code that does not use exceptions, is easier to understand. Also, most
compilers/debuggers don't support debugging of exception conditions very
well.

I have yet to a good prolific use of exceptions in an application. The
rule that seems to work for me is that exceptions are "exceptional" and
so should only be used in "exceptional" circumstances.

For example:
matrix a, b;
....
matrix c = a/b;

in this case, b may be a singular matrix and a/b may not result in a
usable value for c. I have no issue with that code throwing an
exception - but - it had better be managed and this is where C++ breaks.
There is no compile time check that it is handled and there should be.

In this case you have asked user for input. If you can't understand
the input you get - don't proceed.

In this case, the code simply asks again, and again if it does not
understand input. Having exceptions handle this makes code less
readable and hence more prone to making errors.

 

[kwikius]

If you take that argument, all return values should be exceptions.

No. This is the whole point. You throw an exception instead of
returning anything. Your return value is useless anyway so you suspend
normal execution before that point. Once your function has returned
its too late. The invalid data has slipped out of your grasp and your
app is already travelling in the exciting and wonderful (well actually
tedious , time consuming) realms of the unknown.

 From my experience, C++ exceptions are too inflexible, don't work well
with threads (and most libraries today need to work with threads) and
code that does not use exceptions, is easier to understand.

Maybe. I have very limited experience, but it seems to me that threads
are a very low level highly chaotic mechanism and my assumption is
they will gradually be replaced by safer higher level concepts, such
as process management (IOW 3rd party arbitrators between processes) .
Currently thread black magic is akin to assembler. In the same way
that there was inertia to stick with assembler rather than moving to
higher level languages, with the same arguments re performance, so I
hope will go threads, but thats wild speculation of course

regards
Andy Little

 

[Daniel T.]

Note: this article is cross-posted to [comp.lang.c++] and
[comp.programming].

The subject of how to best express a logical "loop-and-a-half" has
popped up in a number of recent [clc++] threads.

The language, C++, is a bit important because in C++ all code must be
prepared for exceptions at any point, so that in this language the
possibility of missed cleanup due to early exit is not an issue.

Assume helpers

void throwX( char const s[] ) { throw std::runtime_error( s ); }

string commandStringFromUser()
{
using namespace std;
string line;

cout << "Command? ";
if( !getline( cin, line ) ) { throwX( "i/o failure" ); }
return line;
}

bool isValidCommandString( string const& s )
{
return (s.length() == 1 && isValidCommandChar( s[1] ));
}

Then, an example of "loop-and-a-half" expressed with exit in the middle:

// Variant 1, exit in middle.

char validUserCommand()
{
for( ;; )
{
std::string const line = commandStringFromUser();

if( isValidCommandString( line ) )
{
return line[1];
}

giveShortHelpAboutValidCommands();
}
}

Example of expressing the loop with redundant duplication of code:

// Variant 2, unrolled.

char validUserCommand()
{
std::string line;

line = commandStringFromUser();
while( !isValidCommandString( line ) )
{
giveShortHelpAboutValidCommands();
line = commandStringFromUser();
}
return line[1];
}

Example of expressing the loop with side-effect in the condition checking:

// Variant 3, side-effect in continuation condition checking.

char validUserCommand()
{
std::string line;

while( !isValidCommandString( line = commandStringFromUser() ) )
{
giveShortHelpAboutValidCommands();
}
return line[1];
}

It has been argued that the last two forms have a loop invariant whereas
the exit-in-middle lacks one, or more specifically, that its loop
invariant isn't established until halfway through the first iteration.

I think that's a bogus argument, and prefer variant 1, exit-in-middle.

There is a long history in both C and C++ of a "single-entry, multiple
exit" style of programming, whether the extra exits are return, break,
or sometimes even goto statements.

I personally don't like the style. Yes, I have read the rational from
several authors but that isn't why I have a problem with it. My feelings
about it were born out of the times I have spent debugging other
people's code. People who used such multiple exits almost
indiscriminately. It became a truism for me that when I needed to find a
bug, the first place I would look is inside blocks of code that had
multiple exits.

Of course C++'s exception system has practically canonized the multiple
exit style. Even if I have no wish to program in that style, a library
provider can force it on me so I have to always be prepared... Several
prominent authors in the C++ community have commented on the difficulty
of writing code that is correct in the face of exceptions. It seems to
be quite a big stumbling block.

I tend to favor something like variant 2 above, avoiding both
conditionals with side-effects and premature exits from blocks of code.
I am in such a habit of using that particular variant that my functions
usually have a variable labeled "result" and take on a characteristic:

T func() {
T result = default;
// computation
return result;
}

 

[Logan Shaw]

Example of expressing the loop with side-effect in the condition
checking:

// Variant 3, side-effect in continuation condition checking.

char validUserCommand()
{
std::string line;

while( !isValidCommandString( line =
commandStringFromUser() ) ) {
giveShortHelpAboutValidCommands();
}
return line[1];
}

It has been argued that the last two forms have a loop invariant
whereas the exit-in-middle lacks one, or more specifically, that
its loop invariant isn't established until halfway through the
first iteration.

I think that's a bogus argument, and prefer variant 1,
exit-in-middle.

That argument *may* be bogus (I can't decide right now, but I do like
loop invariants when I can get them ;-), but why prefer variant 1
over variant 3? 3 seems very idiomatic to me (but I'm primarily a C
programmer). Using the assignment-in-conditional side effect lets
you turn all sorts of potential do loops (or "primed" while loops
with repeated code ala variant 2) into straightforward while loops.

Assignment in conditional works well in many cases. However, it starts
to look really ugly when the assignment needs to be 10 lines in order
to do its think. There are a lot of situations where you want a value
assigned to a variable and then you want to test the assigned value as
your loop condition.

But it's not the case in all of those situations that everything can
naturally be expressed as a one-liner that fits well within the conditional
part of the loop. Sometimes the loop test with its assignment side
effects can be trimmed down, perhaps by factoring some stuff out into
a function or two. But this doesn't always help readability.

In a sense, you could say that the general solution to this problem
is to not limit yourself to while loops where the test is an expression;
instead, the test could be a block, and the body a block as well.
That would be sort of a "while BLOCK BLOCK" syntax instead of a
"while (EXPR) BLOCK" syntax. Here's an example of the hypothetical
syntax (with some keywords added for clarity, though it makes it
too comb-syntaxy):

while
condition {
line = commandStringFromUser();
test !isValidCommandString(line);
}
body {
giveShortHelpAboutValidCommands();
}

return line[0];

I'm not so much saying that any language *should* implement this.
I'm really just saying that when code is to be moved out of the loop
body and into the condition, in a language (like most) where the
condition must be an expression, you are introducing additional
constraints the code must meet in order to be in the condition part
of the loop. And modifying code to meet those constraints may
sometimes end up mangling it.

One argument against this whole approach is that probably loop
tests should not be doing work, so they shouldn't be having major
side effects (other than stashing away a value for later use),
and one way to encourage people not to write loop tests that
have side effects is to limit them to using expressions. I see
some real value in that, from a style point of view, but I would
also argue that in many languages, expressions can so easily have
massive side effects that it's a little weird to be suddenly
worrying about that distinction[1].

- Logan


[1] Of course, it's also meaningful to talk about the subset
of a language that people keep to as a matter of style.

 

[Stuart]

TBH I have no clue what you were talking about with the "loop invariant".

Some logical expression, placed at a point within the loop, that is always
true and captures the essential intent of the loop.

It is typically used in establishing the correctness of an algorithm using
proof. The stages of the proof are roughly:

1) Establish that the invariant is true when the loop is first entered and
executed up to the point of the invariant.
2) Establish that the invariant remains true when the loop iterates.
3) Establish that the loop post conditions are true when the loop executes
from the point of the invariant to its exit.
4) Establish that the loop will exit.

 

[Stuart]

It has been argued that the last two forms have a loop invariant whereas
the exit-in-middle lacks one, or more specifically, that its loop
invariant isn't established until halfway through the first iteration.

Not knowing C++ I do not know whether 'loop invariant' has a special
significance in the language. However, in general use (in program proof)
there is no real problem with a loop invariant not being established until
halfway through the code.

What is the 'perceived problem' with it?

In languages like Ada exiting loops at a mid-point are directly supported,
and this is also allowed by the SPARK subset (which, with the associated
SPARK tools, directly addresses program proof).

I think that's a bogus argument, and prefer variant 1, exit-in-middle.

I would agree with you that the argument appears bogus; again I don't know
about C++ - but there are definitely algorithms that are much better
represented using an exit-in-middle.

Regards

 

[Gerhard Fiedler]

Then, an example of "loop-and-a-half" expressed with exit in the middle:

// Variant 1, exit in middle.

char validUserCommand()
{
for( ;; )
{
std::string const line = commandStringFromUser();

if( isValidCommandString( line ) )
{
return line[1];
}

giveShortHelpAboutValidCommands();
}
} [...]
I think that's a bogus argument, and prefer variant 1, exit-in-middle.

There is a long history in both C and C++ of a "single-entry, multiple
exit" style of programming, whether the extra exits are return, break,
or sometimes even goto statements.

I must have missed something, but I didn't see a single "multiple exit"
example presented here...

This loop-and-a-half is not about multiple exit, it is about single exit in
the middle (rather than at the top or at the bottom).

Gerhard

 

[Daniel T.]

Then, an example of "loop-and-a-half" expressed with exit in the middle:

// Variant 1, exit in middle.

char validUserCommand()
{
for( ;; )
{
std::string const line = commandStringFromUser();

if( isValidCommandString( line ) )
{
return line[1];
}

giveShortHelpAboutValidCommands();
}
} [...]
I think that's a bogus argument, and prefer variant 1, exit-in-middle.

There is a long history in both C and C++ of a "single-entry, multiple
exit" style of programming, whether the extra exits are return, break,
or sometimes even goto statements.

I must have missed something, but I didn't see a single "multiple exit"
example presented here...

This loop-and-a-half is not about multiple exit, it is about single exit in
the middle (rather than at the top or at the bottom).

Got me. The for loop is infinite so there is no way to exit from the
function except through the return in the middle. This shows either how
married I am to the notion that there should always be an exit at the
bottom, or it is a good example as to why such code is less clear/less
readable.

I must say, if I saw such code in a real system I would become very
uncomfortable, just as if I saw something like:

for ( int i = rand(); i == 23; i = rand() ) {
// do whatever
}

There is no guarantee that the loop would ever end. (Isn't that was a
loop invariant is for?

 

[Daniel T.]

Some logical expression, placed at a point within the loop, that is always
true and captures the essential intent of the loop.

It is typically used in establishing the correctness of an algorithm using
proof. The stages of the proof are roughly:

1) Establish that the invariant is true when the loop is first entered and
executed up to the point of the invariant.
2) Establish that the invariant remains true when the loop iterates.
3) Establish that the loop post conditions are true when the loop executes
from the point of the invariant to its exit.
4) Establish that the loop will exit.

It now seems to me that all the examples initially presented fail when
it comes to item 4.