Re: No Go To's Forever!

[Jeff Carter <jrcarter@acm.org>]

Robert Dewar wrote:
> 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;


>    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;

Personally, I find both of these a bit difficult to follow due to the
lack of documentation. Maybe I'm wrong, but I think a variation on the
goto-less version is easier to document because the 2 loop are explicit:

-- Sort D into descending order
Repeat_Until_Sorted : loop
   Sorted := True; -- Assume D is sorted

   Find_Out_Of_Order_Pair : for J in D'First .. D'Last - 1 loop
      if D (J) < D (J + 1) then -- Found an out-of-order pair if True
         Swap (D (J), D (J + 1) );
         Sorted := False; -- We have not determined that D is sorted

         exit Find_Out_Of_Order_Pair; -- Repeat to see if D now sorted
      end if;
   end loop Find_Out_Of_Order_Pair;

   exit Repeat_Until_Sorted when Sorted;
   -- Did not find out-of-order pair if Sorted
end loop Repeat_Until_Sorted;

Now I can see what the algorithm is doing: It scans D looking for an
out-of-order pair of adjacent values. If it doesn't find one, then D is
sorted. If it does find one, it swaps them and repeats the entire
process. This looks like elimination of tail-recursion:

Find_Out_Of_Order_Pair : for J in D'First .. D'Last - 1 loop
   if D (J) < D (J + 1) then
      Swap (D (J), D (J + 1) );
      Sort (D);

      exit Find_Out_Of_Order_Pair;
   end if;
end loop Find_Out_Of_Order_Pair;
-- 
Jeff Carter
"Now go away or I shall taunt you a second time."
Monty Python & the Holy Grail