Re: GOTO considered necessary (reworked)

[nobody@REPLAY.COM (Anonymous)]

On 11 Jun 1997 15:40:22 -0500, smize@news.imagin.net (Samuel Mize)
wrote:

> 
> Greetings,
> 
> [-------------------------------------------------------------------]
> [ I'm re-doing this since a lot of people were apparently at an Ada ]
> [ conference recently, and weren't reading net news.  This version  ]
> [ is updated based on previous comments.  -- Mize                   ]
> [-------------------------------------------------------------------]
> 
> 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.
> 
> Samuel Mize
> 
>                         USE OF "GOTO" IN ADA
>                         --------------------
> 
> 1.0 SUMMARY:

..

> 2.0 UNSUPPORTED CODE STRUCTURES
> -------------------------------
> The central feature of structured programming is not some specific set
> of code structures, but the fact that well-defined structures are used
> to organize the code.  Arbitrary "goto"s are avoided; transfers of
> control occur as part of a larger, coherent structure that helps the
> reader understand the overall program's activity.
> 
> Modern languages like Ada provide a large set of useful structures: "if"
> statements (supporting "then", "elsif", and "else" clauses), "case"
> statements, "while" and "for" loops, etc.
> 
> However, there are some useful structures that are not directly supported.
> This will always be true.  Some of these structures are rarely used, so
> are not worth the cost to add into the compiler; others may be invented,
> or may be domain-specific.
> 
> It is generally acceptable to use a "goto" to implement a well-defined
> code structure that is not directly implemented in the language.
> 
> For instance, the Ada gurus at ACT use "goto" in the GNAT compiler.  On the
> other hand, it occurs in only 3 places (in 3.07), and all are instances of
> the "not-found" pattern shown below.
> 
> Many recommend using "flag" comments to identify jumps that are not part of
> a structure.  This includes "return" and "exit" statements, as well as "goto"
> statements.  Thus, a loop might look like:
> 
>    loop
>       ...
>       exit when A; -------------------EXIT
>       ...
>       if B then
>          return; ---------------------RETURN
>       ...
>       if C then
>          goto CONTINUE; --------------GOTO
>       ...
>       <<CONTINUE>>
>    end loop;
> 
> For example, here are three structures that require "goto" in Ada:
> 
> a) Process continuation logic
> 
>    A sequential process may have several natural completion points.  One
>    example is parsing a string that ends with optional items.  Avoiding
>    "goto" in this case requires increasing levels of "if" indentation:
> 
>       [process first part of string]
>       if [not end-of-line] then
>          [process option1]
> 
>          if [not end-of-line] then
>             [process option2]
> 
>             if [not end-of-line] then
>                [process option3]
> 
>                if [not end-of-line] then
>                   [process option4]
>                    ...
>                endif;
>             endif;
>          endif;
>       endif;
> 
>    This is hard to read, and confusing since all the parsing is really at
>    the same logical level.  A "completed" flag may also be used, but this
>    does not usually improve clarity over the "goto" solution:
> 
>       [process first part of string]
>       if [end-of-line] then
>          goto NO_MORE_OPTIONS;
>       end if;
> 
>       [process option1]
>       if [end-of-line] then
>          goto NO_MORE_OPTIONS;
>       end if;
> 
>       [process option2]
>       if [end-of-line] then
>          goto NO_MORE_OPTIONS;
>       end if;
> 
>       [process option3]
>       if [end-of-line] then
>          goto NO_MORE_OPTIONS;
>       end if;
>       [process option4]
>       ...
>       <<NO_MORE_OPTIONS>>
> 
>    The same effect can be achieved by putting the processing sequence into a
>    block statement and raising an exception on end-of-line.  However, this
>    is generally considered even worse than the "goto" solution.  Most
>    standards limit exceptions to error conditions, not normal processing.

Replace all your code by

   Process_Line (...);

where the body of Process_Line is

   [process first part]

   if [end-of-line] then
      return;
   end if;

   [process option 1]

   if [end-of-line] then
      return;
   end if;

   ...

You can inline Process_Line if the subprogram-call overhead worries you.
Just as readable, and less error-prone on modification.

> 
> b) "Continue" loop logic
> 
>    The "continue" function of C has to be emulated in Ada with a "goto":
> 
>       loop
>         ...
>         goto <<CONTINUE>>
>         ...
>         <<CONTINUE>>
>       end loop;
> 
>    This is a special case of the process continuation structure.

Of course, the code in this example is the same as

   loop
      ... -- This is the first "..." in the example
   end loop;

since the second "..." is never executed. Real use of continue involves
a conditional:

   loop
      ... -- 1

      if Condition then
         continue;
      end if;

      ... -- 2
   end loop;

(assuming "continue" were part of Ada :). This is equivalent to

   loop
      ... -- 1

      if not Condition then
         ... -- 2
      end if;
   end loop;

This is just as readable, and less error-prone on modification than
using a goto.

> 
> c) "Not-Found" loop logic
> 
>    Loops frequently scan through a sequence -- for instance, an array --
>    followed by special processing if the item was not found.  An example
>    would be inserting an item in an ordered array:
> 
>       Items: array (Positive range Lo .. Hi) of Item;
>       Last_Item: Natural := Items'First - 1;
>       ...
>       -- for each item to be inserted
> 
>          for I in Items'First .. Last_Item loop
>             -- duplicates are allowed, and inserted as separate items
>             if Items (I) >= New_Item then
>                Items (I + 1 .. Last_Item + 1) := Items (I .. Last_Item);
>                Items (I) := New_Item;
>                goto ITEM_INSERTED;
>             end if;
>          end loop;
> 
>          -- New_Item's place not found before end of array
>          Last_Item := Last_Item + 1;
>          Items (Last_Item) := Item;
> 
>          <<ITEM_INSERTED>>
>          ...

This seems to have an error: what is the value of Last_Item if the item
is found? If it is not found? If you increment Last_Item after the
label, it has an incorrect value if the item is not found; if not, it
has an incorrect value if the item is found.

If you intend to retain this example, you should correct it.

> 
>    Avoiding "goto" in this case requires one of these approaches:
> 
>     - A "found" boolean.  When element is processed in loop, Found is set
>       and loop exits.  No-element processing is skipped when Found is true.
> 
>     - An "Index" variable, initially set past the end of the array, and reset
>       in the loop if the element is found.  Processing is always done after
>       loop exit, based on this index.
> 
>     - Last-iteration detection in the loop.
> 
>     Each of these is also unclear in its own way.

I don't buy this. In the first place, who's going to use a linear search
on an ordered list instead of a binary search?

The problem is combining the search for the desired location with the
insertion. Separate these two: the loop finds the location; processing
after the loop does the insertion. This needs no goto and is completely
clear.

In summary, I'd say unsupported structures can be emulated using other
structures, of which goto is one. Use of structures other than goto
maybe less error-prone than using goto without loss of clarity. Goto
should only be used if no solution of greater or equal clarity exists,
or if such a solution is found to be too slow (by measurement!), no
faster algorithm is available (binary vs. linear search again), and the
use of goto is fast enough.

> 
> 
> 3.0 FINITE STATE MACHINES (FSMs)
> --------------------------------

..

> 4.0 IMPROVING A "GOTO"-BASED DESIGN
> ---------------------------------
> The existence of "goto"s in code creates some purely mechanical problems for
> maintenance programmers.  New code may be added on the wrong side of a "goto"
> target, and "goto"-based structures are often harder to maintain when
> intervening code changes significantly.  This creates a small but definite
> advantage to eliminating many "goto" statements.

Including, IMNSH (I hope) O, all of the cases in section 2.
 
> Extraneous state variables or other unclear design kludges do not improve on
> a "goto".  If there is no overall design improvement that replaces a "goto"
> with a cleaner structure, you may as well leave the "goto".  For instance,
> the code in section 5.0 would not be improved by mechanically replacing the
> "goto" by adding a "Done" boolean or some other kludge -- this would simply
> trade one unclear design for another.

I'd say it's worth it even if the two designs are equally clear, given
the greater chance of errors during modification if a goto is used.

> 
> For instance, you should be able to say what a loop does each iteration, and
> what it has done once it exits.  (If you like semi-mathematical jargon, it
> needs an invariant and a termination condition).

So, what has the loop in your "not found" example done once it exits?
Maybe it's done an insertion, and maybe not. You have no clear
postcondition.

> 
> So, IF (1) it's worth the effort to review a "goto"-based design, and
> (2) the code can be reorganized into a clearer structure, then you should
> do so to eliminate the "goto".  If a "goto" is needed to create the
> appropriate structure for your code, use it -- and document WHY you used it.
> 

I'd say (2) should read

   the code can be reorganized into a structure that is as clear or
clearer, then ...

> The best approach to eliminating "goto" from your code is to write code in
> the first place that divides the task into logical chunks, organized by
> simple control structures.  If you design your overall approach carefully,
> you will only use "goto" when it really does improve your code.

Which is my suggestion for the "not found" example. One structure finds
the insertion point; the next performs the insertion. Your search logic
has a clear precondition, invariant, and postcondition.

> 
> 5.0 EXAMPLE OF "GOTO"-REDUCING DESIGN IMPROVEMENT

Glad to see you've eliminated the BV'Last = Natural'Last error. However,
now Bit is constrained to the same range, so you'll get an exception if
BV'Last = Bit_Vector_Index'Last and there are no nodes to be created.
Bit should be Natural, so it can be greater than BV'Last.

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/