No Go To's Forever!

No Go To's Forever!

[Bill Dale]

dis90072 wrote:
> 
> Having learned ada for the past six months, I have found no reference to
> the 'jump' command. In MSDOS you can use the 'goto' command. Even in
> damn assembler you can jump. What is the equivalent in ada? I have had
> enough of endless 'IF' statements and everlasting case statements. I
> know it might make the program hard to follow, but I don't care! I must
> have it!
> Please......!
> Regards,
> Matt.

Never use a GOTO - ever. At all. Anywhere. Period.

OK, I'll put you down as not interested in working for me.  

--------------------
No-GOTO Bill

Re: No Go To's Forever!

[Charles Hixson]

Bill Dale wrote:

> Never use a GOTO - ever. At all. Anywhere. Period.
>
> OK, I'll put you down as not interested in working for me.
>
> --------------------
> No-GOTO Bill

Now, now.  I'm sure that I've use a goto instruction at least 6 times in the
last decade.   Well, maybe 5 times.

Re: No Go To's Forever!

[Robert Dewar]

In article <38D7B83B.27DC06C8@earthlink.net>,
  Charles Hixson <charleshixsn@earthlink.net> wrote:
> Bill Dale wrote:
>
> > Never use a GOTO - ever. At all. Anywhere. Period.
> >
> > OK, I'll put you down as not interested in working for me.

Actually the other concern here, apart from having someone
who is so ready to use goto despite knowing it will damage
the code, is to have someone who cannot *easily* track down
for themselves that of course Ada has a goto statement.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Gautier]

Charles Hixson wrote:

> Now, now.  I'm sure that I've use a goto instruction at least 6 times in the
> last decade.   Well, maybe 5 times.

Hum hem. Don't tell it too loud, but -ahem- I confess I've put
a *provisory* one in the last month, to debug an interrupt
in a sound blaster driver for gnat. Will disappear as soon as
possible...
_____________________________________________
Gautier  --  http://members.xoom.com/gdemont/

Re: No Go To's Forever!

[David Starner]

On Tue, 21 Mar 2000 09:40:45 -0800, Bill Dale <william.dale.jr@lmco.com> wrote:
>dis90072 wrote:
>> 
>> Having learned ada for the past six months, I have found no reference to
>> the 'jump' command. In MSDOS you can use the 'goto' command. Even in
>> damn assembler you can jump. What is the equivalent in ada? I have had
>> enough of endless 'IF' statements and everlasting case statements. I
>> know it might make the program hard to follow, but I don't care! I must
>> have it!
>> Please......!
>> Regards,
>> Matt.
>
>Never use a GOTO - ever. At all. Anywhere. Period.

This seems absurd. I occasionally come upon situations
where it's either a goto statment or a boolean variable,
and the boolean variable is no more readable. 
The GNAT sources contain 300-400 goto statements and
a brief glance at parts shows that the goto statements
are highly readable.

(I do realize the evil that a goto statement can be -
I spent much of my youth typing in Basic programs from
books. This does not prove that a judicious use of goto
statements in a language with appropriate control structures
like C or Ada is wrong.)

-- 
David Starner - dstarner98@aasaa.ofe.org
Only a nerd would worry about wrong parentheses with
square brackets. But that's what mathematicians are.
   -- Dr. Burchard, math professor at OSU

Re: No Go To's Forever!

[Michael P. Walsh]

Robert Dewar wrote:

> In article <38D7B83B.27DC06C8@earthlink.net>,
>   Charles Hixson <charleshixsn@earthlink.net> wrote:
> > Bill Dale wrote:
> >
> > > Never use a GOTO - ever. At all. Anywhere. Period.
> > >
> > > OK, I'll put you down as not interested in working for me.
>
> Actually the other concern here, apart from having someone
> who is so ready to use goto despite knowing it will damage
> the code, is to have someone who cannot *easily* track down
> for themselves that of course Ada has a goto statement.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.

Goto damages the code?

Is this something like BASIC causing brain damage?

Mike Walsh

Re: No Go To's Forever!

[David Starner]

On Wed, 22 Mar 2000 00:00:10 +0100, Tim Gahnstr�m <md9tim@mdstud.chalmers.se> wrote:
>I notice that alot of people really hate gotos...
>But why is it sooo bad can someone tell me that???

This is some real code (from Axelrod's simulation of the
Prisoner's Dillema). This, mind you, is opening up the
file and basically randomly grabing a function - there
is much, much worse in that file alone.

    FUNCTION K58R(J,M,K,L,R, JA)
C BY GLEN ROWSAM
C TYPED BY JM
    k58r=ja    ! Added 7/27/93 to report own old value
    IF (M .GT. 1) GOTO 99
    KAM = 0
    NPHA = 0
99  IF (KAM .GT. 6) GOTO 87
    IF (NPHA .GE. 1) GOTO 89
    IF ((M / 18) * 18 .EQ. M .AND. KAM .GT. 2) KAM = KAM - 1
    IF ((M / 6) * 6 .NE. M) GOTO 88
    IF (K .LT. M) GOTO 10
    IF (K * 10 .LT. M * 15) GOTO 11
    IF (K .LT. M * 2) GOTO 12
    IF (K * 10 .LT. M * 25) GOTO 13
    GOTO 88
10  KAM = KAM + 2
11  KAM = KAM + 1
12  KAM = KAM + 1
13  KAM = KAM + 1
    NPHA = 2
    GOTO 87
89  NPHA = NPHA - 1
    IF (NPHA .EQ. 0) GOTO 87
88    K58R = 0
    GOTO 86
87    K58R = 1
86  RETURN
    END

Much of the blame for goto hating must go to FORTRAN <= 77, which
requires goto's for common stuff and provides only numeric labels.

>I assume this is a typical example of bad goto use

At first glance I don't think it works, and it would be
a little easier to read if you used control structures
instead of gotos, but it's not a typical example.

>Is goto statments particular slow?

No, but a modern compiler can frequently handle the other
control structures faster (more information to optimize with.)
Anyway, the arguments against gotos has always been that they're
hard to read, and that readibility should come before optimization.

-- 
David Starner - dstarner98@aasaa.ofe.org
Only a nerd would worry about wrong parentheses with
square brackets. But that's what mathematicians are.
   -- Dr. Burchard, math professor at OSU

Re: No Go To's Forever!

[Andrew Berg]

"Michael P. Walsh" wrote:

> Robert Dewar wrote:
>
> > In article <38D7B83B.27DC06C8@earthlink.net>,
> >   Charles Hixson <charleshixsn@earthlink.net> wrote:
> >
> > Actually the other concern here, apart from having someone
> > who is so ready to use goto despite knowing it will damage
> > the code, is to have someone who cannot *easily* track down
> > for themselves that of course Ada has a goto statement.
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
>
> Goto damages the code?
>
> Is this something like BASIC causing brain damage?
>
> Mike Walsh

Only if you don't have protected memory.

Now, does BASIC cause brain damage, or does brain damage cause BASIC?
That's the question.

-andrew

Re: No Go To's Forever!

[Bill Dale]

David Starner wrote:
> 
> On Tue, 21 Mar 2000 09:40:45 -0800, Bill Dale <william.dale.jr@lmco.com> wrote:
> >dis90072 wrote:
> >>
> >> Having learned ada for the past six months, I have found no reference to
> >> the 'jump' command. In MSDOS you can use the 'goto' command. Even in
> >> damn assembler you can jump. What is the equivalent in ada? I have had
> >> enough of endless 'IF' statements and everlasting case statements. I
> >> know it might make the program hard to follow, but I don't care! I must
> >> have it!
> >> Please......!
> >> Regards,
> >> Matt.
> >
> >Never use a GOTO - ever. At all. Anywhere. Period.
> 
> This seems absurd. I occasionally come upon situations
> where it's either a goto statment or a boolean variable,
> and the boolean variable is no more readable.
> The GNAT sources contain 300-400 goto statements and
> a brief glance at parts shows that the goto statements
> are highly readable.
> 
> (I do realize the evil that a goto statement can be -
> I spent much of my youth typing in Basic programs from
> books. This does not prove that a judicious use of goto
> statements in a language with appropriate control structures
> like C or Ada is wrong.)
> 
> --
> David Starner - dstarner98@aasaa.ofe.org
> Only a nerd would worry about wrong parentheses with
> square brackets. But that's what mathematicians are.
>    -- Dr. Burchard, math professor at OSU

OK, I'll jump back in on this.  I just left an assignment
(incomplete BTW) updating a Fortan program.  Some of the source was 50% 
GOTOs - no kidding.  Line numbers, too.  

	IF (FRED.EQ.0)  GO TO 124
	IF (BARNY.EQ.1) GO TO 234
	IF (WILMA.EQ.2) GO TO 180 

Line after obscure line. Awful crap.  Life is too short 
to deal with this stuff.

I can confidently say I have never used a GOTO in Ada. Never had to.

-- No-GOTO Bill

Re: No Go To's Forever!

[Keith Thompson]

"Ken Garlington" <Ken.Garlington@computer.org> writes:
> "Robert Dewar" <robert_dewar@my-deja.com> wrote in message
> news:8b93n3$8ai$1@nnrp1.deja.com...
> 
> > <<Is goto statments particular slow?>>
> > No, the concern is not for efficiency at all!
> 
> You're the expert, of course, but I'm surprised by this answer. I thought
> that structured code in general allowed for easier determination of scope,
> making certain optimizations more likely to be applied.

It depends on the compiler.  In the old TeleSoft compiler, certain
optimizations were turned off for any scope containing a goto
statement.  This wasn't strictly necessary, but performing the
necessary analysis would have required substantial extra time
(development time, not necessarily compilation time), and it wasn't
considered worth the effort.

I suspect most compiler back-ends work on a lower level and are not as
easily intimidated by gotos.

As for stylistic concerns, IMHO gotos are very rarely appropriate.
The exceptions are: to simulate a structured construct missing from
the language (e.g., a multi-level break or exception handler in C, or
*possibly* a continue statement in Ada), or when a goto accurately
reflects the abstraction being modeled (e.g., in a finite state
machine).

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
Welcome to the last year of the 20th century.

Re: No Go To's Forever!

[Tim Gahnström]

On Tue, 21 Mar 2000, Charles Hixson wrote:
> Bill Dale wrote:
> > Never use a GOTO - ever. At all. Anywhere. Period.
> > OK, I'll put you down as not interested in working for me.
> 
> Now, now.  I'm sure that I've use a goto instruction at least 6 times in the
> last decade.   Well, maybe 5 times.

I notice that alot of people really hate gotos...
But why is it sooo bad can someone tell me that???

eg. this little snipet to eat spaces andnewlines in a textfiles
to get to the first character

look_ahead(in_file,ch,bool);
<<start>>
while bool loop
  skipline(infile);
  look_ahead(in_file,ch,bool);
end loop;

if ch=' ' then
  while ch=' ' loop
    get(infile,ch);
    look_ahead(in_file,ch,bool);
  end loop;
  goto start;
end if;

Start_reading the words

I assume this is a typical example of bad goto use
but I canot figure out why, I think it is nice and easy 
to read and it takes care of potential 
' ',' ','\n','\n',' ',' ','\n'

I realize everything is posible to do without gotos 
but I canot figure out why it is so horible.
Please enlighten me.
Is goto statments particular slow?

Tim

Re: No Go To's Forever!

[Michael P. Walsh]

Robert Dewar wrote:

> I guess the burden here is to explain why the goto formulation
> is so horrible. Yes, it slightly discourages this control flow
> form, but that's probably a good idea, if you can avoid exit's
> and continue's in loops without doing damage to the code that's
> a good idea.

Is it so hard to say that the problem with the goto is not the goto
function, but what many people have done with it?

People are quite capable of writing good code in assembly
language, but it is likely to be quite hard to read and
understand unless it is well commented.

I spent many years as a Fortran programmer and started out
writing quite a bit of "spaghetti code".  Then I read some of
the articles on structured program and decided they made
sense.

I also note that you can write good structured code while
using goto's and write some very poorly organized code
without a single goto.

As far as this Ada newsgroup, I will note that this is a far
more general programming language discussion and
actually has little to do with Ada which, as mentioned,
does have a goto function.

Mike Walsh

Re: No Go To's Forever!

[Paul Graham]

I think the goto implementation of the 'continue' statement is fragile
in the sense that it depends on the "<<continue>> null;" being the last
statement in the loop. A maintainer who wasn't familar with this idiom
might add statements at the end of the loop body, thereby breaking your
construct.

On the other hand, the continue statement in C is really best used in a
for loop, because you want some guarantee that the loop state will
advance. In a while loop it is all too easy for a misplaced continue to
create an infinite loop.

Paul

Robert Dewar wrote:
> 
> In article <38D8DFC2.778826FB@cadence.com>,
>   Paul Graham <pgraham@cadence.com> wrote:
> 
> > Why is there no 'continue' statement in Ada?  You've shown
> > that the function of 'continue' is desirable.
> 
> Yes, the *function* of continue is desirable, but on the other
> hand a continue is indeed a goto, so why not say so? That's the
> other point of view, and as you see from the previous post,
> some people find it clearer to use a goto here. We did discuss
> this in the language revision but there was insufficient
> support for this language addition.

Re: No Go To's Forever!

[Michael P. Walsh]

Ted Dennison wrote:

> In article <Pine.BSF.4.21.0003220851480.3555-100000@shell5.ba.best.com>,
> Brian Rogoff <bpr@shell5.ba.best.com> wrote:
> > Dijkstra also wrote that CS students should be kept away from a
> > computer for their first year and focus on pencil and paper proofs (no
> > problem for me, I was a Math major) and he probably didn't like Ada
> > anyways so phooey on him :-)
>
> I don't ever really expect to agree with Dijkstra. But that's because
> Basic was my first language, therefore I am "mentally mutilated beyond
> all hope of saving", or somesuch.
>
> For the record, I think my wife would agreee with him on that point. :-)
>
> --
> T.E.D.
> http://www.telepath.com/~dennison/Ted/TED.html
>

In addition to being a noted computer expert Dijkstra is noted
for his ascerbic remarks and ability to make thought provoking
comments.

Anyone taking some of Dijkstra's words completely literally
is quite likely rising to his bait.  In some ways you could call
Dijkstra a "trolling" academic.

Note that I am in no way disparaging Dijkstra's truly great
capabilities as a computer scientist.

Mike Walsh

Re: No Go To's Forever!

[tmoran]

> Of course you could argue that it is easier to find your refined
> superior form from my syntactic expression with nested loops
> than from the original with a goto, and that would be an
> interesting argument to make.
 I'll make that argument.  "while" etc make the flow clearer, and
thus easier to understand and improve, than goto's.

>  <<Do_It_Again>>
>     for J in 1 .. N - 1 loop
>        if D (J) < D (J + 1) then
>           Swap (D (J), D (J + 1));
>           goto Do_It_Again;
>        end if;
>     end loop;

  I personally find this clearer, even if a tad longer:
   loop
     J := D'first;
     while J < D'last and then D(J) >= D(J+1) loop
       J := J+1;
     end loop;
     exit when J >= D'last;
     Swap (D (J), D (J + 1));
   end loop;

> After all the little example here that was given (the blanks
> eater with the goto) is perfectly well structured (single
> entry-single exit, well formed loops etc, just not very clear!
  Actually, it had two different entrances: one at the top just
before the initial lookup, and another, which presumably should
never be used, at the label just after that lookup.  One could
imagine a program with a typo where a "goto starter" was
mis-written as "goto start".  The result might be nasty, the
compiler not help, and that kind of typo is notoriously hard to spot.

Re: No Go To's Forever!

[Charles Hixson]

Roger Barnett wrote:

>  -- snip
> I would argue that this use is clearer than the continue statement
> as provided by C.
>
> -- snip

Personally I find that if the break and contiue constructs are supplemented with
named break and continue statements, I never have the need (or desire) for a GoTo.
Unfortunately, these constructs are not always available, so it is sometimes
necessary to simulate (emulate?) them.
Back in the CP/M days I'd occasionally write a driver where I'd need to either use a
goto or drop into assembler.  Usually I choose to use "sort-of" C, with go-to
instructions for ease in understanding.  But it was nearly a tossup.  OTOH, those
were *VERY* small modules.  A couple of branches in a 20 line routine is acceptable
if there is a good reason.  For that matter I'd rather use a state machine
implemented with goto's than one that was implemented with function variables.  I
find them to be "pretty near" the same concept, and even less intelligible (the true
touchstone!).


-- Charles Hixson
-- charleshixson@earthling.net

Re: No Go To's Forever!

[Charles Hixson]

"Michael P. Walsh" wrote:

>  -- snip
>
> People are quite capable of writing good code in assembly
> language, but it is likely to be quite hard to read and
> understand unless it is well commented.
>
> -- snip

It is true that nearly any computer language creates the possibility
of writing well structured code.  The problem come from a little thing
that Linguists call Zipf's law.  Basically it says that people prefer
to do things that are easy, and language tends to structure itself to
make easy those things that people do frequently.

At this point I tend to apply the weak form of Whorf's law, which
states (essentially) if there are two ways to think about something,
people will tend to choose to think about it in the way most
harmonious with their most familiar linguistic habits.

In other words, if you get into the habit of using goto's, you will
tend to become more comfortable with using them.  And if it is twice
as hard to write well structured code, you will tend to write
unstructured code.

To elaborate on the matter, if code is written first in a quick and
dirty fashion, with the intention of cleaning it up once you get it
working, it will probably never get cleaned.  So the better
environment  is the one that makes it easy to write it correctly the
first time.  I don't like goto label constructs unless the label MUST
be attached to a well-marked feature, like the beginning or end of a
loop or routine, and those feature had better be well marked for manyn
other reasons than the goto label.  If the label just happens to be at
the start or end of the routine, and not attached to it, then it might
be advantageous to insert intervening statements for cleanup or
initialization.  And they may become modified by code repairs.  And
all of a sudden you notice that the code doesn't look very structured
at all.  Let's just get off this slope!  I support continue <label>
and break <label> where the label is on a block, preferably at both
the beginning and the end.  GoTo <label> is a much too general
substitute.

The whole purpose of this is to cause the code that is written to be
more legible, both later and at the time!

-- Charles Hixson
-- charleshixson@earthling.net

Re: No Go To's Forever!

[Jon S Anthony]

Robert Dewar wrote:
> 
> In article <38D8E9DE.14E93706@quadruscorp.com>,
>   "Marin D. Condic" <mcondic-nospam@quadruscorp.com> wrote:
> 
> > Don't fight the language! Learn to do it "The Ada Way"
> 
> Last I looked, Ada included a goto statement, it is people
> who absolutely forbid goto's who are failing to follow the
> above advice.

I seem to recall that (at least in the "early days") the designers
put the goto statement in Ada due to a belief that there would be
a significant amount of machine generated Ada (presumably from
much higher level problem descriptions).  Anyone with a clue knows
that in this case goto is mighty handy.

/Jon

-- 
Jon Anthony
Synquiry Technologies, Ltd. Belmont, MA 02478, 617.484.3383
"Nightmares - Ha!  The way my life's been going lately,
 Who'd notice?"  -- Londo Mollari

Re: No Go To's Forever! (I'm sorry I spoke...)

[dis90072]

Jesus, did the thread really have to be this long?
I only asked a question... now I've got replies that fill up a whole screen!

Re: No Go To's Forever!

[Jon S Anthony]

Robert Dewar wrote:
> 
> In article <38D947B9.6C50@synquiry.com>,
>   Jon S Anthony <jsa@synquiry.com> wrote:
> > I seem to recall that (at least in the "early days") the
> designers
> > put the goto statement in Ada due to a belief that there would
> be
> > a significant amount of machine generated Ada (presumably from
> > much higher level problem descriptions).  Anyone with a clue
> knows
> > that in this case goto is mighty handy.
> 
> That's certainly a consideration, but if you recall that this
> was the *only* reason then you recall wrong :-)

I should have been more accurate: I had a vague recollection of
_reading_ this somewhere.  I have no recollection of any of the
actual discussions at the time - if for no other reason than
Ada83 had already existed a few years before I even got into
this business :-).


> usage was not just acceptable but desirable. Encoding the
> state into the PC is an efficient and easy to read and follow
> representation of FSM's.

Seems reasonable.


/Jon

-- 
Jon Anthony
Synquiry Technologies, Ltd. Belmont, MA 02478, 617.484.3383
"Nightmares - Ha!  The way my life's been going lately,
 Who'd notice?"  -- Londo Mollari

Re: No Go To's Forever!

[Roger Barnett]

So I guess this is not the group to discuss the goto label_variable
construct ?

[ essentially a poor man's exception handler from the 1970s ]

-- 
Roger Barnett

[ purveyor of RTL/2 software products & consultancy ]

Re: No Go To's Forever!

[Robert Dewar]

In article
<Pine.SOL.4.21.0003212347450.15450-100000@fraggel81.mdstud.chalm
ers.se>,
  =?ISO-8859-1?Q?Tim_Gahnstr=F6m?= <md9tim@mdstud.chalmers.se>
wrote:

> I realize everything is posible to do without gotos
> but I canot figure out why it is so horible.
> Please enlighten me.
> Is goto statments particular slow?
>
> Tim

Gotos often make simple code hard to read. Your example is
a good one!

   <<start>>
   while bool loop
     skipline(infile);
     look_ahead(in_file,ch,bool);
   end loop;

   if ch=' ' then
     while ch=' ' loop
       get(infile,ch);
       look_ahead(in_file,ch,bool);
     end loop;
     goto start;
   end if;

The following is preferable in every way. It makes the exit
condition from the outer loop far clearer (not to mention making
it clearer that there *is* an outer loop!

    loop
      while bool loop
        skipline(infile);
        look_ahead(in_file,ch,bool);
      end loop;

      exit when ch /= ' ';

      while ch=' ' loop
        get(infile,ch);
        look_ahead(in_file,ch,bool);
      end loop;
    end loop;

It is shorter and clearer.

<<Is goto statments particular slow?>>

No, the concern is not for efficiency at all!

There are (rare) cases where gotos are appropriate, but they
are few and far between, and your example is a good one showing
why gotos should not generally be used.

In fact gotos are so often misused that some people go to the
extreme of saying they should never ever be used. This approach
is excessive, but has the advantage of completely eliminating
the kind of misuse you illustrate in your example.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[tmoran]

> look_ahead(in_file,ch,bool);
> <<start>>
> while bool loop
>   skipline(infile);
>   look_ahead(in_file,ch,bool);
> end loop;
>
> if ch=' ' then
>   while ch=' ' loop
>     get(infile,ch);
>     look_ahead(in_file,ch,bool);
>   end loop;
>   goto start;
> end if;

How about:

loop
  look_ahead(in_file,ch,got_eol);
  if got_eol then
    skipline(infile);
  elsif ch = ' '
    get(infile, ch);
  else
    exit;
end loop;

It's shorter, the logic of what's going on is clearer, only
a single line needs to be changed to add tab skipping,
there's only one way to enter the code sequence (no distant
"goto start") so the first reference to bool or ch is
guaranteed to come *after* the look_ahead call that sets
their values, and, since the compiler can tell the control
flow, it can do better optimization.

>I realize everything is posible to do without gotos
>but I canot figure out why it is so horible.
   A piece of logic expressed with loops, ifs, cases,
and subroutine calls is almost always clearer (and
therefore less likely to be erroneous) and is commonly
also shorter than the (attempted) equivalent using goto.

In MSDOS .bat and assembler you have no choice but to use
a jump/goto.  Your toolset is bigger now, learn to use it.

>I know it might make the program hard to follow, but I don't care!
  But a hard to follow program is hard to debug and hard to
extend, and therefore worth less.

Re: No Go To's Forever!

[Ken Garlington]

Now, now... he asked for a "jump" statement, not a "goto," and the LRM does
not use the word "jump" in section 5.8. Besides, section 5.8 is way down at
the end of section 5; it might have been scrolled off his screen...

What I want to know is, where the heck is the computed IF statement? This
dang language won't even let me assign numeric labels to a line!

"Robert Dewar" <robert_dewar@my-deja.com> wrote in message
news:8b8fha$m1h$1@nnrp1.deja.com...
> In article <38D7B83B.27DC06C8@earthlink.net>,
>   Charles Hixson <charleshixsn@earthlink.net> wrote:
> > Bill Dale wrote:
> >
> > > Never use a GOTO - ever. At all. Anywhere. Period.
> > >
> > > OK, I'll put you down as not interested in working for me.
>
> Actually the other concern here, apart from having someone
> who is so ready to use goto despite knowing it will damage
> the code, is to have someone who cannot *easily* track down
> for themselves that of course Ada has a goto statement.
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.

Re: No Go To's Forever!

[Ken Garlington]

"Robert Dewar" <robert_dewar@my-deja.com> wrote in message
news:8b93n3$8ai$1@nnrp1.deja.com...

> <<Is goto statments particular slow?>>
> No, the concern is not for efficiency at all!

You're the expert, of course, but I'm surprised by this answer. I thought
that structured code in general allowed for easier determination of scope,
making certain optimizations more likely to be applied.

Re: No Go To's Forever!

[Robert Dewar]

In article <TnVB4.10962$624.1043257@news.flash.net>,
  "Ken Garlington" <Ken.Garlington@computer.org> wrote:
> "Robert Dewar" <robert_dewar@my-deja.com> wrote in message
> news:8b93n3$8ai$1@nnrp1.deja.com...
>
> > <<Is goto statments particular slow?>>
> > No, the concern is not for efficiency at all!
>
> You're the expert, of course, but I'm surprised by this
answer. I thought
> that structured code in general allowed for easier
determination of scope,
> making certain optimizations more likely to be applied.


Well that is true in some cases, but if gotos are simply used
to duplicate more rational control structures, then typical
optimizers are not affected. For example, for the two pieces
of code here (the original version with a goto, and the
replacement version with a loop), most optimizers will produce
identical code.

I really think that the concern with not using gotos has nothing
to do with efficiency. Indeed, it takes a very strong optimizer
to recover the efficiency of a goto in some cases. FOr example,
consider the two representations of a finite state machine

   <<state1>> .... goto state2;

   case state1 is ....  current_state := state2;

it is quite difficult for an optimizer to recover the goto
structure from the case statement, and indeed I have not worked
with any compiler that manages to eliminate the loop and case
statement in the second case.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <8b8m2e$8201@news.cis.okstate.edu>,
  dstarner98@aasaa.ofe.org wrote:

> The GNAT sources contain 300-400 goto statements and
> a brief glance at parts shows that the goto statements
> are highly readable.

It's actually quite instructive to look through these goto
statements.

About 60% are in the finite state machine that is part of the
SPITBOL pattern matching unit. I have always felt that gotos
are a very natural representation of the arcs of a finite
state machine, and I invite people to look at the code of
g-spipat.adb to see if you agree :-)

Another section are for the finite state machine in the scanner.

Another big bunch are continue gotos. Ada lacks a continue
statement, and thus this facility must be simulated with a goto
as in

   loop

    if ... then goto Continue;

   <<Continue>> null;
   end loop;

This is actually quite a structured use of goto

There are only about 8 other instances of gotos in the
several hundred thousand lines of sources.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Roger Barnett]

In article: <8b9fk3$l18$1@nnrp1.deja.com>  Robert Dewar <robert_dewar@my-deja.com> 
writes:
> 
> Another big bunch are continue gotos. Ada lacks a continue
> statement, and thus this facility must be simulated with a goto
> as in
> 
>    loop
> 
>     if ... then goto Continue;
> 
>    <<Continue>> null;
>    end loop;
> 
> This is actually quite a structured use of goto


I would argue that this use is clearer than the continue statement
as provided by C.

But then I've been known to suggest compulsory use of labels when
using exit in nested loops.

Like the original poster to this thread, these and other prejudices
come from cruel and unnatural software maintenance.

-- 
Roger Barnett

Interbroker is a registered trademark.

Re: No Go To's Forever!

[Paul Graham]

Robert Dewar wrote:

> Another big bunch are continue gotos. Ada lacks a continue
> statement, and thus this facility must be simulated with a goto
> as in ...

Why is there no 'continue' statement in Ada?  You've shown that the
function of 'continue' is desirable. 

Paul

Re: No Go To's Forever!

[Robert Dewar]

In article <TnVB4.10962$624.1043257@news.flash.net>,
  "Ken Garlington" <Ken.Garlington@computer.org> wrote:
> You're the expert, of course, but I'm surprised by this
> answer. I thought
> that structured code in general allowed for easier
> determination of scope, making certain optimizations more
> likely to be applied.


Here is another way of answering this that may be clearer.

Yes, structured code is easier to optimize

But, a goto does not make code unstructured per se. The goto
makes it possible to write nasty hard-to-optimize code in this
respect, but the mere use of a goto does not mean that you are
in fact creating unstructured code. After all the little example
here that was given (the blanks eater with the goto) is
perfectly well structured (single entry-single exit, well formed
loops etc, just not very clear!


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <0mVB4.193$2K6.17499@news.pacbell.net>,
  tmoran@bix.com wrote:

> How about:
>
> loop
>   look_ahead(in_file,ch,got_eol);
>   if got_eol then
>     skipline(infile);
>   elsif ch = ' '
>     get(infile, ch);
>   else
>     exit;
> end loop;


OK, but that is really changing the algorithm, which is not
always a satisfactory response. FOr example, if I offer the
following sorting algorithm:

  <<Do_It_Again>>
     for J in 1 .. N - 1 loop
        if D (J) < D (J + 1) then
           Swap (D (J), D (J + 1));
           goto Do_It_Again;
        end if;
     end loop;

then you could show me a (much more efficient) bubble sort
(which zips along at O(N**2) instead of the shorter algorithm
above which is O(N**3)) but that would not really speak to the
use of a goto in the above algorithm (I actually prefer the
above statement with a goto, which really in this case is just
a neat way of writing tail recursion) to the use of boolean
flags etc.

Of course you could argue that it is easier to find your refined
superior form from my syntactic expression with nested loops
than from the original with a goto, and that would be an
interesting argument to make.
>


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <8b8m2e$8201@news.cis.okstate.edu>,
  dstarner98@aasaa.ofe.org wrote:

> >
> >Never use a GOTO - ever. At all. Anywhere. Period.
>
> This seems absurd.

Yes, of course it *is* absurd, but some people just don't
understand when goto's are OK, and when they are not, and
just can't grasp this distinction. For such people the above
prohibition is less damaging to their code than the improper
use of gotos.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38D81DF6.D4AA73FC@lmco.com>,
  william.dale.jr@lmco.com wrote:
> Line after obscure line. Awful crap.  Life is too short
> to deal with this stuff.

Yes, but showing an example of a feature being misused is not
an argument for never using the feature, unless you are
incapable of distinguishing good from bad use.
>
> I can confidently say I have never used a GOTO in Ada. Never
> had to.

No one ever *has* to use a GOTO, there are always other ways
to write things, and indeed you can't find an example where
the prohibition of gotos severely damages the code. You can
certainly find cases where the use of a goto clarifies the
code (e.g. the simple use for a 'continue' function in a loop,
where "goto Continue;" is clearer than rigging up an extra
if to skip the rest of the loop in many situations.

What is interesting to me is that I often find that people
like no-goto-Bill are actually allergic not to the notion
of a goto (which would make some sense) but to the actual
keyword GOTO, and are still quite happy to do a RETURN or
EXIT from a deeply nested structure (or even (mis)use a
RAISE statement to get a goto without using the dreaded
keyword. Now if no-goto-Bill says that he would NEVER EVER
use such horrible things, at least he is consistent :-)

I once was looking at a COBOL program, where I found

PERFORM CLOSE-FILES

in a deeply nested structure. I was puzzled because I could
not see any way the program could continue after return from
CLOSE-FILES. Digging into many levels of calls, I finally
found a STOP RUN. statement, so in fact the PERFORM could
not return. The code would have been far clearer if it had
said:

GO TO CLOSE-FILES

I asked why this was not done -- "Oh, we are not allowed
to use GO TO in our programs" was the absurd reply!


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert A Duff]

Robert Dewar <robert_dewar@my-deja.com> writes:

>    loop
> 
>     if ... then goto Continue;
> 
>    <<Continue>> null;
>    end loop;

This sort of example is more convincing if you make the if statement
more deeply nested.

- Bob

Re: No Go To's Forever!

[Robert Dewar]

In article <38D8DFC2.778826FB@cadence.com>,
  Paul Graham <pgraham@cadence.com> wrote:

> Why is there no 'continue' statement in Ada?  You've shown
> that the function of 'continue' is desirable.

Yes, the *function* of continue is desirable, but on the other
hand a continue is indeed a goto, so why not say so? That's the
other point of view, and as you see from the previous post,
some people find it clearer to use a goto here. We did discuss
this in the language revision but there was insufficient
support for this language addition.

I guess the burden here is to explain why the goto formulation
is so horrible. Yes, it slightly discourages this control flow
form, but that's probably a good idea, if you can avoid exit's
and continue's in loops without doing damage to the code that's
a good idea.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38D8E9DE.14E93706@quadruscorp.com>,
  "Marin D. Condic" <mcondic-nospam@quadruscorp.com> wrote:

> Don't fight the language! Learn to do it "The Ada Way"

Last I looked, Ada included a goto statement, it is people
who absolutely forbid goto's who are failing to follow the
above advice.

The Ada way is to use a goto if and only if it improves the
readability and maintainability of the code. Yes, you can
argue that there are zero such cases, but obviously many
programmers and the designers of the Ada language disagree
with you :-)



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38D8E9DE.14E93706@quadruscorp.com>,
  "Marin D. Condic" <mcondic-nospam@quadruscorp.com> wrote:
> Bill Dale wrote:
> >
> > Never use a GOTO - ever. At all. Anywhere. Period.

> Don't fight the language! Learn to do it "The Ada Way"

It suddenly occurs to me that people might not have read
Knuth's paper here (Structured programming with gotos) and
of course this is absolutely required reading for participating
in this thread :-)



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38D8E9DE.14E93706@quadruscorp.com>,
  "Marin D. Condic" <mcondic-nospam@quadruscorp.com> wrote:
> Bill Dale wrote:
> >
> > Never use a GOTO - ever. At all. Anywhere. Period.

> Don't fight the language! Learn to do it "The Ada Way"

It suddenly occurs to me that people might not have read
Knuth's paper here (Structured programming with gotos) and
of course this is absolutely required reading for participating
in this thread :-)



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Brian Rogoff]

On Wed, 22 Mar 2000, Robert Dewar wrote:
> In article <38D8DFC2.778826FB@cadence.com>,
>   Paul Graham <pgraham@cadence.com> wrote:
> 
> > Why is there no 'continue' statement in Ada?  You've shown
> > that the function of 'continue' is desirable.
> 
> Yes, the *function* of continue is desirable, but on the other
> hand a continue is indeed a goto, so why not say so? That's the
> other point of view, and as you see from the previous post,
> some people find it clearer to use a goto here. We did discuss
> this in the language revision but there was insufficient
> support for this language addition.

I agree with Roger Barnett who wrote that he preferred your "goto" form 
to C's continue since it made explicit the flow of control. Adding
continue to Ada would be a mistake IMO (like adding "use type" was. There, 
get those flames going ;-)

> I guess the burden here is to explain why the goto formulation
> is so horrible. 

Because the great Dijkstra said goto is bad, and therefore it is, at least
if it is spelled that way. 

Dijkstra also wrote that CS students should be kept away from a computer
for their first year and focus on pencil and paper proofs (no problem for
me, I was a Math major) and he probably didn't like Ada anyways so phooey
on him :-)

-- Brian

Re: No Go To's Forever!

[Ted Dennison]

In article <Pine.BSF.4.21.0003220851480.3555-100000@shell5.ba.best.com>,
Brian Rogoff <bpr@shell5.ba.best.com> wrote:
> Dijkstra also wrote that CS students should be kept away from a
> computer for their first year and focus on pencil and paper proofs (no
> problem for me, I was a Math major) and he probably didn't like Ada
> anyways so phooey on him :-)

I don't ever really expect to agree with Dijkstra. But that's because
Basic was my first language, therefore I am "mentally mutilated beyond
all hope of saving", or somesuch.


For the record, I think my wife would agreee with him on that point. :-)

--
T.E.D.
http://www.telepath.com/~dennison/Ted/TED.html


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Roger Barnett]

In article: <38D8EAC1.2563A49C@quadruscorp.com>  "Marin D. Condic" 
<mcondic-nospam@quadruscorp.com> writes:
> 
> Ken Garlington wrote:
> > What I want to know is, where the heck is the computed IF statement? This
> > dang language won't even let me assign numeric labels to a line!
> > 
> Or more importantly, how does one do the equivalent of an "alter"
> statement (Cobol) in Ada? What good is a goto statement if you can't
> dynamically alter its destination? I mean, how can you possibly write
> serious programs without it?

I remember using a Basic in which the parameter to the return statement
modified the return address in terms of the number of lines before or 
after the line containing the invoking GoSub statement.

A better introduction to the benefits of KISS would be difficult to find.

-- 
Roger Barnett

Re: No Go To's Forever!

[Wes Groleau]

> Now, does BASIC cause brain damage, or does brain damage cause BASIC?

I once thought it was the former.  But then Kemeny & Kurtz decided to 
release "True BASIC" years after non-programmers were finally starting 
to use other languages.  If that wasn't an odd thing to do, what is?

-- 
Wes Groleau
http://freepages.genealogy.rootsweb.com/~wgroleau

Re: No Go To's Forever!

[Larry Kilgallen]

In article <550178307wnr@natron.demon.co.uk>, Roger@natron.demon.co.uk (Roger Barnett) writes:

> I remember using a Basic in which the parameter to the return statement
> modified the return address in terms of the number of lines before or 
> after the line containing the invoking GoSub statement.
> 
> A better introduction to the benefits of KISS would be difficult to find.

And why didn't DEC's legal department sue them
for copying the PDP-6 instruction set "skip-return" mechanism ? :-)

Re: No Go To's Forever!

[Richard D Riehle]

In article <38D7B41D.B3494C6A@lmco.com>,
	Bill Dale <william.dale.jr@lmco.com> wrote:

>Never use a GOTO - ever. At all. Anywhere. Period.
>
>OK, I'll put you down as not interested in working for me.  

When Dijkstra wrote his letter to the Communications of the ACM
in 1968, "Goto Considered Harmful," lots of people read the 
title but not the letter.  COBOL and Fortran code was mangled
by programmers under the management of people who made up rules
based on the title of the article.  Early languages were not
well-designed to intelligently avoid occasional use of a "jump"
or "goto."  The early adoption of this admonition may have caused
as much damage as good in those early programs.

Later languages, starting with Pascal (some might argue for PL/I
or some other language), introduced well-formed structures with
improved scoping rules.  This eliminated many situations that might
have required a "goto."  It did not eliminate all of them.  I recall
a program where we were able to more effectively meet a deadline
by modifying one little piece of code with a "goto".  It was the
correct decision at the time.  There was no equvilaent of a 
pragma Inline for the language in use and we could not tolerate
the overhead of heavy access to a subprogram call.  We would solve
the problem differently today.

In my humble opinion, we should not design with the goto.  However,
it is sometimes an important mechanism when all other options have
been exhausted.  I have seen some excellent programs that have used
the goto, including some very recent Ada code.  In one example, the
programmer used it to emulate the "continue" statement one finds in 
some other programming languages.  I recall a posting a long time 
ago where Dr. Dewar presented an example of an FSM that lent itself
to design with a goto.

I remember someone once saying that "people who make up rules about
programming tend to be people who no longer write real programs." 
That may be an extreme point-of-view, but it is a point-of-view 
from the trenches and programming managers need to know what the
people who are laying down source code think of such doctrinaire
approaches to software development.  

Richard Riehle
richard@adaworks.com  
 

Re: No Go To's Forever!

[Pascal Obry]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 222 bytes --]


Bill Dale a �crit dans le message <38D7B41D.B3494C6A@lmco.com>...
>dis90072 wrote:
>>
>Never use a GOTO - ever. At all. Anywhere. Period.


Thansk a lot Bill, we are going to have a very lengthy thread :)

Pascal.

Re: No Go To's Forever!

[Marin D. Condic]

Bill Dale wrote:
> 
> Never use a GOTO - ever. At all. Anywhere. Period.
> 
> OK, I'll put you down as not interested in working for me.
> 
While I will concede that there are times when a goto might make sense,
I'll say this much: I have been writing software in Ada since the
original standard was published and it must total up to millions of
lines of code by now. Not only have I never once used the goto (except
possibly in experimental code designed to illustrate its use) but I have
never once encountered it in a fielded, working body of code.

Anyone who says they "need" a goto in order to code has probably not
given the problem enough thought. Or possibly, they have learned a
coding style based on assembler or Fortran and have just never been
shown how to code the same things without the goto.

Don't fight the language! Learn to do it "The Ada Way"

MDC
-- 
=============================================================
Marin David Condic   - Quadrus Corporation -   1.800.555.3393
1015-116 Atlantic Boulevard, Atlantic Beach, FL 32233
http://www.quadruscorp.com/
m c o n d i c @ q u a d r u s c o r p . c o m

***PLEASE REMOVE THE "-NOSPAM" PART OF MY RETURN ADDRESS***

Visit my web site at:  http://www.mcondic.com/

"Because that's where they keep the money."
    --  Willie Sutton when asked why he robbed banks. 
=============================================================

Re: No Go To's Forever!

[Marin D. Condic]

Ken Garlington wrote:
> What I want to know is, where the heck is the computed IF statement? This
> dang language won't even let me assign numeric labels to a line!
> 
Or more importantly, how does one do the equivalent of an "alter"
statement (Cobol) in Ada? What good is a goto statement if you can't
dynamically alter its destination? I mean, how can you possibly write
serious programs without it?

:-)

MDC
-- 
=============================================================
Marin David Condic   - Quadrus Corporation -   1.800.555.3393
1015-116 Atlantic Boulevard, Atlantic Beach, FL 32233
http://www.quadruscorp.com/
m c o n d i c @ q u a d r u s c o r p . c o m

***PLEASE REMOVE THE "-NOSPAM" PART OF MY RETURN ADDRESS***

Visit my web site at:  http://www.mcondic.com/

"Because that's where they keep the money."
    --  Willie Sutton when asked why he robbed banks. 
=============================================================

Re: No Go To's Forever!

[Robert Dewar]

In article <2000Mar22.131336.1@eisner>,
  Kilgallen@eisner.decus.org.nospam wrote:
> And why didn't DEC's legal department sue them
> for copying the PDP-6 instruction set "skip-return" mechanism
? :-)


Because there was prior art!


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <yP9C4.1507$ZT3.32509@news.pacbell.net>,
  tmoran@bix.com wrote:
>   I personally find this clearer, even if a tad longer:
>    loop
>      J := D'first;
>      while J < D'last and then D(J) >= D(J+1) loop
>        J := J+1;
>      end loop;
>      exit when J >= D'last;
>      Swap (D (J), D (J + 1));
>    end loop;

Well that's a different algorithm. It tests J against D'Last
twice as often as my formulation. Yes, perhaps a clever
compiler will be able to rescue this, but algorithmically,
this simply is not equivalent.

Actually most compilers won't fix this, so you will find that
your version actually does run noticably slower that the
original.

Yes, code duplication is one way of getting around the goto
here, but again you are changing the algorithm.

Please tackle the harder problem: Take the algorithm *I*
presented, and remove the goto without changing the sequence
of computations, and see if that result is clearer.

P.S. I don't find your changed algorithm clearer, precisely
because of the peculiar duplicated check.



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article
<Pine.BSF.4.21.0003220851480.3555-100000@shell5.ba.best.com>,
  Brian Rogoff <bpr@shell5.ba.best.com> wrote:
Adding
> continue to Ada would be a mistake IMO (like adding "use type"
was.

Ah ha, very nice Brian, a nested troll :-)


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38D9233B.D51B16A3@cadence.com>,
  Paul Graham <pgraham@cadence.com> wrote:
> I think the goto implementation of the 'continue' statement is
fragile
> in the sense that it depends on the "<<continue>> null;" being
the last
> statement in the loop. A maintainer who wasn't familar with
this idiom
> might add statements at the end of the loop body, thereby
breaking your
> construct.

But surely you would enforce this usage with a tool. There are
no general defences against sufficiently incompetent
maintainers.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38D947B9.6C50@synquiry.com>,
  Jon S Anthony <jsa@synquiry.com> wrote:
> I seem to recall that (at least in the "early days") the
designers
> put the goto statement in Ada due to a belief that there would
be
> a significant amount of machine generated Ada (presumably from
> much higher level problem descriptions).  Anyone with a clue
knows
> that in this case goto is mighty handy.


That's certainly a consideration, but if you recall that this
was the *only* reason then you recall wrong :-)

Jean Ichbiah is not goto-allergic, and agrees that there are
some legitimate uses. Once he was looking at some of my code
and asked what the gotos were there for. I said the magic
words "finite state machine", and he immediately agreed the
usage was not just acceptable but desirable. Encoding the
state into the PC is an efficient and easy to read and follow
representation of FSM's.

Actually relatively few people are completely goto allergic.
Wirth for example feels quite free to use an occasional goto
(see his coding of heap sort in the algorithms book).



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <01bf9436$9c054880$2c5101be@bthomas4663>,
  "William Thomas" <bthomas@aisvt.bfg.com> wrote:
>
>
> People can say what they may about goto's but I have an Uncle
that owns a
> software company down in Texas. He has more software in the
military
> inventory than most of the large military contractors.  His
customers love
> his stuff, its dead simple to use and solves the needs of the
end user,
> which he claims is the most important aspect of software.
>
> In all his software, which takes several CD's to back up (18
years worth)
> there is not one single 'if then else statement', nore is
there a single
> 'loop statement'.  But there's more goto's than you can shake
a stick at.
>
> I'v tried all the "convert it to Ada arguments", all of the
"people don't
> use goto's" arguments, he just laughs and keeps coding.


Yes, well there are still people writing assembler, but that's
not an argument for writing assembler!


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Chris Morgan]

"Marin D. Condic" <mcondic-nospam@quadruscorp.com> writes:

> While I will concede that there are times when a goto might make sense,
> I'll say this much: I have been writing software in Ada since the
> original standard was published and it must total up to millions of
> lines of code by now. Not only have I never once used the goto (except
> possibly in experimental code designed to illustrate its use) but I have
> never once encountered it in a fielded, working body of code.

Do not ever enter HMS ImNotTellingYou. On that boat, IIRC, there are
programs made from hundreds of thousands, perhaps millions of lines of
Ada with a high density of gotos. They naturally express a state
machine for each concurrent application process. The design says "I go
into a loop, I read my input buffer and process these messages until
some condition terminates the loop". The implementation makes that a
function which is called with the next message. Loops that persist
over several invocations of a function obviously have to be "faked"
one way or another. A goto is as good as and possibly more honest than
any other way.

-- 
Chris Morgan <cm at mihalis.net>                  http://mihalis.net
    "O gummier hum warder buffer-lore rum 
     Enter dare enter envelopes ply"

Re: No Go To's Forever!

[Ken Garlington]

"Robert Dewar" <robert_dewar@my-deja.com> wrote in message
news:8bapmj$2o0$1@nnrp1.deja.com...
>
> Here is another way of answering this that may be clearer.
>
> Yes, structured code is easier to optimize
>
> But, a goto does not make code unstructured per se

OK, sure. I thought you were making a more general statement. Maybe my
sensitivity to the issue has to do with all those years working with that
TeleSoft widget :)

Re: No Go To's Forever!

[Ken Garlington]

Let's hope he never retires or gets sick!

"William Thomas" <bthomas@aisvt.bfg.com> wrote in message
news:01bf9436$9c054880$2c5101be@bthomas4663...
>
>
> People can say what they may about goto's but I have an Uncle that owns a
> software company down in Texas.
>
> I'v tried all the "convert it to Ada arguments", all of the "people don't
> use goto's" arguments, he just laughs and keeps coding.

Re: No Go To's Forever! (I'm sorry I spoke...)

[tmoran]

>I only asked a question... now I've got replies that fill up a whole screen!
  In the absence of actual empirical evidence, everyone is free
to have strongly held opinions. ;)

Re: No Go To's Forever!

[Jeff Carter]

Richard D Riehle wrote:
> When Dijkstra wrote his letter to the Communications of the ACM
> in 1968, "Goto Considered Harmful," lots of people read the
> title but not the letter.

Quite true. For example, IIRC the letter was about program correctness
proofs, and argued that the goto made such proofs much harder, not that
the goto made human understanding or modification of software harder.
Few of us perform correctness proofs, but we avoid the goto because it
usually makes the software harder to understand and modify.

I think the message that started this was a troll; I'm sure the author
is please at the response generated.

-- 
Jeff Carter
"English bed-wetting types."
Monty Python & the Holy Grail

Re: No Go To's Forever!

[tmoran]

>Well that's a different algorithm. It tests J against D'Last
>twice as often as my formulation.
  I would hardly call that a different algorithm.  Rather a
different implementation of the same algorithm.  But if you
want to call it different...

>Actually most compilers won't fix this, so you will find that
>your version actually does run noticably slower that the
>original.
  Right.  For each call on Swap and restart of the scanning, plus
one additional time, J will be compared against D'last.  That's
going to be a relatively miniscule slowdown.  If the data is
in order, yours does N comparisons against J and mine does N+1.
If the data is sorted backwards, the worst case, yours does
N + N*(N-1)/2 + N*(N-1)*(N-2)/6 comparisons against J and mine
does an additional N*(N-1)/2+1  That's 66% more when N=2 (5 vs 3)
declining to 3% more when N=100 (171,701 vs 166,750) and so forth.
Hardly "twice as many".  And nobody who cared would use this
algorithm anyway.

>Please tackle the harder problem: Take the algorithm *I*
>presented, and remove the goto without changing the sequence
>of computations, and see if that result is clearer.

>  <<Do_It_Again>>
>     for J in 1 .. N - 1 loop
>        if D (J) < D (J + 1) then
>           Swap (D (J), D (J + 1));
>           goto Do_It_Again;
>        end if;
>     end loop;

This should be pretty close to the same run-time sequence of machine
operations, so I hope you'll accept it as "the same algorithm".
I don't find it as clear as the "changed algorithm" method.

      J := D'first;
      while J < D'last loop
         if D (J) >= D (J + 1) then   -- sorted so far
            J := J+1;                 -- continue
         else
            Swap (D (J), D (J + 1));  -- out of order, move item
            J := D'first;             -- and start over
         end if;
      end loop;

>P.S. I don't find your changed algorithm clearer, precisely
>because of the peculiar duplicated check.
  Perhaps some comments would help?

   loop
     J := D'first;
     while J < D'last and then D(J) >= D(J+1) loop -- compare
       J := J+1;                                   -- continue if in order
     end loop;
     exit when J >= D'last;    -- If at end, we can't swap, but are done.
     Swap (D (J), D (J + 1));  -- Otherwise move item
   end loop;                   -- and start over

So gotos may be appropriate for Adventure games and other FSMs, but
a goto doesn't buy much for this sort algorithm.

Re: No Go To's Forever!

[Ted Dennison]

In article <8bbsl4$ani$1@nnrp1.deja.com>,
Robert Dewar <robert_dewar@my-deja.com> wrote:
> In article <38D9233B.D51B16A3@cadence.com>,
>
> But surely you would enforce this usage with a tool. There are
> no general defences against sufficiently incompetent
> maintainers.

A tool? How would such a tool be written? It looks to me like you'd need
an Ada parser to hook it to. Not everyone has the ability or permission
to hack stuff like this into their compiler. Perhaps ASIS could help,
but not every compiler supports ASIS.

And even if you did have the tool, how are you going to force
maintainers to use it? Perhaps its a bit easier for you to make edicts
like that at ACT, but I often write code that is owned by the government
and will be maintained by whoever they decide to hire to do the job.

Really this is no more of a solution that "lint" is a solution to C's
weak type checking.

--
T.E.D.
http://www.telepath.com/~dennison/Ted/TED.html


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever! (I'm sorry I spoke...)

[Larry Kilgallen]

In article <HKhC4.6117$ZT3.38832@news.pacbell.net>, tmoran@bix.com writes:
>>I only asked a question... now I've got replies that fill up a whole screen!
>   In the absence of actual empirical evidence, everyone is free
> to have strongly held opinions. ;)

I am sure Tom did not mean to commit the group to avoiding discussion
where there _is_ empirical evidence.  :-)

Re: No Go To's Forever!

[Robert Dewar]

In article <HRkC4.1999$U95.38761@news.pacbell.net>,
  tmoran@bix.com wrote:
> >Well that's a different algorithm. It tests J against D'Last
> >twice as often as my formulation.
>   I would hardly call that a different algorithm.  Rather a
> different implementation of the same algorithm.  But if you
> want to call it different...

Of course it is different, it does a different sequence of
computations. The algorithm you give is computationally
equivalent, but you actually need to prove this, it is not
self evident! An algorithm is a prescription for a sequence
of computations, a different sequence is a different algorithm!

> That's
> going to be a relatively miniscule slowdown.  If the data is
> in order, yours does N comparisons against J and mine does
> N+1.
> If the data is sorted backwards, the worst case, yours does
> N + N*(N-1)/2 + N*(N-1)*(N-2)/6 comparisons against J and mine
> does an additional N*(N-1)/2+1  That's 66% more when N=2 (5 vs
3)
> declining to 3% more when N=100 (171,701 vs 166,750) and so
forth.
> Hardly "twice as many".  And nobody who cared would use this
> algorithm anyway.

Yes, but we are not talking efficiency here, we are talking
expression of algorithms. It is a sloppy response to change
the algorithm and then claim that pragmatically it is just
as good. That's not the point here at all. We are not trying
to write efficient sorting algorithms (this particular algorithm
is of course chosen to be space efficient).

Now let's look at your attempted rewrite:

     J := D'first;
      while J < D'last loop
         if D (J) >= D (J + 1) then   -- sorted so far
            J := J+1;                 -- continue
         else
            Swap (D (J), D (J + 1));  -- out of order, move item
            J := D'first;             -- and start over
         end if;
      end loop;

The objection here is again to the duplicated code. You have to
study this to see that the two assignments to J are identical.


Yes, in a trivial case like this, the code duplication is small,
but you must see that it is interesting that your only solutions
so far involve code duplication to get rid of the goto.

It is not at ALL clear that this is a good trade off. Additional
code, other things being equal is unlikely to be a good thing.
In a larger example, you can find the code duplication getting
worse, and even need to introduce a procedure to minimize it.

(side comment: from a pragmatic point of view, the reason we
use this algorithm is that it is short, so making it longer
by duplicating code is a bit counter productive).
Pragmatically of course, the whole idea of the


that J is always D'First. Unlike my original, where this
is evident without scanning the program, here you have a loop
whose advertised invariant.

I still find the original far clearer. Note that you felt it was
necesary to comment the reassignment to J as "start over", but
what could be clearer code to match the conceptual idea of
"start over" than going back to the beginning. Really it is
just like an instruction in a manual saying, "Now you have
completed your first reading, turn back to page 1 and start
reading again".

Let's once again look at my original:

>  <<Do_It_Again>>
>     for J in 1 .. N - 1 loop
>        if D (J) < D (J + 1) then
>           Swap (D (J), D (J + 1));
>           goto Do_It_Again;
>        end if;
>     end loop;

Just for interest, note that my version has

7 lines, 48 tokens
'
yours has

9 lines,  60 tokens

Furthermore, you have lost the fundamental point that the inner
loop is a FOR loop. We always prefer for loops to while loops
since they lead to a much clearer notion of total correctness.
Yes, it is true that the outer loop is a while loop and that
is fundamental, but I find your formulation really obscures
the fact that we have two nested loops here.

In fact I would NEVER rewrite this algorithm the way you did if
I did not have a goto. Instead I would write it this way if I
had a continue statement:

   Outer : loop
     Inner : for J in 1 .. N - 1 loop
        if D (J) < D (J + 1) then
           Swap (D (J), D (J + 1));
           continue Outer;
        end if;
     end loop Inner;
     exit Outer;
   end loop Outer;

That's also 9 lines, and 58 tokens, but preserves the essential
element
of two nested loops.

If your coding standards allow limited use of gotos to simulate
CONTINUE
then that's the best approach if you are not allowed the
original goto.

If you are writing in Ada with your hands tied behind your back
(no gotos)
then the clearest formulation is

   Continue := True;
   Outer : while Continue loop
      Continue := False;
      Inner : for J in 1 .. N - 1 loop
         if D (J) < D (J + 1) then
            Swap (D (J), D (J + 1));
            Continue := True;
            exit Inner;
         end if;
      end loop Inner;
   end loop Outer;

I am not very fond of this idiom for continue (I prefer the goto
idiom
for continue), but it is very familiar, so it seems fine.

This again avoids any code duplication, and preserves the
essential
structure of the algorithm as two nested loops.

Indeed the more I look at your rewriting, the less I like it,
you have
replaced a goto you don't like with spaghetti assignments that
obscure
the structure of the algorithm.

Replacing a for loop with a while loop with an increment is bad
in any
case. Replacing it with a while loop that plays games with the
control
variable to obtain the effect of two nested loops expressed with
one
loop at the syntactic level is really quite nasty.

I am always amazed by the extent to which people are willing to
go in
writing obscure code to avoid gotos; A triumph of form over
substance :-)


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38D9B88B.366CC1AE@acm.org>,
  jrcarter@acm.org wrote:
> Richard D Riehle wrote:
> > When Dijkstra wrote his letter to the Communications of the
ACM
> > in 1968, "Goto Considered Harmful," lots of people read the
> > title but not the letter.

>
> Quite true. For example, IIRC the letter was about program
correctness
> proofs, and argued that the goto made such proofs much harder,
not that
> the goto made human understanding or modification of software
harder.


That's not really a fair formulation of the letter (please
reread it).

But what is important is to realize that in the environment
that EWD was operating (Europe) he was not saying something
new. Everyone who ever wrote in Algol-60 knows that you don't
often need goto statements. Really the letter was an interesting
commentary on the damage that was being done in the US by using
junk languages like Fortran that lacked decent structural
alternatives to the excessive use of gotos.

It is interesting to note that in 1971 (I think that was the
year), there was a survey of programming language use in
unversities in the British Journal of Computing (I think that's
the right citation, I no longer have this at hand). It asked
what language you are teaching now, and what would you like
to teach.

Overwhelming response was

England, now teaching Algol-60, would like to teach Algol-68 (*)

Europe (certainly at that time, England did not consider itself
part of Europe, whether it does now is debatable :-)
now teaching Algol-60, would like to teach Simula-67

USA, now teaching Fortran, would like to teach Fortran

:-)

(*) a reflection of the govt policy of forcing universities to
buy ICL machines, and the excellent Algol-68 compiler available
for the ICL series at that time.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <577547997wnr@natron.demon.co.uk>,
  Roger@natron.demon.co.uk wrote:
>
> So I guess this is not the group to discuss the goto
label_variable
> construct ?


Probably not :-)
Note that most safety critical protocols ban this kind of
construct for very good reasons.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Paul Graham]

Ted Dennison wrote:
> 
> In article <8bbsl4$ani$1@nnrp1.deja.com>,
> Robert Dewar <robert_dewar@my-deja.com> wrote:
> > In article <38D9233B.D51B16A3@cadence.com>,
> >
> > But surely you would enforce this usage with a tool. There are
> > no general defences against sufficiently incompetent
> > maintainers.
> 
> A tool? How would such a tool be written? It looks to me like you'd need
> an Ada parser to hook it to. Not everyone has the ability or permission
> to hack stuff like this into their compiler. Perhaps ASIS could help,
> but not every compiler supports ASIS.

I was wondering the same thing.  I suppose AdaLint could issue a warning
for any goto statement within a loop that jumped to a label within the
loop, unless the label was immediately followed by a null statement and
an end loop.

Indeed, many of Ada's features address the "incompetent maintainer"
problem.  For instance, the problem of maintaining an if statement in C
if there is no brace:

    if (condition)
        stmt1;
        stmt2;

Here the maintainer thinks he's adding stmt2 to the then-clause of the
if statement. The Ada if syntax prevents this from happening.

Paul

Re: No Go To's Forever!

[Robert Dewar]

In article <8bd9ve$r1c$1@nnrp1.deja.com>,
  Ted Dennison <dennison@telepath.com> wrote:
> A tool? How would such a tool be written? It looks to me like
> you'd need
> an Ada parser to hook it to. Not everyone has the ability or
> permission
> to hack stuff like this into their compiler. Perhaps ASIS
> could help,
> but not every compiler supports ASIS.

Most compilers do support ASIS, and indeed this is a good
way or providing such checking tools.

This particular check of course is trivial to program, you
do not need ASIS

> And even if you did have the tool, how are you going to force
> maintainers to use it? Perhaps its a bit easier for you to
> make edicts like that at ACT, but I often write code that is
> owned by the government and will be maintained by whoever they
> decide to hire to do the job.

Maintainers who are under no constraints can do anything they
like, including replacing all your if statements with gotos.
Every significant body of code should be accompanied by a
rigorous set of coding standards, and competent maintenance
should maintain the same set of standards.

Yes, Ted, I know you have often complained of living in an
environment with limited ability compilers, lack of control
over procedures etc, but you should not assume that every
environment is like this :-)

> Really this is no more of a solution that "lint" is a solution
> to C's weak type checking.

You definitely need tools to enforce coding standards. There
are third party tools, e.g. the Xinotech Composer (hope I
am spelling name right) that can do a good job here.

As you know GNAT itself includes some extensive style checks
corresponding to a significant part of our internal coding
standards. Of course this does not include restrictions on
gotos, since we have no codified restrictions (it is merely
a feature in the language, that, like all other features,
should be used when and only when it is appropriate to do
so). Again you may complain that you work in an environment
where programmers cannot make this kind of decision correctly,
but that is not the universal situation.

Actually at ACT, we have a systematic procedure where all
changes made by one person are reviewed by another person,
for both logic and stylistic issues.

I consider such a procedure to be essential in any environment,
and it is even more important in a maintenance situation.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38DA2F9C.BAFF8C60@cadence.com>,
  Paul Graham <pgraham@cadence.com> wrote:
>  For instance, the problem of maintaining an if statement in C
> if there is no brace:
>
>     if (condition)
>         stmt1;
>         stmt2;

>
> Here the maintainer thinks he's adding stmt2 to the
then-clause of the
> if statement. The Ada if syntax prevents this from happening.

Sure, but in a C environment the above code should be ruled
out by the coding rules for indentation, which should most
certainly be checked by a tool (note that EMACS will do this
checking by automatically identing the above code as

>     if (condition)
>         stmt1;
>     stmt2;

which will help avoid this.

I consider careful choice and enforcement of stylistic coding
rules to be an essential element in high quality software
engineering.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Larry Kilgallen]

In article <8bd9ve$r1c$1@nnrp1.deja.com>, Ted Dennison <dennison@telepath.com> writes:
> In article <8bbsl4$ani$1@nnrp1.deja.com>,
> Robert Dewar <robert_dewar@my-deja.com> wrote:
>> In article <38D9233B.D51B16A3@cadence.com>,
>>
>> But surely you would enforce this usage with a tool. There are
>> no general defences against sufficiently incompetent
>> maintainers.
> 
> A tool? How would such a tool be written? It looks to me like you'd need
> an Ada parser to hook it to. Not everyone has the ability or permission
> to hack stuff like this into their compiler. Perhaps ASIS could help,
> but not every compiler supports ASIS.
> 
> And even if you did have the tool, how are you going to force
> maintainers to use it?

If I wanted to enforce use of a checking tool, I would put it into the
checkin mechanism.  Unless you are running in an environment where you
have terribly intertwined the source control and programming functions,
any mid-sized shop should not be permitting direct write-access to the
source code repository.  Programmers can check code in by using the
approved mechanism, but a COPY command will not do it.

If your code does not pass muster, it does not get checked in.

I am not offering an opinion on what the rules should be that
will be enforced, just on how to enforce them.

Re: No Go To's Forever!

[tmoran]

>Of course it is different, it does a different sequence of
  Either you disallow "a different sequence of operations",
in which case "Continue := True;" is disallowed, or you allow
irrelevant differences and thus the first of the goto-less
algorithms.  You can't have it both ways.

>Yes, but we are not talking efficiency here,
  Fine.  Sorry you brought it up.

>      J := D'first;
>       while J < D'last loop
>          if D (J) >= D (J + 1) then   -- sorted so far
>             J := J+1;                 -- continue
>          else
>             Swap (D (J), D (J + 1));  -- out of order, move item
>             J := D'first;             -- and start over
>          end if;
>       end loop;
>
> The objection here is again to the duplicated code. You have to
> study this to see that the two assignments to J are identical.
  Huh?  Do you mean the two places it does a "J := D'first;"?
Hardly what I'd call an obscure statement.

>but you must see that it is interesting that your only solutions
>so far involve code duplication to get rid of the goto.
  Yes, gotos allow you to reuse arbitrary segments of code.
I don't think that's necessarily a good thing.

> We always prefer for loops to while loops since they lead to a
> much clearer notion of total correctness.
  A maintenance programmer, on first glance, will probably see
the For 1 ..  N-1 and think "Oh, we're doing something N-1
times", which of course is false.  On second glance he'll notice
the label and realize he needs to study the code further to
figure out the exit condition.  A While both raises a red flag
that this might take a while, and shows directly the exit
condition.  I find the latter clearer.  It's also easier to see
the kind of running time with the While loop than with the two,
nested, with the inner one aborted, loops.

> but I find your formulation really obscures the fact that we have
> two nested loops here.
  Right.  I think it's a single code sequence being iterated until
everything is in order.  It keeps trying to get all the way through
D without discovering anything out of order.  If it fails, it does
a swap and keeps trying.  You think of it as two loops, a For and
an "if ...  goto" loop.

> Replacing a for loop with a while loop with an increment is bad
> in any case.  Replacing it with a while loop that plays games
> with the control variable to obtain the effect of two nested
> loops expressed with one loop at the syntactic level is really
> quite nasty.
  A While loop by nature does not have an incremented "control
variable".  It has a condition.  It is expected that the actions
inside will bring about a state of affairs where that condition
is true.  This may involve incrementing variables, setting them
to D'first, or anything else.

> I am always amazed by the extent to which people are willing to
> go in writing obscure code to avoid gotos; A triumph of form over
> substance :-)
  I don't think either of the goto-less versions was at all
obscure.  I do think the goto version requires more study to
understand what is going on and thus is more obscure.  It also
requires examination of the rest of the code to see if there are
any other gotos to the label.  I prefer the original, shorter,
goto-less version, but if the exact same sequence of operations
is also required, the second version satisfies.

Re: No Go To's Forever!

[Jeff Carter]

Robert Dewar wrote:
> Let's once again look at my original:
> 
> >  <<Do_It_Again>>
> >     for J in 1 .. N - 1 loop
> >        if D (J) < D (J + 1) then
> >           Swap (D (J), D (J + 1));
> >           goto Do_It_Again;
> >        end if;
> >     end loop;


>    Continue := True;
>    Outer : while Continue loop
>       Continue := False;
>       Inner : for J in 1 .. N - 1 loop
>          if D (J) < D (J + 1) then
>             Swap (D (J), D (J + 1));
>             Continue := True;
>             exit Inner;
>          end if;
>       end loop Inner;
>    end loop Outer;

Personally, I find both of these a bit difficult to follow due to the
lack of documentation. Maybe I'm wrong, but I think a variation on the
goto-less version is easier to document because the 2 loop are explicit:

-- Sort D into descending order
Repeat_Until_Sorted : loop
   Sorted := True; -- Assume D is sorted

   Find_Out_Of_Order_Pair : for J in D'First .. D'Last - 1 loop
      if D (J) < D (J + 1) then -- Found an out-of-order pair if True
         Swap (D (J), D (J + 1) );
         Sorted := False; -- We have not determined that D is sorted

         exit Find_Out_Of_Order_Pair; -- Repeat to see if D now sorted
      end if;
   end loop Find_Out_Of_Order_Pair;

   exit Repeat_Until_Sorted when Sorted;
   -- Did not find out-of-order pair if Sorted
end loop Repeat_Until_Sorted;

Now I can see what the algorithm is doing: It scans D looking for an
out-of-order pair of adjacent values. If it doesn't find one, then D is
sorted. If it does find one, it swaps them and repeats the entire
process. This looks like elimination of tail-recursion:

Find_Out_Of_Order_Pair : for J in D'First .. D'Last - 1 loop
   if D (J) < D (J + 1) then
      Swap (D (J), D (J + 1) );
      Sort (D);

      exit Find_Out_Of_Order_Pair;
   end if;
end loop Find_Out_Of_Order_Pair;
-- 
Jeff Carter
"Now go away or I shall taunt you a second time."
Monty Python & the Holy Grail

Re: No Go To's Forever!

[Michael P. Walsh]

Jeff Carter wrote:

> Richard D Riehle wrote:
> > When Dijkstra wrote his letter to the Communications of the ACM
> > in 1968, "Goto Considered Harmful," lots of people read the
> > title but not the letter.
>
> Quite true. For example, IIRC the letter was about program correctness
> proofs, and argued that the goto made such proofs much harder, not that
> the goto made human understanding or modification of software harder.
> Few of us perform correctness proofs, but we avoid the goto because it
> usually makes the software harder to understand and modify.
>
> I think the message that started this was a troll; I'm sure the author
> is please at the response generated.
>
> --
> Jeff Carter
> "English bed-wetting types."
> Monty Python & the Holy Grail

If you follow some of the more highly publicized comments of
Dijkstra over the years you will find he has labeled some excellent
advice with some pithy and over-simplified comments.

He also has made some comments about anthromorphizing
computer software designations that, in my opinion, are
just sheer old fogyism.

As far as trolls go, Dijkstra is something of an academic
troll.

Mike Walsh

Re: No Go To's Forever!

[Brian Rogoff]

On Thu, 23 Mar 2000, Michael P. Walsh wrote:
> Jeff Carter wrote:
> > I think the message that started this was a troll; I'm sure the author
> > is please at the response generated.
> 
> If you follow some of the more highly publicized comments of
> Dijkstra over the years you will find he has labeled some excellent
> advice with some pithy and over-simplified comments.
> 
> He also has made some comments about anthromorphizing
> computer software designations that, in my opinion, are
> just sheer old fogyism.

Yes, Ada should have been named after a computer, naming a computer 
language after a person is a digusting anthropomorphism. Indeed, even 
calling them computer "languages" is a horrible mistake according to 
Wirth. 

> As far as trolls go, Dijkstra is something of an academic
> troll.

Well sure, but his trolls are usually pretty funny, and that's quite an 
achievement considering that he's Dutch. 

Hmmm, I wonder if the original troller was Edsger Dijkstra himself? 
Probably not, he would have been more inventive, and attacked the 
omission on out mode functions, or the inclusion of ATC (tip of the 
hat to RBKD) or some other Ada "misfeature", and not tried to cover old 
ground. 

-- Brian

PS: Insert ":-)" after all but one of the preceding sentences

Re: No Go To's Forever!

[Keith Thompson]

"Marin D. Condic" <mcondic-nospam@quadruscorp.com> writes:
[...]
> Or more importantly, how does one do the equivalent of an "alter"
> statement (Cobol) in Ada? What good is a goto statement if you can't
> dynamically alter its destination? I mean, how can you possibly write
> serious programs without it?
> 
> :-)

If you want Intercal, you know where to find it.  8-)}

For those not familiar with it, Intercal does not have a goto
statement.  It has a "come from" statement.

The name Intercal, of course, stands for "Compiler Language With No
Pronounceable Acronym".

But Malbolge is much much worse.

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
Welcome to the last year of the 20th century.

Re: No Go To's Forever!

[Roger Barnett]

In article: <8bdc3i$tc1$1@nnrp1.deja.com>  Robert Dewar <robert_dewar@my-deja.com> 
writes:
> 
> In article <577547997wnr@natron.demon.co.uk>,
>   Roger@natron.demon.co.uk wrote:
> >
> > So I guess this is not the group to discuss the goto
> > label_variable construct ?
> 
> 
> Probably not :-)
> Note that most safety critical protocols ban this kind of
> construct for very good reasons.

That must depend on the associated semantics and rules, and
how they are enforced.

-- 
Roger Barnett

Re: No Go To's Forever!

[Tim Gahnstr�m]

>Gotos often make simple code hard to read. Your example is
>a good one!


Gusch I just tried my exact exampel in a lab I handed in.

I got this answer when i got it back.

"Usch you have used gotos in your lab, I can never make my fingers approve a
lab where gotos have been used"

(translated it myself so it is not the exact words).

So I assume it must be verry ugly in some peoples eys :-(

Tim

Re: No Go To's Forever!

[tmoran]

>Of course you could argue that it is easier to find your refined
>superior form from my syntactic expression with nested loops
>than from the original with a goto, and that would be an
>interesting argument to make.

  For example:
> following sorting algorithm:
>
>   <<Do_It_Again>>
>      for J in 1 .. N - 1 loop
>         if D (J) < D (J + 1) then
>            Swap (D (J), D (J + 1));
>            goto Do_It_Again;
>         end if;
>      end loop;

re-written with While instead of goto is

      J := D'first;
      while J < D'last loop
         if D (J) >= D (J + 1) then   -- sorted so far
            J := J+1;                 -- continue
         else
            Swap (D (J), D (J + 1));  -- out of order, move item
            J := D'first;             -- and start over
         end if;
      end loop;

which practically makes you trip over an obvious improvement in the
algorithm to

      J := D'first;
      while J < D'last loop
         if D (J) >= D (J + 1) then   -- sorted so far
            J := J+1;                 -- continue
         else
            Swap (D (J), D (J + 1));  -- out of order, move item
            if J > D'first then       -- and start checking at
              J := J-1;               -- the first changed spot
            end if;
         end if;
      end loop;

Re: No Go To's Forever!

[Robert Dewar]

In article <tNwC4.964$q41.1034@news.pacbell.net>,
  tmoran@bix.com wrote:
> >Of course it is different, it does a different sequence of
>   Either you disallow "a different sequence of operations",
> in which case "Continue := True;" is disallowed, or you allow
> irrelevant differences and thus the first of the goto-less
> algorithms.  You can't have it both ways.

Actually you can, but this is very standard stuff in any
formal algorithms book, not worth repeating here.
>
> >Yes, but we are not talking efficiency here,
>   Fine.  Sorry you brought it up.

No, it was not just a matter of efficiency

>
> >      J := D'first;
> >       while J < D'last loop
> >          if D (J) >= D (J + 1) then   -- sorted so far
> >             J := J+1;                 -- continue
> >          else
> >             Swap (D (J), D (J + 1));  -- out of order, move
item
> >             J := D'first;             -- and start over
> >          end if;
> >       end loop;
> >
> > The objection here is again to the duplicated code. You have
to
> > study this to see that the two assignments to J are
identical.
>   Huh?  Do you mean the two places it does a "J := D'first;"?
> Hardly what I'd call an obscure statement.

You are missing the conceptual point here entirely. I can only
recommend rereading my previous posts.

> >but you must see that it is interesting that your only
solutions
> >so far involve code duplication to get rid of the goto.
>   Yes, gotos allow you to reuse arbitrary segments of code.
> I don't think that's necessarily a good thing.
>
> > We always prefer for loops to while loops since they lead to
a
> > much clearer notion of total correctness.
>   A maintenance programmer, on first glance, will probably see
> the For 1 ..  N-1 and think "Oh, we're doing something N-1
> times", which of course is false.  On second glance he'll
notice
> the label and realize he needs to study the code further to
> figure out the exit condition.  A While both raises a red flag
> that this might take a while, and shows directly the exit
> condition.  I find the latter clearer.  It's also easier to
see
> the kind of running time with the While loop than with the
two,
> nested, with the inner one aborted, loops.
>
> > but I find your formulation really obscures the fact that we
have
> > two nested loops here.
>   Right.  I think it's a single code sequence being iterated
until
> everything is in order.  It keeps trying to get all the way
through
> D without discovering anything out of order.  If it fails, it
does
> a swap and keeps trying.  You think of it as two loops, a For
and
> an "if ...  goto" loop.
>
> > Replacing a for loop with a while loop with an increment is
bad
> > in any case.  Replacing it with a while loop that plays
games
> > with the control variable to obtain the effect of two nested
> > loops expressed with one loop at the syntactic level is
really
> > quite nasty.
>   A While loop by nature does not have an incremented "control
> variable".  It has a condition.  It is expected that the
actions
> inside will bring about a state of affairs where that
condition
> is true.  This may involve incrementing variables, setting
them
> to D'first, or anything else.
>
> > I am always amazed by the extent to which people are willing
to
> > go in writing obscure code to avoid gotos; A triumph of form
over
> > substance :-)
>   I don't think either of the goto-less versions was at all
> obscure.  I do think the goto version requires more study to
> understand what is going on and thus is more obscure.  It also
> requires examination of the rest of the code to see if there
are
> any other gotos to the label.  I prefer the original, shorter,
> goto-less version, but if the exact same sequence of
operations
> is also required, the second version satisfies.

Well if you don't understand why obscuring the two loop
structure is a problem, then I guess there is no explaining
it any further.

But there really is a very fundamental point here. If you want
to study it further, try generating the full denotational
semantics and in fact try generating the full proof conditions.
That will make things clearer I think.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38DA9505.F1AE2989@acm.org>,
  jrcarter@acm.org wrote:
> Robert Dewar wrote:
> > Let's once again look at my original:
> >
> > >  <<Do_It_Again>>
> > >     for J in 1 .. N - 1 loop
> > >        if D (J) < D (J + 1) then
> > >           Swap (D (J), D (J + 1));
> > >           goto Do_It_Again;
> > >        end if;
> > >     end loop;
>
> >    Continue := True;
> >    Outer : while Continue loop
> >       Continue := False;
> >       Inner : for J in 1 .. N - 1 loop
> >          if D (J) < D (J + 1) then
> >             Swap (D (J), D (J + 1));
> >             Continue := True;
> >             exit Inner;
> >          end if;
> >       end loop Inner;
> >    end loop Outer;
>
> Personally, I find both of these a bit difficult to follow due
to the
> lack of documentation. Maybe I'm wrong, but I think a
variation on the
> goto-less version is easier to document because the 2 loop are
explicit:

I must say it never occured to me that anyone would have trouble
following how this algorithm works. I deliberately chose
something so simple that this should not be an issue!

But if you do want to document, I suggest doing it with formal
proof conditions, you will find my point clearer if you do that.




Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Ted Dennison]

In article <yecu2hwgakn.fsf@king.cts.com>,
Keith Thompson <kst@cts.com> wrote:
> "Marin D. Condic" <mcondic-nospam@quadruscorp.com> writes:
> [...]
> > Or more importantly, how does one do the equivalent of an "alter"
> > :-)
>
> If you want Intercal, you know where to find it. 8-)}
>
> For those not familiar with it, Intercal does not have a goto
> statement. It has a "come from" statement.


The "come from" statement is actually a lot more powerful than the goto
statement though. For instance, multiple "come from"s for the same line
is one way to implement a multi-threaded algorithm.

--
T.E.D.
http://www.telepath.com/~dennison/Ted/TED.html


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <255373925wnr@natron.demon.co.uk>,
  Roger@natron.demon.co.uk wrote:

> That must depend on the associated semantics and rules, and
> how they are enforced.

That's right. But I was assuming from the questin a facility
where the expected and actual implementation is a label address
and an indirect jump.

So I was really referring to the *implementation level* here.

A parellel situation would be to say

"Ah you can't use C pointers here, because we don't allow the
use of addresses in registers at any time."

"But C does not require this implementation model"

And yes, that's true, but in practice this is the only
model likely to be implemented :-)

(after all in Ada, even access types, which are much more
abstract, are often implemented this way :-)


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <8berdq$j2p$1@nnrp1.deja.com>,
  Robert Dewar <robert_dewar@my-deja.com> wrote:
> But there really is a very fundamental point here. If you want
> to study it further, try generating the full denotational
> semantics and in fact try generating the full proof
> conditions.
> That will make things clearer I think.


To expand on this a bit. There are two loops here. Both are
trivially tail recursive. The problem is of course proving
*total* correctness in this algorithm, partial correctness
is immediately obvious.

If you separate the two loops clearly, you find that the
proof conditions are very nicely separated. You have of course
to introduce the auxiliary variable that shows how sorted the
set of data is.

You then concentrate on showing that the inner loop increments
this auxiliary variable, and that is easy to show in isolation,
i.e. by analyzing the inner loop separately.

Now once this is shown a simple monotonicity argument applied
to the outer loop proves correctness.

I continue to be sure that the version in which the two loops
are explicit is far clearer to understand and to analyze.

It is very interesting that usually we object to gotos because
they obscure the control structure, and that here the desparate
attempt to get rid of the goto actually ends up *helping* to
obscure the control structure.

I wonder why it is that people are so allergic to gotos. Oddly
this kind of furious allergy seems much more common in the US.

Perhaps it is the conviction of the more recently converted.
Those who grew up on Algol tend to have an easier time of
maintaining a balanced view point :-)



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Marin D. Condic]

Keith Thompson wrote:
> 
> But Malbolge is much much worse.
> 
Never heard of that language. I *did* hear of Befunge, which was
probably the most sick, twisted concept for a programming language I've
ever seen. Could Malbolge be related to that?

MDC
-- 
=============================================================
Marin David Condic   - Quadrus Corporation -   1.800.555.3393
1015-116 Atlantic Boulevard, Atlantic Beach, FL 32233
http://www.quadruscorp.com/
m c o n d i c @ q u a d r u s c o r p . c o m

***PLEASE REMOVE THE "-NOSPAM" PART OF MY RETURN ADDRESS***

Visit my web site at:  http://www.mcondic.com/

"Because that's where they keep the money."
    --  Willie Sutton when asked why he robbed banks. 
=============================================================

Re: No Go To's Forever!

[Richard D Riehle]

In article <yecu2hwgakn.fsf@king.cts.com>,
	Keith Thompson <kst@cts.com> wrote:

>The name Intercal, of course, stands for "Compiler Language With No
>Pronounceable Acronym".
>
>But Malbolge is much much worse.

I personally prefer the DWIM language.  All problems are solved with
no errors, there is never a run-time error, and one can define fuzzy
requirements at any point in the development or maintenance lifecycle.

DWIM = Do What I Mean.

Richard Riehle 

Re: No Go To's Forever!

[Keith Thompson]

Ted Dennison <dennison@telepath.com> writes:
[...]
> The "come from" statement is actually a lot more powerful than the goto
> statement though. For instance, multiple "come from"s for the same line
> is one way to implement a multi-threaded algorithm.

Not the way it's defined in Intercal.  If I recall correctly, only one
"come from" for a given label can be active at a time.

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
Welcome to the last year of the 20th century.

Come From Forever! (was: No Go To's Forever!)

[Ted Dennison]

In article <yecog80f1vr.fsf@king.cts.com>,
Keith Thompson <kst@cts.com> wrote:
> Ted Dennison <dennison@telepath.com> writes:
> [...]
> > The "come from" statement is actually a lot more powerful than the
> > goto statement though. For instance, multiple "come from"s for the
> > same line is one way to implement a multi-threaded algorithm.
>
> Not the way it's defined in Intercal. If I recall correctly, only one
> "come from" for a given label can be active at a time.

That is true for the old C-Intercal (Intercal73?). But for Threaded
Intercal multiple "come from"'s are the means of starting new threads. A
discussion of the proposed standard is available at
http://www.cse.unsw.edu.au/~malcolmr/threaded_intercal.html

Here is the relevant exerpt:
Initially there is only one thread. New threads are created by using
COME FROM statements. Unlike standard C-Intercal, multiple COME FROM
statements are allowed for a particular line number. If more than one
such COME FROM exists, then the thread shall split into several threads,
one for each COME FROM.

--
T.E.D.
http://www.telepath.com/~dennison/Ted/TED.html


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Martin Dowie]

speaking of proving things...

one of the reasons I had always been told for avoiding using gotos, was
that it makes a program unprovable. a) was this true; and if so, b) is
this still true?

Robert Dewar wrote:

> Of course it is different, it does a different sequence of
> computations. The algorithm you give is computationally
> equivalent, but you actually need to prove this, it is not
> self evident! An algorithm is a prescription for a sequence
> of computations, a different sequence is a different algorithm!

Re: No Go To's Forever!

[Robert Dewar]

In article <38E1F6D5.8303903C@dowie-cs.demon.co.uk>,
  Martin Dowie <martin@dowie-cs.demon.co.uk> wrote:
> speaking of proving things...
>
> one of the reasons I had always been told for avoiding using

gotos, was
> that it makes a program unprovable. a) was this true; and if

so, b) is
> this still true?


Well it's an overstatement, obviously limited forms of gotos
are totally equivalent to simple control structures and thus
neither harder or easier to prove correct.

It is true that the denotational semantics of a general goto
is very tricky. If any of you can dig out ancient materials,
have a look at the source code of Ada/Ed. This was basically
an executable denotational semantics. At this level, an
if statement was coded something like:

    if evaluate (expression) = true then
        replace if with then part
    else
        replace if with else part
    end;

the coding for goto was really complex and horrible (and
interestingly REALLY inefficient :-)

So yes, general gotos can definitely make proof of correctness
more difficult.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <38E1F6D5.8303903C@dowie-cs.demon.co.uk>,
  Martin Dowie <martin@dowie-cs.demon.co.uk> wrote:
> speaking of proving things...
>
> one of the reasons I had always been told for avoiding using

gotos, was
> that it makes a program unprovable. a) was this true; and if

so, b) is
> this still true?


Well it's an overstatement, obviously limited forms of gotos
are totally equivalent to simple control structures and thus
neither harder or easier to prove correct.

It is true that the denotational semantics of a general goto
is very tricky. If any of you can dig out ancient materials,
have a look at the source code of Ada/Ed. This was basically
an executable denotational semantics. At this level, an
if statement was coded something like:

    if evaluate (expression) = true then
        replace if with then part
    else
        replace if with else part
    end;

the coding for goto was really complex and horrible (and
interestingly REALLY inefficient :-)

So yes, general gotos can definitely make proof of correctness
more difficult.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <874s9p7jwi.fsf@deneb.cygnus.argh.org>,
  Florian Weimer <fw-usenet@deneb.cygnus.argh.org> wrote:
> Martin Dowie <martin@dowie-cs.demon.co.uk> writes:
>
> > one of the reasons I had always been told for avoiding using
gotos, was
> > that it makes a program unprovable. a) was this true;
>
> No.

I disagree as per previous note

>
> > and if so, b) is this still true?
>
> No.

I disagree as per previous node


>Why should it have changed, BTW?

Becauswe proof of correctness techniques have improved!

> One of the standard textbooks in computer science uses gotos
> quite
> heavily, and it contains correctness proofs.  Although the
proofs are
> not "formal",

informal proofs are a long way from proof of correctness. For
formal proof of correctness you need a formal specification
of the language, and that formal specification is definitely
made much more complex by the inclusion of a general goto
statement.

> and neither is the algorithm description, they are more
> substantial than the "formal" proofs which I've seen at the
> local CS department.

I have no idea what substantial means in this respect, but a
formal proof of correctness of a program is a rather definite
process, involving typically the use of a program to resolve
proof obligations (have a look for example at the Praxis tools
in this area).

> BTW: What does "formal program verification" mean in practice?

It means a formal proof of semantic equivalence of a program
with a form spec, where the languages are formally defined.

> I was told that it must involve quantifiers and other fancy
> stuff.

Well there is nothing "fancy" about a quantifier. Certainly
most proof of correctness techniques make use of predicate
algebra and set theory, and other simple basic mathematics.

> Is this true, or are rigid, but non-formal proofs considered
> sufficient

I have no idea what a "rigid" proof might be. Any non-formal
proof is suspect. For example, it is infeasible to prove any
program written in Ada 95 as such, due to a lack of a formal
definition of the semantics of Ada 95. Praxis uses a well
defined (i.e. formally defined) subset of the language for
its proof arena.

> (i.e. proofs whose formalization is easy, but tedious work,
> and which would result in proofs nobody could understand).

It is not really important if a human can understand a proof,
if all proof obligations have been satisfied algorithmicly
using a verifier.

> After attending some CS
> courses, I should probably know it, but our formal program
verification
> exercises where quite a nightmare (for example, we should
prove the
> correctness of an implementation without having the
specification).

Obviously that's not quite right as stated, the concept of
total correctness requires a specification of what correct
means.

On the other hand, you can prove certain properties of a program
without a spec, e.g. that it terminates for all inputs, or that
it cannot raise an exception etc.




>


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Come From Forever! (was: No Go To's Forever!)

[Keith Thompson]

Ted Dennison <dennison@telepath.com> writes:
[...]
> Initially there is only one thread. New threads are created by using
> COME FROM statements. Unlike standard C-Intercal, multiple COME FROM
> statements are allowed for a particular line number. If more than one
> such COME FROM exists, then the thread shall split into several threads,
> one for each COME FROM.

             hurts.  Thank
       brain               you
             hurts.  Thank
    my                         very
             hurts.  Thank
       brain               you
             hurts.  Thank
Now                                 much.
             hurts.  Thank
       brain               you
             hurts.  Thank
    my                         very
             hurts.  Thank
       brain               you
             hurts.  Thank

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
Welcome to the last year of the 20th century.

Re: No Go To's Forever!

[Florian Weimer]

Martin Dowie <martin@dowie-cs.demon.co.uk> writes:

> one of the reasons I had always been told for avoiding using gotos, was
> that it makes a program unprovable. a) was this true; 

No.

> and if so, b) is this still true?

No.  (Why should it have changed, BTW?  I wouldn't call something
unprovable unless it has been proven to be unprovable.)

One of the standard textbooks in computer science uses gotos quite
heavily, and it contains correctness proofs.  Although the proofs are
not "formal", and neither is the algorithm description, they are more
substantial than the "formal" proofs which I've seen at the local
CS department.

BTW: What does "formal program verification" mean in practice?
I was told that it must involve quantifiers and other fancy stuff.
Is this true, or are rigid, but non-formal proofs considered sufficient
(i.e. proofs whose formalization is easy, but tedious work, and which
would result in proofs nobody could understand).  After attending some CS
courses, I should probably know it, but our formal program verification
exercises where quite a nightmare (for example, we should prove the
correctness of an implementation without having the specification).

Re: No Go To's Forever!

[Robert A Duff]

Robert Dewar <robert_dewar@my-deja.com> writes:

> On the other hand, you can prove certain properties of a program
> without a spec, e.g. that it terminates for all inputs, or that
> it cannot raise an exception etc.

To me, that seems like a more useful approach in most circumstances.

- Bob

Re: No Go To's Forever!

[Robert Dewar]

In article <wcczorgbgwi.fsf@world.std.com>,
  Robert A Duff <bobduff@world.std.com> wrote:
> Robert Dewar <robert_dewar@my-deja.com> writes:
>
> > On the other hand, you can prove certain properties of a
program
> > without a spec, e.g. that it terminates for all inputs, or
that
> > it cannot raise an exception etc.
>
> To me, that seems like a more useful approach in most
> circumstances.

I would have said more practical. Obviously it is more useful
if you can indeed prove your program meets the formal
specification, but often no such exists, or it is infeasible
to carry out the full proof. On the other hand, tasks like
the ones mentioned above may be feasible even if both these
conditions hold :-)

That is why proof of correctness techniques are a valuable tool
that all programmers should have a good awareness of, even if
you are not in situations where full proofs are feasible.

Unfortunately, especially in this country, things are better
in Europe, too many programmers are allergic to formalism, and
lack the necessary training.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert A Duff]

Robert Dewar <robert_dewar@my-deja.com> writes:

> In article <wcczorgbgwi.fsf@world.std.com>,
>   Robert A Duff <bobduff@world.std.com> wrote:
> > Robert Dewar <robert_dewar@my-deja.com> writes:
> >
> > > On the other hand, you can prove certain properties of a
> program
> > > without a spec, e.g. that it terminates for all inputs, or
> that
> > > it cannot raise an exception etc.
> >
> > To me, that seems like a more useful approach in most
> > circumstances.
> 
> I would have said more practical.

Agreed.

And we should never forget that there are some things that can't be
proven because they can't be formalized, but are still important
requirements.  Eg informative error messages from a compiler.

- Bob

Re: No Go To's Forever!

[Robert Dewar]

In article <wcc7lehg5yd.fsf@world.std.com>,
  Robert A Duff <bobduff@world.std.com> wrote:
> And we should never forget that there are some things that
> can't be proven because they can't be formalized, but are
> still important requirements.  Eg informative error messages
> from a compiler.


My favorite example (as Bob knows :-) although I usually like
to say "good" error messages, since that is really the
specification (being informative is one, but not the only,
ingrediant in a good error message, for example clarity and
brevity are important too, a compiler which printed the
entire RM for every message would be VERY informative :-)

Another example is to generate a GUI with good ergonomics.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Wes Groleau]

> ...I support continue <label>
> and break <label> where the label is on a block, preferably at both
> the beginning and the end.  GoTo <label> is a much too general
> substitute.

Label:
  loop
  ....
  continue label;

is surely less error-prone than the goto equivalent, but
I see no reason to add

   break Label;

when it has no practical difference from

   exit Label;

And allowing case branches to flow into each other when 
one forgets to "break" would be very foolish.

-- 
Wes Groleau
http://freepages.genealogy.rootsweb.com/~wgroleau

Re: No Go To's Forever!

[Charles Hixson]

Wes Groleau wrote:

> > ...I support continue <label>
> > and break <label> where the label is on a block, preferably at both
> > the beginning and the end.  GoTo <label> is a much too general
> > substitute.
>
> Label:
>   loop
>   ....
>   continue label;
>
> is surely less error-prone than the goto equivalent, but
> I see no reason to add
>
>    break Label;
>
> when it has no practical difference from
>
>    exit Label;
>
> And allowing case branches to flow into each other when
> one forgets to "break" would be very foolish.
>
> --
> Wes Groleau
> http://freepages.genealogy.rootsweb.com/~wgroleau

ummm....
The reason that I used the break/continue pairing is that they exist as a
pair in C.  Of course "exit label" has the same meaning (and the meaning
of the word exit more nearly approaches the meaning of the use as a
programming construct).  I'm not particularly fond of the word "continue"
rather than "recycle" or "next" either, which both seem to carry a better
semantic mapping to the intended use, but in the language that I was
drawing from the pairing is break/continue.

Re: No Go To's Forever!

[Kenneth Almquist]

Robert Dewar wrote:
> But there really is a very fundamental point here. If you want
> to study it further, try generating the full denotational
> semantics and in fact try generating the full proof conditions.
> That will make things clearer I think.

Here is the "one loop" version of the algorithm, with statement
numbers added for reference:

1      J := D'first;
2      while J < D'last loop
3          if D (J) >= D (J + 1) then  -- sorted so far
4            J := J+1;                 -- continue
5          else
6            Swap (D (J), D (J + 1));  -- out of order, move item
7            J := D'first;             -- and start over
8          end if;
9      end loop;

To avoid special cases in the rest of the analysis, we first consider
the case where D'last < D'first.  To prove termination in this case,
we observe that when the loop is first encountered, J = D'first, which
is greater than D'last, so the loop is never executed.  Since the
loop is never executed, it cannot be an infinite loop.  To prove
correctness, we observe that  if D'last < D'first, then D has only
one possible value, which is sorted by definition.  Therefore the
value of D is unchanged by this algorithm, and D is sorted when the
algorithm terminates.

When D'first <= D'last, the loop invariant is
	(1) J in D'range and
	(2) D(D'first .. J) is sorted and
	(3) D is a permutation of the original D.

Condition (1) holds on initial entry to the loop because statement 1
makes it true.  Considition (2) holds on initial entry to the loop
because J = D'first, and a one element array is sorted by definition.
Condition (3) holds because D has not yet been modified.

The loop preserves condition (1) because the only statements that
modify J are statements 4 and 7.  The condition on the while loop
ensures means that J < D'last is a precondition to statement 4.
After adding 1 to J, J will be less than or equal to  D'last.
Statement 7 preserves condition (1) because D'first is in D'range.

The loop preserves condition (2).  Presonditions of statement 4 are
D(D'first .. J) is sorted and D(J) >= D(J+1).  Since we are sorting
in descending order (largest element first), these preconditions
imply that D(D'first .. J+1) is sorted.  Thus D(D'first .. J) is
sorted after J is incremented.  Condition (2) is true after
statement 7 because a one elment arrary is sorted by definition.

The loop preserves condition (3) because the only modifications to
D are due to the swap operation in statement 6.  A swap operation
always results in the value of D being a permuation of the previous
value of D.

On exit from the loop, we have J <= D'last (due to condition 1 of
the loop invariant) and J >= D'last due to the condition on the
while loop.  Thus J = D'last and condition 2 assures us that D is
sorted.  Condition 3 assures us that the sorted values correspond
to the original values of D.  Therefore the algorithm sorts D.

To prove termination, we observe that the variables which change
while the loop is executing are D and J.  Let S be the set of all
ordered pairs <D1, J1>, where D1 is a permutation of D and J is in
D'range.  Let Out_Of_Order(D) be the number of pairs <I, J> such
that I < J and D(I) < D(J).  (If D is sorted, then Out_Of_Order(D)
will be zero.)  We define a partial ordering on the possible values
of D by sayiung that D1 > D2 if Out_Of_Order(D1) < Out_Of_Order(D2).
The possible values of J are already ordered by the integer ">".
We now order S lexographically.  In other words, <D1, J1> > <D2, J2>
iff D1 > D2 or (D1 = D2 and J1 > J2).

Each iteration of the while loop will change the state from some state
S1 to some new state S2.  We observe that S2 > S1.  If the condition
tested on line 3 is true, then statement 4 will be executed, which
increments J and so S2 > S1.  If the condition is false, then
statement 6 will be executed.  Let M be the mapping <I1, K1> ->
<I2, K2> where
    I2 = if I1 = J then J+1 else if I1 = J+1 then J else I1
    K2 = if J1 = J then J+1 else if K1 = J+1 then J else K1
For all <I, K> such that I < K and <I, K> /= <J, J+1>, the pair
D(I) and D(K) are out of order after statement 6 is executed iff
D(I2) and D(K2) are out of order before statement 6 is executed,
order, where <I2, K2> = M(I, K).  Since M is bijective, the
number of out of order pairs, exclusive of <J, J+1>, is not
changed by the execution of statement 6.  The conditional on
line 3 ensures that the pair D(J), D(J+1) is out of order before
statement 6 is executed.  After the swap operation in statement 6
is performed, this pair will no longer be out of order, so the
number of out of order pairs will be decreased by one and again
we have S2 > S1.

The number of elements in S is finite, because S is the cross product
of a finite set of permutations (Ada does not permit an array with
an infinite number of elements to be declared) and a finite set of
integer values (again, D'range must be finite).  Since the program
state inside the loop consists of a series of nonrepeating values
chosen from a finite set, the loop must terminate.  This concludes
the proof.

Now consider the two loop version, rewritten using the 'first and
'last attributes to match the previous code:

1   <<Do_It_Again>>
2      for J in D'first .. D'last - 1 loop
3          if D (J) < D (J + 1) then
4            Swap (D (J), D (J + 1));
5            goto Do_It_Again;
6          end if;
7      end loop;

As with the previous algorithm, we cover the case where D'first >
D'last separately.  By the same argument, the algorithm terminates
with the correct result in this case.

To handle the normal case (D'first <= D'last), we start with the
"for" loop on line 2.  Rather than define a loop invariant, we
define a condition that will hold on entry to the loop and will
be preserved by the loop unless conditional on line 3 becomes true.
This "semi-invariant" is:
	(1) J in D'range, and
	(2) D(D'first .. J) is sorted

Condition (1) holds on entry to the loop because D'first is in
D'range.  Condition (2) holds on entry to the loop because a one
element array is sorted by definition.

The loop preserves condition (1) because the loop will exit when J =
(D'last - 1) + 1.  The loop preserves condition (2) unless the
conditional on line 3 becomes true.  Since we are sorting in
descending order, if the conditional on line 3 is false then when we
increment J at the end of the loop condition (2) remains true.

The program terminates when the "for" loop exits normally (as opposed
to via the goto statement).  When this happens, the "semi-invariant"
for the "for" loop will be true becase if the conditional on line 3
had become true the "for" loop would have exited via the goto statement
instead of exiting normally.  The loop conditional implies that J =
(D'last - 1) + 1 = D'last.  Thus D(D'first .. D'last) is sorted.

To complete the proof of correctness, we need to add a global
invariant to the program:
	The value of D is a permuation of the original value of D.

This invariant is true at the start of the program because the
original value of D is a permuation of itself.  The program preserves
this invariant because the only statement that modifies D is the
swap operation at line 4, and swaping preserves the invariant.

Thus the final value of D is a sorted permutation of the original
value of D, which proves partial correctness.

To prove termination, we first observe that the "for" loop on line 2
will terminate because all "for" loops terminate.  We then define an
ordering on the set of all possible values of D using the same
definition as we used for the other algorithm.  Using an argument
similar to the one we used for the "one loop" algorithm, we prove that
the value of D after statement 4 is executed will be greater than the
value of D before statement 4 is executed (using the ordering on the
values of D specified in the preceding sentence).  Since the number of
possible values of D is finite, and since no statements other than
statement 4 modify D, statement 4 can only be executed a finite number
of times.  Therefore the goto at line 5 can only be executed a finite
number of times, and both loops in the program will terminate.
Therefore, the program will terminate, which completes the proof.

This is considerably shorter than the proof for the "one loop"
algorithm, but most of the difference is because I haven't repeated
details that were spelled out in the first proof.  The proof of
termination is simpler because we don't have to worry about J; it
is now the control variable of a "for" loop.  On the other hand,
the second algorithm has a more complicated flow of control, which
complicates the proof in various small ways.  Overall I don't see
much difference in the complexity of the proofs.

What does differ, at least for me, is the difficulty of finding the
proofs.  The first proof is basicly a "fill in the blanks" proof.  I
know the overall structure of a correctness proof for a "while" loop;
the work consists of filling in the details.  The second algorithm
consists of two overlapping loops.  I've never tried to prove
correctness of an algorithm with this structure before, and thus had
no idea of how to begin to construct the proof.

I suppose that this is a matter of inexperience; if I had done more
work with correctness proofs I might have found both proofs about
equally easy to construct.  I expect that many people besides myself
lack experience in proving correctness of programs containing goto
statements, because goto statements are used infrequently in modern
software, and even less frequently in computer science texts.
				Kenneth Almquist

Re: No Go To's Forever!

[Robert Dewar]

In article <sfke9p2pivv17@corp.supernews.com>,
  ka@exit109.com (Kenneth Almquist) wrote:
> Robert Dewar wrote:
> > But there really is a very fundamental point here. If you
> > want
> > to study it further, try generating the full denotational
> > semantics and in fact try generating the full proof
conditions.
> > That will make things clearer I think.

Interesting post, but I am afraid not quite I asked for,
the most important word in my above quote here is denotational.
You gave a proof in terms of operational semantics, and I
will repeat my claim that you will more easily see the
fundamental difference between the two algorithms if you
look at things at a higher level, which is where the
denotational semantics will lead you. Basically you want
to think in terms of what the parts of the program *mean*
instead of what they *do*, and that of course is the
fundamental distinction between denotational and operational
semantics.

True the distinction is not always clear. Indeed Ada/Ed was
in many respects an operational version of a denotational
semantic definition for Ada.

At an operational level, it is fairly easy to see that the
two forms are equivalent, as you show in your proof, but
it is much more difficult to see this equivalence at the
denotational semantic level.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <sfke9p2pivv17@corp.supernews.com>,
  ka@exit109.com (Kenneth Almquist) wrote:
> Robert Dewar wrote:
> > But there really is a very fundamental point here. If you
want
> > to study it further, try generating the full denotational
> > semantics and in fact try generating the full proof
conditions.
> > That will make things clearer I think.


Incidentally, one more point, to construct the denotational
semantics of the original formulation with the goto is not
quite trivial. Obviously you don't want to describe the goto
as a general goto (the denotational semantics of general gotos
are gruesome, see the original Ada/Ed implementation for some
indication of what I mean). This goto is really a special kind
of loop construct, and indeed in a language with a bit more
general control over loops (e.g. SETL) you would not use a goto
at all for the outer loop, since it can be formulated more
clearly. Basically the goto here is a "repeat loop q" construct,
and that has a fairly simple denotational semantics. Indeed
in this particular case, you can of course get rid of the
goto by replacing it with a simple tail recursion, and the
denotational semantics should reflect such a replacement.

I sometimes wonder if people who have a hard time with gotos
in general also have a hard time with recursion. For me, the
goto that replaces a tail recursive call is a very special
case, and I regard it as simply a minor syntactic variation
on the tail recursive call (a good compiler will convert such
a tail recursion to the goto in any case). Yes, general gotos
can be a horrible mess, but the special case used here of a goto
that simply reflects a normal tail recursive structure seems
quite straightforward to me, and I see no more reason for
forbidding it than I would see for forbidding tail recursion :-)



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Dale Stanbrough]

Robert Dewar wrote:

> (a good compiler will convert such
> a tail recursion to the goto in any case)


I suppose the stand out question is...

   "is gnat a good compiler?"

dale :-)

Re: No Go To's Forever!

[David Starner]

On Tue, 18 Apr 2000 09:33:38 +1000, Dale Stanbrough <dale@cs.rmit.edu.au> wrote:
>Robert Dewar wrote:
>
>> (a good compiler will convert such
>> a tail recursion to the goto in any case)
>
>
>I suppose the stand out question is...
>
>   "is gnat a good compiler?"

Current versions of gnat will do some, but not a whole lot of tail
recursion. Future versions based on gcc 3.0 will be better at this,
or so I am lead to believe. You can always make some sample programs
and dump to assembly and check if it does where you need it to.

-- 
David Starner - dstarner98@aasaa.ofe.org
Only a nerd would worry about wrong parentheses with
square brackets. But that's what mathematicians are.
   -- Dr. Burchard, math professor at OSU

Re: No Go To's Forever!

[Robert Dewar]

In article <dale-32C6F4.09333818042000@news.rmit.edu.au>,
  Dale Stanbrough <dale@cs.rmit.edu.au> wrote:
> Robert Dewar wrote:
>
> > (a good compiler will convert such
> > a tail recursion to the goto in any case)
>
> I suppose the stand out question is...
>
>    "is gnat a good compiler?"
>
> dale :-)

gcc certainly recognizes tail recursion and optimizes it, so
the answer (in this limited respect at least :-) is yes!


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Robert Dewar]

In article <87wvlshudn.fsf@deneb.cygnus.argh.org>,
  Florian Weimer <fw-usenet@deneb.cygnus.argh.org> wrote:

> That's the point.  I didn't know that such tools are
> available.  If you use them, formal proofs suddenly make much
> more sense.

I would say that formal proofs *ONLY* make sense in the context
of a proof verifier, and this is hardly new, proof of
correctness aided by proof verifiers goes back 30-40 years as
a concept and these tools have steadily improved over time.
A company that deals with such technologies in the Ada context
is Praxis, and a visit to their website is informative.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: No Go To's Forever!

[Florian Weimer]

Robert Dewar <robert_dewar@my-deja.com> writes:

> >Why should it have changed, BTW?
> 
> Becauswe proof of correctness techniques have improved!

Well, I thought that "unprovable" and "difficult to prove" mean
different things.  But you are the native speaker, and I won't argue
with you. ;)

> > and neither is the algorithm description, they are more
> > substantial than the "formal" proofs which I've seen at the
> > local CS department.
> 
> I have no idea what substantial means in this respect, 

The "formal" proofs I was shown had severe gaps, which could have been
filled, but doing so would have made them incomprehensible (at least
for me, the only thing which I could do with such proofs is checking
step by step whether they are valid, but I'm sure I couldn't learn
anything about proof techniques or the structure of the underlying
problem from them).

> > (i.e. proofs whose formalization is easy, but tedious work,
> > and which would result in proofs nobody could understand).
> 
> It is not really important if a human can understand a proof,
> if all proof obligations have been satisfied algorithmicly
> using a verifier.

That's the point.  I didn't know that such tools are available.  If
you use them, formal proofs suddenly make much more sense.