g-rh@cca.CCA.COM (Richard Harter) (05/01/88)
In article <760@dlhpedg.co.uk> cl@datlog.co.uk (Charles Lambert) writes: >In article <27310@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes: >>f) Put the test condition in a while statement and step through the >> actions [somehow]. Unfortunately, I don't see a nice way to do >> this in C. The thought that first occurs to one is something like ... sample code deleted >This is almost a finite-state machine, and state machine programming is an >accepted idiom. Generalise it as follows: ... sample code deleted Strange throat noises resembling the mating call of a frog. [That there is a comment.] State machines are all very well in their way -- I use them myself -- but state machine logic is quintessential goto logic. The essence of state machine logic is that it doesn't matter where you came from; all that matters are the appropriate actions for this state and the appropriate state to transfer to next. From a flow control viewpoint, entering a state machine is like falling into a pin ball machine. You bang around here and there and (if there is a guaranteed halting condition) you eventually get out. Goto logic says leave and don't come back. Heirarchical logic says leave and come back. The prescription against goto's really means -- don't mix the two types of structure. -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
cik@l.cc.purdue.edu (Herman Rubin) (05/01/88)
In article <27568@cca.CCA.COM>, g-rh@cca.CCA.COM (Richard Harter) writes: ....... > >This is almost a finite-state machine, and state machine programming is an > >accepted idiom. Generalise it as follows: > State machines are all very well in their way -- I use them myself -- > but state machine logic is quintessential goto logic. The essence of > state machine logic is that it doesn't matter where you came from; all > that matters are the appropriate actions for this state and the appropriate > state to transfer to next. > > From a flow control viewpoint, entering a state machine is like falling into > a pin ball machine. You bang around here and there and (if there is a > guaranteed halting condition) you eventually get out. > > Goto logic says leave and don't come back. Heirarchical logic says leave > and come back. The prescription against goto's really means -- don't mix > the two types of structure. Sometimes what is needed is to leave with the idea of coming back, and sometimes what is needed to to leave without the idea of coming back. I have written many Fortran programs (expressed in the C idiom) using the following control structure: for(...; ....; ...) { ....; if(....)goto abc; /* normal exit */ .....;} ....; /* abnormal exit */ abc: Writing this without the goto yields code which is no easier to understand and which will have more machine gotos. Another example is the control structure of which I submitted a part with the challenge to come up with a goto-less version with comparable efficiency. I do not believe my posted reply made the net--I have not seen it. A goto-less version of the control structure of the original full code is: b=q; m=0; if(w=3) {i=3; g4=1;} else if (w even) {if (B) i=3; g4 = w/2; else i=4; g4= w/2 - 1;} else if (w=5) ABORT; else {g16 = (w-3)/4; if (w&2) i=5; else .... /* I now leave out further details */ switch(i){ case 4: .... if(...) {.....; i=2; break;} else{ ....; if (...){i=1; break;} case 3: ....; case 2: ....; case 1: ....; break; case 6: ....; i=...; break; /* elaborate code omitted */ case 5: b >>= g16; m |= b; if (....) {u = *(--geom); if EVEN(u) i=1; else i=2; break;} else {u = *(--geom); g4 = (u+1)/2; if EVEN(u) i=4; else i=3; break;} case 7:....; i=....; break; /* code omitted */ default: ....; i=...; break; /* code omitted */} Now what I did, and it obviously produces more efficient code, which I claim is not harder to understand, was to eliminate storing i unless i > 7, which is rare. Instead, the value of i is kept in the current case, which eliminates 99.99% of the storages of i and all transfers to the switch statement. I cannot see how an optimizing compiler, unless it did what I did internally, can do as well. And no flames about how complicated the code is; this is part of a program which is extremely efficient in the use of random bits; all of the variables except the initial values of b and m are current values of random variables. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (ARPA or UUCP) or hrubin@purccvm.bitnet
g-rh@cca.CCA.COM (Richard Harter) (05/02/88)
In article <767@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >In article <27568@cca.CCA.COM>, g-rh@cca.CCA.COM (Richard Harter) writes: ... sundry material that doesn't need to be posted twice ... with the final lines >> Goto logic says leave and don't come back. Heirarchical logic says leave >> and come back. The prescription against goto's really means -- don't mix >> the two types of structure. Perhaps I expressed this unclearly. In heirarchical logic each block has associated with it a statement which is to be executed after the block is completed. In inline code this is the statement immediately following the block; in procedures it is the statement after the procedure invocation. The fundamental rule of heirarchical logic is that you may only escape up the stack of successor statements. In state machine logic each state has associated with it an assertion statement that specifies the state. There is no stack of successor statements. Each state processor must determine the state of the machine after it has completed processing and transfer to that successor state. >Sometimes what is needed is to leave with the idea of coming back, and >sometimes what is needed to to leave without the idea of coming back. I >have written many Fortran programs (expressed in the C idiom) using the >following control structure: > > for(...; ....; ...) > { ....; > if(....)goto abc; /* normal exit */ > .....;} > ....; /* abnormal exit */ >abc: > >Writing this without the goto yields code which is no easier to understand >and which will have more machine gotos. Actually, this is not a good example of "leaving without the idea of coming back". The loop exit escapes the loop and control goes to the successor code of the loop. What your example really expresses is LOOP if (failure) abnormal loop escape ... if (...) normal loop escape ... END LOOP if (abnormal loop escape) ....; I am not terribly impressed with the argument that your cited code will use fewer machine goto's -- the gain in efficiency in any real example is nominal. More to the point is your argument that the code using goto's is as easy or easier to understand than code which avoids gotos. I am not so sure that I agree. I would probably code your example as abend = true; /* Default exit is abnormal */ for (...;...;...) { ....; if (...) { abend = false; break} ....; } if (abend) ...; This involves setting a flag and testing on it afterwards (a minor loss of efficiency) but I am not bothered by flags per se, and this one tells me the status of the result of computation and makes it explicit that the conditional code is executed only if there is an abnormal exit. I would rate it as clearer code, irrespective of the religious status of gotos's. >Another example is the control structure of which I submitted a part with >the challenge to come up with a goto-less version with comparable efficiency. >I do not believe my posted reply made the net--I have not seen it. I didn't go through your example in detail -- it looked equally messy regardless of whether it was expressed with or without goto's! This is not a criticism of the code, which I assume represented the actual situation to be dealt with reasonably well. As far as I can see, this is, indeed, a good example of state machine logic. Purists may shake their heads, but it is perfectly reasonable to implement state machines with goto's. The only reason for not doing so is that the goto is too weak!! Quite often you need code that runs i = result of some calculation; goto case[i]; As a paranthetical note, if you are going to implement state machine logic I would avoid depending on fallthrough and use goto's to transfer to the next state, even if it immediately follows (any reasonable compiler will optimize it out), e.g state_1: ....; goto state_2; state_2: -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
UH2@PSUVM.BITNET (Lee Sailer) (05/02/88)
Please! Let's not get into a GOTO war. I'm not saying that the previous comments on state machines and goto's were bad. I enjoyed them both. But I shudder to think where it's gonna go as soon as everyone puts in their favorite goto anecdote. lee
nevin1@ihlpf.ATT.COM (00704a-Liber) (05/04/88)
In article <27568@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes: >Goto logic says leave and don't come back. Not true. For example: FOO: goto FOO; Goto logic says you can come here anytime you need to and from anywhere you want to (within limits, of course). >The prescription against goto's really means -- don't mix >the two types of structure. I think I agree with you (I'll have to ponder this a little while longer). -- _ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194 ' ) ) "The secret compartment of my ring I fill / / _ , __o ____ with an Underdog super-energy pill." / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah
g-rh@cca.CCA.COM (Richard Harter) (05/09/88)
In article <4627@ihlpf.ATT.COM> nevin1@ihlpf.UUCP (00704a-Liber,N.J.) writes: >In article <27568@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes: >>Goto logic says leave and don't come back. >Not true. For example: > FOO: goto FOO; You misapprehend. This is not an example of 'goto' logic -- it is an implementation of a simple loop using goto's. >Goto logic says you can come here anytime you need to and from anywhere you >want to (within limits, of course). Well, this is a matter of terminology -- what precisely does one mean by the phrase 'goto logic', which is actually a neologism. Since I coined the phrase, I will claim priority and say it is my definitions that should be used :-). Seriously, however, your definition is not of much use, because what you say is true of procedure calls also. The difference is: Procedure logic: Record where you are now, transfer to a labelled block (called a procedure) and transfer back to the recorded transfer point upon completion of the block. Goto logic: Do not record where you are now; simply transfer to a labelled block (no standard name). Determine within the block the next block to be executed. The essence of 'goto logic' is that there is no return point to return to. In theory, procedure logic is stronger than simple goto logic, i.e. you can simulate an N statement program which uses gotos but not procedures with an O(N) statement program using procedures but no gotos, said procedure using program running in O(the execution time of the original program). Conversely there are programs using procedures which cannot be replaced by a program only using gotos without paying a penalty either in space or time. [The reason for this is that the return is actually a 'computed goto' which is stronger than the simple goto.] >>The prescription against goto's really means -- don't mix >>the two types of structure. >I think I agree with you (I'll have to ponder this a little while longer). It is worth mentioning that the reason for the stricture is that in 'goto logic' all control is at the same level. In truth, most real examples of goto logic are actually embedded goto logic, where there is a remembered return point that any 'goto block' can exit to. I.e. you put a state machine inside a block and exit the state machine by exiting the block. I have added comp.lang.misc to the group list and have directed followups there, because this is no longer particularly a C topic. -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.