Ada 95 Problem Solving and Program Design

16.4 Continuing Saga: Multiple Concurrent Spiders

In Section 10.6 we developed the package specification Spiders for multiple spiders ( Program 10.19); we left the body as an exercise. However, we could not, at that time, consider how to program the spiders so that they acted independently of each other, crawling at will around the room. In this section, we show how to develop multiple concurrent spiders.

Developing a Task Type for Drunken Spiders

Recall the "drunken spider" program from Program 7.7. There the spider, in a state of inebriation, lurched around its room, taking a random number of steps and occasionally hitting the wall. Here we see a number of drunken spiders trying to get around, occasionally hitting the wall and sometimes bumping into each other. Suppose a spider refers to itself as Me. The main loop of that spider's life is given by:

    LOOP
    
      FOR Count IN 1..Random_20.Random (Gen => G) LOOP
    
        BEGIN   -- to handle exception
          Spiders.Step(Me);
        EXCEPTION
          WHEN Spiders.Hit_the_Wall =>  -- turn around
            Spiders.Right (Me);
            Spiders.Right (Me);
          WHEN Spiders.Hit_a_Spider =>  -- turn right
            Spiders.Right (Me);
        END;
    
      END LOOP;
    
      Spiders.Right (Me);
    
    END LOOP;

In an endless loop, the spider first selects a random number of steps in the range 1..20, then tries to step forward that number of times. If it hits the wall (Spiders.Hit_the_Wall is raised), it turns around and keeps stepping in the opposite direction; if it bumps into another spider (Spiders.Hit_a_Spider is raised), it turns right and continues its walk.

Program 16.7 shows a full program in which this loop is incorporated in a task type Drunken_Spider_Task, with a discriminant MyColor and a "start button" entry called Hatch. The discriminant has a default value Spiders.Black; this means that if a spider object declaration fails to provide a value for the discriminant, the default value will be taken.

Program 16.7
A Roomful of Drunken Spiders

WITH Spiders;
WITH Ada.Text_IO;
WITH Ada.Numerics.Discrete_Random;
PROCEDURE Drunken_Spiders IS
------------------------------------------------------------------------
--| Multiple drunken spiders try to tour their room.
--| The spiders are represented as task objects.
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: December 1995
------------------------------------------------------------------------
 
  SUBTYPE RandomSteps IS Positive RANGE 1..20;
 
  PACKAGE Random_20 IS NEW Ada.Numerics.Discrete_Random
    (Result_Subtype => RandomSteps);
 
  G: Random_20.Generator;  
 
  PACKAGE RandomHeading IS NEW Ada.Numerics.Discrete_Random
    (Result_Subtype => Spiders.Directions);
 
  D: RandomHeading.Generator;  
 
  -- Now a spider is a task object, as defined by this type.
  -- Note: default color is black.
  TASK TYPE Drunken_Spider_Task 
    (MyColor: Spiders.ScreenColors := Spiders.Black) IS
 
    -- one "start button" entry to bring spider to life
    ENTRY Hatch;
 
  END Drunken_Spider_Task;
 
  TASK BODY Drunken_Spider_Task IS
 
    Me: Spiders.Spider;
 
  BEGIN -- Drunken_Spider_Task
 
    ACCEPT Hatch;    -- come to life here
 
    -- Randomize all starting parameters
    Spiders.Start (Which => Me, 
                   Row => Random_20.Random(Gen => G), 
                   Col => Random_20.Random(Gen => G), 
                   WhichColor => MyColor, 
                   WhichWay => RandomHeading.Random(Gen => D));
 
    LOOP                     
 
      -- Spider will count steps correctly but might change direction
      FOR Count IN 1..Random_20.Random (Gen => G) LOOP
 
        BEGIN   -- to handle exception 
          Spiders.Step(Me);
        EXCEPTION
          WHEN Spiders.Hit_the_Wall =>  -- turn around 
            Spiders.Right (Me);
            Spiders.Right (Me);
          WHEN Spiders.Hit_a_Spider =>  -- turn right
            Spiders.Right (Me);
        END;
 
      END LOOP;
 
      Spiders.Right (Me);
 
    END LOOP;
 
  EXCEPTION
 
    WHEN OTHERS =>
      Ada.Text_IO.Put(Item => "This spider is dying.");
      Ada.Text_IO.New_Line;
 
  END Drunken_Spider_Task;
 
  -- Now declare some spider objects
  Charlotte : Drunken_Spider_Task(MyColor => Spiders.Green);
  Murgatroyd: Drunken_Spider_Task(MyColor => Spiders.Red);
  Arachne   : Drunken_Spider_Task(MyColor => Spiders.Blue); 
 
BEGIN -- Drunken_Spiders
 
  Spiders.DrawRoom;
 
  -- Bring the spiders to life, then stand back and watch!
  Charlotte.Hatch;
  Murgatroyd.Hatch;
  Arachne.Hatch; 
 
END Drunken_Spiders;

Within the task body is a local variable

    Me: Spiders.Spider;

which is referred to further in the task body. If we declare multiple objects of type Drunken_Spider_Task, each one will have its own Me variable.

The rest is straightforward: Each spider waits at its ACCEPT to be hatched, then calls Spider.Start with random values for the starting direction and position. At this point, the spider starts executing its main loop.

In Drunken_Spiders, three Drunken_Spider_Task objects are declared with their respective color discriminants. After the main BEGIN, each spider is brought to life, and nothing is left for the main program to do but watch the action.

Protecting the Spider Move Operation

We are not quite finished with the multiple spider example. Consider the algorithm for detecting a possible collision between spiders and acting accordingly:

Algorithm for Spider Move

1. Compute location into which spider is trying to move

2. IF the spider is trying to move to an occupied square THEN

3. RAISE Hit_a_Spider

ELSE

4. Step out of the current space into the unoccupied square

END IF;

Step 4 can be refined into

Step 4 Refinement

4.1 Draw a colored mark in the current square

4.2 Mark the current space as unoccupied

4.3 Mark the new space as occupied

4.4 Draw a spider symbol in the new square

There are therefore several operations to be done to record the spider's move, involving both the screen and the room board in which we keep track of occupancy. Because several spiders are crawling around concurrently, we must be sure that Steps 4.1 through 4.4 are done as a single operation. Consider a situation in which Murgatroyd executes its Step 4.1 and 4.2, vacating its square. but then--before Murgatroyd actually moves to its new space in Steps 4.3 and 4.4--Charlotte is able to move into that same square because it is not yet marked as occupied. This is not a very good situation--it leaves Murgatroyd without a square.

This is another example of a situation in which mutual exclusion is necessary. We can handle this by analogy with the screen protector from Program 16.6. We will define a protected type which "owns" the room array, with a procedure Move to encapsulate Steps 4.1 through 4.4 in one protected operation.

Let us add to the body of Spiders the following declarations:

    TYPE Status IS (Unoccupied, Occupied);
    TYPE BoardType IS ARRAY (RoomHeight, RoomWidth) OF Status;
    
    PROTECTED TYPE Room_Type IS
    
      PROCEDURE Move (Which: IN OUT Spider; HowMany: IN Natural);
    
    PRIVATE
    
      RoomBoard: BoardType := (OTHERS => (OTHERS => Unoccupied));
    
    END Room_Type;
    
    PROTECTED BODY Room_Type IS SEPARATE;
    
    Room: Room_Type;

Our protected type Room_Type has some memory, RoomBoard, that belongs to it exclusively, as indicated in the PRIVATE section. Move is a protected operation; a given call of Move will be executed in its entirety before another Move can be started. The declarations above show the protected body as a separate subunit; the subunit is given in full as Program 16.8.

Program 16.8
Protecting the Room Board from Multiple Accesses

SEPARATE (Spiders)
PROTECTED BODY Room_Type IS
------------------------------------------------------------------
--| Body of protected type for the spider's room.
--| The room array is protected from concurrent access by 
--| requiring all access to be via the protected procedure Move.
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: December 1995                                     
------------------------------------------------------------------
 
  PROCEDURE Move (Which: IN OUT Spider; HowMany: IN Natural) IS
    Row:    RoomHeight;
    Column: RoomWidth;
  BEGIN -- Move
 
    -- If out of bounds raise exception.
    IF NearWall (Which, HowMany) THEN
      RAISE Hit_the_Wall;
    END IF;
 
    Row    := Which.CurrentRow;
    Column := Which.CurrentColumn;
 
    -- Compute new proposed location
    CASE Which.Heading IS
      WHEN North =>
        Row := Which.CurrentRow - HowMany;
      WHEN East  =>
        Column := Which.CurrentColumn + HowMany;
      WHEN South =>
        Row := Which.CurrentRow + HowMany;
      WHEN West  =>
        Column := Which.CurrentColumn - HowMany;
    END CASE;
 
    -- Is this space occupied?
    IF RoomBoard(Row, Column) = Occupied THEN
      RAISE Hit_a_Spider;
    ELSE
 
      -- put a block down where spider is standing; vacate space
      DrawSymbol(Which => Which, WhichChar => ColorSymbols(Which.Ink));
      RoomBoard(Which.CurrentRow, Which.CurrentColumn) := Unoccupied;
 
      -- occupy new space
      RoomBoard(Row, Column) := Occupied;
      Which.CurrentRow    := Row;
      Which.CurrentColumn := Column;
      ShowSpider (Which);
 
    END IF;
 
  END Move;
 
END Room_Type;

All that remains is to modify the bodies of those operations in the Spiders package body which involve a move. Here is Jump, for example:

    PROCEDURE Jump (Which: IN OUT Spider; HowMany: IN Positive) IS
    BEGIN
    
      -- Concurrent spiders now, so move must be protected.
      Room.Move(Which, HowMany);
    
      IF Debugging = On THEN   -- if debug mode, wait for user to press RETURN
        Ada.Text_IO.Skip_Line;
      ELSE
        DELAY 0.1;
      END IF;
    
    END Jump;

We leave it to you as an exercise to complete the package body.

SYNTAX DISPLAY
Protected Type Specification

Form:
PROTECTED TYPE pname (optional list of discrimnents ) IS specifications of functions, procedures, and entries . . . PRIVATE declarations of encapsulated data structures END pname;

Example:

See the Room_Type and

ScreenManagerType

specifications in this chapter.

Interpretation:

The protected type specification gives a list of the procedures, functions, and entries to be provided by the protected objects. The PRIVATE part is optional.

SYNTAX DISPLAY
Protected Body

Form:
PROTECTED BODY pname IS BEGIN entry, procedure, and function bodies END pname;
Example:: See the Room_Type and ScreenManagerType bodies in this chapter.
Interpretation:: The protected body contains the bodies of the protected operations.

Arrays of Task Objects

Finally, we show an example of how tasks really do have aspects of data objects. Program 16.9 shows how we could create an array of spider objects.

Program 16.9
Creating an Array of Spiders

WITH Spiders;
WITH Ada.Text_IO;
WITH Ada.Numerics.Discrete_Random;
PROCEDURE Drunken_Spiders_Family IS
------------------------------------------------------------------
--| Multiple drunken spiders try to tour their room.
--| The spiders are represented as task objects;
--| a spider family is represented by an array of spiders.
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: December 1995
------------------------------------------------------------------
 
  SUBTYPE RandomSteps IS Positive RANGE 1..20;
 
  PACKAGE Random_20 IS NEW Ada.Numerics.Discrete_Random
    (Result_Subtype => RandomSteps);
 
  G: Random_20.Generator;  
 
  PACKAGE RandomHeading IS NEW Ada.Numerics.Discrete_Random
    (Result_Subtype => Spiders.Directions);
 
  D: RandomHeading.Generator;  
 
  -- Now a spider is a task object, as defined by this type.
  TASK TYPE Drunken_Spider_Task 
    (MyColor: Spiders.ScreenColors := Spiders.Black) IS
 
    -- one "start button" entry to bring spider to life
    ENTRY Hatch;
 
  END Drunken_Spider_Task;
 
  TASK BODY Drunken_Spider_Task IS
 
    Me: Spiders.Spider;
 
  BEGIN -- Drunken_Spider_Task
 
    ACCEPT Hatch;    -- come to life here
 
    -- Randomize all starting parameters
    Spiders.Start (Which => Me, 
                   Row => Random_20.Random(Gen => G), 
                   Col => Random_20.Random(Gen => G), 
                   WhichColor => MyColor, 
                   WhichWay => RandomHeading.Random(Gen => D));
 
    LOOP                     
 
      -- Spider will count steps correctly but might change direction
      FOR Count IN 1..Random_20.Random (Gen => G) LOOP
 
        BEGIN   -- to handle exception 
          Spiders.Step(Me);
        EXCEPTION
          WHEN Spiders.Hit_the_Wall =>  -- turn around 
            Spiders.Right (Me);
            Spiders.Right (Me);
          WHEN Spiders.Hit_a_Spider =>  -- turn right
            Spiders.Right (Me);
        END;
 
      END LOOP;
 
      Spiders.Right (Me);
 
    END LOOP;
 
  EXCEPTION
 
    WHEN OTHERS =>
      Ada.Text_IO.Put(Item => "This spider is dying.");
      Ada.Text_IO.New_Line;
 
  END Drunken_Spider_Task;
 
  SUBTYPE FamilyRange IS Positive RANGE 1..10;
  TYPE FamilyType IS ARRAY (FamilyRange) OF Drunken_Spider_Task;
 
  Family: FamilyType;   -- now we have an entire array of spiders
 
BEGIN -- Drunken_Spiders_Family
 
  Spiders.DrawRoom;
 
  -- Bring the spiders to life, then stand back and watch!
  FOR Which IN FamilyRange LOOP
   Family(Which).Hatch;
  END LOOP;
 
END Drunken_Spiders_Family;

Instead of declaring named spider variables as we did in Program 16.7, we give a few new declarations:

    SUBTYPE FamilyRange IS Positive RANGE 1..10;
    TYPE FamilyType IS ARRAY (FamilyRange) OF Drunken_Spider_Task;
    Family: FamilyType;   -- now we have an entire array of spiders

Here we declare Family as a ten-element array of spider task objects. As in the case of ordinary task variables, the entire array of spiders is activated just after the main BEGIN. We then cause all the spiders to hatch by using a simple FOR loop:

    FOR Which IN FamilyRange LOOP
      Family(Which).Hatch;
    END LOOP;

Varying the bounds of FamilyRange is sufficient to change the size of the spider family.