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

[kwikius]

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

Actually its an interesting example, but from a non-technical
viewpoint.

I remember once at school lunchtime there was one particular kid that
said to some master in charge,when we were presented with some stuff,
"Sir I can't eat this".

The master replied. "Right boy! For that remark, you will stay here
until your plate is clean!".

The rest of the mealtime was somewhat unpleasant. The kid was trying
and was literally pewking into his bowl, but of course having given
the ultimatum the master couldnt lose face by backing down...

Point being, IMO there should be provided a way for the user to
decline to continue in this situation.

regards
Andy Little

 

[Daniel T.]

Actually its an interesting example, but from a non-technical
viewpoint.

I remember once at school lunchtime there was one particular kid that
said to some master in charge,when we were presented with some stuff,
"Sir I can't eat this".

The master replied. "Right boy! For that remark, you will stay here
until your plate is clean!".

The rest of the mealtime was somewhat unpleasant. The kid was trying
and was literally pewking into his bowl, but of course having given
the ultimatum the master couldnt lose face by backing down...

Quite a story. Sounds almost like something Dickins or Monty Python
would write.

Point being, IMO there should be provided a way for the user to
decline to continue in this situation.

Which would require that the loop not be potentially infinite and all my
comments about multiple exits come back into play!

 

[Gerhard Fiedler]

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

There is no guarantee that the loop would ever end.

Whether a loop has a guarantee of ending has nothing to do with where the
condition is, but with the type of condition. In any system that interacts
with the real world, there are usually loops that don't have a guarantee of
ending. The main event loop in a typical Windows application is such a loop
-- there is no guarantee that the event that ends the application ever
comes.

Whether that even sets a flag that then gets checked at the top or bottom
or whether it breaks out of the loop in the middle is a different question.

(Isn't that was a loop invariant is for?

I don't think so. The loop above certainly has a loop invariant
(considering that the "do whatever" code doesn't change i), but there is no
guarantee that it ever ends.

Gerhard

 

[James Kanze]

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.

It never was really an issue. Dijkstra raised the issue over
thirty years ago. The issues were intensely discussed at the
time, and it quickly became clear that Dijkstra was right, and
that spaghetti code couldn't be made correct. I find it simply
amazing that over 30 years later, there are still people ready
to argue that it's better just to hack away, on simple gut
feeling, rather than to use established techniques of
guaranteeing readability and correction.

Note that there are different degrees of "spaghetti". While
there are strong reasons to prefer establishing the loop
invariant at the top, having one exit in the middle is still
orders of magnitude better than having several exits.

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();
}
}

char
getValidatedCommand()
{
std::string line( getUserInput() ) ;
while ( ! isValidCommandString( line ) ) {
giveShortHelpAboutValidCommands();
line = getUserInput() ;
}
return line[ 0 ] ;
}

(I've changed the names to reflect standard conventions as
well---functions are verbs.)

Short, simple, to the point. I don't see why anything more
complicated is needed.

Easy to prove correct. If I'm in the loop, I don't have a valid
command.

[...]

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.

Why do you think it's bogus? Why do you think we should ignore
loop invariants? This is an honest question. Your first
example does not violate the single entry/single exit principle,
which is the most important. But some sort of reasoning
involving loop invariants is necessary if you want to be sure
the code is correct. (I think we can agree that calling
"getUserInput()" makes progress to loop termination, the other
criticall "proof" necessary for correction.) I'm not saying
that such reasoning is necessarily impossible, but it seems to
me much simpler if we establish the condition up front (and that
the post-condition of the function---that we've read a valid
line---is also the termination condition of the loop.

FWIW: at one point (some 15 years ago), I did consider the idea
that the two versions are "equivalent"---that your version is a
transformation (in the Chomskian sense) of my version, much
like, say, "The dog is seen by me" is a transformation of "I see
the dog". And of course, it is possible to prove that if the
underlying sentence is correct, then the transformation is as
well. But that's exactly how I'd go about analysing your
version: prove that it is functionally equivalent to mine, then
prove that mine works. Which means extra work in understanding
yours.

 

[James Kanze]

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.

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.

IMHO, there are two issues involved, and Alf very carefully
crafted his example to address just one. His code does NOT
break the single entry/single exit mold. The only difference is
that his exit point is in the middle of the loop---he has, in
fact, two sets of invariants: a weak set (no valid command has
been entered) which holds for the first half of the loop, and a
stronger set (an invalid command has been entered) for the
second half. If I understand Alf correctly, this is the issue
he wants to address---he's not trying to argue that you can
write just anything, or leave the loop in any old way.

Note that there is a radical difference between the two. I find
it notably simpler to reason about a loop if there is only one
invariant involved---I explained this in my response to Alf.
But there is still a single exit. Multiple exits from a loop
cause problems not only with reasoning about the code, but make
it almost impossible to read.

[...]

Of course C++'s exception system has practically canonized the
multiple exit style.

Throw is just a goto, all dressed up. There's a sense in
which that's true, but...

So are exit(), or abort(), or assert( cond ), when the assertion
fails. There are cases where you want to say: things have
gotten so bad that I can't reason about it anymore. All bets
are off. If the program only does one thing, then abort or exit
with an error message is fully appropriate. But a lot of
programs (including almost all I write), do do more than one
thing---just because all bets are off for one client request
doesn't mean that I can crash the server, and not handle other,
more reasonable requests. Exceptions are a good mechanism for
aborting some sub-processing.

Obviously, they shouldn't be abused. Throwing an exception for
something that should be handled by the algorithm (and thus
making the exception path part of the algorithm's execution
path) is just another way of creating spaghetti, and very
quickly leads to unreadable (and unverifiable) code.

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;
}

That's easily the best idiom when you have a reasonable default.
Alf's example didn't.

 

[James Kanze]

Daniel T. wrote:

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?

Not only. To prove that the loop would never end, you have to
prove progress. "rand()", in this case, doesn't guarantee
progress. And your loop above definitely has a loop invariant:
i != 23.

Alf's code has a loop invariant: a valid command has not yet
been entered. It also has progress. (In a way. Formally, you
can't guarantee that the user will ever enter a valid command,
and depending on the application, you might want to also manage
a retry count, or something. But such issues would only detract
from the issue Alf wants to discuss---I'm sure that such
simplification here is intentional.)

The only problem with Alf's loop is that the latter part of the
loop requires a stronger invariant. You don't want to call
giveShortHelpAboutValidCommands() unless the user has actually
tried to enter a command. So when reasoning about the loop, you
have to deal with two different invariants, a weak invariant in
the first half of the loop (no valid command has been entered)
and a strong invariant in the latter half (the user has entered
an invalid command).

Note that the first invariant can be reformulated as "the user
has not entered a command OR the user has entered an invalid
command". This is a characteristic of the loop and a half---the
weak invariant at the top must be an OR with the strong
invariant as one of its terms.

One could argue from a program maintenance point of view, as
well. It's only a coïncidence that the "action" for both of the
or'ed terms is identical, and that as the program evolves, this
identity is not guaranteed to be maintained. (Note too that in
my version of the code, there was no identity. The
"initialization" created a new string object, where as the
"update" assigned to an existing string object.)

This comes back to my Chomskian transformation, again---for the
transformation to be valid, it is essential that the action be
identical in both cases.

 

[James Kanze]

"Alf P. Steinbach" <[email protected]> wrote in

p> message

<snip examples>

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?

It's not a loop invariant if it isn't established for the entire
loop.

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

For example?

I think Alf's example was very carefully crafted.
Fundamentally, the abstract form of the loop construct is:

initialization() ;
while ( condition() ) {
action() ;
update() ;
}

The loop invariants are not guaranteed until initialization()
has finished, and cease to be guaranteed if condition() is
false. Up to that point, everything is logically simple and
easy to reason about.

The loop and a half question revolves entirely around the case
where "initialization()" and "update()" involve identical,
non-trivial code. If I understand Alf correctly, the only thing
he's arguing is that in such cases, rewriting the loop as:

while ( true ) {
initialization_update() ;
if ( condition() ) break ;
action() ;
}

is to be preferred. I disagree. (But I would not reject such
code in code review---as long as there is a single exit from the
loop.)

 

[Stuart]

It's not a loop invariant if it isn't established for the entire
loop.

This does not sound like my understanding of a 'loop invariant'. I believe
a 'loop invariant' is only required to be true at the point at which it
appears - indeed it is usually awkward to do useful sequential computations
within a loop without temporarily invalidating the 'loop invariant'. The
requirement is that the net effect of all the computations keep the 'loop
invariant' true.

For example?

I think Alf's example was very carefully crafted.
Fundamentally, the abstract form of the loop construct is:

initialization() ;
while ( condition() ) {
action() ;
update() ;
}

The loop invariants are not guaranteed until initialization()
has finished, and cease to be guaranteed if condition() is
false. Up to that point, everything is logically simple and
easy to reason about.

This sounds even less like loop invariants as I have used them in program
proofs.

The post-conditions of initialization() and condition() being true, together
with any actions within the loop up to the loop invariant, would normally
provide the hypotheses that you use to establish that the loop invariant
will be true if and when the loop is entered.

The loop invariant and condition() being true, together with the actions of
the loop, provide the hypotheses you can use to establish that the loop
invariant remains true for each iteration of the loop.

The loop invariant and condition() being false, together with any actions
within the loop from the loop invariant to the loop condition evaluation,
provide the hypotheses you can use to establish the post-conditions of the
loop - and subsequently use in proving the remainder of the code.

The loop and a half question revolves entirely around the case
where "initialization()" and "update()" involve identical,
non-trivial code. If I understand Alf correctly, the only thing
he's arguing is that in such cases, rewriting the loop as:

while ( true ) {
initialization_update() ;
if ( condition() ) break ;
action() ;
}

is to be preferred. I disagree. (But I would not reject such
code in code review---as long as there is a single exit from the
loop.)

Of course you are entitled to your view, I tend to agree with Alf that there
are cases when placing the break in the middle is a preferable solution -
c'est la vie!

Broadly I would agree that having a single exit point is usually desirable;
but my experience is that simple arbitrary rules should not be dogmatically
applied. If I came across such a case in a review I would certainly take a
keen interest in the code and would want to be convinced that the designer
did it as a result of careful and reasoned design rather than sloppy
thinking.

 

[Clive D. W. Feather]

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.

You mean like in Algol, where the syntax is:

WHILE
sequence-returning-Boolean
DO
sequence-returning-void
OD

A sequence is an arbitrary sequence of commands and expressions, ending
with one that returns the appropriate type.

Or you could hack it in BCPL:

WHILE VALOF
$(
arbitrary sequence of commands
RESULTIS expression
$)
DO
$(
arbitrary sequence of commands
$)

 

[lawrence.jones]

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.

In the past, I've proposed an upward-compatible extension to the C
do-while syntax to provide that more general facility:

do /stmt/ while ( /expr/ ) /stmt/

For (a trivial) example:

do {
c = getchar();
} while (c != EOF) {
putchar(c);
}

When the second stmt is a null statement, you get the current do-while
syntax.

-Larry Jones

I wonder what's on TV now. -- Calvin

 

[Logan Shaw]

You mean like in Algol, where the syntax is:

WHILE
sequence-returning-Boolean
DO
sequence-returning-void
OD

A sequence is an arbitrary sequence of commands and expressions, ending
with one that returns the appropriate type.

Or you could hack it in BCPL:

WHILE VALOF
$(
arbitrary sequence of commands
RESULTIS expression
$)
DO
$(
arbitrary sequence of commands
$)

Interesting. Sadly, I do not really know either BCPL or Algol,
but I was thinking of how you could hack it in Perl, and the
method seems to be extremely similar to the BCPL method:

while ( do {
# sequence of statements, the last of which has
# its value become the value of the do{} block.
} )
{
# sequence of statements
}

The do{} syntax in Perl seems to be almost exactly like the
VALOF/RESULTIS syntax in BCPL. This might not be entirely
a coincidence.

- Logan

 

[Clive D. W. Feather]

Interesting. Sadly, I do not really know either BCPL or Algol,
but I was thinking of how you could hack it in Perl, and the
method seems to be extremely similar to the BCPL method:

while ( do {
# sequence of statements, the last of which has
# its value become the value of the do{} block.
} )
{
# sequence of statements
}

Actually, that sounds more like the Algol syntax.

The do{} syntax in Perl seems to be almost exactly like the
VALOF/RESULTIS syntax in BCPL.

In BCPL, you could put a RESULTIS anywhere in the block and it would
exit at that point (thus:
code
IF condition RESULTIS v1;
more code
RESULTIS v2
) just like you can a "return v" in C.

 

[Lars Uffmann]

In any system that interacts
with the real world, there are usually loops that don't have a guarantee of
ending.

Somehow, that made me think of this "loop" when you approach someone on
the sidewalk, and both people try to make way by stepping to the same
side, then both recognize this isn't working at the same moment, and
move to the other side.

There's no guarantee this loop will ever end, but so far it always has
The notion of an infinite loop of this is funny though - given that
both people have the exact same ideas to get out of it at the very same
time, have exactly the same stamina, and whatever else

OTOH of course, if you keep going forward while trying to make way,
you'll eventually bump into each other, which might encourage an end of
the loop... Or a passionate kiss, if the other person is of the other
gender and pretty

Felt like sharing my associations *gg*

Lars

 

[Gerhard Fiedler]

Somehow, that made me think of this "loop" when you approach someone on
the sidewalk, and both people try to make way by stepping to the same
side, then both recognize this isn't working at the same moment, and
move to the other side.

Differently from that "loop", there are applications or services that are
based on loops that are supposed to never end.

Gerhard

 

[John Brawley]

Differently from that "loop", there are applications or services that are
based on loops that are supposed to never end.
Gerhard

Mine does.
It calculates ever-adjusting/vibrating points in a spherical 3D space.
Stops only when the user manually terminates the program.
I'd agree such uses are rare, though.

 

[Gerhard Fiedler]

Mine does.
It calculates ever-adjusting/vibrating points in a spherical 3D space.
Stops only when the user manually terminates the program.
I'd agree such uses are rare, though.

Not so rare. Most embedded systems have somewhere such a never-ending loop.
Most services on a normal system have such a loop. Most GUI applications
have such a loop -- it's a perfectly normal condition for, say, a browser
or a word processor to be opened and then just stay open until the user
manually terminates it. The only exception are command line applications.
So to me it seems that applications without a (potentially) never ending
loop are the exception rather than the rule.

Gerhard

 

[Jerry Coffin]

[ ... ]

Not so rare. Most embedded systems have somewhere such a never-ending loop.
Most services on a normal system have such a loop. Most GUI applications
have such a loop -- it's a perfectly normal condition for, say, a browser
or a word processor to be opened and then just stay open until the user
manually terminates it. The only exception are command line applications.

This is not really true. Just for example, in Windows the standard event
loop looks something like this:

while (GetMessage(&msg, NULL, 0, 0))
{
if (!TranslateMDISysAccel(MdiClient, &msg))
if (!TranslateAccelerator(msg.hwnd, AccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}

The standard event loop for classic MacOS was in Pascal so I won't quote
it in its entirety here, but it's of the form "repeat ... until gDone;"

For OS/X, the usual event loop is hidden in the core foundation. Looking
at the source for CF-lite, we find CFRunLoopRun, which looks like this:

void CFRunLoopRun(void) {
SInt32 result;
do {
result = CFRunLoopRunSpecific(CFRunLoopGetCurrent(),
kCFRunLoopDefaultMode, 1.0e10, false);
} while (kCFRunLoopRunStopped != result &&
kCFRunLoopRunFinished != result);
}

In short, I'd say the event loops for at least a fair amount of GUI code
does have explicit exit conditions.

I could go on about some of your other claims, but you get the idea --
at best, the statements you've made have more exceptions than you're
claiming. It is true that some code really does use infinite loops from
which exits are never expected -- but such code does not seem to be
nearly as common as you're attempting to imply.

 

[Gerhard Fiedler]

Pretty much all embedded systems have somewhere a really never-ending loop.

So do most services on "normal" PC or server type systems. (How "normal"
these are, given that there probably are many more embedded systems around,
is another question

I should have repeated properly the context here: it was about loops that
are /guaranteed/ to exit. A few messages back, Daniel T. wrote:

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

To which I responded:

:> Whether a loop has a guarantee of ending has nothing to do with where
:> the condition is, but with the type of condition. In any system that
:> interacts with the real world, there are usually loops that don't have
:> a guarantee of ending.

The rest of my comments kind of assumed this context.

I still stand by this

This is not really true. Just for example, in Windows the standard event
loop looks something like this:

while (GetMessage(&msg, NULL, 0, 0))
{
if (!TranslateMDISysAccel(MdiClient, &msg))
if (!TranslateAccelerator(msg.hwnd, AccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}

In short, I'd say the event loops for at least a fair amount of GUI code
does have explicit exit conditions.

Yes, but no guarantee of the loop ever ending in most cases, as it depends
on user input.

I could go on about some of your other claims,

Please do so.

It is true that some code really does use infinite loops from which exits
are never expected -- but such code does not seem to be nearly as common
as you're attempting to imply.

And if you do, please try to come up with real numbers (or at least
estimates) of systems in use or applications running of each kind. I think
you'll find that for every PC out there you can probably find more than a
few embedded systems with an explicit never ending loop somewhere in the
program. And for every GUI app (with a loop that can end but is not
guaranteed to end) you find running on a typical PC type system there are
probably a few services running on that PC with a loop that's designed not
to end.

Gerhard