This chapter explains the mechanics of specifying new classes of robots and adding new instructions to the robot vocabulary. It also discusses methods for planning, implementing, and testing our programs. The ability to extend the robot vocabulary combined with these techniques can simplify our work in writing robot programs.
In Chapter Two, we saw a robot perform a complex task. We also saw that it takes many messages to perform such a task. Writing so many messages is verbose and error prone.
Let's look at a particularly clumsy aspect of robot programming. Suppose that we need to program a robot to travel over vast distances. For example, assume that, starting at 3rd Avenue and 2nd Street, the robot must move east along 2nd Street for ten miles (a mile is eight blocks long), pick up a beeper, and then move another five miles north. Because a robot understands about moving blocks but not miles, we must translate our solution into instructions that move the robot one block at a time. This restriction forces us to write a program that contains 120 move messages. Although the conversion from miles to blocks is straightforward, it results in a very long and cumbersome program.
The crux of the problem is that we think in one language, but must program robots in another. Rather than make programmers the slaves of the machine, continually forced to translate their powerful ideas into the robot's primitive methods, Karel-Werke turned the tables and endowed robots with a simple mechanism to learn the definitions of new methods.
The robot programming language permits the robot programmer to specify new classes of robots. These class descriptions provide specifications of new robot instructions. Karel-Werke will then use the class descriptions to create robots able to interpret the new messages.
A robot's learning ability is quite limited. Karel-Werke builds each robot with a dictionary of useful method names and their definitions, but each definition must be built from simpler instructions that robots already understand. By providing robots with a dictionary of instructions that perform complex actions, we can build a robot vocabulary that corresponds more closely to our own. Given this mechanism, we can solve our programming problems using whatever instructions are natural to our way of thinking, and then we can provide robots with the definitions of these instructions.
We can define a moveMile instruction as eight move messages. Then, when a robot is told to moveMile in a program, it looks up the definition associated with this message name and executes it. Now our unwieldy beeper-moving program can be written with a moveMile definition, containing eight move messages, and another 15 moveMile messages. This program, containing these 23 messages, would be quite an improvement over the original program, which needed more than 120 messages to accomplish the task.
Although both programs move the robot exactly the same distance, the smaller program is much easier to read and understand. In complicated problems, the ability to extend a robot's vocabulary makes the difference between understandable programs and unintelligible ones. We will explore in detail this extremely important definition mechanism in the next two sections.
Back in Chapter 2 we saw the declaration of the primitive ur_Robot class. Users of the robot language can also declare new classes of robots and the factory will be able to deliver them, just as it does the standard robots. To specify a new class of robots, we include a class specification in the declaration section at the beginning of our robot program. Isolated from a program, the general form of the specification is shown in the following template.
class <new-class-name> extends <old-class-name>
{
<list-of-new-methods>
}
FOOTNOTE 1 There are a few other things we can include in a robot class declaration. These will be introduced in future chapters.
The class specification uses the reserved words class and extends, and the special symbols like braces to separate the various parts of the declaration. This general form includes elements delimited by angle brackets, < and >, which must be replaced with appropriate substitutions when we include a class specification in a robot program. Angle brackets are not part of the robot programming language, just a way we can set off locations in a program structure where actual language elements may appear. In this case, <new-class-name> must be replaced by a new name, not yet used in the program. This name can be built from upper and lower case letters, digits, and the underscore character, but must not match any other name in the program, nor the spelling of any reserved word. Names must also begin with a letter. The replacement for <old-class-name> is the name of an existing robot class, either ur_Robot or one previously declared in the same program. New messages that apply to this class of robot will replace <list-of-new-methods>, and we will soon see how to define these new methods.
Suppose that we would like to solve the mile mover problem discussed in the introduction to this chapter. Suppose also that, in addition to the new capabilities, we want the robots of the new class to have all of the functionality of the standard ur_Robot class. We can do so with a new class specification as follows.
class MileWalker extends ur_Robot
{
void moveMile()
{ ... // instructions omitted for now
}
}
The name of the new class of robots is MileWalker, which also names its main new capability. We also indicate, by giving the name of the ur_Robot class following the word extends, that mile walkers are to have all of the capabilities of members of the ur_Robot class. As a shorthand we say that ur_Robot is the parent class of MileWalker or that MileWalker is a subclass of ur_Robot. We also say that robots of the new class inherit all the capabilities of the parent class. Therefore, mile walkers know how to move and turnLeft, just like members of the ur_Robot class. They can also pick and put beepers and turn themselves off.
Here we have a list of only a single new method. Each method in the list is written with its definition in braces, but these will be shown in a just below. This specification says that when a robot in this class is first turned on it will be able to execute moveMile instructions as well as all methods inherited from the ur_Robot class.
We will see later that the names of instructions can be either new names or the names of methods already existing in the parent class. In this latter case we can give new meaning to methods as we shall see in section 3.7.
The class declaration introduces the names of new robot methods, but we have not yet explained how they are to be carried out. In the next section we will see how to define the new capabilities.
As we declare a new robot class we need to define all of the new instructions introduced in it. These definitions are part of the class declaration in the declaration part of the robot program. The form of an instruction definition is as follows.
void <instruction_name> () { <list_of_instructions> }
As we see, we begin with the reserved word void. We have to give the name of the instruction we are defining, of course. Between the brace delimiters, we give a list of instructions, similar to a main task block, that tells a robot of this class how to carry out the new instruction. This list of instructions delimited by braces is called a block in the robot programming vocabulary. Again, every instruction in the list is terminated by a semicolon. For example, our moveMile instruction in the MileWalker class would be written within that class as shown below. Most of the instructions in the list of instructions will be messages.
class MileWalker extends ur_Robot
{
void moveMile()
{
move();
move();
move();
move();
move();
move();
move();
move();
}
}
(Here is 100% Java code equivalent to the above.)
This block is like a main task block, but it is also different, since the messages in it are not prefaced here with the name of any robot. The reason for the difference is that in the main main task block, we need to tell some particular robot to carry out an instruction, so we say something like Karel.move( ) to get a robot named Karel to move. Here, however, a robot of the MileWalker class will eventually carry out this instruction when it is sent a moveMile message. The robot will carry out this instruction list itself. Since it is moving itself and not another robot, we don't need to give a robot's name here. If we really wanted to, we could use the name this, as in this.move().
The language could have been designed so that robots were required to refer to themselves with a special reserved word like this, in which case the move instructions in the above could be replaced by this.move(), but this is not required. It makes the language more concise. "this" means "this robot."
If we have a MileWalker named Lisa, we can get it to walk a mile with either
Lisa.moveMile();
or
Lisa.move();
Lisa.move();
Lisa.move();
Lisa.move();
Lisa.move();
Lisa.move();
Lisa.move();
Lisa.move();
In the former case, Lisa will move itself eight times upon receiving the single moveMile message.
The complete robot program for the above is
package kareltherobot;
public class MileWalker extends ur_Robot
{
public MileWalker(int street, int avenue, Direction direction, int beepers)
{ super(street, avenue, direction, beepers);
}
public void moveMile()
{
move();
move();
move();
move();
move();
move();
move();
move();
}
public static void main(String [] args)
{ MileWalker Lisa = new MileWalker (3, 2, East, 0); // Declare a new MileWalker Lisa.
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.pickBeeper();
Lisa.turnLeft();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.moveMile();
Lisa.turnOff();
}
}
Here the static main method is within this same class. Actually it can be in any class in your program.
Notice that having a moveFiveMiles instruction here would be useful. Contemplate writing the program without defining any new instructions. It requires 122 messages to be sent to the robot. This is not hard to write with a good text editor, but once it is written, it is tedious to verify that it has exactly the right number of move commands.
A robot is a machine, a device completely devoid of intelligence. This is something that robot programmers must never forget. The robot does not "understand" what we "mean" when we write a program. It does exactly what we "say"-there is no room for interpretation. A robot class declaration is a description to the robot factory that tells it how to construct robots of this class. At the robot factory the entire declaration part of any robot program is read and examined for errors. As part of the manufacturing and delivery process the robots are given the definitions of each of the new instructions of their class. Each robot stores the definitions of the instructions in its own dictionary of instructions. Thus, when we tell a robot of the MileWalker class to moveMile, it receives the message, consults its dictionary to see how it must respond, and then carries out the required actions. The helicopter pilot does not have to read this part of the program when setting up robots for delivery.
In a robot's world, just because we define a new instruction named moveMile, it doesn't necessarily mean that the instruction really moves the robot one mile. For example, there is nothing that prevents using the following method definition
public void moveMile()
{
move();
move();
move();
move();
move();
move();
}
According to robot programming rules of grammar, this is a perfectly legal definition for it contains neither lexical nor syntax errors. However, by defining moveMile this way, we tell a robot that executing a moveMile instruction is equivalent to executing six move instructions. The robot does not understand what a moveMile instruction is supposed to accomplish; its only conception of a moveMile instruction is the definition we provide. Consequently, any new instruction we define may contain an intent error, as this example shows.
Besides intent errors, a new instruction can cause execution errors if it is defined by using primitive instructions that can cause error shutoffs. Can this incorrect definition of moveMile ever cause an error shutoff? The answer is yes, because we might encounter a wall before we completed six moves. However, it is possible to write a set of instructions for a robot to execute in which it would seem that nothing is wrong with this version of moveMile. Thus we might gain false confidence in this incorrect instruction and be very surprised when it fails us later. This example is somewhat trivial because the error is obvious. With a more complex defined instruction, we must take care to write a definition that really accomplishes what its name implies. The name specifies what the instruction is intended to do, and the definition specifies how the instruction does what the name implies. The two must match exactly, if we are to understand what our programs mean. If not, one or both must be changed.
When simulating a robot's execution of a defined instruction, we must adhere to the rules that the robot uses to execute these instructions. Robots execute a defined instruction by performing the actions associated with its definition. Do not try to shortcut this process by doing what the instruction name means because the robot does not know what a defined instruction means; the robot knows only how it is defined. We must recognize the significance of this distinction and learn to interpret robot programs as literally as the robot does. The meaning of names is supposed to help a human reader understand a program. If the actual instructions defining the meaning of a name are at variance with the meaning of the name, it is easy to be misled.
In this section we display a complete robot program that uses the method definition mechanism. We will first trace the execution of the program (recall that tracing is just simulating the execution of the methods in the order that a robot does). We will then discuss the general form of programs that use the new method definition mechanism. The task is shown below in Figure 3-1: it must pick up each beeper in the world while climbing the stairs. Following these figures is a program that correctly instructs a robot to accomplish the task.
Figure 3-1 A Stair Cleaning Task for Karel to Perform
package kareltherobot;
public class StairSweeper extends ur_Robot
{
public void turnRight()
{
turnLeft();
turnLeft();
turnLeft();
}
public void climbStair()
{
turnLeft();
move();
turnRight();
move();
}
public static void main(String [] args)
{ StairSweeper Alex = new StairSweeper(1, 1, East, 0);
Alex.climbStair();
Alex.pickBeeper();
Alex.climbStair();
Alex.pickBeeper();
Alex.climbStair();
Alex.pickBeeper();
Alex.turnOff();
}
}
Next, we provide an annotated version of the same program that numbers each instruction and message in the order in which it is executed, starting with the delivery specification instruction #0.
public class StairSweeper extends ur_Robot
{
public void turnRight()
{// to here from #4, #13 or #22
turnLeft(); #5 or #14 or #23
turnLeft(); #6 or #15 or #24
turnLeft(); #7 or #16 or #25
}// return to #4 #13 #22
public void climbStair()
{// to here from #1, #10, or #19
turnLeft(); #2 #11 #20
move(); #3 #12 #21
turnRight(); #4 #13 #22
move(); #8 #17 #26
}// return to #1 #10 #19
public static void main(String [] args)
{ StairSweeper Alex = new StairSweeper(1, 1, East, 0); #0
Alex.climbStair(); #1
Alex.pickBeeper(); #9
Alex.climbStair(); #10
Alex.pickBeeper(); #18
Alex.climbStair(); #19
Alex.pickBeeper(); #27
Alex.turnOff(); #28
}
}
To verify that this program is correct, we trace the execution of it, carefully simulating the execution of the instructions. Only one instruction can be executed at a time in the robot world. When a program is executing, we call the current instruction the "focus of execution. When the helicopter pilot starts to execute a program, the focus is initially on the first instruction within the main task block.
In this sample program the initial focus is the climbStair message, which is annotated as #1. The climbStair message is sent through the satellite to the robot Alex. When Alex receives this message, the focus of execution passes from the pilot to Alex. The pilot, who must wait until the instruction has been completed, is very careful to remember where he or she was in the program when the climbStair message was sent. Alex, upon receiving this message, consults its list of dictionary entries and goes to the definition of climbStair. In the sample program the new execution point is annotated as "to here from #1".
Alex focuses on the list of instructions defining the new instruction, climbStair, and encounters a turnLeft message (marked as #2). Alex trains the focus of execution on the turnLeft message executes it, and then focuses on #3, move. Alex executes this move and focuses on #4, turnRight. Since this is not a primitive instruction, Alex must retrieve its definition from its dictionary. It then focuses on the instruction list from from definition of turnRight and executes the three turnLeft instructions, # 5, #6, and #7. Having completed the execution of the turnRight instruction, Alex now returns its focus to the place in which the turnRight message occurred within climbStair. Alex shifts focus to #8 and executes the move. After Alex performs this move, it is finished executing the instruction climbStair so its yields execution back to the pilot since it has completely carried out the task required by the message climbStair. The focus of execution returns to the place in the program marked #1, and the pilot sends Alex the pickBeeper message that is marked #9. With this message, the focus of execution is again passed from pilot to robot. Alex also interprets and carries out this pickBeeper instruction and yields focus back to the pilot at #10. The pilot then sends Alex another climbStair message. Alex repeats this same sequence of steps a second time for this climb-stair instruction marked #10 and the pickBeeper that follows and again for the third climb-stair and pickBeeper messages. Alex is finally instructed to execute the turnOff instruction and then the program's execution is complete.
Notice that an instruction definition can become Alex's focus from any place in the program that sends Alex that message. The pilot and the robot must always remember the place in the program where they were when the focus changes. This allows the execution to return to its correct place and continue executing the program. It is important for us to understand that no complex rules are needed to execute a program containing new instructions. Tracing the execution of this program was a bit tedious, because each step is small and simple, but Alex is not equipped to understand anything more complicated. Alex can follow a very simple set of rules that tell it how to execute a program. Yet we can use these simple rules, coupled with every robot's willingness to follow them, to command the robot to perform complicated tasks.
We should now understand how the helicopter pilot and the robots work together to execute a program that includes the instruction definition mechanism. We next turn our attention toward program form, and we make the following observations about the stair-cleaning program.
* We mentioned earlier that declarations are always written before the main main task block. In our programming example, we saw that the declaration of the new class and the definition of the new instructions for the class are placed here. We must always write our new instruction definitions in this area. The names defined within a robot class, including the names of the parent class and the parent of the parent, etc. (collectively called ancestors), are called the dictionary of the class. Dictionary entries are always defined in this declaration part of a robot program.
* The declaration of ur_Robot does not need to be included in your robot programs, since it is "factory standard." Any other class that you need to define must be completely written in the declaration part, along with the definitions of all of its instructions. We will soon see a shorthand method that we can use to make the writing of this dictionary much easier.
* Each instruction in a block is terminated by a semicolon. The definition of a new instruction is not. Neither is the main main task block.
The class dictionary entries are not permanent and the world does not remember any definitions from program to program. Each time we write a robot program, we must include a complete set of all dictionary entries required in that program.
Earlier in this chapter we built the class MileWalker that gave robots the ability to walk a mile at a time. Notice that they retained their ability to walk a block at a time as well. Sometimes we want to build a class in which some previously defined instruction is redefined to have a new meaning. For example, suppose we had a problem in which a robot always needed to move by miles, but never by blocks. In this case it would be an advantage to create a class with a new definition of the move instruction so that when a robot in this class was told to move, it would move a mile. This is easily done.
package kareltherobot;
public class MileMover extends ur_Robot
{ public void move()
{ super.move();
super.move();
super.move();
super.move();
super.move();
super.move();
super.move();
super.move();
}
...
}
We say that the new definition of move in this class overrides the original definition inherited from the class ur_Robot. We now have a problem, since to move a mile, we need to be able to move eight blocks, but we are defining move to mean move a mile here. Therefore we can't just say move eight times, because that is this instruction. (See Problem 19.) Instead, we need to indicate that we want to use the original, or overridden, instruction, move, from class ur_Robot. We can do this since ur_Robot is the parent class. We just need to preface the move message with the keyword super and a period. It gives us a way to specify a particular method from the parent class.
Note that in Java, if we override a public method we must do so with a public method. All of the methods defined in ur_Robot are public, so if, as above, we want to override move, we must mark it as public. In fact you should generally mark your methods as public unless there is a reason not to.
Now if we complete the above program with
public static void main(String [] args)
{ MileMover Karel = new MileMover(5, 2, North, 0);
Karel.move();
Karel.pickBeeper();
Karel.move();
Karel.putBeeper();
Karel.turnOff();
}
Karel will find the beeper at (13, 2) and will leave it at (21, 2).
Notice now that if we had several different robots in the same program and we sent each of them the same messages, they might each respond differently to those messages. In particular, a MileWalker only moves a block when told to move, while a MileMover, moves a mile.
Before reading this section, quickly look at the small program in the example below, and see if you can find a syntax error.
public class BigStepper extends ur_Robot
{
public void longMove()
move();
move();
move();
}
public static void main(String [] args)
{ BigStepper Tony(5, 2, North, 0);
Tony.longMove();
Tony.turnLeft();
Tony.turnOff();
}
}
The factory reads the declaration part of a program and the main task block of the program to check for lexical and syntax errors. A reader (human or otherwise) discovers syntax errors by checking "meaningful" components of the program and checking for proper grammar and punctuation. Examples of meaningful components are class declarations, method definitions, and the main task block. In effect we verify the meaningful components separately. Let us illustrate how the factory finds the mistake in the program above using this examination. Remember that the factory only reads the program's words and is not influenced by our indentation.
The factory examines the new robot class declaration. It has a name, a parent class, and a correct list of features. The punctuation all checks out as well. Then it sees the class name and method name in the instruction definition. It then looks for a block to include with the definition, but doesn't find the opening brace. Instead it finds a name. So the factory tells us that a syntax error has occurred. In summary, forgetting to use necessary braces around a block can lead to syntax errors.
We are rapidly becoming experts at analyzing programs. Given a robot program, we should now be able to detect grammar and punctuation errors quickly. We should also be able to simulate programs efficiently. Nevertheless, the other side of the programming coin, constructing programs, may still seem a little bit magical. The next few sections take a first step toward demystifying this process.
Designing solutions for problems and writing robot programs involve problem solving. One model2 describes problem solving as a process that has four activities: definition of the problem, planning the solution, implementing the plan, and analyzing the solution.
FOOTNOTE 2 G. Polya, How to Solve It, Princeton University Press, 1945, 1973.
The initial definition of the problem is presented when we are provided figures of the initial and final situations. Once we examine these situations and understand what task a robot must perform, we begin to plan, implement and analyze a solution. This section examines techniques for planning, implementing and analyzing robot programs. By combining these techniques with the new class and instruction mechanism, we can develop solutions that are easy to read and understand.
As we develop and write programs that solve robot problems, these three guidelines must be followed:
* our programs must be easy to read and understand,
* our programs must be easy to debug, and
* our programs must be easy to modify to solve variations of the original task.
In this section, we will discuss stepwise refinement, a method we can use to construct robot programs. This method addresses the problem of how we can naturally write concise programs that are correct, simple to read, and easy to understand.
It may appear natural to define all the new classes and methods that we will need for a task first, and then write the program using these instructions. But how can we know what robots and which new instructions are needed before we write the program? Stepwise refinement tells us first to write the program using any robots and instruction names we desire, and then define these robots and their instructions. That is, we write the sequence of messages in the main main task block first, and then we write the definitions of the new instruction names used within this block. Finally, we assemble these separate pieces into a complete program.
We will explore this process more concretely by writing a program for the task shown in Figure 3-2. These situations represent a harvesting task that requires a robot to pick up a rectangular field of beepers.
Figure 3-2 The Harvest Task
Our first step is to develop an overall plan to guide us in writing a robot program that allows Karel to perform the task. Planning is probably best done as a group activity. Sharing ideas in a group allows members to present different plans that can be thoughtfully examined for strengths and weaknesses. Even if we are working alone, we can think in a question and answer pattern such as the following.
QUESTION: How many robots do we need to perfrom this task?
ANSWER: We could do it with one robot that walks back and forth over all of the rows to be harvested, or we could do it with a team of robots.
QUESTION: How many shall we use?
ANSWER: Let's try it with just one robot named Mark, for now.
QUESTION: How can Mark pick a row?
ANSWER: Mark could move west to east across the southern most unpicked row of beepers, picking each beeper as it moves.
QUESTION: How can Mark pick the entire field?
ANSWER: Mark could turn around and move back to the western side of the field, move north one block, face east, and repeat the actions listed above. Mark could do this for each row of beepers in the field. Since Mark is not standing on a beeper we will move it to the first beeper before starting to harvest the first row.
If this idea seems like it might work, our next step is to write out the main task block of the program using English-like new message names. We briefly move from planning to implementing our plan. Even though this is done on paper, we should still concentrate on correct syntax and proper indenting to reduce errors when we copy our program into the computer. Suppose we call the class of the new robot by the name Harvester.
public static void main(String [] args)
{ Harvester Mark = new Harvester(2, 2, East, 0);
Mark.move();
Mark.harvestOneRow();
Mark.returnToStart();
Mark.moveNorthOneBlock();
Mark.harvestOneRow();
Mark.returnToStart();
Mark.moveNorthOneBlock();
Mark.harvestOneRow();
Mark.returnToStart;
Mark.moveNorthOneBlock();
Mark.harvestOneRow();
Mark.returnToStart();
Mark.moveNorthOneBlock();
Mark.harvestOneRow();
Mark.returnToStart();
Mark.moveNorthOneBlock();
Mark.harvestOneRow();
Mark.returnToStart();
Mark.turnOff();
}
Notice that what we have really done here is to design a new class of robot that can perform three new messages. We can think of a robot class as a mechanism for creating service providers; the robots. These robots, an example of objects in object-oriented programming, provide specific services when sent messages requesting the service. Here we seem to require three different services, harvestOneRow, returnToStart, and moveNorthOneBlock, beyond the basic services that all ur_Robots can provide.
Before we continue with this plan and begin to work on the new instructions, harvestOneRow, returnToStart and moveNorthOneBlock, we should analyze our original plan looking at its strengths and weaknesses. We are asking if we are requesting the right services. Our analysis might proceed as follows.
QUESTION: What are the strengths of this plan?
ANSWER: The plan takes advantage of the new instruction mechanism and it allows Mark to harvest the beepers.
QUESTION: What are the weaknesses of the plan?
ANSWER: Mark makes some "empty" trips.
QUESTION: What are these empty trips?
ANSWER: Mark returns to the starting point on the row that was just harvested.
QUESTION: Why are these bad?
ANSWER: Because robots (and computers) are valuable resources that should generally be used efficiently. Some tasks must be done "on time" if solving them is to confer any benefit.
QUESTION: Can Mark pick more beepers on the way back?
ANSWER: Instead of harvesting only one row and then turning around and returning to the start, Mark can harvest one row, move north one street and come back to the west harvesting a second row. Mark can then move one street north to begin the entire process over for the next two rows. If Mark repeats these steps two more times the entire field of beepers will be harvested.
Again we analyze this new plan for its strengths and weaknesses.
QUESTION: What advantage does this offer over the first plan?
ANSWER: Mark makes only six trips across the field instead of twelve. There are no empty trips.
QUESTION: What are the weaknesses of this new plan?
ANSWER: None that we can see as long as there are an even number of rows.
When we are planning solutions, we should be very critical and not just accept the first plan as the best. We now have two different plans and you can probably think of several more. Let's avoid the empty trips and implement the second plan.
public static void main(String [] args)
{ Harvester Mark = new Harvester(2, 2, East, 0);
Mark.move();
Mark.harvestTwoRows();
Mark.positionForNextHarvest();
Mark.harvestTwoRows();
Mark.positionForNextHarvest();
Mark.harvestTwoRows();
Mark.move();
Mark.turnOff();
}
We must now begin to think about planning the new instructions harvestTwoRows and positionForNextHarvest.
Our plan contains two subtasks: one harvests two rows and the other positions Mark to harvest two more rows. The planning of these two subtasks must be just as thorough as the planning was for the overall task. Let's begin with harvestTwoRows.
QUESTION: What does harvestTwoRows do?
ANSWER: harvestTwoRows must harvest two rows of beepers. One will be harvested as Mark travels east and the second will be harvested as Mark returns to the west.
QUESTION: What does Mark have to do?
ANSWER: Mark must pick beepers and move as it travels east. At the end of the row of beepers, Mark must move north one block, face west, and return to the western edge of the field picking beepers as it travels west.
Continuing to use English-like message names, we can now implement this part of the plan.
public class Harvester extends ur_Robot
{
public void harvestTwoRows()
{
harvestOneRowMovingEast();
goNorthToNextRow();
harvestOneRowMovingWest();
}
...
}
We analyze this plan as before looking for strengths and weaknesses.
QUESTION: What are the strengths of this plan?
ANSWER: It seems to solve the problem.
QUESTION: What are the weaknesses of this plan?
ANSWER: Possibly one-we have two different instructions that harvest a single row of beepers.
QUESTION: Do we really need two different harvesting instructions?
ANSWER: We need one for going east and one for going west.
QUESTION: Do we really need a separate instruction for each direction?
ANSWER: Harvesting is just a series of pickBeepers and moves. The direction Mark is moving does not matter. If we plan goToNextRow carefully, we can use one instruction to harvest a row of beepers when Mark is going east and the same instruction for going west.
Our analysis shows us that we can reuse a single dictionary entry (harvestOneRow) instead of defining two similar instructions, making our program smaller. Here is the new implementation.
public void harvestTwoRows()
{
// Before executing this, the robot should be facing East,
// on the first beeper of the current row.
harvestOneRow();
goToNextRow();
harvestOneRow();
}
Let's now plan positionForNextHarvest.
QUESTION: What does the positionForNextHarvest instruction do?
ANSWER: This instruction is used when Mark is on the western side of the beeper field. It moves the robot north one block and faces Mark east in position to harvest two more rows of beepers.
QUESTION: What does Mark have to do?
ANSWER: Mark must turn right to face north, move one block and turn right to face east. We implement this instruction as follows.
public class Harvester extends ur_Robot
{
...
public void positionForNextHarvest()
{
// Before executing this, the robot should be facing West,
// on the last corner of the current row.
turnRight();
move();
turnRight();
}
public void turnRight()
{
turnLeft();
turnLeft();
turnLeft();
}
...
}
We should analyze this instruction to see if it works properly. Since it seems to work correctly, we are ready to continue our planning and in the process define more new instructions.
goToNextRow
We now focus our efforts on harvestOneRow and finally goToNextRow.
QUESTION: What does harvestOneRow do?
ANSWER: Starting on the first beeper and facing the correct direction, Mark must harvest each of the corners that it encounters, stopping on the location of the last beeper in the row.
QUESTION: What does Mark have to do?
ANSWER: Mark must execute a sequence of harvestCorner and move instructions to pick all five beepers in the row.
QUESTION: How does Mark harvest a single corner?
ANSWER: Mark must execute a pickBeeper instruction.
We can implement harvestOneRow and harvestCorner as follows.
public class Harvester extends ur_Robot
{
...
public void harvestOneRow()
{
harvestCorner();
move();
harvestCorner();
move();
harvestCorner();
move();
harvestCorner();
move();
harvestCorner();
}
public void harvestCorner()
{
pickBeeper();
}
...
}
We again simulate the instruction and it seems to work. We now address the instruction, goToNextRow.
QUESTION: What does goToNextRow do?
ANSWER: This instruction moves Mark northward one block to the next row.
QUESTION: Didn't we do that already? Why can't we use positionForNextHarvest?3
Footnote 3: At this point you should simulate the instruction positionForNextHarvest on paper. Start with Mark facing west and see where the robot is when you finish simulating the instruction.
ANSWER: It will not work properly. When we use positionForNextHarvest, Mark must be facing West. Mark is now facing East so positionForNextHarvest will not work.
QUESTION: What does Mark have to do?
ANSWER: Mark must turn left to face North, move one block, and turn left to face West.
The following is the implementation of this new instruction.
public class Harvester extends ur_Robot
{
...
public void goToNextRow()
{
// Before executing this, the robot should be facing East,
// on the last corner of the current row.
turnLeft();
move();
turnLeft();
}
...
}
We can use simulation to analyze this instruction and show that it is correct and our program is done.
Since we have spread this program out over several pages, we print it here so you will find it easier to read and study.
package kareltherobot;
public class Harvester extends ur_Robot
{
public Harvester(int street, int avenue, Direction direction, int beepers)
{ super(street, avenue, direction, beepers);
}
public void harvestTwoRows()
{ // Before executing this, the robot should be facing East,
// on the first beeper of the current row.
harvestOneRow();
goToNextRow();
harvestOneRow();
}
public void positionForNextHarvest()
{ // Before executing this, the robot should be facing West,
// on the last corner of the current row.
turnRight();
move();
turnRight();
}
public void turnRight()
{ turnLeft();
turnLeft();
turnLeft();
}
public void harvestOneRow()
{ harvestCorner();
move();
harvestCorner();
move();
harvestCorner();
move();
harvestCorner();
move();
harvestCorner();
}
public void harvestCorner()
{ pickBeeper();
}
public void goToNextRow()
{ // Before executing this, the robot should be facing East,
// on the last corner of the current row.
turnLeft();
move();
turnLeft();
}
public static void main(String [] args)
{ Harvester Mark = new Harvester(2, 2, East, 0);
Mark.move();
Mark.harvestTwoRows();
Mark.positionForNextHarvest();
Mark.harvestTwoRows();
Mark.positionForNextHarvest();
Mark.harvestTwoRows();
Mark.move();
Mark.turnOff();
}
}
We are not done. We have used simulation to analyze the individual instructions in the program to see if they work correctly. We have not examined how they work in concert as one large robot program. We must now simulate Mark's execution of the entire program to demonstrate that all the parts work correctly to be sure the program is correct. We may have relied on some invalid assumptions when writing the instructions that move Mark between rows, or we may discover another error in our planning or implementing; maybe our analysis was wrong. A skeptical attitude toward the correctness of our programs will put us in the correct frame of mind for trying to verify them.
Stepwise refinement blends the problem solving activities of planning, implementing and analyzing into the programming process. It is a powerful programming technique and can shorten the time required to write correct robot programs.
It is useful to divide a program into a small set of instructions, even if these instructions are executed only once. New instructions nicely structure programs, and English words and phrases make programs more understandable; they help convey the intent of the program. Read back through the programs we have just written and see if you can find any place where they are confusing or difficult to understand.
We could, of course, use a different plan to solve the above (or any) problem. It is useful to think in terms of services required. For example, in the harvester example above, it might be useful to think of harvestField as a service. Fulfillment of this service would result in harvesting of an entire field, as the name suggests. We could easily add this feature to the Harvester class. Its implementation could be all of the statements of the main task block above except the first and last. It would also be possible to create a new class, say FieldHarvester, that adds just this new instruction, and that is derived from the Harvester class above.
public class FieldHarvester extends Harvester
{
public FieldHarvester(int street, int avenue, Direction direction, int beepers)
{ super(street, avenue, direction, beepers);
}
public void harvestField()
{ move();
harvestTwoRows();
positionForNextHarvest();
harvestTwoRows();
positionForNextHarvest();
harvestTwoRows();
move();
}
public static void main(String [] args)
{ FieldHarvester Jim = new FieldHarvester(2, 2, East, 0);
Jim.harvestField();
Jim.turnOff();
}
}
To use this new class we can include its definition as well as the definition of the Harvester class in a single file. However, to do this, only one of the classes can be public and this one must contain the main task block.
Another way to do this efficiently is to take advantage of an import feature of the robot language that we have not used yet. Suppose that we put the above definition in a file named "FieldHarvester.java" and put the definitions of the Harvester class in another different file "Harvester.java." Either or both or neither could contain a main task block. We could actually specify a task within a different file, say "Task.java" that contains only the following lines. Separating our robot definitions into separate files makes it easier to reuse them in other programs.
package kareltherobot
public class Task implements Directions
{
public static void main(String [] args)
{ FieldHarvester Tony = new FieldHarvester(2, 2, East, 0);
Tony.harvestField();
Tony.turnOff();
}
}
The first line tell the factory to include everything in the kareltherobot package into this program. You may need to either include all three files in the javac compile instruction or include all three in your project if you use an IDE (integrated development environment.)
Many novices think that all of this planning, analyzing, tracing, and simulating of programs as shown in the previous sections takes too much time. What really takes time is correcting mistakes. These mistakes fall into two broad categories:
- Planning mistakes (execution and intent errors) happen when we write a program without a well-thought-out plan and can waste a lot of programming time. They are usually difficult to fix because large segments of the program may have to be modified or discarded. Careful planning and thorough analysis of the plan can help us avoid planning mistakes.
- Programming mistakes (lexical and syntax errors) happen when we actually write the program. They can be spelling, punctuation, or other similar errors. If we write the entire program without testing it, we will undoubtedly have many errors to correct, some of which may be multiple instances of the same mistake. Writing the program in slices will both reduce the overall number of errors introduced at any one time and may prevent multiple occurrences of the same mistake (e.g., we discover a misspelling of a new instruction name).
Stepwise refinement is a tool that allows us to plan, analyze and implement our plans in a way that should lead to a robot program containing a minimum of errors.
Earlier in this chapter we said we must write programs that are easy to read and understand, easy to debug, and easy to modify. The robot's world can be readily changed and we must be able modify existing programs to keep the robot out of trouble. It can be much simpler and takes less time to modify an existing program to perform a slightly different task than to write a completely new one. Below are two situations that differ somewhat from the Harvester task.
Figure 3.4 a. Longer rows
Figure 3.4 b. More rows
How difficult would it be to modify our Harvester class and the program containing it to accomplish the new beeper harvesting tasks? The second problem is easy to solve; we just add two new lines to the original main task block to solve the new task! We don't need any changes to the Harvester class itself.
What about the first problem? The change here is very different from the change in the first one since we have to pick up an additional beeper in each row. The use of new instructions allows us to quickly find where we need to make the change. There is only one instruction that actually picks up any beepers. We make a simple change to harvestOneRow as follows,
public void harvestOneRow()
{
harvestCorner();
move();
harvestCorner();
move();
harvestCorner();
move();
harvestCorner();
move();
harvestCorner();
move(); // Add these two
harvestCorner(); // new messages
}
This change to the Harvester class is fine provided that we will not need to solve the original problem in the future. It is truly advantageous here to leave the Harvester class unchanged and create a new class, Long_Harvester that contains this modified harvestOneRow instruction.
package kareltherobot;
public class Long_Harvester extends Harvester
{
public void harvestOneRow()
{
super.harvestOneRow(); // Execute the inherited instruction
move(); // Add these two
harvestCorner(); // new messages
}
}
The use of new instructions also simplifies finding and fixing intent errors. This is especially true if the instructions are short and can be easily understood. Suppose our robot makes a wrong turn and tries to pick up a beeper from the wrong place. Where is the error? If we use new instructions to write our program, and each new instruction performs one specific task (e.g., positionForNextHarvest) or controls a set of related tasks (e.g., harvestTwoRows), then we can usually determine the probable location of the error.
Below is a program that attempts to solve the original beeper planting problem with only primitive instructions. Examine the program and ask the same questions we have just explored.
- Where would we change the program to solve the first modified situation?
- Where would we change the program to solve the second modified situation?
- Suppose Mark makes a wrong turn while planting the beepers. Where would we first look to correct the error?
As an example, find the single error that we included in this program.
public static void main(String [] args)
{ ur_Robot Mark = new ur_Robot(2, 2, East, 0);
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.turnLeft();
Mark.move();
Mark.turnLeft();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.turnRight();
Mark.move();
Mark.turnRight();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.turnRight();
Mark.move();
Mark.turnLeft();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.turnLeft();
Mark.move();
Mark.turnLeft();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.pickBeeper();
Mark.move();
Mark.turnOff();
}
Long lists of messages such as this may correctly solve a problem but they are very difficult to read and understand. They are also very difficult to debug and modify.
Writing understandable programs is as important as writing correct ones; some say that it is even more important. They argue that most programs initially have a few errors, and understandable programs are easier to debug. Good programmers are distinguished from bad ones by their ability to write clear and concise programs that someone else can read and quickly understand. What makes a program easy to understand? We present two criteria.
* A good program is the simple composition of easily understandable parts. Each part of the programs we just wrote can be understood by itself. Even without a detailed understanding of the parts, the plans that the programs use to accomplish their respective tasks are easy to understand.
* Dividing a program (or a large instruction definition) into small, easy to understand pieces is not enough. We must also make sure to name our new instructions properly. These names provide a description, possibly the only description, of what the instruction does. Imagine what the previous programs would look like if for each meaningful instruction name we had used a name like firstInstruction or doItNow. The robot programming language allows us to choose any instruction names we want, but with this freedom comes the responsibility to select accurate and descriptive names.
It is much easier to verify or debug a program that contains new instructions. The following two facts support this claim.
* New instructions can be independently tested. When writing a program, we should hand simulate each instruction immediately after it is written, until we are convinced that it is correct. Then we can forget how the instruction works and just remember what the instruction does. Remembering should be easy, if we name the instruction accurately. This is easiest if the instruction does only one thing.
* New instructions impose a structure on our programs, and we can use this structure to help us find bugs. When debugging a program, we should first find which of the new instructions is malfunctioning. Then we can concentrate on debugging that instruction, ignoring the other parts of our program, which are irrelevant to the bug.
Thus we see that there is an interesting psychological phenomenon related to the robot instruction definition mechanism. Because the human brain can focus on only a limited amount of information at any one time, the ability to ignore details that are no longer relevant is a great aid to program writing and debugging.
To help make our new instruction definitions understandable, we should also keep their lengths within a reasonable range. A good rule of thumb is that definitions should rarely exceed five to ten instructions. This limit leaves us enough room to write a meaningful instruction, but restrains us from cramming too much detail into any one definition. If an instruction's size exceeds this limit, we should try to divide it naturally into a set of smaller instructions.
This rule applies to the number of instructions written within the main task block too. Most novice programmers tend to write instruction definitions that are too large. It is better to write many small, well-named instructions, instead of a few oversized definitions.
If a new instruction that we write can only be executed correctly in a certain situation, then we should include comments in the definition explaining what those conditions are. For example, an instruction that always picks up a beeper should indicate in a comment where that beeper must appear. For example:
public void moveandpick() // from class Walker
// Requires a beeper on the next corner in front.
{ move();
pickBeeper();
}
Writing understandable programs with new instructions and using the technique of stepwise refinement can reduce the number of errors we make and the amount of time we spend writing robot programs. The real goal, however, is to write beautiful programs; programs that other programmers read with enjoyment and we read with satisfaction.
subclass
override
extends
import
stepwise refinement
The problems in this section require defining new methods for a robot named Karel, or writing complete programs that include such new methods. Concentrate on writing well-structured programs, built from naturally descriptive new methods. Practice using stepwise refinement and freely define any new instructions that you need. If you find yourself continually writing the same sequence of messages, it is a sure sign that you need to define that sequence as a new instruction. Carefully check for syntax errors in your program, and simulate Karel's execution of each program to verify that it is correct.
Paradoxically, the programs in this problem set will be among the largest you will write. The instructions covered in the next chapters are so powerful that we will find that complex tasks can be solved with programs comprising a small number of these potent instructions.
1. Write appropriate definitions for the following new methods: (1) moveMile, remembering that miles are 8 blocks long; (2) move_backward, which moves Karel one block backward, but leaves it facing the same direction, and (3) move_kilo_mile, which moves Karel 1000 miles forward. This last problem is difficult but a fairly short solution does exist. You may use the moveMile message in this problem without redefining it. Can any of these methods cause an error shutoff when it is executed?
2. Karel sometimes works as a pin-setter in a bowling alley. Write a program that instructs Karel to transform the initial situation in Figure 3-5 into the final situation. Karel starts this task with ten beepers in its beeper-bag.
Figure 3-5 A Pin-Setting Task
3. Rewrite the harvesting program using a different stepwise refinement.
4. Figure 3-6 illustrates a field of beepers that Karel planted one night after a baseball game. Write a program that harvests all these beepers. Hint: this task is not too different from the harvesting example. If you see the correspondence between these two harvesting tasks, you should be able to develop a program for this task that is similar to the original harvesting program.
Figure 3-6 Another Harvesting Task
...
19. Suppose we define an instruction in some robot class like this.
public void move()
{
super.move();
move();
}
What will happen if we send our robot such a message? If you want to test this, start your robot facing West or South. What is the meaning of the move instruction within this method?
20. Read Problem 10 of Chapter 2 again. How short a program can you write now to carry out this task, using knowledge from this chapter?
The remaining exercises have been omitted.