nested while - how to go to the beginning of the first while?

[CBFalconer]

I get a 404 on the above URL; do you perchance know an alternative
location where I can get the paper?

No. Just that I recorded that that is where I got it. I imagine
Knuth may have it on his pages somewhere.

 

[Michael Mair]

No. Just that I recorded that that is where I got it. I imagine
Knuth may have it on his pages somewhere.

Had some more time; Knuth's Bibliography says
\p P67. Structured programming with {\bf go to} statements.
{\sl Computing Surveys\/ \bf 6} (December 1974), 261--301. Reprinted
with revisions in {\sl Current Trends in Programming Methodology},
Raymond T. Yeh, ed., {\bf 1} (Englewood Cliffs, N.J.: Prentice-Hall,
1977), 140--194; {\sl Classics in Software Engineering}, Edward Nash
Yourdon, ed.\ (New York: Yourdon Press, 1979), 259--321. Reprinted with
``final'' revisions as Chapter~2 of {\sl Literate Programming\/}
(see under Books).
However, it seems to be nowhere for free, so I went back to the
original site and searched some more; the paper has moved:
<http://pplab.snu.ac.kr/courses/adv_pl04/papers/p261-knuth.pdf>

Thanks for pointing me towards this article


Cheers
Michael

 

[CBFalconer]

.... snip ...

However, it seems to be nowhere for free, so I went back to the
original site and searched some more; the paper has moved:
<http://pplab.snu.ac.kr/courses/adv_pl04/papers/p261-knuth.pdf>

Thanks for pointing me towards this article

Now maybe someone will find it again later. They are certainly
moving it about.

 

[jdallen2000]

Note: The one thing you should *never* do, not *ever* *ever*, is jump
from outside a loop to inside a loop, or even into a block.
(If anyone can think of a valid example of such, please post now!)

The (in)famous Duff's Device does this, in a strange
way, but more interesting is:

http://tinyurl.com/2452h/dbldum.htm

Many will disparage the software at URL above,
but talk is cheap and *no one* during the 15 years I've
posted this code on Usenet has ever managed
to produce a "better" version (or *any* version)
of the routine without GOTO.

(Most of the disparaging comments have come
from people who obviously made no effort to
understand the code or even read the comments.
Let's see if comp.lang.c has improved over the
years....)

James Dow Allen

 

[Lawrence Kirby]

The (in)famous Duff's Device does this, in a strange
way, but more interesting is:

http://tinyurl.com/2452h/dbldum.htm

Many will disparage the software at URL above,
but talk is cheap and *no one* during the 15 years I've
posted this code on Usenet has ever managed
to produce a "better" version (or *any* version)
of the routine without GOTO.

Well the code license does expressly prohibit the removal of gotos.

The code is sufficiently complex that it would take some effort to
understand what it is doing and come up with possible alternatives.

I'm not a "goto gestapo", the Nim code is a nice example of using goto.
But I'm not going to accept that goto is the best way of doing something
just because somebody else says so.

The comments say

* Yes, the `goto' won't operate properly unless all the local variables
* are in precisely the right state to make their strange voyage from
* one inner loop to the other. But that's exactly the concept which
* the potential code-maintainer is intended to grasp.
*

Grasping is one thing, verifying is another. The fact is that this sort of
thing (jumping into loops) does make code more difficult to read, it
creates extra coupling between different parts of the code and a whole set
of preconditions that need to be checked.

I'm not convinced that goto is the best approach for this particular
problem. Of course it needs code to "prove" this. Maybe I'll look at it
further at some point. And if I can't find a better approach I'll agree
with you.

(Most of the disparaging comments have come
from people who obviously made no effort to
understand the code or even read the comments.
Let's see if comp.lang.c has improved over the
years....)

I hope "improve" doesn't mean that people can't argue about it.

Lawrence

 

[James Dow Allen]

The comments say

* Yes, the `goto' won't operate properly unless all the local variables
* are in precisely the right state to make their strange voyage from
* one inner loop to the other. But that's exactly the concept which
* the potential code-maintainer is intended to grasp.
*
Grasping is one thing, verifying is another. The fact is that this sort of
thing (jumping into loops) does make code more difficult to read, it
creates extra coupling between different parts of the code and a whole set
of preconditions that need to be checked.

Yes, but there already is extremely tight coupling between the two
loops,
since one precisely undoes what the other does. There may seem to be
a lot of local variables, but each one has a clear direct meaning in
its
context (number of cards played to the trick, which player led, etc.)

I'll agree that the code will be harder to grasp than a typical routine
of
the same length, but that isn't the proper criterion. Compare it with
the readability of the alternate routine, however long, that *solves
the
same problem.*

I'm not convinced that goto is the best approach for this particular
problem. Of course it needs code to "prove" this. Maybe I'll look at it
further at some point. And if I can't find a better approach I'll agree
with you.

Thank you, Lawrence. FWIW your comments are more reasoned
and objective than any responses received to this in the past.

The term "best" approach is ambiguous: do we seek speed or
readability? The algorithm can be factored into recursive functions
(which may or not be more readable) but which will probably be clumsy
and slow. Certain idiosyncrasies of this particular problem (e.g.
player sequencing depends on prior trick) weaken the case of
alternatives
to the wierd goto but, though perhaps I shouldn't admit it, I often
adopt this wierd-goto model to hack out other backtrackers quickly.

I hope "improve" doesn't mean that people can't argue about it.

Of course not! I'd love to see comp.lang.c'ers come up with the
"proper" alternative. I have psychological trouble doing that myself,
since I already know I like my way best

James Dow Allen

 

[CBFalconer]

Yes, but there already is extremely tight coupling between the two
loops, since one precisely undoes what the other does. There may
seem to be a lot of local variables, but each one has a clear
direct meaning in its context (number of cards played to the trick,
which player led, etc.)

I'll agree that the code will be harder to grasp than a typical
routine of the same length, but that isn't the proper criterion.
Compare it with the readability of the alternate routine, however
long, that *solves the same problem.*

Luckily I already had a copy of that article, since I won't use the
'unknown destination' tinyurls. I have no great complaint about
the goto, in fact I often recommend it. What that package needs is
the description of its metamorphosis from something
understandable. Even the existance of a (possibly very slow)
top-down crafted solution would help.

A 30 or more year old Knuth article on the use of gotos that I
recommended here (or there) a few days ago did precisely that. It
followed the evolution from a clear to an efficient solution step
by step.

 

[James Dow Allen]

Luckily I already had a copy of that article, since I won't use the
'unknown destination' tinyurls.

Doesn't the ".htm" at the end offer some reassurance?
And anyway, is my reputation so poor here that you
thought *I* was trying to break into your machine?
But point taken, I'll give regular URL in future. (The host
I use is nice in some ways, but has a ridiculously long URL.)

[A] Knuth article ...
followed the evolution from a clear to an efficient solution step
by step.

It's probably obvious that my routine is faster than a
"properly written" alternative. My claim is that it may also
be *clearer* once one escapes the mental block of disliking
the peculiar structure. (The alternative will be clumsy.)

Admittedly I should add detailed comments and rewrite some
of the long expressions to make this point. But the "cute"
programming examples I show at my website are a low priority
for me, and I've not received much encouragement here....

James

 

[S.Tobias]

Doesn't the ".htm" at the end offer some reassurance?
And anyway, is my reputation so poor here that you
thought *I* was trying to break into your machine?
But point taken, I'll give regular URL in future. (The host
I use is nice in some ways, but has a ridiculously long URL.)

This is the first time I hear about it. What is the difference
in terms of security between different URLs, be they short or long?
Except that posting tinyurls is not a good idea in itself, the only
problem I can see is that tinyurl.com might be hijacked, but so
might any other homepage.

 

[Stephen Hildrey]

This is the first time I hear about it. What is the difference
in terms of security between different URLs, be they short or long?
Except that posting tinyurls is not a good idea in itself, the only
problem I can see is that tinyurl.com might be hijacked, but so
might any other homepage.

tinyurl.com is a "URL shortening" service - you give it a long, unwieldy
URL and it will "convert" it to a shorter one beginning with
"http://tinyurl.com/".

When you request the tinyurl.com URL, your browser receives and follows
an HTTP 302 redirect to the original, longer URL. Because there is no
"are you sure you want to visit long_url?" confirmation, you're
effectively clicking blind links.

Other "URL shortening" services acknowledge this problem and insert a
time delay or confirmation before redirecting the client (though I can't
think of them off the top of my head).

To James: the .htm should be of no reassurance - browsers will interpret
content based on the HTTP Content-type header they receive, not based on
file extension.

Steve

 

[CBFalconer]

CBFalconer wrote:
.... snip ...


Doesn't the ".htm" at the end offer some reassurance?
And anyway, is my reputation so poor here that you
thought *I* was trying to break into your machine?
But point taken, I'll give regular URL in future. (The host
I use is nice in some ways, but has a ridiculously long URL.)

No, but when you arrive here you are just another pretty face. You
can always supply both forms. Do check the Knuth quotation. I
think it is now at:

<http://pplab.snu.ac.kr/courses/adv_p104/papers/p261-knuth.pdf>

 

[CBFalconer]

tinyurl.com is a "URL shortening" service - you give it a long,
unwieldy URL and it will "convert" it to a shorter one beginning
with "http://tinyurl.com/".

When you request the tinyurl.com URL, your browser receives and
follows an HTTP 302 redirect to the original, longer URL. Because
there is no "are you sure you want to visit long_url?" confirmation,
you're effectively clicking blind links.

Other "URL shortening" services acknowledge this problem and insert
a time delay or confirmation before redirecting the client (though
I can't think of them off the top of my head).

To James: the .htm should be of no reassurance - browsers will
interpret content based on the HTTP Content-type header they
receive, not based on file extension.

Other problems - the tinyurl has a relatively short lifespan. If
you try to follow one from a saved message of an appropriate age,
it just won't work, or will lead elsewhere. The actual URL at
least has a chance of being valid.

Also, since you have no idea where you are going, you can simply be
leaving your return address as a location for some form of bot to
probe. When I am connected my zonealarm log shows something like
1/2 to 10 probes per minute from outside that have been rejected.

The log shows something like 25,000 probes in the past 5 years, or
about 400 per month. Other records show that I am on-line and
connected about 50 mins per month. So that leaves a consistent
probe level of the order of 10 per minute. I am sure some of the
probes may be relatively benign, but the rest are not. Zonealarm
is the one really necessary piece of protection. Other things can
be avoided by a little hygiene, such as rejecting html/mime mail.

I didn't even realize the long term level was that high until I
looked for this reply! And I operate mainly off-line.

 

[Anonymous 7843]

Doesn't the ".htm" at the end offer some reassurance?

No. The content-type is established in the HTTP header
and need not match the file suffix. A malicious
web site can send you activex or JPG files that
are innocuously named "index.html".

And anyway, is my reputation so poor here that you
thought *I* was trying to break into your machine?

I would not fear that so much, but I don't need inappropriate
JPEG's appearing on my screen during work hours. It's usually
not something to fear on comp.lang.c but if one's employer is
strict you need to be careful with slashdot for example.

 

[Tim Rentsch]

I have a nested while. How do I go from the inner while to the
beginning of the outer while? Can this be done without using goto?

[unclear code snipped]

I think it is instructive that you need labels and a precise
definition to describe what you want. The above is not at all
precise.

lb1: while (c1) {
....
while (c2) {
....
if (c3) goto lb1;
....
}
....
}

can be replaced with:

int flag;

while (c1) {
....
flag = 0;
while (c2) {
....
if (c3) {
flag = 1; break;
}
....
}
if (flag) continue;
....
}

which lacks the clarity and simplicity of the goto version. When
appropriate, just use goto.

I agree with the commentary, but I think the last sentence does a
disservice to the OP. The reason a 'goto' statement is usually a bad
idea is not that it's a 'goto' but that most often it's symptomatic of
bad program structure. When a situation arises where 'goto' seems
like the best way to write something, usually that means the function
in question is in need of significant revision. The first version
above may be cleaner than the second, but either version should raise
a red flag [*] during code review. Explore alternatives; neither of
the examples above should be accepted unless evidence that a better
alternative can't be found is fairly compelling.


[*] No pun intended.

 

[Tim Rentsch]

[A] Knuth article ...
followed the evolution from a clear to an efficient solution step
by step.

It's probably obvious that my routine is faster than a
"properly written" alternative. My claim is that it may also
be *clearer* once one escapes the mental block of disliking
the peculiar structure. (The alternative will be clumsy.)

Admittedly I should add detailed comments and rewrite some
of the long expressions to make this point. But the "cute"
programming examples I show at my website are a low priority
for me, and I've not received much encouragement here....

Alright, I'll offer some encouragement. Consider an approach along
the following lines.

void
find_optimal_play(){
... a few local variables ...

... initialize ...

FOREVER {

FOREVER {
play one more card from alternatives
set alternatives for next play
if( at end of trick ){
advance state to next trick
if( one side "won" ) break;
}
}

FOREVER {
if( at start of trick ){
if( at first trick ) return;
regress state to previous trick
}
regress state to previous play
undo effects of card played
if( this side should try other plays ) break;
}
}
}

I coded up something along these lines. The control flow is just what
is shown here: three infinite loops, two break's, one return. The
state of the computation was in a data structure much like the one you
used - a stack of "tricks" with information about alternatives and
cards played. Only a few local variables, and I made essentially no
effort to micro-optimize; for example, the suit led is recalculated
each time through the "advance the state" loop:

suit_led = SUIT( S->card_played[ S->on_lead ] );

Except for the different method of doing control flow, the two
programs use basically the same algorithm. The structured code ran
about 25% faster than your code with goto's.

So I guess I'm encouraging you to reconsider whether this problem is a
good example to illustrate when goto's are clearer or faster. Neither
seems to be true in this particular case.

 

[James Dow Allen]

Alright, I'll offer some encouragement. Consider an approach
[with] three infinite loops, two break's, one return....

Except for the different method of doing control flow, the two
programs use basically the same algorithm. The structured code ran
about 25% faster than your code with goto's.

Congratulations and thank you!

Would you like to post your code at my site, with whatever
commentary you choose?

James Dow Allen (e-mail jamesdowallen at gmail.com)

 

[Robert Maas, see http://tinyurl.com/uh3t]

The important thing is how it is presented.

I agree. Loops of the FOR or WHILE type, and mappings down sequences
such as are common in Lisp, make it obvious at first glance what kind
of loop is done, compared to a GOTO loop where you have to read the
code carefully to diagonse the various kinds of loops.

Structured programming constructs don't do anything you can't do with
conditional gotos,

Nobody ever said otherwise: It's the converse that is claimed:
Structured programming constructs *prevent* you from using the full
flexibility that GOTO would allow, thereby preventing you from doing
things you shouldn't do anyway and shouldn't even want to do.

On the other hand, tail recursion can be used to emulate GOTO, so
syntactic structured programming doesn't actually prevent you from
writing haywire algorithms.

it is simply a better means of presentation and conceptualisation.

Only if you keep your FOR and WHILE and MAP loops simple. A really
hairy set of nested FOR and WHILE loops full of BREAK and CONTINUE in
all sorts of odd places can end up being as inscrutable as a GOTO
haywire.