[comp.lang.c] Re^2: Oh noooooo!!

raph@tigger.planet.bt.co.uk (Raphael Mankin) (09/12/89)

Before most readers of this new group were born, Dijkstra wrote an
article called Uncontrolled use of Goto Considered Harmful. It was
		^^^^^^
not called 'Goto considered Harmful'.

It is possible to program without goto provided taht you have a
do-forever and an if available, but it remains true that the goto is
sometimes the best way of doing things.
              ^^^^

Personally, I restrict gotos to forward trasnfers - this minimises the
risk of infinite loops; and to the multi-level break/continue or error
escape cases. After some 20 yewars of programming I have not found
this to cause any problems and the code remains readable.

The issue of use/non-use of goto is not one of theology. What matters
is
	does it work
	is it safe
	is it readable.
Nothing else matters.
-- 
Raphael Mankin
raph@planet.bt.co.uk

knighten@pinocchio (Bob Knighten) (09/14/89)

In article <556@tigger.planet.bt.co.uk>, raph@tigger (Raphael Mankin) writes:
>
>Before most readers of this new group were born, Dijkstra wrote an
>article called Uncontrolled use of Goto Considered Harmful. It was
>		^^^^^^
>not called 'Goto considered Harmful'.
>

Well, actually Dijkstra wrote a Letter to the Editor of the Communications of
the ACM (CACM, vol. 11, no. 3 (March 1968) pp. 147-148) which has the heading
"Go To Statement Considered Harmful".  And the second sentence of that letter
contains the statement ". . . and I have become convinced that the go to
statement should be abolished from all ``higher level'' programming languages 
(i.e. everything except, perhaps, plain machine code)."

That raised the adrenalin level!
--
Bob Knighten                        Encore Computer Corp.
(508) 460-0500 ext. 2626	    257 Cedar Hill St.        
                                    Marlborough, MA 01752
Internet:  knighten@encore.com      UUCP:  {bu-cs,decvax,gould}!encore!knighten

buck@siswat.UUCP (A. Lester Buck) (09/14/89)

In article <556@tigger.planet.bt.co.uk>, raph@tigger.planet.bt.co.uk (Raphael Mankin) writes:
> 
> Before most readers of this new group were born, Dijkstra wrote an
> article called Uncontrolled use of Goto Considered Harmful. It was
> 		 ^^^^^^
> not called 'Goto considered Harmful'.
> -- 
> Raphael Mankin
> raph@planet.bt.co.uk

This is incorrect.  Following the recent suggestion in this newsgroup, I
pulled down my copy of "Classics in Software Engineering" (a collection of
reprints) and started to read Knuth's 1974 paper _Structured Programming
with go to Statements_.  Knuth carefully traces the history of the goto
debate, and lists three items before Dijkstra's name is mentioned.
Dijkstra's first discussion of goto's was in a paper entitled "Programming
Considered as a Human Activity" in 1965, also included in the above
mentioned book.  A few more people made comments about the desirablility
of goto's, but then

	"The next chapter in the story is what many people regard as the
	first, because it made the most waves. Dijkstra submitted a short
	article to _Communications of the ACM_ devoted entirely to a
	discussion of _go to_ statements.  In order to speed publication,
	the editor decided to publish Dijkstra's article as a letter, and
	to supply a new title, "Go to statement considered harmful."  This
	note rapidly became well-known; it expressed Dijkstra's conviction
	that _go to_'s "should be abolished from all 'higher level'
	programming languages (i.e., everything except, perhaps, plain
	machine code)....  The _go to_ statement as it stands is just too
	primitive; it is too much an invitation to make a mess of one's
	program."  He encouraged looking for alternative constructions
	which may be necessary to satisfy all needs.  Dijkstra also recalled
	that Heinz Zemanek had expressed doubts about _go to_ statements
	as early as 1959;..."


The "Classics" reprint book also includes Dijkstra's "Go To Statement
Considered Harmful", as well as "A Case Against the GOTO" by W. A. Wulf
and "A Case for the GOTO" by M. E. Hopkins.


Knuth's paper is excellent, including classic lines such as:

	"It is impossible to read the recent book _Structured Programming_
	[by Dahl, Dijkstra, and Hoare, 1972] without having it change
	your life."

and my favorite

	"At the IFIP Congress in 1971 I had the pleasure of meeting
	Dr. Eiichi Goto of Japan, who cheerfully complained that he was
	always being eliminated."


Classics in Software Engineering
Ed. by Edward Nash Yourdon
ISBN 0-917072-14-6
Yourdon Press, 1979


-- 
A. Lester Buck		...!texbell!moray!siswat!buck

news@ism780c.isc.com (News system) (09/14/89)

In article <556@tigger.planet.bt.co.uk> raph@tigger.planet.bt.co.uk (Raphael Mankin) writes:
>
>Before most readers of this new group were born, Dijkstra wrote an
>article called Uncontrolled use of Goto Considered Harmful. It was
>		^^^^^^
>not called 'Goto considered Harmful'.
>

Sorry, but that is not true.  The article appears on page 147 of the
March 1968 issue of the CACM.  The EXACT title is (I have the issue before
me as I write):

       "Go To Statement Considered Harmful"

Note that it is the GO TO STATEMENT that is considered harmful.  The thrust
of the article was (again I quote):

     "More recently I discovered why the use of the GO TO statement statement
     has such disastrous effects, and I have become convinced that the GO TO
     statement should be abolished from all "higher level" programming
     languages (i.e. everything except perhaps plain machine code)."

   Marv Rubinstein

rpb@dasys1.UUCP (Robert Brady) (09/22/89)

	Of course if someone said it before I was born this means it must
be true. That's why I never use gotos when not on airplanes on a flat planet.
Sorry, but Dijkstra was wrong. How can you attempt to write a program that
will be optimized in machine code by using constructs that are alien to 
machine code? The only validity I can lend to the abhorrence for gotos so 
prevalent today is that they are misused by beginning programmers. This does
does not mean in any way that I should not be able to use them.

> "More recently I discovered why the use if the GOTO  statement
> has such disastrous effects..."


-- 
+---------------------+------------------------------------------------------+
|  Robert Brady       | rpb@dasys1.UUCP                                      |
|     Logic.          | !cmcl2!{ccnysci,cucard,hombre}!dasys1!rpb            | 
|"An elective despotism was not the government we fought for..." T.Jefferson |

flaps@dgp.toronto.edu (Alan J Rosenthal) (09/23/89)

rpb@dasys1.UUCP (Robert Brady) writes:
>Sorry, but Dijkstra was wrong. How can you attempt to write a program that
>will be optimized in machine code by using constructs that are alien to 
>machine code?

That's what is called a "high-level language".  Read a book about programming
languages, or compilers.  The whole point of a high-level language is to write
a program using constructs that are alien to machine code.  And, read a book
about optimizing compilers.  Goto statements make programs harder to optimize,
not easier.

ajr

gwyn@smoke.BRL.MIL (Doug Gwyn) (09/23/89)

In article <10756@dasys1.UUCP> rpb@dasys1.UUCP (Robert Brady) writes:
>Sorry, but Dijkstra was wrong. How can you attempt to write a program that
>will be optimized in machine code by using constructs that are alien to 
>machine code?

Actually, most Algol-like languages can be better optimized with less
effort if GOTOs are outlawed.  It has almost nothing to do with whether
the machine language supports PC reloads (aka branch instructions).

hjm@cernvax.UUCP (Hubert Matthews) (09/27/89)

In article <11132@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes:
>In article <10756@dasys1.UUCP> rpb@dasys1.UUCP (Robert Brady) writes:
>>Sorry, but Dijkstra was wrong. How can you attempt to write a program that
>>will be optimized in machine code by using constructs that are alien to 
>>machine code?
>
>Actually, most Algol-like languages can be better optimized with less
>effort if GOTOs are outlawed.  It has almost nothing to do with whether
>the machine language supports PC reloads (aka branch instructions).

Programs that don't use GOTOs generate only reducible flow-graphs;
programs that use GOTOs may generate irreducible flow-graphs.
Optimising a reducible flow-graph can be done without having to resort
to full data-flow analysis (just consider the problem of trying to
find loop-invariant expressions if you don't know trivially where the
loops are).  Thus, the optimiser can be simpler for languages such as
C, PASCAL and Modula-2 compared to FORTRAN.  Take a look in the Dragon
Book (Aho et al.) for more details.
-- 
Hubert Matthews      ...helping make the world a quote-free zone...

hjm@cernvax.cern.ch   hjm@vxomeg.decnet.cern.ch    ...!mcvax!cernvax!hjm

jlg@lanl.gov (Jim Giles) (09/27/89)

From article <1098@cernvax.UUCP>, by hjm@cernvax.UUCP (Hubert Matthews):
> Programs that don't use GOTOs generate only reducible flow-graphs;
> programs that use GOTOs may generate irreducible flow-graphs.
> [...]        Thus, the optimiser can be simpler for languages such as
> C, PASCAL and Modula-2 compared to FORTRAN.  Take a look in the Dragon
  ^
> Book (Aho et al.) for more details.

The problem here is that C allows GOTOs in all the same contexts
that Fortran does.  More importantly, C allows GOTOs that even 
Fortran doesn't.  For example:

   C                                          Fortran

   if (a<b) {                               IF (A.LT.B) THEN
      ...                                      ...
lab1: ...                             10    CONTINUE
      ...                                      ...
   }                                        ENDIF
...                                         ...
goto lab1                                   GOTO 10

This jump is allowed by C but not by Fortran.  In fact, even the
proposed C standard has no constraints on the target of a GOTO
other than that the target label must be within the same program
unit as the GOTO statement.

So, the optimizer for C _cannot_ be any simpler than that for
Fortran.

amull@Morgan.COM (Andrew P. Mullhaupt) (09/27/89)

In article <14052@lanl.gov>, jlg@lanl.gov (Jim Giles) writes:
> 
> The problem here is that C allows GOTOs in all the same contexts
> that Fortran does.  More importantly, C allows GOTOs that even 
> Fortran doesn't.  For example:
> 
>    C                                          Fortran
> 
>    if (a<b) {                               IF (A.LT.B) THEN
>       ...                                      ...
> lab1: ...                             10    CONTINUE
>       ...                                      ...
>    }                                        ENDIF
> ...                                         ...
> goto lab1                                   GOTO 10
> 
> This jump is allowed by C but not by Fortran.  In fact, even the
> So, the optimizer for C _cannot_ be any simpler than that for
> Fortran.

 If you have Sun's f77 "fortran" compiler, or any other BSD "fortran"
monstrosity, do not expect to have the preceding construct outlawed.
F77 forbids it, but f77 on Suns will compile and run the following
"outflawed" program:

      END DO
      IF (I.LT.100000) GOTO 2
      DO 1 I = 3, 10
    2 WRITE(*,*) I
    1 CONTINUE
      STOP
      END

with the output 0, 1, 2, ... 10. Now you can twiddle with the useless
"-ansi" switch on the compiler all you want. I believe that the last
few postings in this thread are essentially correct: FORTRAN is a
more optimizable language than C. However, almost all UNIX based f77
implementations use the same intermediate language as the C compiler,
and the identical code generation. I believe that this economy measure
may have introduced limitations on the optimization of the FORTRAN, 
and perhaps even on some aspects of the F77 standard flow of control
conformance, but the main point is that FORTRAN is simpler than C to
optimize, but "fortran" may not be.

Flaming replies that comp.lang.c is not the right group for this post
will be ignored on the grounds that this post is about the detrimental
side effect of the C language in the UNIX environment. All other 
flaming replies will be cheerfully extinguished...

Later,
Andrew Mullhaupt
Disclaimer: Morgan Stanley bears no responsibility for any opinions
expressed in this posting.

hjm@cernvax.UUCP (Hubert Matthews) (09/27/89)

In article <14052@lanl.gov> Jim Giles writes:
>
>The problem here is that C allows GOTOs in all the same contexts
>that Fortran does.  More importantly, C allows GOTOs that even 
>Fortran doesn't.  For example:
>[... perfectly correct example of C v. FORTRAN GOTOs...]
>So, the optimizer for C _cannot_ be any simpler than that for
>Fortran.

GOTOs are ubiquitous in FORTRAN and uncommon in C.  A FORTRAN compiler
needs to be able to optimise in the face of GOTOs, whereas a C
compiler is rarely called upon so to do.  Data-flow analysis is
complex and the need for it is justified for FORTRAN compilers but not
for C compilers owing to the relative frequencies of occurrence of
GOTOs in the two languages.


-- 
Hubert Matthews      ...helping make the world a quote-free zone...

hjm@cernvax.cern.ch   hjm@vxomeg.decnet.cern.ch    ...!mcvax!cernvax!hjm

djones@megatest.UUCP (Dave Jones) (09/28/89)

From article <1100@cernvax.UUCP>, by hjm@cernvax.UUCP (Hubert Matthews):
...
> 
> GOTOs are ubiquitous in FORTRAN and uncommon in C.  A FORTRAN compiler
> needs to be able to optimise in the face of GOTOs, whereas a C
> compiler is rarely called upon so to do.

Statements like this never fail to mystify me.

So what if program A is rarely called upon to do task B?  If it is ever
called on to do it, will it do it?

Please clarify.

bill@twwells.com (T. William Wells) (09/28/89)

In article <14052@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
: So, the optimizer for C _cannot_ be any simpler than that for
: Fortran.

Sure it can. All it has to do is refuse to try to optimize once a
goto is encountered. All too many do just that.

---
Bill                    { uunet | novavax | ankh | sunvice } !twwells!bill
bill@twwells.com

wallace@hpdtl.HP.COM (David E. Wallace) (09/29/89)

In article <14052@lanl.gov>, jlg@lanl.gov (Jim Giles) writes:
> This jump is allowed by C but not by Fortran.  In fact, even the
...
> So, the optimizer for C _cannot_ be any simpler than that for
> Fortran.

Sure it can.  Just turn off flow-based optimization for any program unit that
contains a goto (or that contains a backwards goto, or that contains a goto
that is not trivially recognizeable as a loop exit, or whatever).
Since 99.999% of all C program units contain no gotos, this is a perfectly
viable option for a C compiler.  The same cannot be said of Fortran: any
Fortran optimizer that followed this strategy would find that it wasn't doing
enough optimization to be generally useful.

Dave W.

wallace@hpdtl.HP.COM (David E. Wallace) (09/30/89)

> jones@megatest.UUCP (Dave Jones)
> From article <1100@cernvax.UUCP>, by hjm@cernvax.UUCP (Hubert Matthews):
> ...
> > 
> > GOTOs are ubiquitous in FORTRAN and uncommon in C.  A FORTRAN compiler
> > needs to be able to optimise in the face of GOTOs, whereas a C
> > compiler is rarely called upon so to do.
> 
> Statements like this never fail to mystify me.
> 
> So what if program A is rarely called upon to do task B?  If it is ever
> called on to do it, will it do it?
> 
> Please clarify.

An optimizer is required to produce correct code for all possible legal inputs.
If it doesn't do this, it has a bug.

An optimizer is not required to produce optimal code for all possible legal
inputs.  Thus it is perfectly acceptable for an optimizer to drop back
and punt in rare cases, by passing the (correct) unoptimized code
through unchanged.  If you can gain some other design win by doing so
(faster compiles, faster time to market, better results on more common cases),
it makes sense to do this.  This is just a performance tradeoff issue.

Walter Bright notes that goto's may be more common in machine-generated
code, such as the output of lex and yacc.  This is true, and it is a reason
to not ignore goto-containing code completely.  Any optimizations that can
be done easily should be done.  The point is that you don't need to optimize
every possible pathological case.

Dave W.

mcdonald@aries.uiuc.edu (Doug McDonald) (10/01/89)

If data-flow analysis is made difficult by goto-s, why should be any different
for a program restructured, probably by use of 
flag variables (which are exactly equivalent to assigned-goto-s
in Fortran). C is sufficiently rich in constructs that goto-s
are used only for really pathological cases (at least that is how I
use them, and I really love to tweek the toes of goto-haters) such as
multilevel breaks and genuine, uncontrollable, spaghetti logic.

I have two programs in which the control structure is so awful
(they parse English!) that the only hope of de-goto-ing them is
to use a state variable and a huge, really huge, switch statement
in which the goto-labels are replaced by case-labels. Why would
this be easier to understand for purposes of optimization: an
optimizer still should figure out that certain labels can follow
only after the execution of certain other code, and not dump
(for example) all the variables it has put in registers out of them.

Do C optimizers give up on switch statements also?

Doug McDonald (mcdonald@aries.scs.uiuc.edu)
(Aries is our new Mips machine. I hope this address works - it
should if you name resolver is working right. Aries has a twin,
Taurus. If we get a third, I am going to demand that it follow
the same line and be Camelopardalus!)

bright@Data-IO.COM (Walter Bright) (10/03/89)

In article <1989Sep30.172817.17852@ux1.cso.uiuc.edu> mcdonald@aries.scs.uiuc.edu (Doug McDonald) writes:
<If data-flow analysis is made difficult by goto-s, why should be any different
<for a program restructured, probably by use of 
<flag variables.

Data-flow analysis is not made difficult by goto's. Simple and powerful
algorithms exist to deal with them.

Replacing goto-s with flag variables makes it very difficult to optimize,
and I know of no optimizer that is able to convert them into equivalent
goto's.

P.S. My optimizer works by initially converting whiles, fors, dos, etc.
into goto's! The internal structure is a graph of expressions connected
by goto's. All memory of high level constructs is lost. Graph analysis is
used to determine loops and such.