7.3 Continuing Saga: Random Numbers and the Drunken Spider

It is common in simulation and other applications to use random or pseudorandom numbers. A random number has a completely unpredictable value, (e.g., the Seconds part of a call to Ada.Calendar.Clock), that depends on the precise time it was called. Running the program at a different time of day will most likely give a different number. A pseudorandom sequence, on the other hand, is a sequence of numbers within a given range. The numbers are produced by some mathematical formula such that the numbers appear to have been chosen randomly, but the sequence can be repeated the next time the program is run.

Pseudorandom Numbers in Ada.Numerics

It is beyond our scope to discuss the mathematics of pseudo-random numbers, but it is useful to know that Ada provides random number generators in Ada.Numerics. Figure 7.5 shows part of the specification of a discrete random number generator.

Figure 7.5
Partial Specification for Ada.Numerics.Discrete_Random

GENERIC
  TYPE Result_Subtype IS (<>);
PACKAGE Ada.Numerics.Discrete_Random IS

  -- Basic facilities

  TYPE Generator IS LIMITED PRIVATE;

  FUNCTION Random (Gen : Generator) RETURN Result_Subtype;

  PROCEDURE Reset (Gen  : IN Generator);

PRIVATE

  ... -- as in Ada.Calendar.Time, we do not know the form of this

END Ada.Numerics.Discrete_Random;

This package is generic, like Ada.Text_IO.Enumeration_IO. Before it can be used, it must be instantiated or "tailored." You will learn more about writing and using generics in Chapter 11; for now, you need to know that the line

    TYPE Result_Subtype IS (<>);

means that the package can be instantiated for any integer or enumeration type or subtype and that the resulting instance will produce pseudorandom values in the range of that type or subtype. For example, to produce a generator of random integers in the range 1 to 50, we'd write

    SUBTYPE Fifty IS Integer RANGE 1..50;
    PACKAGE Random50 IS 
      NEW Ada.Numerics.Discrete_Random (Result_Subtype => Fifty);

The line

    TYPE Generator IS LIMITED PRIVATE;

indicates a type whose values have no operations available. Contrast this with Ada.Calendar.Time, a merely PRIVATE type whose values we can assign and test for equality. It is beyond our scope to explain why this type is necessary; to use the random number generator you must declare a variable of this type (say, G) and simply pass it to the operations Random and Reset each time you call them. For example, given a variable Number of type Fifty, the statement

    Number := Random50.Random (Gen => G);

stores in Number a pseudorandom value in the range 1 to 50. The random number generator produces a sequence of numbers. The generator starts itself with the same value (unknown to us) each time the program is run. Therefore, if we just make a sequence of calls as above, we will get the same sequence of values tomorrow as we did yesterday. The procedure Reset can be used to prevent this repetition of the sequence; for example, the call

    Random50.Reset(Gen => G);

causes the generator to be set from the time-of-day clock, so each run of the program produces a different sequence.

Example 7.13

Program 7.6 generates a sequence of 120 pseudo-random integers in the range 1..50. The nested loops provide for displaying these numbers in rows of 12. Try compiling this program and running it several times. Do you get the same sequence each time? Try "commenting out" the line that resets the generator and then recompiling the program and running it several times. Do you get the same sequence each time now?

Program 7.6
Generating a Pseudorandom Sequence

WITH Ada.Text_IO;
WITH Ada.Integer_Ada.Text_IO;
WITH Ada.Numerics.Discrete_Random;
PROCEDURE Random_Numbers IS
------------------------------------------------------------------------
--| Generates 120 random integers in the range 1..50
--| Uses the random number generator from Ada.Numerics
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: July 1995
------------------------------------------------------------------------

  SUBTYPE RandomRange IS Positive RANGE 1..50;

  PACKAGE Random_50 IS NEW Ada.Numerics.Discrete_Random
    (Result_Subtype => RandomRange);

  G: Random_50.Generator;     -- funny variable; we must keep 
                              -- passing it to Random, but can't use it.

BEGIN -- Random_Numbers

  Random_50.Reset (Gen => G);  -- starts G from time of day clock

  FOR Row IN 1..10 LOOP        -- displays 10 rows of 12 numbers

    FOR Num IN 1..12 LOOP

      Ada.Integer_Ada.Text_IO.Put
        (Item => Random_50.Random(Gen => G), Width => 4);

    END LOOP;

    Ada.Text_IO.New_Line;

  END LOOP;

END Random_Numbers;

Sample Run

  14  36  11   6  17   6  31  39  15  31  46  27
  35  43  12  35  43  44  39   1  35  33  21  46
  47  41  25  40  20  37  32  37   5  48  26  46
  50  30   2  30  13  30  39  25  13  11   7  45
  41  10   9  14  11   6  41  47  32  24  33  25
  15  15  27  26  32  36   5  34  47  30  22  21
   8  14  29  17  41  34  17  25  46  15  38  33
  43   5  31  13  23   1  30   3  46  14   8  10
   3  47   6  44  29  33  33  11  48  33   2   6
  42  14  45   5  38  29  34  43  38   9  32  23

The Drunken Spider

It was mentioned at the start of this section that random numbers are often used in simulations. Our spider package is really a simulator of sorts, imitating the actions of the spider in walking around its room.

Suppose the spider accidentally drank a quantity of beer and became intoxicated. Like any intoxicated creature, it would stagger forward for a while, then perhaps turn and keep trying to walk. Evetually it would walk into an obstacle, which would cause it to turn around and walk in the opposite direction.

Program 7.7 simulates the actions of this inebriated (drunken) spider. The spider, using an instance of the random number generator for the range 1 to 20, chooses a number of steps to take, say, 10. If it hits the wall before finishing 10 steps, it turns around and completes the count. Upon completing the desired number of steps, it turns right, chooses another random number and starts counting steps again. Note how the exception Spider.Hit_the_Wall is used to detect a collision.

Program 7.7
The Drunken Spider

WITH Spider;
WITH Ada.Numerics.Discrete_Random;
PROCEDURE Drunken_Spider IS
------------------------------------------------------------------------
--| Spider tries to tour its room but has drunk too much, so
--| takes a random number of steps and may hit the wall. If the
--| spider hits the wall, it turns around and keeps going.
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: July 1995
------------------------------------------------------------------------

  SUBTYPE RandomSteps IS Positive RANGE 1..20;

  PACKAGE Random_20 IS NEW Ada.Numerics.Discrete_Random
    (Result_Subtype => RandomSteps);

  G: Random_20.Generator;  -- funny variable; we must keep passing it
                           -- to Random, but can't use it.

  HowMany: RandomSteps;

BEGIN -- Drunken_Spider

  Spider.Start;

  LOOP                     -- keep going forever

    HowMany := Random_20.Random(Gen => G);

    -- Spider will count steps correctly but might change direction
    FOR Count IN 1..HowMany LOOP

      BEGIN   -- to handle exception 
        Spider.Step;
      EXCEPTION
        WHEN Spider.Hit_the_Wall =>  -- turn around 180 degrees
          Spider.Right;
          Spider.Right;
      END;

    END LOOP;

    Spider.Right;

  END LOOP;

END Drunken_Spider;

Sample Run

                    ----------------------------------------- 
 ---               |. . . . . . O O O O O O O O O O O O O O O|
| ^ |              |. . . . . . O . . . O . . . . . . O . O .|
| O |              |. . . . . . O . . . O . . . . . . O . O .|
 ---               |. . . . . . O . . . O . . . . . . O . O .|
                   |. . . . . . O O O O O O O O O O O O O O O|
                   |. . . . . . O . . . O O . . O . . O . O .|
                   |. . . . . . O O O O O O . . O . . O . O .|
                   |. . . . . . O . . . O O . . O . . O . O .|
                   |. . . . . . O . . . O O . . O . . O . O .|
                   |. . . . . . O . . . O O O O O O O O . O .|
                   |. . . . . . O . . . O . . . O . . . . O .|
                   |. . . O O O O O O O . . . . O . . . . O .|
                   |. . . O . . O . . O . . . . O . . . . O .|
                   |. . . O . . O . . O . . . . O . . . . O .|
                   |. . . O . . O . . O . . . . O . . . . O .|
                   |. . . O . . O . . O . . . . O . . . . O .|
                   |. . . O . . O . . O . . . . O . . . . O .|
                   |. . . O O O O . . O . . . . O O O . . O .|
                   |. . . . . . . . . * . . . . O . O O O O O|
                   |  . . . . . . . . O . . . . O . O . . . .|
                   |. . . . . . . . . O . . . . O . O . . . .|
                    -----------------------------------------

Programs that Never Halt

This program is a bit unusual in that its main loop has no stopping condition. Generally, we write programs that are designed to halt after a finite numbers of steps, and we think it undesirable if a program logic error causes the program not to halt. In this case, there is no harm in writing the program to continue indefinitely. The "bug" is our spider, which will just keep staggering until you interrupt the program from the keyboard. This kind of external interrupt is not part of Ada, but rather a function of the operating system. In most systems, pressing control-C will interrupt the program, but this is not always the case.

Programs that never halt are actually quite common in control systems. For example, an automatic teller machine has a program in it that starts when power is switched on and stops only when power is switched off. There is probably no halting code in the program itself. A nonhalting program is only undesirable if you did not intend to write it!

Exercises for Section 7.3

Programming

The discrete random number generator can be instantiated for enumeration types. Declare
```
TYPE Coin IS (Tails, Heads);
```
and write a program similar to Program 7.6 that generates and displays a large number of coin flips and counts the number of heads and tails. Instantiate Ada.Text_IO.Enumeration_IO to display the flips. Is the number of heads roughly the same as the number of tails? Do the heads and tails alternate, or are there runs of heads and runs of tails?
Modify Program 7.7 so that the spider also starts its random walk in a random direction. (Hint: The discrete random number generator can be instantiated for enumeration types.)