Selections from

M.B. Feldman and E.B. Koffman, Ada 95 Problem Solving and Program Design, 3rd edition. 

Copyright 1999, Addison-Wesley Publishing Company
ISBN 0-201-36123-X (textbook includes multiplatform CD-ROM). All Rights Reserved.

Publisher's information on this text is available from the Addison-Wesley web page.



Chapter 2: Introducing Algorithms: Adventures of the Spider

2.1 Introducing the Spider

2.2 Straight-Line Algorithms

Spider Commands with Parameters

2.3 Algorithms with Single Loops

Random Directions and Colors

2.4 Algorithms with Nested Loops

Spiral Patterns

2.5 Algorithms with Conditional Execution

Using Conditional Execution to Prevent Run-Time Exceptions

The General Loop Structure

Using EXIT WHEN instead of IF for Conditional Loop Execution

2.6 Putting It All Together: The Drunken Spider

Chapter Review


The purpose of this chapter is to introduce you to algorithms through programming a simple picture-drawing creature called the spider. This chapter is the first of several installments in a "continuing saga," an example that begins here and recurs in some sections of later chapters. We introduce an imaginary spider that steps around an imaginary room drawn on the screen. The spider recognizes a number of commands, which we can issue by writing, compiling, and executing spider programs.

We use the spider to introduce a number of algorithmic concepts, including control structures and parameters. We'll return to these much more formally and completely beginning in Chapter 3; the goal here is to just give you a quick introduction, to get you started writing some "fun" programs while you continue to read the more thorough chapters that follow.

This chapter and the other spider sections in the book are optional in the sense that no other parts of the book depend upon them. However, because they introduce programs that are very simple and clear and give you obvious feedback on the screen, we think you will find them useful in understanding algorithms and a number of Ada program constructs. We urge you to compile and run these examples on a computer, observe their behavior, and experiment with them by making changes as you see fit.


2.1 Introducing the Spider

This section introduces an imaginary spider that steps around an imaginary room drawn on the screen. The spider recognizes a number of commands, which we can issue by writing, compiling, and executing spider programs.

The spider is simulated by an Ada package within which is the set of commands that the spider recognizes and obeys. The package is a very important construct in Ada; it provides a way of encapsulating, or grouping, a set of related operations. Most Ada programs consist of a main procedure and a number of packages. We'll be using many packages in this book; some are standard Ada packages, and others are specific to the book. The spider package is one of the latter.

An Ada package is divided in two parts: the interface or specification, which gives a "table of contents" for the set of resources it provides, and the implementation or body, which contains the actual program segments for the various operations. Everything you need to know to use an Ada package is generally contained in the interface: There are specifications for the various resources and (in a well-written package) comments indicating how these are to be used.

The standard Ada packages are "built in," that is, provided with the compiler and ready to use. Generally, the interface and implementation for a nonstandard package like Spider are provided in the form of two Ada source files; we assume that you have access to this book's packages on the computer you are using.

The Spider specification is shown as Program 2.1 and explained in this chapter. We will study the body of the spider package in detail in Chapter 8. In this chapter, we just show and explain 14 programs that use some of the commands in the spider package; you don't need to understand yet just how the package works. By the time you've completed Chapter 8, you will be able to understand the spider package's internal mechanisms.

 Before you can use the spider package, you must compile (but not link) both the specification and the body. If you have a collection of this book's programs available on disk or CD-ROM, now is a good time to find and compile the two files. File names are not part of the Ada standard, but some compilers require certain naming conventions. The Spider specification and body files will probably be called spider.ads and spider.adb, respectively (ads = Ada specification; adb = Ada body). but the file names may vary. You will also need to compile the package Screen, whose file names are (most likely) screen.ads and screen.adb.

Program 2.1 The Spider Package

PACKAGE Spider IS|
----------------------------------------------------------------
--| This package provides procedures to emulate "Spider"
--| commands. The spider can move around
--| the screen drawing simple patterns.
--| Author: John Dalbey, Cal Poly San Luis Obispo, 1992
--| Adapted by M. B. Feldman, The George Washington University
--| Last Modified: December 1998
----------------------------------------------------------------

  -- These are the spider's simple parameterless method

  PROCEDURE Start;
  -- Pre:  None
  -- Post: Spider's room appears on the screen
  --   with spider in the center.

  PROCEDURE Quit;
  -- Pre:  None
  -- Post: End the drawing

  PROCEDURE Step;
  -- Pre:  None
  -- Post: Spider takes one step forward in the direction it is facing.
  -- Raises: Hit_the_Wall if spider tries to step into a wall.

  PROCEDURE TurnRight;
  -- Pre:  None
  -- Post: Spider turns 90 degrees to the right

  -- now some types, and methods that use the types

  TYPE Directions IS (North, East, South, West);
  TYPE Colors     IS (Red, Green, Blue, Black, None);
  SUBTYPE Steps IS Integer RANGE 1..20;

  PROCEDURE Face (WhichWay: IN Directions);
  -- Pre:  WhichWay has been assigned a value
  -- Post: Spider turns to face the given direction.

  FUNCTION IsFacing RETURN Directions;
  -- Pre:  None
  -- Post: Returns the direction the spider is facing.

  FUNCTION RandomDirection RETURN Directions;
  -- Pre:  None
  -- Post: Returns a random direction

  PROCEDURE ChangeColor (NewColor: Colors);
  -- Pre:  NewColor has been assigned a value
  -- Post: Spider leaves its tracks in the new color

  FUNCTION IsPainting RETURN Colors;
  -- Pre:  None
  -- Post: Returns the color in which the spider is painting

  FUNCTION RandomColor RETURN Colors;
  -- Pre:  None
  -- Post: Returns a random color

  FUNCTION AtWall RETURN Boolean;
  -- Pre:  None
  -- Post: Returns True if the spider is standing next to a wall

  FUNCTION RandomStep RETURN Steps;
  -- Pre:  None
  -- Post: Returns a random number in the range 1..20

  Hit_The_Wall: EXCEPTION;

  TYPE Switch IS (On, Off);

  PROCEDURE Debug (Setting: Switch);
  -- Pre:  None
  -- Post: Turns on or off single stepping through the program.

  FUNCTION  Debugging RETURN Switch;
  -- Pre:  None
  -- Post: Returns on or Off depending on Debug setting

END Spider;

2.2 Straight-Line Algorithms

In this section we use the spider to introduce you to straight-line algorithms. A straight-line algorithm is one that is just a straight sequence of instructions, with no decisions or "forks in the road" and no backtracking to an earlier point in the algorithm. The algorithm just moves in one direction.

Let's look at a very simple spider program, Program 2.2. As you can see, it just calls the spider's start and stop commands. The sample run shows that calling Spider.Start draws a "room" on the screen, placing the spider icon (an asterisk) in the center. The spider starts out facing north (up the screen). Calling Spider.Quit just ends the program.

Program 2.2 The Simplest Spider Program

WITH Spider;
PROCEDURE Startup IS
----------------------------------------------------------------
--| Very simple Spider program; just starts and stops
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------
BEGIN -- Startup
  Spider.Start;
  Spider.Quit;
END Startup;

Sample Run of Program 2.2

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| G |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . * . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------


In Program 2.3 the spider takes five steps forward. You can see this from the five commands, each reading Spider.Step. The sample run shows the spider in a location five rows north (upward) from the starting point.

Program 2.3 The Spider Walks a Line

WITH Spider;
PROCEDURE Walk_Line IS
----------------------------------------------------------------
--| Walk line with spider
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

BEGIN -- Walk_Line

  Spider.Start;

  Spider.Step;
  Spider.Step;
  Spider.Step;
  Spider.Step;
  Spider.Step;

  Spider.Quit;

END Walk_Line;

Sample Run of Program 2.3

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| G |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . * . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------

In Program 2.4 the spider walks around a square box, taking three steps forward, then turning right, then taking more steps, turning right again, and so on. Since it ends up back where it started from, there's nothing to show in the sample run. If you run the program, though, you'll observe the spider walking around the square.

Program 2.4 The Spider Walks around a Box

WITH Spider;
PROCEDURE Walk_Box IS
----------------------------------------------------------------
--| Walk 4 x 4 box with spider
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

BEGIN -- Walk_Box

  Spider.Start;

  Spider.Step;
  Spider.Step;
  Spider.Step;
  Spider.TurnRight;

  Spider.Step;
  Spider.Step;
  Spider.Step;
  Spider.TurnRight;

  Spider.Step;
  Spider.Step;
  Spider.Step;
  Spider.TurnRight;

  Spider.Step;
  Spider.Step;
  Spider.Step;
  Spider.TurnRight;

  Spider.Quit;

END Walk_Box;

Spider Commands with Parameters

So far, we've used four spider commands: Start, Quit, Step, and TurnRight. In Program 2.5 we introduce two more commands: Face and ChangeColor. Here are two lines selected from the specification in Program 2.1:
 
TYPE Directions IS (North, East, South, West);
TYPE Colors IS (Red, Green, Blue, Black, None);


These lines introduce enumeration types, which we'll cover in more depth in Chapter 4. For now, just understand that each of these types provides a list of values: Directions gives the four compass points, and Colors gives five possibilities: red, green, blue, white, and no color at all. We come now to two procedures defined in the specification:

PROCEDURE Face (WhichWay: IN Directions);
-- Pre:  WhichWay has been assigned a value
-- Post: Spider turns to face the given direction.

PROCEDURE ChangeColor (NewColor: Colors);
-- Pre:  NewColor has been assigned a value
-- Post: Spider leaves its tracks in the new color


The first, Face, must be called by including a parameter selected from one of the directions, for example,

Spider.Face(WhichWay => Spider.West);
which will cause the spider to turn (without moving) to face in a westerly direction (leftward on the screen). The second procedure, ChangeColor, must be called with a parameter selected from one of the color values, for example,
Spider.ChangeColor(NewColor => Spider.Red);
which will cause the spider to leave a red mark on the screen each time it takes a step.

As with all the packages provided by this book, each operation is accompanied by a pair of comments. These, like all comments, are ignored by the compiler but are important parts of the documentation that a human reader needs. The first comment describes the preconditions for using the operation. Preconditions are the expectations or assumptions the operation makes about the way it is called. In this case the precondition warns us that the operations must be called with well-defined direction and color values. The second comment gives the postconditions, that is, the results after the operation has completed its work.

The combination of preconditions and postconditions serve as a kind of contract between the writer of an operation and its user; if the user promises to meet the preconditions, the writer promises that the operation will deliver the postconditions.

Now let's use these two operations. In Program 2.5 the spider walks around the same kind of square as in Program 2.4, but this time it "draws" each side in a different "color." We've put "color" in quotation marks because the spider package does not require a color monitor to operate properly. As you can see from the sample run, the spider uses the letters R, G, B, and K to simulate the actual colors red, green, blue, and black. Also, a dot simulates the no-color ("invisible") case; it does not show up on the screen because a new dot is displayed over the one in the room grid. You've probably guessed by now that the spider starts up leaving its tracks in the "none" color, that is, leaving no tracks.

Now is a good time to mention the small status box in the upper-left corner of the screen, which displays the spider's current direction and color.

Program 2.5 The Spider Draws a Box

WITH Spider;
PROCEDURE Draw_Box IS
----------------------------------------------------------------
--| Draw 4 x 4 box with spider, changing colors as we go
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

BEGIN -- Draw_Box

 Spider.Start;

 Spider.Face(WhichWay => Spider.West);

 Spider.ChangeColor(NewColor => Spider.Green);
 Spider.Step;
 Spider.Step;
 Spider.Step;
 Spider.TurnRight;

 Spider.ChangeColor(NewColor => Spider.Black);
 Spider.Step;
 Spider.Step;
 Spider.Step;
 Spider.TurnRight;

 Spider.ChangeColor(NewColor => Spider.Red);
 Spider.Step;
 Spider.Step;
 Spider.Step;
 Spider.TurnRight;

 Spider.ChangeColor(NewColor => Spider.Blue);
 Spider.Step;
 Spider.Step;
 Spider.Step;
 Spider.TurnRight;

 Spider.Quit;

END Draw_Box;

Sample Run of Program 2.5

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| < |              |. . . . . . . . . . . . . . . . . . . .|
| B |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . R R R B . . . . . . . . . .|
                   |. . . . . . K . . B . . . . . . . . . .|
                   |. . . . . . K . . B . . . . . . . . . .|
                   |. . . . . . K G G * . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------
 

Exercises for Section 2.2

1. Write a spider program that requests the spider to draw two of your initials on the screen. For example,
XXXXX      X
X          X
XXX        X
X      X   X
XXXXX  XXXXX

2.3 Algorithms with Single Loops

Program 2.5 contains four sequences of almost identical statements. Leaving aside color changes for a moment, Program 2.5 contains sequences of the form
 
Spider.Step;
Spider.Step;
Spider.Step;
Spider.TurnRight;


This sequence appears four times in this straight-line program.

Algorithms quite frequently involve repetitive sequences of steps. Indeed, we could write the basic box-drawing algorithm as a repetition:

 Algorithm for drawing a box:

 1. Repeat steps 1.1 and 1.2 four times.

1.1 Take three steps forward.

 1.2 Turn right.


In programming, a repetition is generally called a loop. We can translate this algorithm into a program that uses an Ada control structure called the FOR construct. Program 2.6 contains just such a structure. The phrases

FOR Side IN 1..4 LOOP


 and
 

END LOOP;


instruct the spider to repeat, four times, whichever statement or sequence of statements appears between them. These two phrases are said to bracket the intervening statements; the intervening statements themselves are called the loop body. The FOR construct in this case starts a counter, called Side here, with the value 1, and carries out the loop body for each value of the counter from 1 to 4 inclusive (that is what 1..4 means).

Program 2.6 The Spider Draws a Box Using a Loop Control Structure

WITH Spider;
PROCEDURE Draw_Box_with_1_Loop IS
----------------------------------------------------------------
--| Draw 4 x 4 box with spider - use loop
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

BEGIN -- Draw_Box_with_1_Loop

  Spider.Start;

  Spider.ChangeColor(NewColor => Spider.Red);

  FOR Side IN 1..4 LOOP

    Spider.Step;
    Spider.Step;
    Spider.Step;
    Spider.TurnRight;

  END LOOP;

  Spider.Quit;

END Draw_Box_with_1_Loop;

Sample Run of Program 2.6

 
                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| R |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . R R R R . . . . . . .|
                   |. . . . . . . . . R . . R . . . . . . .|
                   |. . . . . . . . . R . . R . . . . . . .|
                   |. . . . . . . . . * R R R . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------


Random Directions and Colors

The box drawn by the spider in Program 2.6 is exactly the same every time the program is run: always in the same location, always red. Let's make the program more interesting by causing the spider to start walking in a randomly selected direction, and to change the color of each side by a random color selection. We can get random colors and directions from these two spider operations:
 
FUNCTION RandomDirection RETURN Directions;
-- Pre: None
-- Post: Returns a random direction

FUNCTION RandomColor RETURN Colors;
-- Pre: None
-- Post: Returns a random color


These have obvious meanings, made more so by the postconditions. Program 2.7 makes use of these operations to draw a box that will look different each time the program is one. The sample run shows just one execution; try running the program a number of times to observe its behavior.

Program 2.7 Drawing a Box Using Random Colors and Starting Direction

WITH Spider;
PROCEDURE Draw_Box_with_1_Loop_2 IS
----------------------------------------------------------------
--| Draw 4 x 4 box with spider - use loop
--| Colors and starting direction are selected randomly
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

  BEGIN -- Draw_Box_with_1_Loop_2

    Spider.Start;
    Spider.Face(WhichWay => Spider.RandomDirection);

    FOR Side IN 1..4 LOOP
      Spider.ChangeColor(NewColor => Spider.RandomColor);
      Spider.Step;
      Spider.Step;
      Spider.Step;
      Spider.TurnRight;
    END LOOP;

    Spider.Quit;

END Draw_Box_with_1_Loop_2;

Sample Run of Program 2.7

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| R |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . * G G K . . . . . . .|
                   |. . . . . . . . . R . . K . . . . . . .|
                   |. . . . . . . . . R . . K . . . . . . .|
                   |. . . . . . . . . R R R R . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------
 

Exercises for Section 2.3

1. Write and test a program that instructs the spider to draw a pattern in the shape of a highway "yield" sign, that is,
 
    RRRRRRR
     R   R
      R R
       R
Hints: Start the spider facing west, draw the top line, and so on. Also note that you can get the spider to draw a "blank" by changing its color to None.


2.4 Algorithms with Nested Loops

Programs 2.6 and 2.7 both contain a sequence of statements
 
Spider.Step;
Spider.Step;
Spider.Step;


which is, itself, a repetition. Let's take this into account by rewriting the box-drawing algorithm, adding the color change as we go:

Algorithm for drawing a box:

 1. Repeat steps 1.1 through 1.3 four times.

 1.1 Choose a color.

 1.2 Repeat step 1.2.1 three times.

 1.2.1 Take one step forward.
1.3 Turn right.
This algorithm is saying that each of the four times we reach step 1.2, we execute step 1.2.1 three times. The real power in algorithms is that we can combine straight-line sequences with repetitions (and conditional executions, as we shall see shortly) in almost unlimited ways.

How can we represent this new algorithm in a program? We can combine control structures, to reflect the algorithm steps. In this case we can include an entire FOR construct inside another one. To put it another way, a statement in a loop body can be another entire loop construct. This is called nesting control structures. Program 2.8 shows this: The inner loop construct

FOR Count IN 1..5 LOOP
 Spider.Step;
END LOOP;
is nested inside the outer one; for variety we changed the number of steps to 5. We use indentation in the program to highlight the nesting, as we use indentation in algorithms and other outlining methods. The indentation is not required by the compiler, but it certainly makes a difference in the clarity of the program! The behavior of this program is very similar to that of Program 2.7, so we have omitted the sample run. Try running it yourself several times to observe the randomness again.

Program 2.8 The Spider Draws a Box Using Nested Loop Control Structures

WITH Spider;
PROCEDURE Draw_Box_with_2_Loops IS
----------------------------------------------------------------
--| Draw 4 x 4 box with spider - use nested loops
--| Colors and starting direction are selected randomly
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

  BEGIN -- Draw_Box_with_2_Loops

    Spider.Start;
    Spider.Face(WhichWay => Spider.RandomDirection);

    FOR Side IN 1..4 LOOP
      Spider.ChangeColor(NewColor => Spider.RandomColor);
      FOR Count IN 1..5 LOOP
        Spider.Step;
      END LOOP;
   Spider.TurnRight;
    END LOOP;

    Spider.Quit;

END Draw_Box_with_2_Loops;


Spiral Patterns

So far, our loop constructs have used literals to represent the bounds (starting and ending values) of the counters. This is not required; loop bounds can vary. To see this, consider the loop structure of Program 2.9:
 
FOR Line IN 1..10 LOOP
  Spider.ChangeColor(NewColor => Spider.RandomColor);
  
  -- inner loop takes its bound from outer count
  FOR Count IN 1..Line LOOP
    Spider.Step;
  END LOOP;

  Spider.TurnRight;
END LOOP;


As the comment indicates, the inner loop takes its high bound from the current value of the outer loop's counter. When the first line is being drawn (Line is 1), the inner loop counter ranges from 1 to 1, so the spider takes one step. When the second line is drawn (Line is 2), the spider takes two steps, and so on until the spider takes ten steps to draw the tenth line. This results in the spiral pattern shown in the sample run; make sure you understand how this happens.

Program 2.9 The Spider Draws a Spiral Pattern

WITH Spider;
PROCEDURE Spiral IS
----------------------------------------------------------------
--| Draw spiral pattern with spider - use nested loops
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------
BEGIN -- Spiral

  Spider.Start;
  Spider.Face(WhichWay => Spider.RandomDirection);

  -- draw ten lines, starting in a random direction
  FOR Line IN 1..10 LOOP
    Spider.ChangeColor(NewColor => Spider.RandomColor);

    -- inner loop takes its bound from outer count
    FOR Count IN 1..Line LOOP
      Spider.Step;
    END LOOP;

    Spider.TurnRight;
  END LOOP;

  Spider.Quit;
END Spiral;

Sample Run of Program 2.9

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| < |              |. . . . . . . . . . . . . . . . . . . .|
| R |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . R R R R R R R R R R . . . . .|
                   |. . . . . G . . . . . . . . R . . . . .|
                   |. . . . . G . K K K K K K . R . . . . .|
                   |. . . . . G . K . . . . K . R . . . . .|
                   |. . . . . G . K . G G . K . R . . . . .|
                   |. . . . . G . K . . G . K . R . . . . .|
                   |. . . . . G . K . . . . K . R . . . . .|
                   |. . . . . G . . . . . . K . R . . . . .|
                   |. . . . . G G G G G G G G . R . . . . .|
                   |. . . . . . . . . . . . . . R . . . . .|
                   |. . . . . . . . . . . . . . * . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------
 

 
 
 
 
 

Exercises for Section 2.4

1. Write and test a program that instructs the spider to draw a pattern in the shape of a solid triangle, that is,
 B
 BB
 BBB
 BBBB
 BBBBB
 BBBBBB
2. Write a spider program to draw a checkerboard pattern, that is,
 G G G G
  G G G G
 G G G G
  G G G G





2.5 Algorithms with Conditional Execution

Another important algorithmic structure is conditional execution. To introduce the need for this, consider Program 2.10, which commands the spider to take 12 steps forward. As you can see from the sample run, this program terminates with the raising of an exception, in this case Spider.Hit_the_Wall.

Program 2.10 The Spider Crashes into a Wall

WITH Spider;
PROCEDURE Spider_Crash IS
----------------------------------------------------------------
--| This program demonstrates an Ada 95 runtime error.
--| Spider tries to take 12 steps from center of room;
--|   it hits the wall and an exception is raised.
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------
BEGIN -- Spider_Crash

  Spider.Start;
  Spider.ChangeColor(NewColor => Spider.Red);

  FOR Count IN 1..12 LOOP
    Spider.Step;
  END LOOP;

  Spider.Quit;

END Spider_Crash;

Sample Run of Program 2.10

                    ---------------------------------------
 ---               |. . . . . . . . . R . . . . . . . . . .|
| ^ |              |. . . . . . . . . R . . . . . . . . . .|
| R |              |. . . . . . . . . R . . . . . . . . . .|
 ---               |. . . . . . . . . R . . . . . . . . . .|
                   |. . . . . . . . . R . . . . . . . . . .|
                   |. . . . . . . . . R . . . . . . . . . .|
                   |. . . . . . . . . R . . . . . . . . . .|
                   |. . . . . . . . . R . . . . . . . . . .|
                   |. . . . . . . . . R . . . . . . . . . .|
                   |. . . . . . . . . R . . . . . . . . . .|
                   |. . . . . . . . . R . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    --------------------------------------- 

raised SPIDER.HIT_THE_WALL
 Traceback Information
     Program Name    File Name               Line
     ------------    ---------               ----
     spider.step     spider.adb              26
     spider_crash    spider_crash.adb        16
Because the spider started out in the middle of its room, it could not take more than ten steps forward in the same direction; its crashing into the wall is simulated in the spider package by this exception. The traceback--whose form, like that of a listing file, depends on the compiler--shows the line number in Spider_Crash in which the exception was raised, in this case line 16, or the Spider.Step statement. The traceback also shows where the exception originated, back in the Spider package body, but we are not studying that body yet.

The exception is Ada's mechanism for signaling an error condition in a program. A raised exception can be handled by the subprogram in which it raised, or by the one that called that subprogram, or, eventually, by the main program. The Ada standard prescribes that when an exception is raised in some called subprogram and is not handled there, it is propagated (passed back to) to the calling subprogram. If no subprogram handles the exception, it eventually comes back to the main program. If it is not handled in the main program either, the main program terminates, with or without a compiler-dependent traceback.


Using Conditional Execution to Prevent Run-Time Exceptions

We will take up exception handling in detail in Chapter 7. Meanwhile, it is important to consider how to prevent the exception from being raised. In this case the spider program can check to see whether the spider will step into a wall, using a conditional execution. The spider package provides a condition-testing, or Boolean operation
FUNCTION AtWall RETURN Boolean;
 -- Pre: None
 -- Post: Returns True if the spider is standing next to a wall
which will be true if, and only if, the spider will hit the wall on its next step.

Now in Program 2.11 the lines

IF Spider.AtWall THEN
 EXIT;
END IF;
test the condition Spider.AtWall. If the condition is true, the EXIT statement causes the program to exit the repetition early, continuing execution just below END LOOP. The effect of this in the current program is that the spider walks up to, but not into, the wall. You can see from the sample run that this program terminates normally, with no exception.

Program 2.11 The Spider Goes to the Wall and Stops

WITH Spider;
PROCEDURE Go_to_Wall IS
----------------------------------------------------------------
--| Spider steps up to the first wall it meets, then stops
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

BEGIN -- Go_to_Wall

  Spider.Start;
  Spider.ChangeColor(NewColor => Spider.Blue);

  FOR Count IN 1..12 LOOP
    IF Spider.AtWall THEN
      EXIT;
    END IF;
    Spider.Step;
  END LOOP;

  Spider.Quit;

END Go_to_Wall;


The General Loop Structure

In Program 2.11 the spider tries to count to 12 but never gets there because it reaches the wall and stops. In fact, it is unnecessary to count at all. We can use a general loop construct for this, as Program 2.12 shows.

Program 2.12 The Spider Goes to the Wall, Using a General Loop Structure

WITH Spider;
PROCEDURE Go_to_Wall_2 IS
----------------------------------------------------------------
--| Spider steps up to the first wall it meets, then stops
--| This version uses a general loop instead of a counting loop
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

BEGIN -- Go_to_Wall_2

  Spider.Start;
  Spider.ChangeColor(NewColor => Spider.Blue);

  LOOP
    IF Spider.AtWall THEN
      EXIT;
    END IF;
    Spider.Step;
  END LOOP;

  Spider.Quit;

END Go_to_Wall_2;
A general loop structure looks like a FOR structure without a FOR phrase. In the statements
LOOP
 IF Spider.AtWall THEN
  EXIT;
 END IF;
 Spider.Step;
END LOOP;
each time the program reaches the end of the loop body--in this case, after it has executed Spider.Step--it returns to the top of the loop body and executes the body again. Since the first statement of the loop body is our condition-testing construct, the program has the desired effect: it keeps looping until the spider reaches the wall, then stops.

General loops like this must be used with care. What if the condition never becomes true? (This will not happen in this program, of course, but might happen in some other program.) The program will keep looping indefinitely. Programs (especially embedded ones) are sometimes written to loop indefinitely, and we will see one shortly, but a program that unintentionally loops without stopping is a program with a bug in it!

Program 2.13 builds on the previous one by commanding the spider to take a walk around the edges of its room. The first section of the program repeats the general loop of Program 2.12; the second section consists of a four-repetition counting loop, inside of which is nested another general loop as above.

Program 2.13 The Spider Tours Its Room

WITH Spider;
PROCEDURE Tour_Room IS
----------------------------------------------------------------
--| Spider takes a tour around the edges of its room.
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

BEGIN -- Tour_Room

  Spider.Start;
  Spider.ChangeColor(NewColor => Spider.Blue);

  -- first get to a wall
  LOOP
    IF Spider.AtWall THEN
      EXIT;
    END IF;
    Spider.Step;
  END LOOP;

  -- now turn and tour the four walls
  FOR Wall IN 1..4 LOOP
    Spider.TurnRight;

    -- walk the length of this wall
    LOOP
      IF Spider.AtWall THEN
        EXIT;
      END IF;
      Spider.Step;
    END LOOP;
  END LOOP;

  Spider.Quit;

END Tour_Room;

Sample Run of Program 2.13

                    ---------------------------------------
 ---               |* . . . . . . . . B B B B B B B B B B B|
| ^ |              |B . . . . . . . . B . . . . . . . . . B|
| B |              |B . . . . . . . . B . . . . . . . . . B|
 ---               |B . . . . . . . . B . . . . . . . . . B|
                   |B . . . . . . . . B . . . . . . . . . B|
                   |B . . . . . . . . B . . . . . . . . . B|
                   |B . . . . . . . . B . . . . . . . . . B|
                   |B . . . . . . . . B . . . . . . . . . B|
                   |B . . . . . . . . B . . . . . . . . . B|
                   |B . . . . . . . . B . . . . . . . . . B|
                   |B . . . . . . . . B . . . . . . . . . B|
                   |B . . . . . . . . . . . . . . . . . . B|
                   |B . . . . . . . . . . . . . . . . . . B|
                   |B . . . . . . . . . . . . . . . . . . B|
                   |B . . . . . . . . . . . . . . . . . . B|
                   |B . . . . . . . . . . . . . . . . . . B|
                   |B . . . . . . . . . . . . . . . . . . B|
                   |B . . . . . . . . . . . . . . . . . . B|
                   |B . . . . . . . . . . . . . . . . . . B|
                   |B B B B B B B B B B B B B B B B B B B B|
                    ---------------------------------------

Using EXIT WHEN instead of IF for Conditional Loop Execution

Program 2.14 is very similar to Program 2.13, with identical screen behavior (and, therefore, no sample run).

Program 2.14 The Spider Tours Its Room, Using EXIT WHEN

WITH Spider;
PROCEDURE Tour_Room_2 IS
----------------------------------------------------------------
--| Spider takes a tour around the edges of its room.
--| This version uses EXIT WHEN instead of IF.
--| Author: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

BEGIN -- Tour_Room_2

  Spider.Start;
  Spider.ChangeColor(NewColor => Spider.Blue);

  -- first get to a wall
  LOOP
    EXIT WHEN Spider.AtWall;
    Spider.Step;
  END LOOP;

  -- now turn and tour the four walls
  FOR Wall IN 1..4 LOOP
    Spider.TurnRight;

    -- walk the length of this wall
    LOOP
      EXIT WHEN Spider.AtWall;
      Spider.Step;
    END LOOP;
  END LOOP;

  Spider.Quit;

END Tour_Room_2;
The difference is that the two conditional statements
IF Spider.AtWall THEN
 EXIT;
END IF;
are replaced with a more concise Ada equivalent,
EXIT WHEN Spider.AtWall;
which gives the indefinite loop construct
LOOP
 EXIT WHEN Spider.AtWall;
 Spider.Step;
END LOOP;

Exercise for Section 2.5

1. Modify Program 2.14 so that the spider covers the four walls completely but does not visit any parts of the walls a second time. Hint: Count the number of steps the spider takes while touring the first wall and the number of steps in touring the third (parallel) wall.


2.6 Putting It All Together: The Drunken Spider

Finally, we develop a spider program that puts together everything we've learned here. Imagine that the spider discovers a large glass of beer in its room and drinks enough beer to become inebriated (a fancy word for "drunk"). The spider tries to tour its room but is too drunk to do this properly. Instead, the spider tries to take a random number of steps. If it does so without reaching a wall, it turns right, selects another random number, and resumes walking. If the spider reaches a wall, it turns around and walks in the opposite direction, completing its count in the new direction. You can probably understand this program, Program 2.15, without further explanation.

Program 2.15 The Drunken Spider

WITH Spider;
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: M. B. Feldman, The George Washington University
--| Last Modified: July 1998
----------------------------------------------------------------

BEGIN -- Drunken_Spider

  Spider.Start;

  LOOP                     -- keep going forever

    Spider.Face(WhichWay => Spider.RandomDirection);
    Spider.ChangeColor(NewColor => Spider.RandomColor);

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

      IF Spider.AtWall THEN
        Spider.TurnRight;
        Spider.TurnRight;
      END IF;

      Spider.Step;

    END LOOP;

    Spider.TurnRight;

  END LOOP;

END Drunken_Spider;

Sample Run of Program 2.15

                    ---------------------------------------
 ---               |. R . . . R . . . . . . R . R . . . . .|
| ^ |              |. R . . . R . . . . . . R . R . . . . .|
| R |              |. R . . . R . . . . . . R . R . . . . .|
 ---               |. R . . . R . . . . . . R . R . . . . .|
                   |. R . . . R . . . . . . R . R . . . . .|
                   |. R . . . R . . . . . . R . K . . . . .|
                   |. R . . . R . . . . . . R . K . . . . .|
                   |. R . . . R . . . . . . R . K . . . . .|
                   |. R . . . R . . . . . . R . K . . . . .|
                   |. R . . . R K K K K K K K K K K K K G G|
                   |. R . . . R . . . G G R . . K . . . . .|
                   |. R . . . B B B B B B G G G K . . . . .|
                   |. R . . . . . . . . . . . . K . . . . .|
                   |. R K K K K K *^C K K K K K K . . . . .|
                   |. R . . . . . R . . . . . . B . . . . .|
                   |. R . . . . . R . . . . . . B . . . . .|
                   |. R . . . . . R . . . . . . B . . . . .|
                   |. R . . . . . R . . . . . . B . . . . .|
                   |. B B B B B B R . . . . . . B . . . . .|
                   |. . . . . . . . . . . . . . B . . . . .|
                    ---------------------------------------
The main loop in this program is a general loop without a count or EXIT condition to terminate it. It is therefore a program that will loop indefinitely. This is similar to the program in an automatic teller machine or similar embedded program, which terminates only when the equipment itself is shut off. In our case, we need not shut off the computer. Rather, in most computers, pressing the CONTROL and C keys simultaneously (usually referred to as ctrl-C) will terminate your currently executing program. In the sample run of Drunken_Spider, we pressed ctrl-C to stop the program; most terminals will display this on the screen as ^C, and you can see this here at the end of the bottom row of Bs.


Chapter Review

The goal of this chapter has been to get you started with developing algorithms and implementing them as programs using control structures. We introduced straight-line algorithms, as well as those with single and nested repetitive loops and with conditional execution. The spider has served as an easy-to-understand mechanism for introducing these structures; the patterns drawn by the spider gave you obvious feedback on the behavior of the spider programs.

Each structure and technique that we discuss here is covered in full detail, with many more applications, in the chapters to come: straight-line programming in Chapters 3 and 4, conditional execution in Chapter 5, counting loops in Chapter 6, general loops and exception handling in Chapter 7.

In this chapter--and most of the book--all the programs are in standard, platform-independent Ada, assuming only that your computer has a simple monochrome screen with 24 rows and 80 columns. In case you are wondering how to do high-resolution or color graphics with Ada, Appendix A shows how to do just this and even provides a high-resolution color spider package. High-resolution color graphics is always dependent upon a particular "platform" (computer plus operating system) and the kind of monitor you have.


last modified November 1, 1999