how to get out of double for loops?

[Ersek, Laszlo]

You keep making puns like that and you're going to be in a heap of
trouble.

Care to explain what "use a stake" means here? I tried to look it up,
with not much success.

Thanks,
lacos

 

[Ben Bacarisse]

Care to explain what "use a stake" means here? I tried to look it up,
with not much success.

It's a pun. Eric is playing on the oft quoted phrase "C does not use
a stack". Hence Lawrence's "heap" pun in reply.

Eric's did register on my humour meter but Lawrence is talking a load
of mallocs.

 

[James Harris]

In a language (or programming style) without break and goto one can
make strong arguments about the behaviour of loops.  After

  while (E) { S; }

one can assert that !E is true (there may not be an "after" of
course).

(As you know) that's not much of a deduction. So what advantage can
similar reasoning be expected to give in imperative programming? (Not
functional programming which is another matter.) I've seen people
write about advantages of certain control structures but I've never
come across an explanation of the principles, if there are any.

For example the most general imperative loop construct would be of the
form

for (; {
<code>
if (c1) break;
<more code>
if (c2) break;
<even more code>
if (c3) break;
<etc>
}

Top and bottom decision loops as well as arbitrary mid decisions can
all be expressed using such a control structure. Is there something
about that form which inhibits reasoning?

 Banning continue and non-terminal return statements also
simplifies the reasoning about the interaction of S and E.

I'm glad to hear it but in what way or ways does *continue* work
against reasoning?

I guess you are referring to mid-routine return statements. They can
return no value or a value of the wrong type. Any other problems with
them from the point of view of reasoning?


James

 

[Ersek, Laszlo]

It's a pun. Eric is playing on the oft quoted phrase "C does not use
a stack". Hence Lawrence's "heap" pun in reply.

Eric's did register on my humour meter but Lawrence is talking a load
of mallocs.

Okay, thanks I got the "heap of trouble" (even without understanding
the stack/stake pun) and also your malloc()'s/bollocks pun. I even
considered shortly what some witty response to Lawrence's pun might be,
with "stack" in it. I was completely oblivious to the fact that the
original pun ran with "stack" already. "stake" doesn't rhyme with
"stack" when pronounced, and I didn't notice the eye rhyme(?).

http://en.wikipedia.org/wiki/Eye_rhyme

Thanks,
lacos

 

[Ben Bacarisse]

(As you know) that's not much of a deduction. So what advantage can
similar reasoning be expected to give in imperative programming?

I was simplifying and obviously went too far. You also have a loop
invariant, P, and it is this along with !E that forces the
post-condition, R, that the code intends to set up. On its own P
says very little but P /\ !E => R.

(Not
functional programming which is another matter.) I've seen people
write about advantages of certain control structures but I've never
come across an explanation of the principles, if there are any.

For example the most general imperative loop construct would be of the
form

for (; {
<code>
if (c1) break;
<more code>
if (c2) break;
<even more code>
if (c3) break;
<etc>
}

Top and bottom decision loops as well as arbitrary mid decisions can
all be expressed using such a control structure. Is there something
about that form which inhibits reasoning?

That one is not too bad because it is structured. It means

do {
<code>
if (!c1) {
<more code>
if (!c2) {
<even more code>
if (!c3) {
<etc>
}
}
}
} while (!c1 && !c2 && !c3);

(barring side-effects in the ci). The breaks imply a nesting that
complicates the reasoning but that is not the fault of the break. If
the loop has to be this complex because that is what is needed then
the break form is just a neater way to write it.

The problems come when break is used in far less structured ways. One
could argue that the problem is then not the break but the fact that
the code is a mess, and I'd probably go along with that.
Well-organised uses of break don't cause a lot of trouble.

I'm glad to hear it but in what way or ways does *continue* work
against reasoning?

This is likely to come out all hand-waving... When continue is used
in messy ways, for example:

while (E) {
if (C1) {
S1;
if (C2) {
S2;
continue;
}
}
S3;
}

you end up having to roll up lots of steps in the reasoning so as to
reason about the whole loop body. You can't use the usual rules about
if statements because the continue ties the inner if to the semantics
of the whole loop body.

I guess you are referring to mid-routine return statements. They can
return no value or a value of the wrong type.

Yes, by 2non-terminal" I meant mid-function return statements but I
don't follow what you mean here.

Any other problems with
them from the point of view of reasoning?

They have the same effect as on the continue example except the linkage
is to the enclosing function.

 

[Stefan Ram]

That one is not too bad because it is structured.

... if you make the assumption that <code> has one entry and
one exit, but it was not excluded that <code> might contain
even more break statements.

Once the style guidelines allows use of break statements,
one must inspect the - possibly long - section <code> for
more break statements.

When the style guidelines exclude this, one can trust the
eye, which sees the indentation in

do
{ <code>
if( !c1 )
{ ... }}
while( ... );

 

[Ben Bacarisse]

... if you make the assumption that <code> has one entry and
one exit, but it was not excluded that <code> might contain
even more break statements.

I think it was by context, but I see your point. If some says "what
about this pattern of break usage?" I think it is reasonable to assume
they mean these are all the break statements.

I agree that in practise one might have to check, but that's true even
if coding style excludes break.

<snip>

 

[lawrence.jones]

Eric's did register on my humour meter but Lawrence is talking a load
of mallocs.

Hey, let's not cast aspersions.

 

[Al Pech]

This is how I'd do it.....

----------------

flag = 0;
while(i<H && !flag){
while(j<H && !flag){
if(x[j] == 1)
flag = 1;
j++;
}
i++;
}

// i-1 and j-1 where the value looked for is...
----------------











===========================================================

(e-mail address removed) (Richard Harter) writes:

I am not good with smileys.  I have tried, recently, to inject a few
in to my posts but I am not entirely happy with the results :-(

As a result, I probably come over as serious and ponderous about
things that I take with a pinch of salt.  Sorry if that is the case.

To keep things light and topical, here is another single loop version
to ponder the merits of:

    for (i = 0; i < H*H && x[i/H][i%H] != 1; i++);

I rather like it

And well you should.

You could make it more efficient (if I have the syntax right)
with

    int  **y;  /* use appropriate type */

    for (i = 0, y = (int **)x; i <HH && y != 1; i++);
    j = i%H; i /= H;

There is no end of good solutions.  

Richard Harter, [email protected]://home.tiac.net/~cri,http://www.varinoma.com
It's not much to ask of the universe that it be fair;
it's not much to ask but it just doesn't happen.

 

[Eric Sosman]

Hey, let's not cast aspersions.

... nor make it an automatic response to dish out this
type of static.

 

[Flash Gordon]

... nor make it an automatic response to dish out this
type of static.

if we could break out of this loop it would be good, but we can't while
the coding standards forbid it.

 

[James Harris]

  ... if you make the assumption that <code> has one entry and
  one exit, but it was not excluded that <code> might contain
  even more break statements.

  Once the style guidelines allows use of break statements,
  one must inspect the - possibly long - section <code> for
  more break statements.

In languages which support exceptions they generally break the
apparent flow of control by jumping forward to a handler. There seems
to be an analog between exceptions, break and return. All jump forward
to a well-defined point. So I'm not sure there is much to be gained by
outlawing embedded break statements. In fact ISTM sensible and natural
to add the ability to break out of more than one level of control
structure (the OP's initial query). For example, if a for loop was
named "row" something like

break row

would break out of as many nested structures as necessary to continue
after the "row" loop.

I'm not suggesting a change to C, merely stating an opinion on a
programming language design issue.

James

 

[David Bolt]

Oi! Can't you take an 'int?

I think a pointer might help us understand the long and short of it.


Regards,
David Bolt

 

[Richard Bos]

"Any references to Goto (an obscure Japanese admiral) are obscene,
unfit for your eyes and anyway don't mean what you think they do -
delete them" (notes on the Algol manual from a university course in
the 1970s).

Well, yeah. And where is Algol now? Just over a hundred light years
away, and long may it stay there.

Richard

 

[Richard Bos]

I think a pointer might help us understand the long and short of it.

IMO, this entire argument is null and void.

Richard

 

[Eric Sosman]

IMO, this entire argument is null and void.

... serving only to block progress, to limit the scope
of endeavor, to foul the nest. Participants are dys-functional
and deserve to be switched.

 

[Phil Carmody]

... serving only to block progress, to limit the scope
of endeavor, to foul the nest. Participants are dys-functional
and deserve to be switched.

In that case we should shift onto another topic.

As if...

Phil

 

[Luca Forlizzi]

Ben Bacarisse <[email protected]> writes:

      int *y;
      for (i = 0, y = x[0]; i < H*H && y != 1; i++);
      j = i%H; i /= H;
but that brings up another c.l.c FAP[1]: is indexing y from y[H]
onwards really permitted?
[1] Frequently Argued Point.
Isn't it generally agreed that the Standard expects 'y = x[0]' not to
(have to) work, but 'y = (int*)x' or 'y = (int*)&x' to work?  Is
there any real contention on what the Standard expects on this
particular point (even though there is debate about how well it
says it)?

I am surprised you think anything like this could be "generally
agreed"

Well, I did say "generally agreed", not "universally agreed."

To be more specific, isn't it essentially universally agreed that
using '(T*)&x' will get an array for the entire region
occupied by x, even if x is a multi-dimensional array?  That
assertion seems pretty uncontroversial.

I toyed with using a pointer that unambiguously referred to the whole
array (I'd have gone for (void *)x) but I did not want to invite the
debate by including a cast that some might think is not needed.  I
failed of course, since here we are again.

What, you're trying to say that there is debate about whether
or not a debate exists?  In comp.lang.c?  Preposterous!

While I knew that the "Standard expects 'y = x[0]' not to (have to)
work", I didn't know
that "it essentially universally agreed that using '(T*)&x' will get
an array for the entire region occupied by x, even if x is a multi-
dimensional array". I don't have anything against it and it is not my
intention to reopen a debate on a F.A.P. but, just to improve my
knowledge on the Standard, I would like to know from what part(s) of
it that fact can be deduced. I confess that I don't understand much of
what the standard says about pointer conversions.
Could you please explain or give links to previous discussions about
this?

thanks a lot!

 

[Tim Rentsch]

Tim Rentsch <[email protected]> writes:

<snip>
int *y;
for (i = 0, y = x[0]; i < H*H && y != 1; i++);
j = i%H; i /= H;

but that brings up another c.l.c FAP[1]: is indexing y from y[H]
onwards really permitted?

[1] Frequently Argued Point.

Isn't it generally agreed that the Standard expects 'y = x[0]' not to
(have to) work, but 'y = (int*)x' or 'y = (int*)&x' to work? Is
there any real contention on what the Standard expects on this
particular point (even though there is debate about how well it
says it)?

I am surprised you think anything like this could be "generally
agreed"

Well, I did say "generally agreed", not "universally agreed."

To be more specific, isn't it essentially universally agreed that
using '(T*)&x' will get an array for the entire region
occupied by x, even if x is a multi-dimensional array? That
assertion seems pretty uncontroversial.

I toyed with using a pointer that unambiguously referred to the whole
array (I'd have gone for (void *)x) but I did not want to invite the
debate by including a cast that some might think is not needed. I
failed of course, since here we are again.

What, you're trying to say that there is debate about whether
or not a debate exists? In comp.lang.c? Preposterous!

While I knew that the "Standard expects 'y = x[0]' not to (have to)
work", I didn't know
that "it essentially universally agreed that using '(T*)&x' will get
an array for the entire region occupied by x, even if x is a multi-
dimensional array". I don't have anything against it and it is not my
intention to reopen a debate on a F.A.P. but, just to improve my
knowledge on the Standard, I would like to know from what part(s) of
it that fact can be deduced. I confess that I don't understand much of
what the standard says about pointer conversions.
Could you please explain or give links to previous discussions about
this?

I don't have any links to previous discussions (perhaps a
search engine could provide some), but here is my explanation
(or rationalization, depending on one's point of view).

An array identifier just by itself is converted to a pointer to
the array's first element -- 'a == &a[0]', and not just equal but
definitionally equal, as I believe most people see it. The array
name 'a' must be usable to access the entire array of 'a', and
therefore so must '&a[0]' (or so the reasoning goes). Similar
reasoning (not identical reasoning, but similar) applies to the
address of any particular element of 'a' -- 'a+i == &a', again
not just equal but definitionally equal (again AIBMPSI). So for
a two-dimensional array 'x[M][N]', 'x[1] == &x[1][0]' can access
all of "the array x[1]" but not (definedly) access any of "the
array x[2]". (Notice the difference between English and C. In
English 'x[1]' means "the array x[1]", whereas in C 'x[1]' means
"a pointer to the first element of the array x[1]". But it's
still true that that pointer can access all of "the array x[1]".)
So, reasoning by analogy with the one-dimensional array case, we
conclude that using an N-1 dimensional index, and no address
operator, is the same as using an N dimensional index _with_ an
address operator, which must be able to access the whole
one-dimensional array (with the first N-1 dimensions fixed,
varying just the last index). That assumption, or conclusion if
you will, is wired very deeply in the minds of all long term
C programmers.

The question of what happens with the higher dimensions proceeds
by analogy with what simpler array indexing does. Suppose
again we have two-dimensional array 'x[M][N]'. We expect the
pointer value of 'x', which is '&x[0]', to be able to access
each of the elements in 'x', because that's how array indexing
works. The elements of the array 'x' are themselves arrays,
but that doesn't change the reasoning about what can be accessed;
since 'x' is an array, using 'x' (or '&x[0]' which is the same
thing) ought to be able to access all of the array 'x'. Again
this is just how array indexing works in C.

Now we get to the $64 question -- what happens when such a
pointer value is converted to another type? As far as I know,
and I've never seen any text in any official document that
contradicts this, converting a pointer from one type to
another allows access to exactly the same region of storage
as the original pointer (assuming that there are no alignment
problems, and not counting any "fractional objects" that
might result when converting to a type whose size does not
evenly divide the amount of storage accessible using the
pre-conversion pointer type). This rule is not spelled out
in the Standard, and least not clearly enough so I can
identify any text that does. Despite that, as a practical
matter I think everyone takes it as a working assumption,
otherwise how could things like memcpy() or qsort() work?
If you believe this rule, you believe that doing '(T*)x' or
'(T*)&x[0]' allow access to all the storage occupied by 'x'.

Finally, the last case, '&x', is the easiest. We know for at
least one case, namely, '(char*)&x', that this pointer conversion
must allow access to all the bytes that make up "the entire array
x". (Again 'x' is a two-dimensional array 'x[M][N]', but the
same conclusion holds for arrays of higher dimensions.) Since
'(char*)&x' must be able to access all of "the array x", the most
obvious and sensible conclusion, absent specific text in the
Standard to the contrary, is that '(T*)&x' also must be able to
access all memory occupied by x (again taking into account
alignment and "fractional object" issues, but those aren't an
issue when we are converting to the sub-most element type of the
array whose address we are converting).

To restate what I said at the beginning, most of this isn't stated
explicitly in the Standard. But it is the reasoning that I use, and
I think that reasoning rests only on specific statements made in the
Standard and on common working assumptions held (at least for
practical purposes) by every C programmer I know or whose views on
the subject I'm aware of.