Re: No Go To's Forever!

[Robert Dewar <robert_dewar@my-deja.com>]

In article <HRkC4.1999$U95.38761@news.pacbell.net>,
  tmoran@bix.com wrote:
> >Well that's a different algorithm. It tests J against D'Last
> >twice as often as my formulation.
>   I would hardly call that a different algorithm.  Rather a
> different implementation of the same algorithm.  But if you
> want to call it different...

Of course it is different, it does a different sequence of
computations. The algorithm you give is computationally
equivalent, but you actually need to prove this, it is not
self evident! An algorithm is a prescription for a sequence
of computations, a different sequence is a different algorithm!

> That's
> going to be a relatively miniscule slowdown.  If the data is
> in order, yours does N comparisons against J and mine does
> N+1.
> If the data is sorted backwards, the worst case, yours does
> N + N*(N-1)/2 + N*(N-1)*(N-2)/6 comparisons against J and mine
> does an additional N*(N-1)/2+1  That's 66% more when N=2 (5 vs
3)
> declining to 3% more when N=100 (171,701 vs 166,750) and so
forth.
> Hardly "twice as many".  And nobody who cared would use this
> algorithm anyway.

Yes, but we are not talking efficiency here, we are talking
expression of algorithms. It is a sloppy response to change
the algorithm and then claim that pragmatically it is just
as good. That's not the point here at all. We are not trying
to write efficient sorting algorithms (this particular algorithm
is of course chosen to be space efficient).

Now let's look at your attempted rewrite:

     J := D'first;
      while J < D'last loop
         if D (J) >= D (J + 1) then   -- sorted so far
            J := J+1;                 -- continue
         else
            Swap (D (J), D (J + 1));  -- out of order, move item
            J := D'first;             -- and start over
         end if;
      end loop;

The objection here is again to the duplicated code. You have to
study this to see that the two assignments to J are identical.


Yes, in a trivial case like this, the code duplication is small,
but you must see that it is interesting that your only solutions
so far involve code duplication to get rid of the goto.

It is not at ALL clear that this is a good trade off. Additional
code, other things being equal is unlikely to be a good thing.
In a larger example, you can find the code duplication getting
worse, and even need to introduce a procedure to minimize it.

(side comment: from a pragmatic point of view, the reason we
use this algorithm is that it is short, so making it longer
by duplicating code is a bit counter productive).
Pragmatically of course, the whole idea of the


that J is always D'First. Unlike my original, where this
is evident without scanning the program, here you have a loop
whose advertised invariant.

I still find the original far clearer. Note that you felt it was
necesary to comment the reassignment to J as "start over", but
what could be clearer code to match the conceptual idea of
"start over" than going back to the beginning. Really it is
just like an instruction in a manual saying, "Now you have
completed your first reading, turn back to page 1 and start
reading again".

Let's once again look at my original:

>  <<Do_It_Again>>
>     for J in 1 .. N - 1 loop
>        if D (J) < D (J + 1) then
>           Swap (D (J), D (J + 1));
>           goto Do_It_Again;
>        end if;
>     end loop;

Just for interest, note that my version has

7 lines, 48 tokens
'
yours has

9 lines,  60 tokens

Furthermore, you have lost the fundamental point that the inner
loop is a FOR loop. We always prefer for loops to while loops
since they lead to a much clearer notion of total correctness.
Yes, it is true that the outer loop is a while loop and that
is fundamental, but I find your formulation really obscures
the fact that we have two nested loops here.

In fact I would NEVER rewrite this algorithm the way you did if
I did not have a goto. Instead I would write it this way if I
had a continue statement:

   Outer : loop
     Inner : for J in 1 .. N - 1 loop
        if D (J) < D (J + 1) then
           Swap (D (J), D (J + 1));
           continue Outer;
        end if;
     end loop Inner;
     exit Outer;
   end loop Outer;

That's also 9 lines, and 58 tokens, but preserves the essential
element
of two nested loops.

If your coding standards allow limited use of gotos to simulate
CONTINUE
then that's the best approach if you are not allowed the
original goto.

If you are writing in Ada with your hands tied behind your back
(no gotos)
then the clearest formulation is

   Continue := True;
   Outer : while Continue loop
      Continue := False;
      Inner : for J in 1 .. N - 1 loop
         if D (J) < D (J + 1) then
            Swap (D (J), D (J + 1));
            Continue := True;
            exit Inner;
         end if;
      end loop Inner;
   end loop Outer;

I am not very fond of this idiom for continue (I prefer the goto
idiom
for continue), but it is very familiar, so it seems fine.

This again avoids any code duplication, and preserves the
essential
structure of the algorithm as two nested loops.

Indeed the more I look at your rewriting, the less I like it,
you have
replaced a goto you don't like with spaghetti assignments that
obscure
the structure of the algorithm.

Replacing a for loop with a while loop with an increment is bad
in any
case. Replacing it with a while loop that plays games with the
control
variable to obtain the effect of two nested loops expressed with
one
loop at the syntactic level is really quite nasty.

I am always amazed by the extent to which people are willing to
go in
writing obscure code to avoid gotos; A triumph of form over
substance :-)


Sent via Deja.com http://www.deja.com/
Before you buy.