Re: GOTO considered necessary (reworked)

[bobduff@world.std.com (Robert A Duff)]

In article <dewar.866548262@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>First, to me, the mapping of states into sections of code, and the mapping
>of transitions as gotos, seems pretty direct -- direct enough that I do not
>think it would make sense to dream up some syntactic gizmo -- although as
>Robert Eachus points out, a preprocessor can very well provide the equivalent
>of this syntactic gizmo.

The reason some syntactic gizmo shouldn't be in the language is that
these FSM cases are rare.  If they were common, then we would get enough
benefit from such a syntactic gizmo to make it worthwhile.  (See also
languages like Lisp, where you can create your own gizmos.)

>As for fall through, that is quite a bogus argument. If you map a FSM into
>a loop/case structure with an explicit state variable, then you have to be
>equally careful not to forget to modify the state variable. The error in one
>case is accidental transition to the following state, the error in the other
>is an infinite loop in one state -- not much to call there.

I disagree.  In the loop/case method, you can put "State := Bad_State;"
at the top of the loop, and then "when Bad_State => Assert(False);" in
the case statement.  With the goto solution, you have to use care on
each state, rather than once for the whole mess.

If you want to stay in the same state, then you would write (under "when
Some_State =>", "State := Some_State;".

>Of course in practice, one of the advantages of the goto model is that in
>some cases, it is quite natural to fall through to the following state:
>
>   <<Sign>>
>      code to acquire sign
>
>   <<Digits>>
>      code to acquire digit
>      ..
>
>      if Another_Digit then
>	 goto Digits;
>      else
>	 goto Exponent;
>      end if;
>
>or somesuch, where Sign does fall through to Digits. I find this quite
>readable, and code of this kind can be found in many lexical analyzers
>in compilers.
>
>yes, of course you can often replace a specific instance (like the one above
>if that is all there is to it), with a simpler structure (e.g. a loop for
>the Digits above).

In my experience, a hand-coded lexical analyzer is always better done
with loops and ifs and case statements, rather than as above.  That is,
forget that it's a FSM, and just write it in the natural way.  ("An
identifier is a letter, followed by a sequence of zero or more letters
and digits" translates quite nicely into loops, not gotos.)  I know you
agree, since I've seen the GNAT lexer.  (A tool-generated lexer is a
whole 'nother story, of course -- throw readability to the winds, and go
for efficiency.  Funny thing is, tool-generated lexers are less
efficient, in practise, in my experience.)

>The time that a goto threaded structure becomes appropriate is when you have
>a very involved FSM with many intertwined transitions.

Yes.  In this case, I would use loop/case, whereas you would use goto.
At least we agree on the meta rule: Goto is not *always* evil, and
should be considered on a case-by-case basis.

>Basically an FSM of this kind *fundamentally* corresponds to spaghetti code,
>in that the states are executed in some non-structured sequence depending on
>the input, and therfore cannot be arranged into neat structures.
>
>We have only two methods of handling such spaghetti sequences in typical
>PL's, the code+goto representation, or the loop-case representation. 

I can think of others: E.g. an array of pointers-to-procedures, indexed
by state.

>...One
>might say that neither is perfectly happy, and that is right, since the
>underlying sequence of control is in some sense unhappy. 

That's why I don't like viewing a lexer as an FSM, nor coding it as such.

>...But given this
>choice I prefer the code+goto representation.
>
>As Robert Eachus notes, for a complex FSM, there is considerable merit in
>using one of the standard tools to generate the code.

Well, if tools are generating the code, then this whole argument is
irrelevant.  If a tool is generating it, then efficiency is paramount,
and readability of the generated Ada code is unimportant.  (Unless
you're debugging the tool, of course!)

- Bob