GOTO considered necessary

GOTO considered necessary

[Samuel Mize]

Greetings,

I'm rebeating a dead horse, in order to write up a consensus paper to
submit to adahome.  I'll appreciate your input.

This one concerns use of "goto" statements.

I have scanned through the back c.l.a messages in DejaNews.  I request
your comments on this summary.  I also have a few questions for everyone.

Samuel Mize

                        USE OF "GOTO" IN ADA
                        --------------------
SUMMARY:
--------

1) In general, "goto" statements should be avoided.  They create
   confusing execution flow structures -- at first, or after a few
   maintenance changes.

2) As a rule of thumb, if your code needs a "goto" to work efficiently
   (or at all), you have probably overlooked a simpler, better design.

3) "Goto" statements are acceptable in machine-generated code, but ONLY
   if a human is NEVER expected to read the code.  (For example, a
   module generated by a tool from data-flow diagrams.)

4) As an exception, Finite State Machines (FSMs) are often implemented
   with goto statements.

   The people doing this argue that, for FSMs, "goto"s improve clarity
   and readability, primarily because they let the code more directly
   reflect the FSM model.

5) Other usages are very suspect, but there may be OK cases.  If it really
   improves clarity, go ahead -- but document WHY you used a "goto," and
   why other approaches were found lacking.

6) Norm Cohen recommended Knuth's article in the December 1974 Computing
   Surveys, as "the best discussion I've ever seen of the goto issue."

[------------------------------------------------------------------------]
[ Point 2 is new material from me.  As an example, some code (originally ]
[ from Knuth) was posted as a case where a goto makes sense.  Yet when   ]
[ redesigned without it, the code is clearer and simpler.  I've appended ]
[ the example and my analysis at the end of this write-up.               ]
[------------------------------------------------------------------------]

QUESTIONS:
----------

1) Are there other enumerable cases where "goto" improves clarity?
   (Not examples -- I'll grant as given that isolated instances may
   occur -- but application classes or general situations that could
   be described and watched out for.)

2) In what application areas do goto-based FSM implementations
   commonly occur?

3) Does this template reflect the design of a goto-based FSM, or have I
   missed something?  Is there a better general approach?

      begin
         <<State_1>>                  -- A block like this exists for
            [processing for state 1]  -- each state of the machine.
                                      --
            if [condition] then       -- An explicit variable keeping
               goto [State_X];        -- the "current" state is not
            elsif [condition] then    -- needed -- it is represented
               goto [State_Y];        -- by the program counter.
            else                      --
               goto [State_Z];        -- The coder must ensure execution
            end if;                   -- does not "fall through" to the
                                      -- next state by accident.
   
         <<State2>>
            ...

4) The alternative would be as shown below.  This discussion is biased
   by my ignorance of leading-edge FSM work.  Please comment on
   advantages and disadvantages of this approach.

      -- good grief, use meaningful names in a real application
      type State is (Initial_State, State1, ... Staten);
      Current_State: State;
   
      -- variables that may affect the next transition
      ...

      function Next_State (Current_State: State) return State;
   
      loop
         exit when
           (Current_State = [a terminal state])
           or 
           (Current_State = [another terminal state])
               ...;
   
         -------------------------------------------------------- AAA
         case Current_State is
            when State_1 =>
               [Processing for state 1]
               Current_State := Next_State (Current_State);
            ...
         end case;

         if Debug then
            Text_Io.Put_Line (State'Image (Current_State)); ----- BBB
         end if;

      end loop;

   Next_State can use an if/elsif cascade, or an array or hash-table
   lookup, or whatever is appropriate for the application-specific
   transition table.
   
   It has these advantages:

   (a) The transition logic is separate from the processing logic for
       each state.  (This is good or bad, depending on how intertwined
       their logic naturally is.)

   (b) There is a place to put processing that must occur at the start
       or end of each state (note lines AAA and BBB).

   (c) The possible states are listed in an enumeration, usable for
       I/O or to represent a "memory" of previous states, if needed.

   It has these disadvantages:

   (a) The transition logic is separate from the processing logic for
       each state.

   (b) It is less efficient: at the end of each state, we jump to restart
       the loop, evaluate the case expression, and only then jump to the
       next state.

   (c) If may be harder to locate accidentally-"killed" states.  A
       cross-reference tool could identify unused statement labels.

   Adding or deleting a state is harder with the case structure because
   you have to edit in two locations, keeping the type definition and
   the case structure synchronized.  On the other hand, adding or
   deleting a state is harder with the goto structure because the logic
   that jumps to the new (or deleted) state is less localized -- you
   have to hunt through all the code for the "goto"s.  This seems to
   be a wash.

EXAMPLE OF SIMPLIFYING DESIGN TO ELIMINATE GOTOS:
-------------------------------------------------

The code as given was: - - - - - - - - - - - - - - - - - - - - - - -

> Here's an example to ponder:  Consider the declarations
> 
>    type Node_Type;
> 
>    type Tree_Type is access Node_Type;
> 
>    type Node_Type is
>       record
>          Count       : Natural := 0;
>          Left, Right : Tree_Type;
>       end record;
> 
>    type Bit_Vector_Type is array (Natural range <>) of Boolean;
> 
>    type Bit_Vector_Pointer_Type is access Bit_Vector_Type;
> 
>    Root : Tree_Type;
>    BV   : Bit_Vector_Pointer_Type;
> 
> BV points to a bit vector describing a path (False = left, True = right)
> through the tree pointed to by Root.  We are counting the number of times
> a given bit vector is encountered in the Count component of the
> corresponding tree node.  Root starts out pointing to a tree consisting
> only of a root node, and new nodes are added to the tree as needed.  The
> loop below has three exits, and the actions appropriate when one of the
> exits is taken is different from the actions appropriate when the other
> two are taken, so a goto comes in handy.  Here's the code:
> 
>       Node := Root;
>       Bit := BV'First;
>       loop
>          if Bit > BV'Last then
>             goto Increment;
>          end if;
>          if BV(Bit) then
>             if Node.Left = null then
>                Node.Left := new Node;
>                Node := Node.Left;
>                exit;
>             else
>                Node := Node.Left;
>             end if;
>          else
>             if Node.Right = null then
>                Node.Right := new Node;
>                Node := Node.Right;
>                exit;
>             else
>                Node := Node.Right;
>             end if;
>          end if;
>          Bit := Bit + 1;
>       end loop;
> 
>       -- We've reached a leaf.  Read the rest of BV.all while extending
>       --    the tree along the corresponding path only.
>       for I in Bit+1 .. BV'Last loop
>          if BV(I) then
>             Node.Left := new Node;
>             Node := Node.Left;
>          else
>             Node.Right := new Node;
>             Node := Node.Right;
>          end if;
>       end loop;
> 
>    <<Increment>>
>       Node.Count := Node.Count + 1;


Is this a good design?

It would be clearer to just let the first loop do all the work.  Eliminate
the "exit" statements and turn it into a "for" loop.  This works, but it
checks for "null" in nodes you just created.  If this makes a significant
performance difference to your application, you can optimize the loop.
(In this case, the compiler can't do it.)

However, the code should still be readable.  Specifically, you should be
able to state what each loop does each iteration, and what it has done
once it exits.  (If you like semi-mathematical jargon, you need a loop
invariant and a termination condition).

Let's use two clearly-defined loops:

    -- Move to the last existing node on the path
    FOR all existing nodes on path
        move to node

    -- Create any new nodes
    FOR all new nodes on path
        create the node

The new code is: - - - - - - - - - - - - - - - - - - - - - - - - - - -

     -- Declarations the same (but declare Bit and initialize Root)
   begin

      Node := Root;
      Bit := BV'First;

      ---------------------------------------------
      -- Move to the connect-node for the first  --
      -- node that needs to be created (if any). --
      ---------------------------------------------
      -- We are manually simulating a "for" loop to
      -- retain the index after loop termination.
      loop
         exit when Bit > BV'Last;

         if BV(Bit) then
            if Node.Left = null then
               exit;
            else
               Node := Node.Left;
            end if;
         else
            if Node.Right = null then
               exit;
            else
               Node := Node.Right;
            end if;
         end if;
         Bit := Bit + 1;
      end loop;

      ---------------------------------------------------
      -- We are at the last existing node in the path. --
      -- If there are any non-existent nodes on the    --
      -- path, Bit defines the first; create them.     --
      ---------------------------------------------------

      for I in Bit .. BV'Last loop
         if BV(I) then
            Node.Left := new Node;
            Node := Node.Left;
         else
            Node.Right := new Node;
            Node := Node.Right;
         end if;
      end loop;

      -------------------------------------------------------
      -- Increment the count at the node identified by BV. --
      -------------------------------------------------------

      Node.Count := Node.Count + 1;

This is exactly as efficient, and easier to maintain.  The loops have
clear missions, node creation is more localized, and the Increment
statement is only reached by one path of execution.

-- end --


-- 
Samuel Mize -- smize@imagin.net -- Team Ada
(personal net account)

Re: GOTO considered necessary

[Michel Gauthier]

In article <5n977i$2cmc$1@prime.imagin.net>, smize@imagin.net (Samuel
Mize) wrote:

>>  Greetings,
>>  
>>  I'm rebeating a dead horse, in order to write up a consensus paper to
>>  submit to adahome.  I'll appreciate your input.
>>  This one concerns use of "goto" statements.
>>  [...]
>>  3) Does this template reflect the design of a goto-based FSM, or have I
>>     missed something?  Is there a better general approach?
>>  
>>        begin
>>           <<State_1>>                 
>>              [ . . . ]      -- The coder must ensure execution
>>                             -- does not "fall through" to the
>>                             -- next state by accident.
>>     
>>           <<State2>>
>>              ...

It is probably advisable in such cases to use blocks and other 
protections in a spirit like :

     <<StateX>> declare
                                 -- it is very rare to have no local variables
                            begin
                                ...
                            end ;
                            raise Program_Error ;
    <<StateY>> ...
Although style rules generally prohibit raising predefined exceptions,
this might be a valid usage of Program_Error. Yet better :
      Ada.Exceptions.Raise_Exception(FSM_Exit_Error,"Bad exit of state X.");

----------          ----------          ----------          ---------- 
Michel Gauthier / Laboratoire d'informatique
123 avenue Albert Thomas / F-87060 Limoges
telephone + 33 5 55 43 69 73
fax +33 5 55 43 69 77
----------          ----------          ----------          ----------
Si l'an 2000 est pour vous un mysticisme stupide, utilisez la base 9
If you feel year 2000 a stupid mystic craze, use numeration base 9
----------          ----------          ----------          ----------

Re: GOTO considered necessary

[Michael F Brenner]

Item 4 states that GOTOs in FSAs are done to match the style of what
an FSA actually is. I disagree. The reason is for speed. Speed is the
purpose of designing and implementing code; the language is the method
used to provide that speed (e.g. readably, with no memory leakages,
with memory leakages, with hanging pointers, without hanging pointers,
in a go-to-less style, or whatever language attributes you wish to use).
Until language reference manuals specify a method of guaranteeing
tail recursion optimization, total inlining, gargantuan level movement,
and algorithm rewriting, there will be many FSAs that are more quickly
implemented with each state as a label, and the transition matrix
implemented as GOTO statements. This is independent of the field
(compiler theory, business processes, command and control, 
ASIC, or other custom chip or application). When a language attribute
(procedures, table-driven, good style, bit matrixing, maintainable,
readable, etc.) interferes with speed, then there will be applications
where the trade-off must be made in favor of the speed. However,
the world is full of unmaintainable FSAs which were implemented
as thousands of GOTOs, the original table-driven FSA prototype was
lost, and now it is almost impossible to reliably change the GOTOs.
So when you make a trade-off to increase your speed by manually
compiling a table-driven FSA into a bunch of GOTOs, consider
typing the original table into comments right after the label 
corresponding to the START state. 

Re: GOTO considered necessary

[Robert Dewar]

Michael Brenner says

<<Item 4 states that GOTOs in FSAs are done to match the style of what
an FSA actually is. I disagree.>>


Nope, that is wrong. People certainly disagree on the issue of whether
labels/gotos or a case statement are preferable in representing FSA's, but
the issue is NOT speed. Many people, including me certainly, think that it
is CLEARER to express an FSA in terms of labels and gotos, because it is
a clearer representation of the diagram with labels being the states, and
gotos the arrows.

Many excellent and experienced programmers agree with this point of view,
and many do not. It is a pointless argument at this stage because nothing
new is likely to be added (Michael, you are relatively new to this group,
so you may not have seen previous threads on this topic).

But you are quite wrong if you think the concern is about efficiency. I
would prefer the representation with labels and gotos even if it were
*less* efficient if I was concerned primarily about clarity. 

You cannot argue that one way is clearer than another here, since this is
really a case of personal preference. You can argue that Michael Brenner
finds the case representation clearer, and I can argue that Robert Dewar
finds the label/goto form clearer, but so what?

What is certainly the case is that for many (in my experience a slight, but
only slight, majority) of experienced programmers, this is one of the few
situations in which they feel the use of gotos is not only permissible,
but indeed desirable.

Two little anecdotes. Once Jean Ichbiah was looking at some code I was
writing for the Alsys compiler, and expressed surprise at the use of 
gotos. I replied that it was a FSA, and he immediately agreed that in 
that case it was fine.

Second, Fran Allen tells a story about one of the most experienced compiler
writers at IBM using gotos extensively in the lexical scanner of a compiler.
But at that time, IBM standards permitted no more than X% of source lines to
be gotos, and this code required high level management approval ...

Re: GOTO considered necessary (FSAs)

[Nick Roberts]

Surely a tool (program) other than a programming language should be used to
implement, document, and maintain finite state machines anyway. This tool
could then generate an object file which would be linked into the main
program. I admit to ignorance as to the existence of such tools - I would
be amazed if there were none - but perhaps this could be an interesting
little market. How about a graphical diagram-based program, which allowed
editing by mouse, etc?

Nick.

Re: GOTO considered necessary

[Robert Dewar]

Sam says

<<2) As a rule of thumb, if your code needs a "goto" to work efficiently
   (or at all), you have probably overlooked a simpler, better design.
>>

Oh dear, yes, this horse is truly dead and almost mummified one would say,
but the above rule of thumb is far too dogmatic (and see Knuth by all means!)

There are many places where a goto is the natural and clearest way of doing 
things. It is true that there exist programmers who are so incompetent that
the only way of stopping them from misusing gotos is to stop them from using
them at all, but assuming you are not in this category, there is no reason
to write convoluted code to avoid a goto.

THere are many obvious examples, one of the most familiar is to provide
a continue facility for loops

    while ..... loop
       ...
       <<Continue>>
    end loop;

Re: GOTO considered necessary

[Woodrow Yeung]

In article <dewar.865693869@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> There are many places where a goto is the natural and clearest way of doing 
> things.

> THere are many obvious examples, one of the most familiar is to provide
> a continue facility for loops
> 
>     while ..... loop
>        ...
>        <<Continue>>
>     end loop;

Oh dear, I have to disagree with this on two levels.  It's far cleaner to
have a continue control structure than using a goto to implement it.  One
of the classic example of using gotos is jumping out of nested loops, but
labeled loops are much better.  Goto's should not be used in a HLL to
implement structured control flow, especially in a language as rich as Ada.

On the other level, I find the continue facility to be of marginal utility
and counterproductive.  It would be a pity to let a continue statement
destroy the principle of maintaining single entry and exit in a control
structure.  (I'm more tolerate of breaking out of loops.)  It doesn't buy
you anything compared to just reorganizing your loop body with if's, and
continues sure make maintenance a nightmare.  If one argues that a continue
makes the loop clearer compared to guarding with an if then I have to say
that the body of the loop has gotten to be too convoluted.  Parts could be
implemented in routines so you don't get a really gross looking if then
else block.  A good compiler should be able to inline the routine so you
don't loose any efficiency.

Goto's should not be used to fake continues.

Woody Yeung
yeung@reed.edu

Re: GOTO considered necessary

[Robert Dewar]

<<Goto's should not be used to fake continues.
 
Woody Yeung>>


See, Sam, there are plenty of dogmatic folks around on this issue, so I
think it is clear that your write up is worth the effort!!!

Re: GOTO considered necessary

[Woodrow Yeung]

In article <dewar.866852335@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> <<Goto's should not be used to fake continues.
>  
> Woody Yeung>>
> 
> 
> See, Sam, there are plenty of dogmatic folks around on this issue, so I
> think it is clear that your write up is worth the effort!!!

Dogmatic?  I gave pretty good reasons against it as a continue.  I guess I
must be dogmatic about not using goto's to jump to the next statement too.

[Robert Dewar from previous post]
> There are many places where a goto is the natural and clearest way of doing 
> things.

You seem pretty dogmatic about using gotos.  I suppose you have to dogmatic
to be programming in Ada in the first place. ;-)

Woody Yeung

PS  I should have said MODERN HLL.  Break is broken in C, you need a goto
to break from a while/switch.

Re: GOTO considered necessary

[Adam Beneschan]

yeung@reed.edu (Woodrow Yeung) writes:
 >
 >> THere are many obvious examples, one of the most familiar is to provide
 >> a continue facility for loops
 >> 
 >>     while ..... loop
 >>        ...
 >>        <<Continue>>
 >>     end loop;
 >
 >Oh dear, I have to disagree with this on two levels.  It's far cleaner to
 >have a continue control structure than using a goto to implement it. . . .

I have to disagree.  When I used to program in C, I made a rule for
myself not to use the "continue" statement.  The reason: When I did
use it in a loop, it worked fine, but then I'd find I had to make a
modification that required that some extra actions to be taken at the
end of each loop, before going to the next iteration.  So I'd add
those changes just before the closing }.  All of a sudden, "continue"
no longer worked; if I had any continue's up in the remainder of the
loop code, I would have to search for them so that I could replace
them with something else, and if I forgot, oops, I just put a bug into
the program.  

At least if you have a goto-label construct:

    while ..... loop
       ...
       <<Continue>>
    end loop;

Now, when you have to add something just before "end loop", at least
the presence of a label alerts you to the fact that something might be
jumping there in order to perform a "continue"; now, you have to
decide whether to add your code after or before the label.  But you're
less likely to make a modification that would screw things up.  At
least, that's my experience.

Sure, one could come up with a case where "break" (or "exit", in Ada)
has the same problem, but my experience is that problems like this
don't occur--or rarely occur--with exit constructs; while they seem to
be more frequent with "continue".  I don't know why "continue" should
be considered cleaner than an appropriate GOTO construct; I don't know
what definition of cleanliness would make this so, except for one that
proclaims that GOTO's are inherently unclean just because they are.  I
had to get over this attitude when programming in COBOL 66.  [I think
I got the language version right this time.  :)]

(BTW, I'm not likely to use *either* construct: boolean variables seem
to work better for me.)

                                -- Adam

Re: GOTO considered necessary

[Anonymous]

One comment about the example with and without goto for a binary tree:
Both versions make the implicit assumption that Bv'Last < Natural'Last
(so that Bit > Bv'Last can be used to terminate if no new nodes are
needed). It would be better to make this assumption explicit by using a
different index subtype for Bit_Vector:

   subtype Bit_Vector_Index is Natural range 0 .. Natural'Last - 1;
   type Bit_Vector is array (Bit_Vector_Index range <>) of Boolean;
   Bit : Natural;

Murphy guarantees that someone will invoke this with Bv'Last =
Natural'Last sometime, causing a failure, if this change isn't made.

Jeff Carter  PGP:1024/440FBE21
My real e-mail address: ( carter @ innocon . com )
"Now go away, or I shall taunt you a second time."
Monty Python & the Holy Grail

Posted with Spam Hater - see
http://www.compulink.co.uk/~net-services/spam/

Re: GOTO considered necessary

[Wolfgang Gellerich]

In article <5n977i$2cmc$1@prime.imagin.net>, smize@news.imagin.net (Samuel Mize) writes:

|> 
|> I'm rebeating a dead horse, in order to write up a consensus paper to
|> submit to adahome.  I'll appreciate your input.
|> 
|> This one concerns use of "goto" statements.
|> 

Last year, we made a study about today's usage of GOTO statements, comparing
Ada, C, and Fortran and also giving a short summary of the GOTO discussion.
That paper is available in postscript (data about citation etc appended on
the last page). The www address is:

http://www.informatik.uni-stuttgart.de/ifi/ps/Gellerich/publications.html


---

  Wolfgang Gellerich