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
******************************