Karel J. Robot
A Gentle Introduction to the Art of Object-Oriented Programming in Java
This manuscript has not been published. It is Copyright, Joseph Bergin.
7 ADVANCED TECHNIQUES FOR ROBOTS
This chapter presents a number of quite challenging topics. First we will introduce the concept of recursion. Recursion, like loops, allows robots to execute a sequence of statements more than once. We will also look at the formal relationship between recursion and loops. Next, we study two interesting new instructions that give robots the ability to solve some novel beeper-manipulation problems, including numerical computations. Then we will look again at object-oriented programming and see some implications of what we have learned here.
7.1 Introduction to Recursion
Having thoroughly looked at loops in the last chapter, we are now going to examine a different way to get a robot to repeat an action. The technique is calledrecursion. The word means, simply, to recur or repeat. When a programming language allows recursive definitions or recursion, it means that within a new method we can send the same message (the one with the name of the executing method) to the executing robot. This may seem odd at first, but after a few examples, we hope that it will appear as natural as using a WHILE loop to control a robot's execution. We note that recursion is just another control structure and, while it may appear magical at first, it can be understood as readily as loops. It is another programming tool to add to your collection.
In all of the examples prior to Chapter 6, when we asked a robot to move from one point to another, we knew exactly how far it would move. There are many situations, however, in which this is not true. Suppose, for example, that a robot named Kristin is standing at the origin facing east, and suppose that there is a beeper somewhere along 1st Street. We want Kristin to go to the beeper and pick it up and return to the origin.
Kristin.retrieveBeeper ();
If we knew that the beeper was on 1st and 23rd we would be able to write a program without loops to do this. If we knew that it was no more than, say, 15 blocks away, then we could find a solution. (How?) But what if we don't know how far it is. To get started, let's build a new class: BeeperFinder.
public class BeeperFinder extends Robot
{
public void retrieveBeeper ()
{ findBeeper();
pickBeeper();
turnLeft();
turnLeft();
returnToWestWall();
}
public void findBeeper(){...}
public void returnToWestWall(){...}
}
Well, that will certainly do the job, if we can write the other two new methods. Let's now attack findBeeper. We know that there is a beeper somewhere on 1st Street. We also know that Kristin is on 1st Street facing East. It may be that Kristin is already on the beeper corner, in which case there is nothing to do. Therefore we may get started by writing:
public void findBeeper()
{ if (! nextToABeeper())
{
...
}
}
This will correctly terminate having done nothing if Kristin is already at the beeper corner. Suppose next that the beeper is on some other corner. Then Kristin needs to move, of course, and check other corners.
public void findBeeper()
{ if (! nextToABeeper())
{ move();
???
}
}
Well, what does Kristin need to do after a move? Notice that Kristin is on a different corner than the one on which it started and that the original corner was checked and found to lack a beeper. Therefore we may conclude that the beeper is now (after the move) either at Kristin's current location or farther East of it. But this is exactly the same situation (relatively) that Kristin was in when it started this task. Therefore, we can conclude that what Kristin needs to do now is exactly findBeeper and nothing more.
public void findBeeper()
{ if (! nextToABeeper())
{ move();
findBeeper();
}
}
Notice that findBeeper has been completely defined, but it has been defined by using findBeeper itself. How can this be done? Well, suppose we needed to empty an ocean with a bucket. To perform emptyTheOcean, we first ask if the ocean is empty. If so, we are done. Otherwise we just remove one bucket of water from the ocean and then emptyTheOcean.
The important thing in such a definition, called a recursive definition, is that we don't define a thing in terms of precisely itself. We define a thing in terms of a simpler or smaller version of itself, and also define the smallest or simplest version separately. Here we define findBeeper as either "nothing", if Kristin is already on the beeper corner, or "move(); findBeeper();", if Kristin is anywhere else. It is also necessary to know before we start executing such an instruction that there is, indeed, a beeper somewhere in Kristin's path. Otherwise, after every move, the reexecution of findBeeper will find that the test is true, generating yet another reexecution of findBeeper without end.
The other method, returnToWestWall is similar, except for the test. Here, however we know that there is a wall to the west. If we can guarantee that the robot is also facing west, then the following method will serve.
public void returnToWestWall()
{ if (frontIsClear())
{ move();
returnToWestWall() ;
}
}
Programming with recursion is a very powerful and sometimes error-prone activity.
7.2 More on Recursion
Given the problem--a robot must clean all beepers from its current corner--we could easily write a loop that looks like the following.
public class Sweeper extends Robot
{
public void sweepCorner()
{ while ( nextToABeeper() )
{ pickBeeper();
}
}
...
}
This correctly solves the problem and is known as an iterative solution
("iterative" means that a loop of some sort, WHILE or
FOR- LOOP, was used). Contrast this solution with a recursive one.
public void sweepCorner()
{ if ( nextToABeeper() )
{ pickBeeper();
sweepCorner();
}
}
The difference between these two methods is very subtle. The first method, which uses the WHILE loop, is called once and the robot's focus never leaves the loop until it is finished, executing zero or more pickBeepers (depending on the initial number on the corner). What happens in the second, recursive, sweepCorner? Let's look at it very carefully.
If the robot is initially on an empty corner when the message is sent, nothing happens (similar to the WHILE loop). If it is on a corner with one beeper when the message is sent, the IF test is true, so the robot executes one pickBeeper instruction (thus emptying the corner). It then makes a second call of sweepCorner, remembering where it was in the first call. When sweepCorner is called the second time, the IF test is false, so nothing happens and the robot returns to the first call.
[initial instantiation of]
public void sweepCorner()
{ if ( nextToABeeper() )
{ pickBeeper();
sweepCorner(); // <-- This is the second call to
} //sweepCorner. The robot will return to
} //this point when that call
// finishes executing.
[second instantiation of]
public void sweepCorner()
{ if ( nextToABeeper() ) // <-- this is now false
{ pickBeeper();
sweepCorner();
}
}
Each call results in a separate instance (or instantiation) of the instruction sweepCorner. The robot must completely execute each instance, always remembering where it was in the previous instance so it can return there when it finishes.
The process for writing recursive robot instructions is very similar to that for writing loops:
Step 1: Consider the stopping condition (also called the base case)--what is the simplest case of the problem that can be solved? In the sweepCorner problem, the simplest, or base, case is when the robot is already on an empty corner.
Step 2: What does the robot have to do in the base case? In this example there's nothing to do.
Step 3: Find a way to solve a small piece of the larger problem if not in the base case. This is called "reducing the problem in the general case." In the sweepCorner problem, the general case is when the robot is on a corner with one or more beepers and the reduction is to pick up a beeper.
Step 4: Make sure the reduction leads to the base case. Again, in the above example of sweepCorner, by picking up one beeper at a time, the robot must eventually clear the corner of beepers, regardless of the original number present.
Let's compare and contrast iteration and recursion:
* An iterative loop must complete each iteration before beginning the next one.
* A recursive method typically begins a new instance before completing the current one. When that happens, the current instance is temporarily suspended, pending the completion of the new instance. Of course, this new instance might not complete before generating another one. Each successive instance must be completed in turn, last to first.
* Since EACH recursive instance is supposed to make some (often minimal) progress toward the base case, we should not use loops to control recursive calls. Thus, we will usually see an IF or an IF/ELSE in the body of a recursive new method, but not a WHILE.
Suppose we wanted to use recursion to move a robot named Karel to a beeper. How would we do it? Following the steps presented earlier:
* What is the base case? Karel is on the beeper.
* What does the robot have to do in the base case? Nothing.
* What is the general case? The robot is not on the beeper.
* What is the reduction? Move toward the beeper and make the recursive call.
* Does the reduction lead to termination? Yes, assuming the beeper is directly in front of the robot , the distance will get shorter by one block for each recursive call.
The final implementation follows.
public void findBeeper()
{ if ( ! nextToABeeper() )
{ move();
findBeeper();
}
}
Note that this problem could also have been easily solved with a WHILE loop. Let's look at a problem that is not easily solved with a WHILE loop. Remember the Lost Beeper Mine, the corner with a large number of beepers? Imagine we must write the following method in our search for the mine. A robot named Karel must walk east from its current location until it finds a beeper. The Lost Beeper Mine is due north of that intersection a distance equal to the number of moves Karel made to get from its current position to the beeper. Write the new method, findMine.
It is not easy to see how to solve this problem with a WHILE loop as we do not have any convenient way of remembering how many intersections have been traversed. Oh, we could probably come up with a very convoluted beeper-tracking scheme, but let's look at a recursive solution that's pretty straightforward. Again, we'll answer our questions:
* What is the base case? Karel is on the beeper.
* What does Karel have to do in the base case? turnLeft (this will face Karel north).
* What is the general case? Karel is not on the beeper.
* What is the reduction? Move one block forward, make the recursive call and have Karel execute a second move after the recursive call. This second move will be executed in all instances but the base case, causing Karel to make as many moves north after the base case as it did in getting to the base case.
* Does the reduction lead to termination? Yes, assuming the beeper is directly in front of Karel.
Let's look at the complete method:
public void findMine()
{ if ( nextToABeeper() )
{ turnLeft();
}
else
{ move();
findMine();
move();
}
}
How many turnLefts are executed? How many moves? How many calls to findMine?
A good way to think about recursion and the recursive call is in terms of the specification of the method itself. In the above case, the specification is that when a robot executes this instruction it will walk a certain number of steps, say k, to a beeper, turn left, and then walk k steps farther. Suppose we start the robot N steps away from the beeper (k = N). When we examine the method above, the ELSE clause has a move message first. That means that the robot is now N-1 steps from the beeper. Therefore, by the specification, the recursive (k = N-1) call will walk N-1 steps forward, turn left, and then walk N-1 steps beyond. We therefore need to supply one additional move message after the recursion to complete the required N steps.
It will take solving a number of problems and a good deal of staring before recursion becomes as comfortable to use as iteration. A large part of this is because recursion requires some intuition to see the correct reduction, especially in difficult problems. This intuition will come with practice, which is just what the sample problems are designed to provide.
7.3 Tail Recursion and Looping
Suppose we have an method with a WHILE loop and we would like to rewrite it so that it doesn't use a loop, but still carries out the same task. To consider the simplest case, suppose that the outermost control mechanism in an method is a loop. Take, for example, the method
public void findBeeper()
{ while ( ! nextToABeeper())
{ move();
}
}
By the definition of the WHILE given in Section 6.2, this is the same as
public void findBeeper()
{ if ( ! nextToABeeper())
{ move();
while ( ! nextToABeeper()) <--
{ move(); <-- findBeeper
} <--
}
}
However, the nested WHILE instruction in this latter form is exactly the body of findBeeper using the definition of findBeeper given first, so we can rewrite this second form as:
public void findBeeper()
{ if ( ! nextToABeeper())
{ move();
findBeeper();
}
}
Thus, the first form, a while, is equivalent to the last form, a recursive program. Also notice that we could just as easily transform the second form into the first, since they are execution equivalent.
Notice, finally, that this is a special form of recursion, since after the recursive step (the nested findBeeper) there is nothing more to do in this method. It is, after all, the last instruction within an IF instruction, so when it is done, the IF is done, and therefore the method of which this is the body is done. This form of recursion is called tail recursion, because the recursive step comes at the very tail of the computation.
It is possible to prove formally that tail recursion is equivalent to WHILE looping. Therefore, we can see that a WHILE loop is just a special form of recursion. So anything that you can do with a loop, you can also do with a recursive program. There are some deep and beautiful theories in computer science (and in mathematics) that have been developed from this observation.
By way of contrast, the findMine method discussed in Section 7.2, was certainly recursive, but it is not tail-recursive, because the final move message follows the recursive message. That method is also equivalent to one using only WHILE loops, but, as suggested in Section 7.2, it is very convoluted.
7.4 Going Formal
At the beginning of this chapter we saw that it is possible to get a robot to perform an operation repeatedly without using LOOP or WHILE instructions. Perhaps you are wondering if there is a relationship between recursive programming and iterative programming. The answer, of course, is yes and we would like to go a bit deeper into the relationship.
In Chapter 6, we learned about the WHILE instruction and how to use it. However, the description we gave of it was somewhat informal, relying on examples and intuition. That is fine at the beginning, but it is also useful to look at a formal definition of a WHILE statement, so that it can be analyzed logically.
Suppose we permit instructions themselves to be named. We don't permit this in the robot language itself, only in talking about the robot language. This is the so-called meta level; the level at which we don't use a thing (the programming language), but discuss and analyze it. In any case, suppose that we let the simple WHILE statement form "while (<test>){<instruction-list>}" be known as statement W. Let us also denote the <test> of the WHILE as T and the <instruction-list> as L. Then W can be written as:
W == while ( T ) { L }
The formal definition of W is
W == if ( T ){ L; W; }
This says that to perform the while instruction W we must first test T ( if (T) . . . ) and if T is false, do nothing at all, but if T is true, then we must perform L followed by W, the while instruction itself. By the definition this means that we must test T again and if it is false do nothing else, but if it is true, we must perform L again followed by W again, etc.
The looping should be clear from this description, but if you look at the definition we have written, you see the recursive nature of the WHILE. This means that the WHILE statement W is defined in terms of itself, since W appears on the right side of the definition as well as the left. We hope that the W on the right is not exactly the same as the one on the left, but a simpler, smaller version of the W that appears on the left. What that means is that for a while loop to make sense, or be defined, the execution of the instruction list L, must partially solve the problem that the entire WHILE set out to solve, and take us closer to termination of the loop. If that is not the case, and the execution of L leaves the robot in the same state, relative to termination, that it was in at the start, then the loop is guaranteed to run forever. This is because in this case the definition is purely circular and so doesn't define anything.
7.5 Searching
This section introduces two new methods named zigLeftUp and zagDownRight, that move a robot diagonally northwest and southeast respectively. Both of these methods are defined by using only UrRobot's methods such as turnLeft, but we derive immense conceptual power from being able to think in terms of moving diagonally. For reasons that will become clear in the exercises, the class into which we put these methods is Mathematician. It will have the class Robot as the parent class.
The following definitions introduce the stars of this section: zigLeftUp and zagDownRight. These direction pairs are not arbitrary; if a robot moves to the left and upward long enough, it eventually reaches the western boundary wall. The same argument holds for traveling down and toward the right, except that in this case the robot eventually reaches the southern boundary wall.
The other two possible direction pairs lack these useful properties: a robot will never find a boundary wall by traveling up and toward the right, and we cannot be sure which of the two boundary walls it will come upon first when traveling downward and to the left.
The following methods define zigLeftUp and zagDownRight.
public class Mathematician extends Robot
{
public void zigLeftUp ()
{ // Precondition: facingWest and frontIsClear
// Postcondition: facingWest
move();
turnRight();
move();
turnLeft();
}
public void zagDownRight()
{ // Precondition: facingSouth and frontIsClear
// Postcondition: facingSouth
move();
turnLeft();
move();
turnRight();
}
...
}
Assume that we have a Mathematician named Karel. Observe that no part of these methods forces Karel to move in the intended directions. To execute zigLeftUp correctly, Karel must be facing west; to execute zagDownRight correctly, Karel must be facing south. These requirements are called the pre-conditions of the methods. Recall that a pre-condition of a method is a condition that must be made true before a robot can correctly execute the method. We have seen many other examples of pre-conditions in this book.
For this example, the directional pre-condition of zigLeftUp is that Karel is facing west; likewise, the directional pre-condition of zagDownRight is that Karel is facing south. Karel's execution of these methods, when their pre-conditions are satisfied, is shown in Figure 7-1.
Figure 7-1: Execution of the Zig-Zag Methods
Here is a statement that is loaded with terminology: the directional pre-conditions of zigLeftUp and zagDownRight are invariant over each instruction's execution. This just means that if Karel is facing west and it executes zigLeftUp , the robot is still facing west after the instruction has finished executing. This property allows Karel to execute a sequence of zigLeftUp 's without having to reestablish their directional pre-condition. A similar statement holds about Karel's facing south and zagDownRight. Also observe that each instruction must be executed only when Karel's front is clear. This pre-condition is not invariant over the instructions, because Karel may be one block away from a corner where its front is blocked (e.g., Karel may execute zigLeftUp while facing west on the corner of 4th Street and 2nd Avenue).
The first major method that we will write solves the problem of finding a beeper that can be located anywhere in the world. Our task is to write an method named findBeeper that positions Karel on the same corner as the beeper. We have seen a version of this problem in Chapter 6 where both Karel and the beeper are in an enclosed room. This new formulation has less stringent restrictions: the beeper is placed on some arbitrary street corner in Karel's world, and there are no wall sections in the world. Of course, the boundary walls are always present.
One simple solution may spring to mind. In this attempt, Karel first goes to the origin and faces east. The robot then moves eastward on 1st Street looking for a beeper. If Karel finds a beeper on 1st Street, it has accomplished its task; if the beeper is not found on 1st Street, Karel moves back to the western wall, switches over to 2nd Street, and continues searching from there. Karel repeats this strategy until it finds the beeper. Unfortunately, a mistaken assumption is implicit in this search instruction: there is no way for Karel to know that the beeper is not on 1st Street. No matter how much of 1st Street Karel explores, the robot can never be sure that the beeper is not one block farther east.
It looks as if we and Karel are caught in an impossible trap, but there is an ingenious solution to our problem. As we might expect, it involves zig-zag moves. We need to program Karel to perform a radically different type of search pattern; Figure 7-2 shows such a pattern, and we use it below to define the findBeeper method.
Figure 7-2: A Method for Searching Every Corner
This search method expands the search frontier similar to the way water would expand over Karel's world from an overflowing sink at the origin. Roughly, we can view Karel as traveling back and forth diagonally on the fringe of this water wave. Convince yourself that this search pattern is guaranteed to find the beeper eventually, regardless of the beeper's location--in our analogy, we need to convince ourselves that the beeper will eventually get wet. We can use stepwise refinement to write the findBeeper method using this search strategy with the zigLeftUp and zagDownRight methods.
public void findBeeper()
{ goToOrigin();
faceWest();
while ( ! nextToABeeper() )
{ if ( facingWest() )
{ zigMove();
}
else
{ zagMove();
}
}
}
The findBeeper method starts by moving Karel to the origin and then facing west. (We saw how to write the faceWest instruction in Chapter 5.) These messages establish the directional pre-condition for zigLeftUp . The WHILE loop's purpose is to keep Karel moving until it finds a beeper, and is correct if the loop eventually terminates. The IF condition, which is nested within the body of the loop, determines which direction Karel has been traveling and continues moving the robot along the diagonal in this same direction. We continue the stepwise refinement by writing zigMove and zagMove.
public void zigMove()
{ // Pre-condition: facingWest
if ( frontIsClear() )
{ zigLeftUp ();
}
else
{ advanceToNextDiagonal();
}
}
and
public void zagMove()
{ // Pre-condition: facingSouth()
if ( frontIsClear() )
{ zagDownRight();
}
else
{ advanceToNextDiagonal();
}
}
The moving methods, zigMove and zagMove operate similarly; therefore we discuss only zigMove. When Karel is able to keep zigging, the zigMove method moves it diagonally to the next corner; Otherwise, the robot is blocked by the western boundary wall and must advance northward to the next diagonal. We now write the method that advances Karel to the next diagonal.
public void advanceToNextDiagonal()
{ if ( facingWest() )
{ faceNorth();
}
else
{ faceEast();
}
move();
turnAround();
}
The advanceToNextDiagonal method starts by facing Karel away from the origin; it turns a different direction depending on whether the robot has been zigging or zagging. In either case, Karel then moves one corner farther away from the origin and turns around. If Karel has been zigging on the current diagonal, after executing advanceToNextDiagonal, the robot is positioned to continue by zagging on the next diagonal, and vice versa.
Observe that when Karel executes a zigLeftUp or a zagDownRight method, it must visit two corners; the first is visited temporarily, and the second is catty-corner from Karel's starting corner. When thinking about these methods, we should ignore the intermediate corner and just remember that these instructions move Karel diagonally. Also notice that the temporarily visited corner is guaranteed not to have a beeper on it, because it is part of the wave front that Karel visited while it was on the previous diagonal sweep.
Trace Karel's execution of findBeeper in the sample situation presented in Figure 7-2 to acquaint yourself with its operation. Try to get a feel for how all these instructions fit together to accomplish the task. Pay particularly close attention to the advanceToNextDiagonal method. Test findBeeper in the situation where the beeper is on the origin and in situations where the beeper is next to either boundary wall.
7.6 Doing Arithmetic
One of the things that computers do well is manipulating numbers. Robots can be taught to do arithmetic as we shall see. One way to represent numbers in the robot world is to use beepers. We could represent the number 32 by putting 32 beepers on a corner, but we can be more sophisticated. Suppose that we represent the different digits of a multi-digit number separately. Therefore to represent the number 5132 we could, using 2nd street as an example of a place to put the number, put 5 beepers at 2nd Street and 1st Avenue, 1 beeper at 2nd and 2nd, 3 beepers at 2nd and 3rd, and 2 beepers at 2nd and 4th. We could write a whole column of numbers as shown in Figure 7. 3.
Figure 7.3 A Column of Numbers to be Added.
Let's start with a simpler case, however and just add up a column of single digit numbers. See Figure 7.4 for an example. Suppose we start with an Adder robot on 1st Street with a column of numbers represented by beepers north of it. On each such corner there will be between 1 and 9 beepers. We want to "write" on 1st Street the decimal number representing the sum of the column. Since we must "carry" if the total number of beepers is more than 9 we assume that we are not starting at 1st Avenue.
Figure 7.4 Adding Single Digit Numbers Before and After
Our adder robot will utilize two helper robots. The first of these will check to see if a carry is necessary and the second will actually do the carry if it is necessary. Since these robots will need to be created and find the adder robot that created them, we will start with a super (parent) class that provides this finding method. All of our other classes for this problem will be derived as subclasses of this base class; Finder. We won't actually create any Finder robots, however. This class is just a convenient place to place methods that must be common to other classes.
public class Finder extends Robot
{
public void turnAround(){...}
public void turnRight(){...}
public void moveToRobot() // Robot directly ahead.
{ while( ! nextToARobot() )
{ move();
}
}
...
}
public class Carrier extends Finder
{
public void carryOne(){...} // Carry a "one" to the next column
}
public class Checker extends Finder
{
public boolean enoughToCarry(){...} // Are there enough to require carrying?
. . .
}
public class Adder extends Finder // Always create on 1st Street, facing North.
{
private Carrier Carry = new Carrier(1,1, East, infinity);
private Checker Check = new Checker(1,1, East, 0);
public void gatherHelpers(){...}
public void addColumn(){...}
. . .
}
public void gatherHelpers() // Adder class
{ Carry.findRobot();
Carry.turnLeft();
Check.findRobot();
Check.turnLeft();
}
Once the Adder robot has created its helpers, it can execute addColumn. To do this it merely picks up all of the beepers north of it until it finds an empty corner, returns to 1st Street, deposits all of the beepers there and then has the helpers finish the task.
public void addColumn() // Facing north on 1st Street.
{ move();
while(nextToABeeper()
{ pickBeeper();
if ( ! nextToABeeper() )
{ move();
}
}
turnAround();
while( frontIsClear() )
{ move();
}
turnAround();
while ( anyBeepersInBeeperBag() )
{ putBeeper();
}
// Compute the quotient and the remainder.
while( Check.enoughToCarry()
{ Carry.carryOne();
}
}
Carrying is quite simple. Notice that we gave the Carrier an infinite number of beepers in its beeper-bag, so it can't possibly run out.
public void carryOne() // Facing north on 1st Street. -- Carrier class
{ turnLeft();
move(); // Note: Error shutoff here if we try to carry
// from 1st Street.
putBeeper;
turnAround();
move();
turnLeft();
}
The Checker robot does all of the interesting work. It must determine if there are ten or more beepers on the current corner. If there are it must return true, otherwise false. It can try to pick up ten beepers to check this. However, it has more to do since it is going to be called repeatedly to see how many multiples of ten there really are. Therefore it must find a way to dispose of each group of ten beepers before it attempts to check for the next group of ten. It has another important task also. If it finds less than ten beepers in a group it must leave them on the current corner. This is to account for the first digit of the answer; the one that isn't carried.
public boolean enoughToCarry() // Facing north on 1st Street. -- Checker class
{ for(int i = 0; i < 10; i++)
{ if (nextToABeeper() )
{ pickBeeper();
}
else
{ emptyBag();
return false;
}
}
// We have found ten beepers.
move();
emptyBag(); // leave them on 2nd Street.
turnAround();
move();
turnAround();
return true;
}
To finish we need only add emptyBag to the Checker class:
public void emptyBag()
{ while( anyBeepersInBeeperBag() )
{ putBeeper();
}
}
Now we are ready to tackle the problem of a multi-column sum. Notice that if we start at the right end of the row of values and just slide the adder and its helpers to the left after adding a column, the three robots will be positioned for the next column. Then, working from right to left, we will compute the correct sum since we carry into a column before that column is added.
We need two additional methods in the Adder class: slideLeft and addAll. Method slideLeft is easy.
public void slideLeft()
{ turnLeft();
move();
turnRight();
carrier.turnLeft();
carrier.move();
carrier.turnRight();
checker.turnLeft();
checker.move();
checker.turnRight();
}
How will addAll know when it is done adding columns? One way is to have the left most number start on Second Avenue so that there is room to carry any value from the left most column. The Adder will then need to check to see if it is on Second Avenue before adding. This requires a new predicate.
public boolean onSecondAve() //precondition facing North and Not on 1st. Ave.
{ turnLeft();
move();
if (frontIsClear)
{ turnAround();
move();
turnLeft();
return False;
}
turnAround();
move();
turnLeft();
return True;
}
We are now ready to write the addAll method in the Adder class.
public void addAll()
{ while( ! onSecondAve() )
{ addColumn();
slideLeft();
}
addColumn();
}
7.7 Polymorphism--Why Write Many Programs When One Will Do?
Polymorphism means literally "many forms." In object-oriented programming it refers to the fact that messages sent to objects (robots) may be interpreted differently, depending on the class of the object (robot) receiving the message. Perhaps the best way to think of this is to remember that a robot is autonomous in its world. We send it messages and it responds. It doesn't come with a remote control unit by which the user directs its actions. Rather, it "hears" the messages sent to it and responds according to its internal dictionary. Recall that each robot consults its own internal dictionary of instructions to select the method that it uses to respond to any message. The new version of any method, then, changes the meaning of the message for robots of the new class.
To illustrate the consequences of this, let's take a somewhat dramatic, though not very useful example. Suppose we have the following two classes
public class Putter extends Robot
{
public void move()
{ super.move();
if (anyBeepersInBeeperBag())
{ putBeeper();
}
}
}
public class Getter extends Robot
{
public void move()
{ super.move();
while (nextToABeeper())
{ pickBeeper();
}
}
}
Both classes override the move method, and nothing more. Thus, a Putter robot puts beepers on corners that it moves to and Getter robots sweep corners to which they move. Suppose now that we use these two classes in the following task.
public static void main(String [] args)
{ Putter Lisa = new Putter(1, 1, East, infinity);
Getter Tony = new Getter(2, 1, East, 0);
for (int i = 0; i < 10; i++)
{ Lisa.move();
}
for (int j = 0; j< 10; j++)
{ Tony.move();
}
}
If the world contains a beeper on each of the first ten corners of 1st Street and also each of the first ten corners of 2nd Street, then, when the task is done, there will be two beepers on each of the first ten blocks of 1st Street, and none on the corresponding blocks of 2nd Street. There is nothing surprising about this, but note that both Lisa and Tony responded to the same messages in identical (relative) situations.
The meaning of polymorphism is even deeper than this, however. In fact, the names that we use to refer to robots are not "burned in" to the robots themselves, but only a convenience for the user. A given robot can be referred to by different names, called aliases.
First, we declare that a name will be used as an alias. We won't give make it refer to a new robot yet, howver.
Robot Karel; // "Karel" will refer to some robot.
Secondly, we need to "assign" a value to the name Karel. In other words we need to specify which robot the name "Karel" will refer to. We do this with an assignment instruction. This assumes that the name Tony already refers to a robot as it would if it were part of the above main task block.
Karel = Tony;
This establishes Karel as an alternate name (alias) for the robot also known as Tony. We could just as easily make the name "Karel" refer to the robot Lisa. It is very important to note, however, that an alias doesn't refer to any robot until we assign a value to the name.
Then sending a turnLeft message using the name Karel will send the message to the same robot that the name Tony refers to, since they are the same robot.
Karel.turnLeft();
Suppose now that we consider the slightly revised task that follows. We use the same setup and assume the world is as before. The only difference is that we refer to the robots using the name Karel in each case. Note that while we have three names here, we only have two robots.
public static void main(String [] args)
{ Robot Karel;
Putter Lisa = new Putter(1, 1, East, 100);
Getter Tony = new Getter(2, 1, East, 0);
Karel = Lisa; // "Karel" refers to Lisa;
for (int i = 0; i < 10; i++)
{ Karel.move(); // Lisa puts down ten beepers
}
Karel = Tony; // "Karel" refers to Tony
for (int j = 0; j< 10; j++)
{ Karel.move(); // Tony sweeps ten blocks
}
}
So note that not only can we have identical messages (move) referring to different actions; even if the message statements as a whole are identical (Karel.move();)we can have different actions. Notice though, that we are still sending messages to two different robots, and that these robots are from different classes. It is even possible to arrange it so that different things happen on two different executions of the same statement. Consider the following.
public static void main(String [] args)
{ Robot Karel;
Putter Lisa = new Putter(1, 1, East, 100);
Getter Tony = new Getter(2, 1, East, 0);
for (int i = 0; i < 10; i++)
{ Karel = Lisa; // "Karel" refers to Lisa;
for (int j = 0; j< 2; j++)
{ Karel.move(); // ??
Karel = Tony; // "Karel" refers to Tony
}
}
}
Note that the move message is sent 20 times, but 10 times it is sent to Lisa, and 10 times to Tony, alternately. Again, 1st Street gets extra beepers and 2nd Street gets swept.
7.8 Conclusion
Finally, we want to ask the question: When is it appropriate to design a new class, and when should we modify or add to an existing robot class?
The full answer to this question is beyond the scope of this book, because there are many things to be considered in this decision, but we can set some general guidelines here. If, in your judgment, a robot class contains errors or omissions, by all means, modify it. Here omissions mean that there is some method (action or predicate) that is needed to complete the basic functionality of the class or to make robots in the class do what the class was designed to do.
On the other hand, if we have a useful class, and we need additional functionality, especially more specialized functionality than that provided by the class we already have, then building a new class as a subclass of the given one is appropriate. This way, when we need a robot with the original capabilities, we can use the original class, and when we need the new functionality we can use the new one. Sometimes the choice is made because we find that most of the methods of some class are just exactly what we want, but one or two methods would serve better in the new problem if they were modified or extended.
7.9 Important Ideas From This Chapter
recursion
tail recursion
searching
meta
formal definition/proof
7.10 Problem Set
The following problems use the recursion, searching, and arithmetic methods discussed in this chapter. Some of the following problems use combinations of the zigLeftUp and zagDownRight methods, or simple variants of these. Each problem is difficult to solve, but once a plan is discovered (probably through an "aha experience"), the program that implements the solution will not be too difficult to write. You may also assume that there are no wall sections in the world. Finally, you should assume that our robot, Karel, starts with no beepers in its beeper-bag, unless you are told otherwise. Do not make any assumptions about Karel's starting corner or starting direction, unless they are specified in the problem.
1. Rewrite your program that solves Problem 6.9-21 using a recursive method instead of an iterative one.
2. Karel has graduated to advanced carpet layer. Karel must carpet the completely enclosed room. Only one beeper can be placed on each corner. The room may be any size and any shape. Figure 7-5 shows one possible floor plan. The gray area is not to be carpeted by Karel. Karel may start from any place within the room and may be facing any direction.
Figure 7-4 A Big Carpeting Job
3. Rewrite both zigLeftUp and zagDownRight so that they automatically satisfy their directional pre-conditions.
4. Assume that there is a beeper on 1st Street and Nth Avenue. Program Karel to find it and move to Nth Street and 1st Avenue.
5. Assume that there is a beeper on Sth Street and Ath Avenue, and that Karel has two beepers in its beeper-bag. Program Karel to put the beepers from its beeper-bag on to 1st Street and Ath Avenue and Sth Street and 1st Avenue. The original beeper must remain at the corner on which it starts.
26. Do Problem 29 of Chapter 6 again, but have the Spy find the Accomplices recursively.
27. Discuss the LinkStrategy class of the optional section of Chapter 4 in terms of recursion. Write a short paper on the relationship.
28. A Contractor wants to build a house with three helpers, a Mason, a Carpenter, and a Roofer, but the helpers are spread around the robot world. Have the Contractor go on a search for its three helpers and pass each a strategy concerning the location of the house when it finds them. It will also need to tell them to get to work. Then have the helpers build the house.
The rest of the exercises are omitted, except for the last one:
29. If you enjoy computer science and eventually take a course in computability theory, fondly recall the days you spent programming Karel and try to solve the following problem: Prove that Karel, even without the aid of any beepers is equivalent to a Turing machine. Hint: Use the equivalence between Turing machines and 2-counter automata.