soft_eng%mwvms@MITRE.ARPA (05/22/88)
-------- Received: From MWULTRIX(NIGAM) by MWVMS with RSCS id 0990 for SOFT_ENG@MWVMS; Thu, 19 May 88 20:53 EDT Full-Name: Alok Nigam To: soft_eng%mwvms@mitre.arpa Subject: Soft-Eng-Digest Date: Thu, 19 May 88 19:21:38 EDT From: nigam Soft-Eng Digest Thu, 19 Apr 88 V: Issue 3 Today's Topics: Control flow and common sense (5 msgs) gotos State Machines, The Ultimate Goto (5 msgs) ---------------------------------------------------------------------- Date: 2 May 88 14:28:24 GMT From: ihnp4!ihlpf!warren@ucbvax.Berkeley.EDU (Montgomery) Subject: Control flow and common sense Control flow seems to be an area that brings out the worst in people. There isn't one set of control structures that is right for every problem. If you want to look for the ultimate in gotos, look at some of the constructs that the AI folks use: Production rules, pattern directed invocation, blackboards, etc. That doesn't mean that these are bad, just that the problems they are solving lend themselves to different kinds of control flow. One of the most difficult to understand programs I ever came accross was a "gotoless" program written shortly after the original Djikstra article. It was a printer driver that consisted of a large outer loop "while (not_done)" and a loop body that consisted of deeply nested if-then-else's. At the leaves of the if-then-elses were statements that did something and generally set variables tested by the if-then-elses, possibly also setting the loop condition. The structure being implemented was actually a finite state machine, and fairly simple to understand as such, but impossible to discern from the style in which it was written. What I'd like to suggest is this: 1) Use control structures that are appropriate for your application and readily understood. For many problems, loops and conditionals are natural control structures, but some applications naturally call for finite state machines, production rules, or more exotic strucutres. 2) Use an implementation that makes that control structure explicit. Implementing a finite state machine obscurely to avoid gotos doesn't make the program more maintainable. ------------------------------ Date: 3 May 88 01:02:15 GMT From: EGNILGES@pucc.princeton.edu (Ed Nilges) Subject: Control flow and common sense In article <4605@ihlpf.ATT.COM>, warren@ihlpf.ATT.COM (Montgomery) writes: > > 2) Use an implementation that makes that control structure > explicit. Implementing a finite state machine obscurely to > avoid gotos doesn't make the program more maintainable. > >-- > If you are not too concerned about efficiency, the best way to implement a finite state machine is as a two-dimensional table searched by old state and current symbol, yielding new state and perhaps some representation of an action to be carried out. The neat thing is that your end users can check or even specify the table, and (if your project is sufficiently complex) the table can serve as the basis for tools that draw finite-state diagrams, check test coverage, or even produce automated documentation. I used this technique for a now-bought-out switch manufacturer that needed to simulate one of their PBXs using a Cobol program, running on the customer's mainframe, in order to produce accurate usage reports and bills. The Cobol program had to be general, running on unpredictable machines. It didn't have to be fast. My predecessor had written a GOTO-ridden monstrosity that was ridden with bugs and impossible to understand. In the space of two months or so, a customer team and I collaborated on a table-based program that worked with every case that the customer could throw at it. The tables were clearly demarcated in the program data division, such that the switch engineers and I could clearly communicate about how the PBX worked. Gotos could have been used to implement the finite state auto- maton, but this would have tempted maintenance people to add gotos outside of the table interpreter. I've seen a compiler generated using syntax-driven techniques where subsequent changes have obscured the designer's intent and changed the language compiled because the maintainers did not have any access to the syntax tables; this is a similar situation. I'm not saying gotos are bad; the optimal and most maintainable method, IF you have cycles to burn, is a table interpreter. The technique was more popular when storage was expensive (Ref 1), since a dense representation could be used for the table. However, Gerald Weinberg describes an incident (Ref 2) in compu- s ting's early days when the method of table interpretation was used to increase quality and user/programmer communication. Poor mana- gers, in this writer's experience, have always hated the technique, since it seems to cut them out of the user/programmer communication loop; good managers like it, because it almost always works well. REFERENCES 1. Brooks, Frederick R., THE MYTHICAL MAN-MONTH: Essays in Software Engineering. Reading, MA, 1975: Addison-Wesley Publishing Company. Page 102. 2. Weinberg, Gerald M., THE PSYCHOLOGY OF COMPUTER PROGRAMMING. New York, NY, 1971: Van Nostrand Reinhold. Page 17. ------------------------------ Date: 4 May 88 13:17:15 GMT From: uh2%psuvm.BITNET@jade.berkeley.edu.user%host.BITNET@CUNYVM.CUNY.EDU (Lee Sailer) Subject: Control flow and common sense In article <4605@ihlpf.ATT.COM>, warren@ihlpf.ATT.COM (Montgomery) says: > >nested if-then-else's. At the leaves of the if-then-elses were >statements that did something and generally set variables tested by >the if-then-elses, possibly also setting the loop condition. The >structure being implemented was actually a finite state machine, and >fairly simple to understand as such, but impossible to discern from >the style in which it was written. This is where "literate programming" should come in. Perhaps if the author had written a long comment that said something like, "I've implemented a fsm using deeply nested if-then-elses. At the end of each if-then-else is a block of statements that do stuff, and set the state variables for the next go around. I could have uses case stements but didn't because. etc etc etc," then it wouldn't have been necessary for you to "discern" the fsm from the structure of the code. Now, this also presumes a certain degree of expertise on the part of the reade, who has to know what a fsm is, and how to program one. ------------------------------ Date: 5 May 88 12:49:05 GMT From: mnetor!spectrix!yunexus!geac!daveb@uunet.uu.net (David Collier-Brown) Subject: Control flow and common sense In article <5110@pucc.Princeton.EDU> EGNILGES@pucc.Princeton.EDU writes: | If you are not too concerned about efficiency, the best | way to implement a finite state machine is as a two-dimensional | table searched by old state and current symbol, yielding new | state and perhaps some representation of an action to be carried | out. The neat thing is that your end users can check or even | specify the table, and (if your project is sufficiently complex) | the table can serve as the basis for tools that draw finite-state | diagrams, check test coverage, or even produce automated documentation. Yup! try using Wart, from the kermit distribution. It is a full-fleged (if trivially inefficent) DFA compiler ,with a very nice notation: <state1,state2> event { some code } <state> event { more code } event { general-case code } ------------------------------ Date: 6 May 88 17:53:49 GMT From: sgi!daisy!david@ucbvax.Berkeley.EDU (David Schachter) Subject: Control flow and common sense One fellow I know documented a particularly complex and obscure code with the comment "This procudure implements the <something or other> algorithm given on page <xyz> of <some book> by <some author>". (The angle bracketed items are mine.) Real helpful. If I want to understand his code, I have to get the book from a speciality bookstore or get my company to purchase library access at Stanford University. Then, hoping the edition I get is the same as his (so the page numbers match), I read some author's description of the algorithm and hope the programmer implemented the algorithm exactly. Great, just great. It is folks like him who justify, in my mind, the existence of nuclear weapons. ------------------------------ Date: 28 Apr 88 12:51:30 GMT From: mcvax!ukc!stl!stc!datlog!dlhpedg!cl@uunet.uu.net (Charles Lambert) Subject: gotos 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 > >for (step=0,done=0;!done;step++) { > switch(step) { > case 0: action_0; > break; > case 1: action_1; > break; > ...... > default: done = 1; > break; > } > if (!done && test_condition) done=1; > } This is almost a finite-state machine, and state machine programming is an accepted idiom. Generalise it as follows: state=STAT0; while ( state != STATE_DONE ) { switch (state) { STATE0: action_0(); if (exit_condition_0) state = STATE_DONE; else state=STATE1; break; STATE1: action_1(); if (exit_condition_1) state = STATE_DONE; else state = STATE2; break; . . . } } Note that with this model, states may occur in any order and even repetitively. The "if...goto" construct is simply a sequential case of the general state machine. ------------------------------ Date: 1 May 88 00:15:05 GMT From: cca!g-rh@husc6.harvard.edu (Richard Harter) Subject: State Machines, The Ultimate Goto 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. ------------------------------ Date: 1 May 88 16:23:02 GMT From: l.cc.purdue.edu!cik@k.cc.purdue.edu (Herman Rubin) Subject: State Machines, The Ultimate Goto 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. ------------------------------ Date: 2 May 88 06:01:46 GMT From: cca!g-rh@husc6.harvard.edu (Richard Harter) Subject: State Machines, The Ultimate Goto 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: ------------------------------ Date: 2 May 88 13:40:57 GMT From: uh2%psuvm.BITNET@jade.berkeley.edu.user%host.BITNET@CUNYVM.CUNY.EDU (Lee Sailer) Subject: State Machines, The Ultimate Goto 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. ------------------------------ Date: 4 May 88 00:13:39 GMT From: ihnp4!ihlpf!nevin1@ucbvax.Berkeley.EDU (00704a-Liber) Subject: State Machines, The Ultimate Goto 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). ------------------------------ End of Soft-Eng Digest ******************************