Re: Should internet support software be written in Ada?

[eachus@spectre.mitre.org (Robert I. Eachus)]

In article <3lbp1k$jij@theopolis.orl.mmc.com> Theodore Dennison <dennison@escmail.orl.mmc.com> writes:

  > Could you be more specific than "state machines"? Any algorithm
  > can be expressed as a state machine (I believe there is actually a
  > theorem to this effect, but it's been a while since college).

  > I have written a dispatcher before. It seemed clean enough as a
  > loop enclosing a case statement. I don't think goto's would have
  > made it clearer.

    A simple state machine can be expressed as a case statement in a
loop.  A more complex state machine will often have several selection
criteria, or may have states for which the "normal" method of choosing
the next state do not apply.  (The canonical example of these is error
recovery.)

    In such a state machine you can keep adding flags and tests to
keep the original structure intact, but a much better approach is to
say goto when you know where to go next.  It is much easier to
understand, and, surprise, surprise, it is a lot easier to maintain.

    Let me give you a simple example.  A parser generator generated
tables which were headers followed by lists of triples: (symbol,
action, next state).  Since many lists only differed from the a
similar state because they had one or two added triples, we put in an
optimization where some table headers indicated that if you didn't
find a match in this table you should go to some other table and try
there.  (There are the magic words again.)

    Now I could have written the parser with a loop of the form:

    while In_Continue_Table loop
      --search table...
    end loop;

    But that code would be totally misleading.  What I wrote was:


    <<Try_Again>>
       case Table.Kind is
         ...
         when Continue_Table =>
           if S /= Table.Entries(1)
           then
             Table := Table.Continuation;
             goto Try_Again;
           else
             -- process a match.
           end if;
    
    This makes it much clearer that you go back to the "top" of the
case statement only in specific failure cases.

    Another example in the same parser involved "panic mode" recovery.
If a neat clean correction can be found that allows the compiler to
continue can be found, make it and go on.  If not, you want to go back
to a consistant state and proceed from there.  Again if hand-waving
description uses go to, the proper implementation probably uses gotos.
In this case the reason for using goto was that the proper
continuation point depended on the type of error detected.  I could
have written this in Ada with several exceptions, several block
statements, several loops, etc.  Or I could, and did just use gotos
with appropriate labels so that the code was understandable.

    Now in both these cases, my description admitted that either one
could have been implemented without gotos.  As it happened, since both
of these were in the same code, and the artificially created nested
scopes would not have matched, one or the other had to be done with
gotos.  (Or you could use a number of artificial state variables,
etc., etc., like you learned in classes on computability theory.  But
not in anything I'm going to maintain!)

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...