Re: Using Ada for device drivers? (Was: the Ada mandate, and why it collapsed and died)

["Robert I. Eachus" <rieachus@attbi.com>]

Robert I. Eachus wrote:

 > My favorite example is a program I wrote in a few hours to 
demonstrate > the "right" way to generate random permutations in Ada.

Hyman Rosen wrote:
> I think this is a perfect example of the blind spot of Ada programmers.
> You are so enamored of enumerations and perfectly indexed arrays and
> lack of buffer overflows that you will probably miss the most likely
> and subtle bug of this kind of code, which is that the Shuffle routine
> fails to produce each possible permutation with uniform probability!

Did you read what I wrote, really?  Should I have included the notes in 
the Shufflling routine which showed why this particular method of 
generation permutations was unbiased?  Okay done:

    procedure Shuffling (List : in out List_Type;
                         Gen  : in     Generator) is
-- a routine for producing permutations of a list of elements.  Note
-- that this method is unbiased for any independent sequence.  (For
-- any two cards the possibility that they will be in a particular
-- order is exactly 1/2, this can be extended by iteration to show
-- that each sequence has a probablity of 1/N!   Note that for large
-- lists of elements not all permutations will be generated.  There
-- are N! permutations of a list of N values, and this may be much
-- greater than the number of generator states.  Note also that the
-- actual number of different possible permutations generated from
-- one starting seed is k/GCD(N,k) for a generator with k states.

       List_Copy : constant List_Type := List;

       type Rec is
          record
             Index : Index_Type;
             Rand  : Float;
          end record;

       type Rec_Array is array (Index_Type range <>) of Rec;

       Temp : Rec_Array(List'Range);

       function "<" (L, R: Rec) return Boolean is
       begin return L.Rand < R.Rand; end "<";

       procedure Sort is new Sorting(Rec, Index_Type, Rec_Array, "<");

     begin
        for I in Temp'Range loop
           Temp(I) := (I, NFR.Random(Gen));
        end loop;

        Sort(Temp);  --  Sort based on value of random number

        --  Now rearrange List based on the order of indices in Temp
        for I in List'Range loop
           List(I) := List_Copy(Temp(I).Index);
        end loop;
     end Shuffling;

Again, no subtlety present or wanted.

Note that for Ada, the generator you get from Ada.Numerics.Float_Random 
will usually have more that 2^32 states.  If it is the one I wrote that 
is in Gnat, the GCD mentioned will be one, unless N has a factor that is 
one of two five digit primes. Oh, and this is the body of a generic 
where Element_Type, List_Type, and Index_Type are generic parameters. 
Okay? No?

Well if you really need a longer period generator, write me.  The other 
alternative is to combine two generators with independent seeds and 
periods.  Adding typical [0..1) generators and if >1, subtracting 1 
works just fine unless one of the generators is biased.  In fact, for 
most tests of randomness, you get more random behavior than either 
generator alone.