In the preceding chapters, a Robot's exact initial situation was known at the start of a task. When we wrote our programs, this information allowed Karel to find beepers and avoid running into walls. However, these programs worked only in their specific initial situations. If a robot tried to execute one of these programs in a slightly different initial situation, the robot would almost certainly perform an error shutoff.
What a robot needs is the ability to survey its local environment and then decide from that information what to do next. The IF instructions are discussed in this chapter. There are two versions of the IF statement, the IF and the IF/ELSE. They provide robots with their decision ability. Both allow a robot to test its environment and, depending on the result of the test, decide which instruction to execute next. The IF instructions enable us to write much more general programs for our robots that accomplish the same task in a variety of similar, but different, initial situations. These instructions are especially suited for letting robots deal with things like walls and beepers that are not objects. If they were objects, we could interact with them polymorphically as we saw in the last chapter.
Robot programs contain several different kinds of instructions. The first, and most important, is the message to a robot. These messages are sent to robots, either by the pilot (when they appear in the main task block) or by another robot (when they occur in a method of some class). The action associated with this kind of instruction is defined by the corresponding method in the class of the robot to which the message is directed.
Another kind of instruction is the delivery specification, which is sent to the factory to construct a new robot and have the helicopter pilot deliver it.
The IF instruction is yet another different kind of instruction. The rest of this chapter and the next are going to add to this list of kinds of instructions.
The IF instruction is the simpler of the two IF variants. It has the following general form.
if ( <test> )
{
<instruction-list>
}
The IF instruction introduces the new reserved word if (spelled in lowercase). The reserved word if signals a program reader that an IF instruction is present, and the braces enclose a list of instructions. The<instruction-list> is known as the THEN clause of the instruction. We indent the IF instruction as shown, to highlight the fact that <instruction-list> is a component of the IF instruction. Note that we do not follow the right brace of an IF instruction with a semicolon.
A robot executes the IF instruction by first checking whether <test> contained in the parentheses is true or false in the robot's current situation. If <test> is true, the robot executes <instruction-list>; if <test> is false, the robot skips <instruction-list>. In either case, the robot is then finished executing the entire IF instruction. For an example, let's look at the program fragment1 below, which consists of an IF instruction followed by a move message. Assume that this fragment is contained in a method of some class. Some robot of that class will be executing the code.
FOOTNOTE To conserve space, we often demonstrate a programming idea without writing a complete robot program or new method. Instead, we just write the necessary instruction, which is called a program fragment.
if ( nextToABeeper())
{
pickBeeper();
}
turnLeft();
When this IF instruction is executed by the robot, it first checks whether it is next to (on the same corner as) a beeper. If it finds that nextToABeeper is true, the robot executes the THEN clause, which instructs it to execute pickBeeper. The robot is now finished executing the IF instruction, and continues by executing the rest of the instructions, starting at the turnLeft message.
Now suppose that there are no beepers on the corner when the robot executes this program fragment. In this case nextToABeeper is false, so the robot does not execute the THEN clause. Instead, it skips directly to the turnLeft message and continues executing the program from there. The result of this second case is that the robot executes the IF instruction by doing nothing more than asking itself to check whether or not it is next to a beeper. An error shutoff cannot occur in either case, because the robot executes the pickBeeper message only if it confirms the presence of at least one beeper on the corner.
It is also possible to use IF statements in the main task block, but here we must be careful to ask a particular robot about its state. We ask about a robot's state by sending messages, just as we ask robots to perform instructions using messages. If we want to know about the state of a particular robot we must send a message to that robot. When we don't name any robot at all, we are asking about the state of the robot actually executing the current instruction. Since the main task block is not a method of any particular robot, we must use a robot's name there.
if ( Karel.nextToABeeper())
{
Karel.pickBeeper();
}
Karel.turnLeft();
In Chapter 1 we briefly discussed the sensory capabilities or robots. We learned that a robot can see walls, hear beepers, determine which direction it is facing, and feel if there are any beepers in its beeper-bag or other robots on its current corner. The conditions that a robot can test are divided according to these same four categories.
Below is a new class, with several conditions that robots of this class can test. This class can serve as the parent class of many of your own classes for the remainder of your visit to Karel's world. The class is so important, in fact, that the Karel-Werke makes its definition available to all robot purchasers. Therefore you may use this class in the same way that you use ur_Robot. You don't need to type it or even import it. Since these are the most common type of robot, the name of the class is simply Robot. These robots will be able to make good use of IF and other similar statements.
public class Robot extends ur_Robot
{
boolean frontIsClear(){...}
boolean nextToABeeper(){...}
boolean nextToARobot(){...}
boolean facingNorth(){...}
boolean facingSouth(){...}
boolean facingEast(){...}
boolean facingWest(){...}
boolean anyBeepersInBeeperBag(){...}
}
The items in the instruction list name the tests that a robot of the Robot class may perform using its sensors. They return true or false values to the robot mechanism and so we mark them as boolean.1 These methods are called predicates. They provide the means by which robots can be queried (or can query their own internal state) to decide whether certain conditions are true or false. On the other hand, actions like move and turnOff are flagged as void because the robot gets no feedback information from them. The word void indicates the absence of a returned value. In computer programming languages, parts of a program that have a value are called expressions. Expressions are usually associated with a type, giving the valid values of the expression. A predicate represents a boolean expression, meaning that its value is either true or false.
FOOTNOTE boolean methods are named after George Boole, one of the early developers of logic.
Robot programmers can create new predicates in their own classes, just as they can create new void methods.
Recall that robots have a microphone that they can use to listen and determine if there are any beepers present on their current corner. This action is activated by the nextToABeeper message. If a robot, say Carol, is sent the message Carol.nextToABeeper() it will activate the microphone, and will respond to the message with true or false. The state of the robot doesn't change, but the sender of the message will obtain information about the state of the robot. This information can be put to use only by statements like the IF instruction and others in this and the next chapter. The nextToABeeper test is true when a robot is on the same corner as one or more beepers. A robot cannot hear beepers any farther away, and it cannot hear beepers that are in the sound proof beeper-bag.
The nextToARobot predicate is similar and returns whether or not there is another robot on the same corner. This predicate activates the robot's arm, which is used to feel about for other robots.
Remember that each robot has a TV camera for eyes, focused to detect a wall exactly one half of a block away to the front. This camera is facing directly ahead. The frontIsClear predicate tests this condition. If a robot needs to test if its right is clear, it will need to proceed by first turning to the right to check for the presence of a wall. It can then return to its original orientation by turning back to its left.
A robot consults its internal compass to decide what direction it is facing. Finally, a robot can test whether or not there are any beepers in the beeper-bag by probing it with the mechanical arm. This condition is returned by the anyBeepersInBeeperBag predicate.
We will often want both positive and negative forms of many predicates. For example, we would probably want a predicate frontIsBlocked as the negative form of frontIsClear. Only the positive forms are provided by the Robot class, however. To aid in the writing of such negative forms, we will rely on the logical negation operator. In English this is usually written not. In the robot programming language we use the negation operator, "!", for this. For example, we have nextToABeeper. If we also want "not nextToABeeper", what we write is "! nextToABeeper()". Any message evaluating a predicate can be "negated" by preceding it with the negation operator, "!" (sometimes called "bang"). Thus, if robot Karel has beepers in its beeper-bag then it could respond to the instruction
if (! Karel.nextToABeeper())
{
//Read: "If it is not true that Karel is next to a beeper . . . "
Karel.putBeeper();
}
Alternatively we could create our own subclass of the Robot class and provide a new predicate not_nextToABeeper, as shown in the next section. In this case we would use:
if ( Karel.not_nextToABeeper())
{
Karel.putBeeper();
}
While the eight predicates defined above are built into the language, the user can also write new predicates. Predicates return boolean values, true and false. Therefore, in the block of the definition of a new predicate we need to indicate what value is to be returned. For this we need a new kind of instruction: the RETURN instruction. The form of the RETURN instruction is the reserved word return, followed by an expression. In a boolean method the value of the expression must be true or false. RETURN instructions are only legal in predicates. They can't be used in ordinary (void) methods, nor in the main task block.
We might want predicates that are negative forms of the Robot class predicates. They can be defined using the not operator. For example, in a class CheckerRobot, we might want the following as well as some others.
public class CheckerRobot extends Robot
{ public boolean frontIsBlocked()
{ return ! frontIsClear();
}
...
}
public boolean not_nextToABeeper()
{ return ! nextToABeeper();
}
public boolean rightIsClear()
{ turnRight();
if ( frontIsClear() )
{ turnLeft();
return true;
}
turnLeft();
return false;
}
The return instruction immediately terminates the predicate it is contained within. Therefore, if frontIsClear is true then the robot will turn left and return true. This method will have then terminated (returned). It won't reach or execute the second turnLeft or the return false instruction. On the other hand, if the frontIsClear test returns false, then the robot skips the THEN clause, and so it executes the second turnLeft and the return false instruction. Notice that we were careful here to leave the robot facing the same direction that it was facing before this predicate was executed. Therefore the programmer using rightIsClear can ignore the fact that the robot executes turns in order to evaluate this predicate, since any turn is undone. We can say that the turn is "transparent" to the user.
Notice that in the rightIsClear method, if we reverse the order of the last two messages in the body, then the return instruction will be executed before the turnLeft (only when frontIsClear() is false of course). But since the return will terminate the predicate, we won't ever execute the turnLeft. This would be an error, since it wouldn't leave the robot facing the original direction as was intended.
This section examines three new methods that use the IF instruction. During our discussion we will also discuss how IF instructions are checked for correctness.
Let's give Karel a new task similar to the harvesting task discussed in Section 3.8.1. Karel's new task still requires the robot to harvest the same size field, but this time there is no guarantee that a beeper is on each corner of the field. Because Karel's original program for this task would cause an error shutoff when it tried to execute a pickBeeper on any barren corner, we must modify it to avoid executing illegal pickBeeper instructions. Karel must harvest a beeper only if it determines that one is present.
Knowing about the new IF instruction, we can now write a program for this slightly more general task. One sample initial situation is illustrated in Figure 5-1.
Figure 5-1: A Modified Harvest Task-not all corners have beepers
Please notice that this is only one of many possible initial situations. Our program must be able to harvest this size field (six by five) regardless of which corners have beepers and which corners do not.
Luckily for us, most of our previously written harvesting program can be reused -- another advantage of object-oriented programming with classes. All we need to do is to create a new version of the harvestCorner method in a new subclass of Harvester. The new version of harvestCorner only picks up a beeper if it knows there is one on the current corner. To do this we create a new class, SparseHarvester, whose parent class is Harvester. We will also, however, need to modify Harvester so that its parent class is Robot rather than ur_Robot. With this change we can take advantage of the predicates defined in class Robot.
package kareltherobot;
public class SparseHarvester extends Harvester
{
public void harvestCorner()
{ if ( nextToABeeper() )
{ pickBeeper();
}
}
}
This section will demonstrate how we decide when to use the IF instruction and how we decide what condition we want a robot to check in <test>. As part of this and future discussions, let's assume we are planning and implementing the solution to a large problem where a robot named Karel is on a treasure hunt for the "Lost Beeper Mine" which is a very large pile of beepers.
Let's further assume that we have developed an overall plan and are working on one small task within this plan. This task requires that Karel face to the north only if it is currently facing south. In Chapter 3 we introduced a question and answer format to show how we might plan and analyze possible ways to solve a problem. The same format also works well in the implementing phase of problem solving.
Question: What does Karel have to do?
Answer: Karel must turn to face north only if it is currently facing south.
Question: How many alternatives does the robot have to choose from?
Answer: Two.
Question: What are these alternatives?
Answer: Alternative #1 is to turn to the north if it is facing south. Alternative #2 is to do nothing if it is facing any other direction.
Question: What instruction can we use to allow Karel to decide which alternative to choose?
Answer: The IF instruction allows Karel to decide which alternative to choose.
Question: What test can Karel use in the IF instruction?
Answer: Since Karel is supposed to turn to the north only if it is facing to the south, the facingSouth test can be used.
Question: What does Karel do if it is facing south?
Answer: Karel will turnLeft twice.
Question: What does Karel do if it is not facing south?
Answer: Karel does nothing.
The thought process for implementing each instruction definition in our program must be as careful and detailed as it was when we were developing our original plan for the solution. Each step must be carefully analyzed for its strengths and weaknesses. If we ask a question and we cannot answer it satisfactorily, then either we have asked the wrong question or our plan for the instruction's definition is flawed. The longer we spend thinking about the implementation, the less time we will spend correcting errors. Having taken the time to analyze our answers, our instruction implementation looks like this. We assume here that we are building a new class, Prospector, of robots that can search for the Lost Beeper Mine.
public void faceNorthIfFacingSouth()
{ if (facingSouth())
{ turnLeft();
turnLeft();
}
}
Here is a new problem to solve. Let's assume we are planning the definition of another part of the Lost Beeper Mine problem. We must implement an instruction definition that faces a robot north regardless of the direction it is currently facing. Using the question/answer format, we approach this solution by first thinking about Karel's situation. Can we use the information about the direction Karel is currently facing to solve the problem?
Question: What does Karel have to do?
Answer: It must determine which direction it is facing to decide how many turnLefts to execute so it will be facing north.
Question: How many different alternatives does the robot have?
Answer: Karel has one alternative for each direction it could be facing. Therefore it has four alternatives.
Question: What are these alternatives?
Answer: Alternative #1 facing north - do nothing.
Alternative #2 facing east - turn left once.
Alternative #3 facing south - turn left twice.
Alternative #4 facing west - turn left three times.
Question: What test(s) can Karel use to decide which direction it is facing?
Answer: Karel can check to see if it is facingEast, facingSouth, facingWest--since Karel does not have to do anything when it is facing north, we do not have to use that test.
We can use these questions and their answers to aid us in implementing the new method, faceNorth.
public void faceNorth()
{ if (facingEast())
{ turnLeft();
}
if (facingSouth())
{ turnLeft();
turnLeft();
}
if (facingWest())
{ turnLeft();
turnLeft();
turnLeft();
}
}
Compare this method to the set of questions preceding it. Did we ask all of the necessary questions? Did we answer them correctly? Trace this method for execution and simulate it four times, one for each direction Karel could initially be facing. Does it work in all cases?
There is another way to solve this problem. Examine this set of questions.
Question: What does Karel have to do?
Answer: Karel must turnLeft until it is facing north.
Question: How many alternatives does the robot have?
Answer: Two.
Question: What are they?
Answer: Alternative # 1 is to turnLeft if it is not facing north.
Alternative # 2 is to do nothing if it is already facing north.
Question: How can we use this information?
Answer: Karel can never be more than three turnLefts away from facing north so we can use a sequence of three IF instructions; each one will check to see if Karel is not facingNorth. If the test is true, Karel will turnLeft and be one turnLeft closer to facing north.
Question: What happens when Karel starts out facing north?
Answer All three tests will be false and Karel does nothing.
Question: What happens when Karel is facing east?
Answer: The first test is true and Karel executes a turnLeft. The remaining two tests are false and Karel does nothing.
Question: What happens when Karel is facing south?
Answer: The first two tests are true so Karel executes two turnLefts. The third test is false and its THEN clause is skipped.
Question: What happens when Karel is facing west?
Answer: All three tests will be true so Karel will execute three turnLefts.
Here is our resulting new instruction.
public void faceNorth()
{ if ( ! facingNorth() )
{ turnLeft();
}
if ( ! facingNorth() )
{ turnLeft();
}
if ( ! facingNorth() )
{ turnLeft();
}
}
Trace this instruction for execution and simulate it four times, one for each direction Karel could initially be facing. Does it work in all cases?
The question must be asked as to which of these two faceNorth instructions is better. For now, either is perfectly acceptable.
Checking an IF instruction is similar to checking a dictionary entry, since both are "meaningful" components of a program. Both IF instructions and dictionary entries use reserved words and braces to separate their different parts. You check the IF instruction by first checking the <test>, making sure it is correct and contained in parentheses. You then check the instructions inside the braces. Finally, you check the entire IF instruction including its braces.
Study, for example, the version of captureTheBeeper that follows.
public void captureTheBeeper()
{ move();
if (nextToABeeper())
{ pickBeeper();
turnAround();
}
move();
}
This definition contains three instructions: the first move, the IF and the second move. The move messages are terminated by semicolons, and the two messages inside the block of the IF are likewise terminated by semicolons. The predicate is correct and contained in parentheses and the braces for the IF correctly enclose the two messages. It seems OK. Notice, however, that it leaves us in one of two different places, facing in one of two different directions, depending on whether it finds a beeper or not. It might be important in some problems to avoid this difference since other instructions will be executed after this one. If we are not careful, the robot could wander away from the desired path. We try to be careful to pick a name for a method that describes alll that the robot will do when executing it. We also generally try to leave the robot in the same state regardless of how it executes the instruction. The next instruction will help in this.
In this section we discuss the second type of IF instruction built into the robot vocabulary. The IF/ELSE instruction is useful when, depending on the result of some test, a robot must execute one of two alternative instructions. The general form of the IF/ELSE is given below.
if ( <test> )
{
<instruction-list-1>
}
else
{
<instruction-list-2>
}
The form of the IF/ELSE is similar to the IF instruction, except that it includes an ELSE clause. Note the absence of a semicolon before the word else and at the end. A robot executes an IF/ELSE in much the same manner as an IF. It first determines whether <test> is true or false in the current situation. If <test> is true, the robot executes <instruction-list-1>; if <test> is false, it executes <instruction-list-2>. Thus, depending on its current situation, the robot executes either <instruction-list-1> or <instruction-list-2>, but not both. By the way, the first instruction list in an IF/ELSE instruction is called the THEN clause and the second instruction list is called the ELSE clause.
Let's look at a task that uses the IF/ELSE instruction. Suppose that we want to program a robot to run a one mile long hurdle race, where vertical wall sections represent hurdles. The hurdles are only one block high and are randomly placed between any two corners in the race course. One of the many possible race courses for this task is illustrated in Figure 5-2. Here we think of the world as being vertical with down being south. We require the robot to jump if, and only if, faced with a hurdle.
Figure 5-2: A Hurdle Jumping Race
The robot could easily program this race by jumping between every pair of corners, but although this strategy is simple to program, it doesn't meet the requirements. (Perhaps it would slow the robot down too much.) Instead, we must program the robot to move straight ahead when it can, and jump over hurdles only when it must. The program implementing this strategy consists of a main task block that contains eight raceStride messages followed by a turnOff. The definition of raceStride can be written using stepwise refinement as follows.
public class Racer extends Robot
{
public void raceStride()
{
if ( frontIsClear() )
{ move();
}
else
{ jumpHurdle();
}
}
...
}We continue our refinement by writing jumpHurdle.
public void jumpHurdle()
{ jumpUp();
move();
glideDown();
}
Finally, we write jumpUp and glideDown, the methods needed to complete the definition of jumpHurdle.
public void jumpUp()
{ turnLeft();
move();
turnRight();
}
public void glideDown()
{ turnRight();
move();
turnLeft();
}
To verify that these methods are correct, complete and assemble the program. Then simulate a Racer robot running the race in Figure 5-2.
Although we have seen many IF instructions, we have ignored an entire class of complex IF'S. These are known as nested IF instructions, because they are written with an IF instruction nested inside the THEN or ELSE clause of another IF. No new execution rules are needed to simulate nested IF' s, but a close adherence to the established rules is required. Simulating nested IF instructions is sometimes difficult because it is easy for us to lose track of where we are in the instruction. The following discussion should be read carefully and understood completely as an example of how to test instructions that include nested IF'S.
To demonstrate a nested IF instruction, we propose a task that redistributes beepers in a field. This task requires that a robot named Karel traverse a field and leave exactly one beeper on each corner. The robot must plant a beeper on each barren corner and remove one beeper from every corner where two beepers are present. All corners in this task are constrained to have zero, one, or two beepers on them. One sample initial and final situation is displayed in Figure 5-3. In these situations, multiple beepers on a corner are represented by a number. We can assume that Karel has enough beepers in its beeper-bag to replant the necessary number of corners.
Figure 5.3: A Beeper Replanting Task
The heart of the program that solves this task is a method that enables Karel to satisfy the one-beeper requirement for each corner. Here is the method. We can provide an override method for the harvestCorner method of the Harvester class.
public
class Replanter extends Robot
{
public void harvestCorner()
{ if ( ! nextToABeeper() )
{ putBeeper();
}
else
{ pickBeeper();
if ( ! nextToABeeper() )
{ putBeeper();
}
}
}
...
}
The outer IF statement in this definition is an IF/ELSE and the nested IF statement is an ordinary IF. The nested IF instruction is inside the ELSE clause of the outer IF. Next, we simulate Karel in the three possible corner situations: an empty corner, a corner with one beeper, and a corner with two beepers.
In the empty corner situation, Karel executes the outer IF and determines that the test is true. The robot executes the putBeeper message in the THEN clause placing one beeper on the corner. Karel has now finished executing the outer IF instruction and thus has finished executing harvestCorner.
Next we assume that there is one beeper on Karel's corner. Karel first executes the outer IF. The test is false so the robot executes the ELSE clause. This clause consists of two instructions, pickBeeper and the nested IF instruction. Karel picks the beeper and performs the test associated with the nested IF. The test is true so Karel executes the THEN clause of this IF instruction and puts a beeper back on the empty corner. Karel is now finished with the nested IF, the ELSE clause, the outer IF, and the entire harvestCorner instruction.
Finally, we assume that Karel is on a corner with two beepers. Karel executes the outer IF, finds the test is false, and then executes the ELSE clause. Karel picks up one of the two beepers on the corner. Up to this point Karel has duplicated its actions in the one-beeper situation, but now comes the difference in execution. Karel executes the nested IF instruction, finds the test is false, and skips the nested IF'S THEN clause. Once again, Karel is now finished with the nested IF, the ELSE clause, the outer IF, and the entire harvestCorner instruction.
It is worth mentioning that when nested IF instructions seem too intricate we should try replacing the nested IF with a new instruction name. The definition of this auxiliary method must command Karel to perform the same actions as the nested IF and may help us better understand what Karel is doing. Because nesting also makes an instruction less readable, a good rule of thumb is to avoid nesting IF instructions more than one level deep. The harvestCorner method, which has one level of nesting, is rewritten below using an auxiliary method.
public void harvestCorner()
{ if ( ! nextToABeeper() )
{ putBeeper();
}
else
{ nextToOneReplantOne();
}
}
We write the nextToOneReplantOne method by copying the ELSE clause from our original definition of harvestCorner.
public void nextToOneReplantOne()
{ pickBeeper();
if ( ! nextToABeeper() )
{ putBeeper();
}
}
Given the entire program from Section 3.9.1 along with either of these new definitions of the harvestCorner method, do we have a correct solution for the beeper replanting task? We may consider using our old method of verification and test the program with Karel in every possible initial situation, but there are more than 200 trillion (2) different fields that this program must be able to replant correctly! Attempting verification by exhaustively testing Karel in every possible initial situation would be ludicrous.
FOOTNOTE 2: There are 3 different possibilities for each corner; and there are 30 corners in the field. The total number of different fields is thus 3 multiplied by itself 30 times. For you mathemagicians, the exact number of different fields is 205,891,132,094,649.
Instead, we will try to establish correctness based on the following informal argument: (1) we have verified that harvestCorner works correctly on any corner that is empty or contains one or two beepers, and (2) we can easily verify that our program commands Karel to execute this instruction on each corner of the field. Therefore we conclude that the program correctly replants the entire field.
This argument further enhances the claim that Karel's mechanism for instruction definition is a powerful aid to programming. Usually, we can informally conclude that an entire program is correct by verifying that: (1) each new instruction in the program works correctly in all possible situations in which it can be executed, and (2) the program executes each new instruction at the appropriate time. This method allows us to verify a program by splitting it into separate, simpler, verifications, just as stepwise refinement allows us to write a program by splitting it into separate, simpler instructions.
Suppose that a robot is in a situation in which it must determine if there are exactly two beepers on the current corner. We would like to write a predicate to return true if this is so, and false otherwise. Suppose that this were needed in some replanting task, so we will add it to the Replanter class. We can write such a predicate if we pick up beepers one at a time and then ask if there are any more. We must remember to put back any beepers that we pick up, however. Note that if we have picked two beepers up, we still need to ask if there are any more to determine if there are exactly two beepers on the current corner.
public boolean exactlyTwoBeepers()
{ if (nextToABeeper()) // one or more beepers
{ pickBeeper();
if (nextToABeeper()) // two or more beepers
{ pickBeeper();
if(nextToABeeper()) // more than two
{ putBeeper();
putBeeper();
return false;
}
else // exactly two beepers
{ putBeeper();
putBeeper();
return true;
}
}
else // only one beeper
{ putBeeper();
return false;
}
}
else // no beepers
{ return false;
}
}
It is not a trivial matter to have a robot make two or more tests at the same time. More sophisticated programming languages provide the capability to make multiple tests within an IF or an IF/ELSE instruction. We can do this but we must be clever with our programming as illustrated by the following example.
Let's assume we are still working on the Lost Beeper Mine problem introduced earlier. Recall that the Lost Beeper Mine is a very large pile of beepers. We have another assignment from that problem--a very important landmark along the way is found where all of the following are true:
* Karel is facing west,
* Karel's right side is blocked,
* Karel's left side is blocked,
* Karel's front is clear, and
* there is at least one beeper on the corner.
Following these requirements we must plan an instruction that will test all of these conditions simultaneously. If we do what seems logical we might try to write something like this:
if ( facingWest()
AND rightIsBlocked()
AND leftIsBlocked()
AND frontIsClear()
AND nextToABeeper() )
{ . . .
This seems very logical, but there is one major problem. Robots do not understand, "AND". The "AND" will result in a lexical error, so we must use a sequence of nested IF instructions to do the job.
if (facingWest() )
{ if ( ! rightIsClear() )
{ if ( ! leftIsClear() )
{ if (frontIsClear() )
{ if (nextToABeeper() )
{
<instruction>
}
}
}
}
}
If we trace this, we will find that all of the tests must evaluate to true before Karel can execute <instruction>.
Another way to build complex tests is to define new predicates. Suppose we would like to write
if (nextToABeeper() AND leftIsBlocked()) { . . .
This can be done if we write a new predicate in the class in which we need such a test. For example:
public boolean nextToABeeper_AND_leftIsBlocked()
{ if(nextToABeeper())
{ if ( ! leftIsClear())
{ return true;
}
else
{ return false;
}
}
return false;
}
This can be simplified to:
public void nextToABeeper_AND_leftIsBlocked()
{ if(nextToABeeper())
{ return ! leftIsClear();
}
return false;
}
One way to help determine if a predicate with two or more conditions is correct is to look at the truth table, which gives all possible combinations of the parts of the predicate. The truth table for AND is shown below.
nextToABeeper leftIsBlocked | AND
T T | T
T F | F
F T | F
F F | F
The IF instruction in the predicate says that when nextToABeeper is true we should return the negation of leftIsClear, which is the same as leftIsBlocked. Note that the first two lines of the truth table also say this. On these two lines nextToABeeper is true and the leftIsBlocked lines exactly match the AND lines here. Likewise, the predicate says that when nextToABeeper is false we should return false. Again, this matches the truth table exactly, since on the last two lines, where nextToABeeper is false, we return false.
Note that in the nextToABeeper_AND_leftIsBlocked instruction there is no need to check that the left is clear if we have already determined that we are NOT next to a beeper. We can simply return false in this case. We only need to check the second part of the AND when the first part is true. This is known as "short-circuit evaluation" of the predicate, and it is very useful. To use it wisely, however, so that a user isn't misled, you must check the leftmost part (nextToABeeper) first. Some computer languages that have the AND operator built in to them automatically use short-circuit evaluation. Others do not.
A similar instruction can be used to simulate
if (nextToABeeper() OR leftIsBlocked()) { . . .
The truth table for an OR is as follows. Notice that when nextToABeeper is true the OR is also true, and when nextToABeeper is false the result is the same as leftIsBlocked.
nextToABeeper leftIsBlocked | OR
T T | T
T F | T
F T | T
F F | F
Footnote: Java (and C++) do have AND and OR instructions, though they are called operators, and they are spelled && and ||, respectively.
Thus far we have spent most of our time and effort in this chapter explaining how the IF and the IF/ELSE instructions work. It is at this point that students are usually told, "Write a program that uses the IF and the IF/ELSE instructions so that a robot can . . . " It is also at this point that we hear the following question being asked by students, "I understand how these work but I don't understand when to use them." It is "understanding when to use them" that is the focus of this section.
Let's review what the IF and the IF/ELSE instructions allow robots to do in a robot program:
* The IF instruction allows a robot to decide whether to execute or skip entirely the block of instructions within the THEN clause.
* The IF/ELSE instruction allows a robot to decide whether to execute the block of instructions in the THEN clause or the ELSE clause.
* Nesting these instructions allows Karel to make more complex choices if required.
We can use these three statements to build a decision map. A decision map is a technique that asks questions about the problem we are trying to solve. The answers to the questions determine the branch we follow through the map. Here is the section of the decision map that a programmer would use for choosing between an IF and an IF/ELSE.
Figure 5-4 Part of the Decision Map
To use this part of the decision map we must be at a point during our implementation where a robot needs to choose from among alternatives. We use the map by asking each question as we encounter it and following the path that has the answer. If done correctly, we eventually arrive at an implementation suggestion. If the map does not work, we probably do not need to choose between alternatives or have not correctly thought out our plan. By the way, we say we choose from among one alternative as a shorthand for the situation where the choice is simply to do something or not.
Suppose a robot must face north if there is a beeper on the current corner and face south otherwise. How many tests does the robot have to make? One-either nextToABeeper or !nextToABeeper. This answer directs us down the left path to the next question, how many alternatives does the robot have available? Two-the robot must either face north or face south. This takes us down the path to the IF/ELSE instruction. Our implementation looks like this.
if( nextToABeeper() )
{ faceNorth();
}
else
{ faceSouth();
}
This section discusses four useful transformations that help us simplify programs containing IF instructions. We start by observing that when two program fragments result in a robot's performing exactly the same actions, we call this pair of fragments execution equivalent. For a simple example, turnLeft(); putBeeper(); is execution equivalent to putBeeper(); turnLeft();.
In general, we can create one execution equivalent IF/ELSE instruction from another by replacing <test> with its opposite and interchanging the THEN and the ELSE clauses as illustrated below. We call this transformation test reversal. Notice that if we perform test reversal twice on the same instruction, we get back to the instruction with which we started.
if(frontIsClear()) if( ! frontIsClear() )
{ move(); { jumpHurdle();
} }
else else
{ jumpHurdle(); { move();
} }
Test reversal can be used to help novice programmers overcome the following difficulty. Suppose that we start to write an IF instruction and get ourselves into the dilemma illustrated below on the left. The problem is that we want a robot to do nothing special when its front is clear (3) but when its front is blocked we want Karel to execute <instruction>. We would like to remove the THEN clause, but doing so would cause a syntax error -- Karel does not understand an IF/ELSE instruction without a THEN clause. The solution to our problem is illustrated on the right.
FOOTNOTE 3: We can define the method doNothing as four left turns. Executing this instruction would leave Karel's position unchanged, and this instruction is also immune to error shutoffs. This would be wasteful of the Robot's battery capacity, however. We could also simply not write anything between the braces of the THEN part.
if(frontIsClear()) if( ! frontIsClear())
{ doNothing(); { <instruction>
} }
else
{ <instruction>
}
To transform the IF on the left into the IF on the right, we use test reversal. First we change <test> to its opposite, then switch the doNothing instruction into the ELSE clause and bring <instruction> into the THEN clause. By the previous discussion of test reversal, execution equivalence is preserved. Finally, the new ELSE clause (which contains the doNothing instruction) can be removed, resulting in the simpler IF instruction on the right.
The second transformation we discuss is bottom factoring. Bottom factoring is illustrated below, where we will show that the IF/ELSE instruction on the left is execution equivalent to the program fragment on the right. We have kept the bracketed words in these instructions because their exact replacements do not affect this transformation.
if(<test>) if(<test>)
{ <instruction_1> { <instruction_1>
<instruction_3> }
} else
else { <instruction_2>
{ <instruction_2> }
<instruction_3> <instruction_3>
}
In the program fragment on the right, we have factored <instruction_3> out of the bottom of each clause in the IF. We justify the correctness of this transformation as follows: If <test> is true, the instruction on the left has the robot execute <instruction_1> directly followed by <instruction_3>. In the program fragment on the right, if <test> is true the robot executes <instruction_1> and then, having finished the IF, it executes <instruction_3>. Thus, when <test> is true, these forms are execution equivalent. A similar argument holds between the left and right fragments whenever <test> is false.
In summary, <instruction_3> is executed in the IF on the left regardless of whether <test> is true or false. So we might as well remove it from each clause and put it directly after the entire IF/ELSE instruction. Moreover, if the bottoms of each clause were larger, but still identical, we could bottom factor all of the common instructions and still preserve execution equivalence. Think of this process as bottom factoring one instruction at a time until all common instructions have been factored. Since execution equivalence is preserved during each factoring step, the resulting program fragment is execution equivalent to the original instruction.
The third transformation we discuss in this section is top factoring. Although this transformation may seem as simple and easy to use as bottom factoring, we will see that not all instructions can be top factored successfully. We divide our discussion of this transformation into three parts. First, we examine an instruction that can safely be top factored. Then we show an instruction that cannot be top factored successfully. Finally, we state a general rule that tells us which IF instructions can safely be top factored.
Top factoring can safely be used in the following example to convert the instruction on the left into the simpler program fragment on the right. These two forms can be shown to be execution equivalent by a justification similar to the one used in our discussion of bottom factoring.
if(facingNorth()) move();
{ move(); if(facingNorth())
turnLeft(); { turnLeft();
} }
else else
{ move(); { turnRight();
turnRight(); }
}
In the next example, we have incorrectly used the top factoring transformation. We will discover that the program fragment on the right is not execution equivalent to the instruction on the left.
if(nextToABeeper()) move();
{ move(); if(nextToABeeper())
turnLeft(); { turnLeft()
} }
else else
{ move(); { turnRight();
turnRight(); }
}
To show that these forms execute differently, let's assume that a robot named Karel is on a corner containing one beeper, and that the corner in front of the robot is barren. If Karel executes the instruction on the left, the robot will first find that it is next to a beeper, and then will execute the THEN clause of the IF by moving forward and turning to its left. The program fragment on the right will first move Karel forward to the next corner and then will instruct it to test for a beeper. Since this new corner does not contain a beeper, Karel will execute the ELSE clause of the IF, which causes the robot to turn to its right. Thus, top factoring in this example does not preserve execution equivalence.
Why can we correctly use top factoring in the first example but not in the second? The first instruction can be top factored safely because the test that determines which way Karel is facing is not changed by having it move forward. Therefore, whether Karel moves first or not, the evaluation of the test will remain unchanged. But in the second example, the move changes the corner on which Karel checks for a beeper, so the robot is not performing the test under the same conditions. The general rule is that we may top factor an instruction only when the conditions under which the test is performed do not change between the original and factored versions of the instruction.
The fourth and final transformation is used to remove redundant tests in nested IF instructions. We call this transformation redundant-test-factoring and show one application of this rule.
if(facingWest()) if(facingWest())
{ move(); { move();
if(facingWest()) turnLeft();
{ turnLeft(); }
}
}
In the instruction on the left, there is no need for the nested IF instruction to recheck the condition facingWest. The THEN clause of the outer IF is only executed if Karel is facing west, and the move inside the THEN clause does not normally change the direction that Karel is facing. Therefore, facingWest is always true when Karel executes this nested IF instruction. This argument shows that Karel always executes the THEN clause of this nested IF. So, the entire nested IF instruction can be replaced by turnLeft, as has been done in the instruction on the right. Once again, this transformation preserves execution equivalence. Of course, if we have given move a new meaning in the class of which this is a member, then we cannot guarantee that move doesn't change the direction. In this case the two fragments would not be equivalent. A similar transformation applies whenever we look for a redundant test in an ELSE clause. Remember, though, in an ELSE clause <test> is false.
This transformation is also a bit more subtle than bottom factoring, and we must be careful when trying to use it. The potential difficulty is that intervening instructions might change Karel's position in an unknown way. For example, if instead of the move message we had used a turnAroundIfNextToABeeper message, we could not have used redundant-test factoring. Here we cannot be sure whether Karel would be facing west or east when it had to execute the nested IF.
These four transformations can help us make our programs smaller, simpler, more logical, and--most important--more readable.
Since polymorphism is in many ways the most important topic of this book, we would like to say a few more things about it and see how it can be used in conjunction with IF statements to do some wonderful things. In a certain sense IF statements achieve a measure of polymorphism, called ad-hoc polymorphism, since the program must make explicit (or ad-hoc) decisions. In some circumstances we don't have a choice of using IF statements or polymorphism to achieve an end, but when we do, polymorphism gives a more satisfactory result. This is because problems change and when they do, IF statements usually need to be modified and when a program contains a large number of IF statements and only some of them need to be changed for the new problem, it can be a major task keeping the updates consistent. In this section we will solve a few problems that use both IF statements and polymorphism to get a sense of the difference.
The situations in which we cannot use polymorphism in the robot language as in Java involve those things that cannot behave polymorphically. Beepers and walls are not objects, so we can't use polymorphism to deal with them. Robots on the other hand can behave (and always behave) polymorphically so with robot behavior we prefer polymorphism.
Here is a simple problem that we looked at in Chapter 4, but can extend here. Suppose we have a bunch of robots, one on each corner of a street from some avenue to some avenue farther on and we want to ask each of them to put down one beeper. We want to write a program that will work no matter how many robots there are. To make it explicit, suppose there is a robot on first street and n'th avenue and we want a robot with one beeper on each corner between the origin and this robot and then we want to ask them all to put down their beepers. We will use IF statements to set up the situation and then use polymorphism to get the robots to put down their beepers.
To do this we need at least two classes of robots. What we will do here is to make a few changes to our BeeperPutter hierarchy of classes that we built in the prevous chapter. We will make these classes a bit more polymorphic as well as illustrating how we can use IF statements to set up later polymorphic actions.
First, we will need a different rememberNeighbor instruction. In Chapter 4 we used rememberNeighbor to tell a robot who its neighbor is. Here we will not need to do that since each robot will create its own neighbor. Therefore we will want a rememberNeighbor method with no parameters. We will also want this method to be polymorphic, since a NoNeighbor robot has no neighbor so it needs to do nothing at all when it performs rememberNeighbor. Therefore we will implement a "no action" version of rememberNeighbor in our abstract superclass BeeperPutter. This method will be inherited by all subclasses, in particular by NoNeighbor, but we will override it in NeighborTalker.
publicabstract class BeeperPutter extends Robot implements Cloneable {publicabstract void distributeBeepers(); void rememberNeighbor() { } }
In the rememberNeighbor method of NeighborTalker we will have a robot create its own neighbor. We want to be able to do this so that the neighbor is one street to the left of the given robot. Furthermore, if the robot is standing on second avenue then the neighbor it creates (on first avenue) will be a NoNeighbor robot rather than a NeighborTalker robot. If it creates a NeighborTalker then it will send the rememberNeighbor message to the newly created neighbor.
We have a problem with this, however. No robot knows the corner on which it is standing, so it can't create this neighbor using new. To do so would require knowing the street and avenue on which to place it. We will therefore need to use another way to create this neighbor. Any robot can ask the factory to create a robot just exactly like itself. When it does so, the newly created robot will be delivered to the corner on which the robot sits when it makes the request and will be set up in the same state as the existing robot: facing the same direction, with the same number of beepers. To do this we send the robot the clone message. A robot can even send this message to itself, of course, as it can with any other message. The clone message takes no parameters, but returns a new robot of the same class as the original. Thus, we see for the first time that methods can return things other than boolean values.
Note that the clone method itself is highly polymorphic. It can be executed in any robot class and it always returns a robot of the same class and in the same state as the original.
Since we want the neighbor on the adjoining corner, we will move to that corner before sending the clone message. Then we can return to the original corner and then send the neighbor the rememberNeighbor message. The exception will be when we discover that after the first move we find that front is blocked, meaning that we are about to create a robot on first avenue. In this case we want to create a NoNeighbor robot instead of a clone.
public class NeighborTalker extends BeeperPutter
{ ...
public void rememberNeighbor() // PRE: facing West and front is clear
{ move();
if (frontIsClear())
{ neighbor = (BeeperPutter) clone();
}
else
{ neighbor = new NoNeighbor(1, 1, North, 1);
}
goBack();
neighbor.rememberNeighbor();
} // POST: facing North on original corner.
...
}More on Java Cloning
With these changes our main task block becomes especially simple.
public static void main(String [] args)
{ NeighborTalker ARobot = new NeighborTalker(1, 6, West, 1);
ARobot.rememberNeighbor();
ARobot.distributeBeepers();
}
Let's focus for a moment on why we needed IF statements here and why the solution couldn't be entirely polymorphic. In the robot world the walls and beepers are not objects so we cannot build subclasses of them. They are just primitive data. Therefore they cannot act polymorphically (or act at all, actually). The robots CAN be polymorphic but in this situation the robot needs to interact with a wall to find out if its front is clear. We therefore use the non-polymorphic tool, the IF statement, to set up the situation in which polymorphism can then act. Note that aside from the clone and rememberNeighbor methods the only method of interest here was distributeBeepers which was polymorphic. However, we could also have other polymorphic methods in these classes and once the situation was set up, all of them would work without additional IF statements. Thus, if our problem changes we can either add a new class for a new kind of robot that must behave differently from these, or we can add a new polymorphic method to each of these classes. We do not have to visit a large number of if statements and add a new part for each new part of the problem. At most we have to do the rememberNeighbor differently.
Finally, let's consider the Enumeration interface and enumeration objects a bit more. We are now in a position to understand the other method of this interface.
public interface Enumeration
{
public Object nextElement();
public boolean hasMoreElements();
}
The hasMoreElements method is a boolean method, just like nextToABeeper is: a predicate. It tells us if the enumeration has been exhausted yet, either because it was initially empty, or because we have called nextElement a sufficient number of times to enumerate all the elements in the collection. We shall see an even more important use of this method in the next chapter, but for now, note that you can protect yourself against a NoSuchElementException by placing the nextElement instruction inside an if.
Enumeration neighbors = neighbors();
if(neighbors.hasMoreElements())
{
ur_Robot myNeighbor = (ur_Robot)neighbors.nextElement();
...
}
If there are no neighbors at all, this won't do anything.
selection
nested instructions
predicate
condition
statement transformation
clone
The problems in this section require the use of the IF instruction in its two forms. Try using stepwise refinement on these problems, but no matter what instruction you use to obtain a solution, write a clear and understandable program. Keep the nesting level small for those problems requiring nested IF instructions. Use proper punctuation and grammar, especially within the THEN and ELSE clauses of the IF instructions. Carefully simulate each definition and program that you write to ensure that there are no execution or intent errors.
1. Write a new predicate leftIsBlocked that determines if there is a wall exactly one half block away on a robot's left. Be sure that when it terminates, the robot is on the same corner and facing in the same direction.
2. Look at the following instruction. Is there a simpler, execution equivalent instruction? If so, write it down; if not, explain why. Hint: A simplifying transformation for the IF may prove useful. Common sense helps too.
if( ! nextToABeeper())
{ move();
}
else
{ move();
}
3. Assume that a Prospector robot is on a corner with either one or two beepers. Write a new method that commands the robot to face north if it is started on a corner with one beeper and to face south if it is started on a corner with two beepers. Besides facing the robot in the required direction, after it has executed this method there must be no beepers left on the corner. Name this method findNextDirection.
4. Write another version of findNextDirection(see the previous problem). In this version the robot must eventually face the same directions, but it also must leave the same number of beepers on the corner as were there originally.
...
15. We are used to writing tests to be sure that a robot doesn't get into trouble. For example:
if(karel.frontIsClear())
{
karel.move();
}
However, there is a situation in some robot programs in which this is not safe. For example, if we override move. Suppose we do override move to do something other than move one block. What can we also do in the same class to make the above safe again?
16. Modify your solution to Problem 13 of Chapter 4 so that the spiral walking robot properly shuts off when it reaches a wall.
The remaining exercises have been omitted.