ramsey@NCoast.ORG (Cedric Ramsey) (09/28/90)
Hello once again peoplekind. I have a question about goto's. We all know that there usage is taboo in any language but what better way do we have to implement finite state machines. A switch statement ? All a switch statement is a goto statement, internally that is. So then, maybe it is okay to implement goto's for NFA's, DFA's, and transition diagrams. Is it okay for a programmer to break a TABOO intentionally; by design?
lerman@stpstn.UUCP (Ken Lerman) (09/29/90)
In article <1990Sep28.121230.17767@NCoast.ORG> ramsey@NCoast.ORG (Cedric Ramsey) writes: -> ->Hello once again peoplekind. I have a question about goto's. We all ->know that there usage is taboo in any language but what better way ->do we have to implement finite state machines. A switch statement ? ->All a switch statement is a goto statement, internally that is. So ->then, maybe it is okay to implement goto's for NFA's, DFA's, and ->transition diagrams. -> ->Is it okay for a programmer to break a TABOO intentionally; by design? IMHO, yes. In one situation where I cared about efficiency, I felt justified in using a bunch of gotos in the same program. The code looked something like this. /* state1 is the state where some pixels may be clipped. state2 is the state where all pixels are clipped. state3 is the state where no pixels are clipped. */ state1name: { /*...*/ if(someCondition)goto state1name; else if(someOtherCondition)goto state2name; else goto state3name; } state2name: { /*...*/ if(someCondition)goto state3name; else goto state1name; } state3name: { /*...*/ if(someCondition)goto state2name; else goto state1name; } Each state was carefully commented as to its functionality. Each was a block of code which was entered at the top. At the time, I felt that the code could be written most cleanly using gotos. (That may not be true of the code above.) Of course, the other place one should feel free to use gotos is as the output of an automatic tool (such as YACC). Ken
steve@taumet.com (Stephen Clamage) (09/30/90)
ramsey@NCoast.ORG (Cedric Ramsey) writes: |Hello once again peoplekind. I have a question about goto's. We all |know that there usage is taboo in any language but what better way |do we have to implement finite state machines. A switch statement ? |All a switch statement is a goto statement, internally that is. So |then, maybe it is okay to implement goto's for NFA's, DFA's, and |transition diagrams. Probably the best discussions on this topic were published in ACM Computing Surveys Vol 6, No 4, December 1974 If you have access to a CS library, go look up this volume. In one paper, Niklaus Wirth shows why goto's are unnecessary, and in another Donald Knuth shows why "absolutely no goto's" is a needlessly harsh dictum. I strongly recommend that anyone tempted to comment on goto usage read these papers first. (They total more than 50 6"x9" pages. I cannot provide copies, so please don't ask.) -- Steve Clamage, TauMetric Corp, steve@taumet.com
ark@alice.UUCP (Andrew Koenig) (09/30/90)
In article <1990Sep28.121230.17767@NCoast.ORG>, ramsey@NCoast.ORG (Cedric Ramsey) writes: > Hello once again peoplekind. I have a question about goto's. We all > know that there usage is taboo in any language but what better way > do we have to implement finite state machines. A switch statement ? Please, please, please -- before saying anything about this, go read D. E. Knuth: Structured Programming with Goto Statements ACM Computing Surveys, January 1974 (I think) Almost everything you're thinking about saying has been covered there. Let's not rehash the whole discussion again. -- --Andrew Koenig ark@europa.att.com
henry@zoo.toronto.edu (Henry Spencer) (09/30/90)
In article <1990Sep28.121230.17767@NCoast.ORG> ramsey@NCoast.ORG (Cedric Ramsey) writes: >... what better way >do we have to implement finite state machines. A switch statement ? >All a switch statement is a goto statement, internally that is... All control structures are gotos "internally". The question is, should one use a goto or a more disciplined structure to achieve one's goals? Usually readability is a primary goal, both so you can understand the code yourself and so your successors can too. More disciplined structures win big here. Efficiency, the little tin god of incompetent programmers, is seldom crucial enough to be a decisive argument in favor of gotos, although there *are* exceptions to this. Finite-state machines are a difficult case. The standard advantage of disciplined control structures is that you can tell how you got to a particular point, and generally grasp the overall structure more easily... but in a complex finite-state machine, by definition control hops around almost at random. It is better to avoid doing things as complex FSMs if you can. If you can't, I would still say that switch gets the nod unless absolute maximum speed is vital. At least the switch enforces some small modicum of organization on what is basically a disorganized control structure (the FSM). >Is it okay for a programmer to break a TABOO intentionally; by design? As I've said in other threads, one should treat such taboos as wise guidelines rather than holy law. You should have a *good* reason for violating them, and it takes experienced judgement to decide how good a reason is. If you are new to the business, you are best advised to stick to the rules until you understand things better. -- Imagine life with OS/360 the standard | Henry Spencer at U of Toronto Zoology operating system. Now think about X. | henry@zoo.toronto.edu utzoo!henry
rh@smds.UUCP (Richard Harter) (09/30/90)
In article <5624@stpstn.UUCP>, lerman@stpstn.UUCP (Ken Lerman) writes: > In article <1990Sep28.121230.17767@NCoast.ORG> ramsey@NCoast.ORG (Cedric Ramsey) writes: > ->Is it okay for a programmer to break a TABOO intentionally; by design? > > IMHO, yes. In one situation where I cared about efficiency, I felt > justified in using a bunch of gotos in the same program. The code looked > something like this. [example of state machine code deleted.] Actually, there is a good chance that you lost efficiency rather than gained it. Many optimizing compilers don't deal well with goto's. As I understand it, they make the register assignment task messy and their presence invalidates many assumptions used in optimizing code in blocks. Switches for contiguous integer ranges typically optimize out to a range check and a branch from a jump table. The 3-4 instructions that you pay for a range check and two jumps will be outweighed by extra instructions induced by less efficient optimization. In any case the potential gain is negligible unless the state execution code is mostly one liners. I have nothing against goto's -- I average about 1 per 20,000 lines of code. However IMHO you should scrupulously avoid them in code which is intended to be both portable and efficient. -- Richard Harter, Software Maintenance and Development Systems, Inc. Net address: jjmhome!smds!rh Phone: 508-369-7398 US Mail: SMDS Inc., PO Box 555, Concord MA 01742 This sentence no verb. This sentence short. This signature done.
raymond@math.berkeley.edu (Raymond Chen) (10/01/90)
In article <11403@alice.UUCP>, ark@alice (Andrew Koenig) writes: > D. E. Knuth: Structured Programming with Goto Statements > ACM Computing Surveys, January 1974 (I think) ^^^^^^^ December 1974. Vol 6, No 4.
pmk@craycos.com (Peter Klausler) (10/01/90)
In article <201@smds.UUCP> rh@smds.UUCP (Richard Harter) writes: >... Many optimizing compilers don't deal well with goto's. As I understand >it, they make the register assignment task messy and their presence >invalidates many assumptions used in optimizing code in blocks. Switches >for contiguous integer ranges typically optimize out to a range check and >a branch from a jump table. The 3-4 instructions that you pay for a range >check and two jumps will be outweighed by extra instructions induced by >less efficient optimization. In any case the potential gain is negligible >unless the state execution code is mostly one liners. Within a basic-block flow graph built by an "optimizing" compiler, everything's a "goto", regardless of whether it was coded as "break", "continue", "if", or whatever. The messiness that can come from a "goto" is that they can be used to construct so-called irreducible flow graphs, which are admittedly tougher to analyze. Irreducible flow graphs arise from loops with multiple entries. Example: if (...) goto A; B: ... A: if (...) goto B; In real life C code, you're going to produce irreducible graphs only when you use "goto" to jump into a "for"/"while"/"do" loop, which is bad practise for other, more obvious, reasons. Irreducibility would be the only excuse for "less efficient [sic] optimization" in a real compiler. Further, the "3-4 instructions that you pay for a range check and two jumps" cost different amounts on different platforms. On a Cray, a "switch" involves falling through the two range check jumps, a load from the switch table, and an indirect jump; none of these are cheap, especially the load. I personally use "goto" most often in search loops like this: for (...; ...; ...) if (...) goto found; fprintf (stderr, "didn't find it!\n"); abort (); found: ... Fast, clear, and often vectorizable. -Peter Klausler, Cray Computer Corp. compiler development (pmk@craycos.com)
henry@zoo.toronto.edu (Henry Spencer) (10/02/90)
In article <1990Sep30.190344.25031@agate.berkeley.edu> raymond@math.berkeley.edu (Raymond Chen) writes: >> D. E. Knuth: Structured Programming with Goto Statements >> ACM Computing Surveys, January 1974 (I think) > ^^^^^^^ > December 1974. Vol 6, No 4. Do note, though, that a lot of Knuth's "just gotta have a goto" examples go away when looked at through the right tools. For example, his syntax- scanning example clearly shows that he'd never heard of pushback. :-) -- Imagine life with OS/360 the standard | Henry Spencer at U of Toronto Zoology operating system. Now think about X. | henry@zoo.toronto.edu utzoo!henry
asylvain@felix.UUCP (Alvin E. Sylvain) (10/03/90)
In article <1990Sep28.121230.17767@NCoast.ORG> ramsey@NCoast.ORG (Cedric Ramsey) writes: > >Hello once again peoplekind. I have a question about goto's. We all >know that there usage is taboo in any language but what better way >do we have to implement finite state machines. A switch statement ? >All a switch statement is a goto statement, internally that is. So >then, maybe it is okay to implement goto's for NFA's, DFA's, and >transition diagrams. > >Is it okay for a programmer to break a TABOO intentionally; by design? Natch, it's OK. A coupla' points to consider, tho: 1) Just because a switch is implemented as a goto has no bearing on the problem. For, While, If, etc., are all implemented with goto's in one aspect or another. However, most of us don't have to *read* the implemented machine code. 2) Foo, I wish I'd saved the other fellow's posting where he talks about "Holy Law". Very appropriate. The point is, goto's are a negative impact on readability and maintainability of software, and, as such, should be avoided. But only avoided to the point where the alternatives become a negative impact, not beyond. There exist situations where the goto *is* the best solution, or at least the most expedient. I.e., don't spend a week trying to design-out a single goto ... If you need them, *comment* them for the next guy. (E.g., "/* this is an error-exit goto */") Summary: I think software development is an art, like painting or writing, etc. I once heard a artist (I don't remember who, but I believe he was a playwriter) say something to the effect: "To be great, you must have a style. To have a style, you must break some rules. But you must first *know* the rules!" -- -=--=--=--"BANDWIDTH?? WE DON'T NEED NO STINKING BANDWIDTH!!"--=--=--=- "If you come in at 10am and leave at 7pm one day, then come in at 6am and leave at 3pm the next day, people will deduce that you are coming in at 10am and leaving at 3pm every day." --- me
wald@theory.lcs.mit.edu (David Wald) (10/07/90)
In article <465@taumet.com> steve@taumet.com (Stephen Clamage) writes: >Probably the best discussions on this topic were published in > ACM Computing Surveys > Vol 6, No 4, December 1974 >If you have access to a CS library, go look up this volume. In one >paper, Niklaus Wirth shows why goto's are unnecessary, and in another >Donald Knuth shows why "absolutely no goto's" is a needlessly harsh >dictum. Also recommended reading on this topic, especially if you feel very strongly about it: "A Linguistic Contribution to GOTO-less Programming", by R. Lawrence Clark, in the December 1973 issue of Datamation, reprinted in the April 1984 issue of Communications of the ACM (vol. 27, no. 4, pp 349-350). This article describes an alternative to the "harmful" goto construct, called "come from". -David -- ============================================================================ David Wald wald@theory.lcs.mit.edu ============================================================================