INSTRUCTORS' GUIDE TO Karel++

Joseph Bergin

based on the Teacher's Guide to Karel the Robot by Jim Roberts and Mark Stehlik

Introduction

Karel++ is a gentle introduction to object-oriented programming.  It is intended for those who have never programmed a computer previously, or have very little experience doing so.  The book is fundamentally object oriented and the philosophy of teaching is that the most important aspects of the paradigm should be taught first and emphasized throughout.  This is why students see a class definition before they see a function definition, why all functions are part of classes, and why the above is taught long before IF and WHILE statements.  Students write classes almost immediately and use inheritance from the beginning.  Only the built-in features (five robot actions) and thier come before classes and inheitance. 

If you have questions and especially corrections related to this guide or the book itself, please let me know at

berginf at pace.edu

You may also find additional information about Karel++ and the simulator at my home page

http://csis.pace.edu/~bergin/

The simulator is available directly from Wiley.  It will not be available from my homepage. Sorry.

We hope you enjoy using Karel++. 

Part One:  Summary of Changes

Karel++ is based on the second edition of Karel the Robot and is a blend of Richard Pattis's work, Roberts' and Stehlik's programming and teaching techniques, with a thorough retargeting to object-oriented methodology.  Much of the original text is still in this book.  We have attempted to blend the new material with the original material in such a way that the brilliance of the original work is not dimmed.  Here is an overview of the changes in the this work.  If the reader has taught previously with Karel the Robot there are a few things to look out for.  If not, there are some parts of the second edition that might be helpful to you.  We will refer to the predecessor books as Karel the Robot (first and second editions) as distinct from Karel++. 

Additional problems have been added to each chapter (a few of the original problems were removed). 

Chapter One  THE ROBOT WORLD

This is based closely on the second edition. The major change is that there can be several robots in the world at once but each robot has only a single camera for vision. The camera is pointed straight ahead.  To see to the side, a robot must turn first.  Previously Karel had three cameras and only a single robot named Karel could exist. Each robot in a world has a different name. 

Chapter Two  PRIMITIVE INSTRUCTIONS AND SIMPLE PROCEDURES

One change (from first to second edition of Karel the Robot and retained in this work) is very subtle and might be overlooked—the text used to say, "To avoid damaging himself, Karel will not move forward if he sees a wall section or boundary wall between himself and the corner the he would move toward.  Instead, Karel executes a move instruction in this situation by turning himself off."

We now say, "To avoid damage, Karel will not move forward if it sees a wall section or boundary wall between its current location and the corner to which it would move.  Instead, Karel turns itself off." 

The first statement implied that Karel executed a move but did it differently that it was done when the front is clear.  The second statement says that Karel does not execute the move but turns off instead.  Similar changes are found for pickBeeper and putBeeper.

Karel no longer memorizes a program.  Syntax and lexical checking is done either by the factory or by the Helicopter pilot.  If the program is free of these kinds of errors, Karel is read the program.  The idea of reading fits better with the dictionary of new instructions presented in Chapter Three. 

This chapter is very similar to the 2ed.  However, we introduce the class construct for binding all of the instructions together into a whole.  The class of the most primitive robots is ur_Robot.  The language is case-sensitive, by the way.  Robots in class ur_Robot have only five capabilities as detailed on page 10 of the text.  They have no sensory capability at all.  This will be introduced in Chapter 4 in the derived class Robot. 

The syntax of Karel++ is very close to that of C++ and Java--much closer than the original was to Pascal.  In particular, we require parentheses for instruction invocations, even though we won't ever have parameters.  We also need to create a Robot explicitly.  The creation statement (declaration/definition) belongs inside of the main task block (or inside some instruction definition).  Note that the task block is uniformly referred to in the text as the "main task block" to ease the transition to C++ and Java where it is called main. 

We also use a style in which braces { } always line up either horizontally or vertically. 

The Turn-On Button is gone.  (from 1ed) 

As in 2ed we discuss the idea of tracing execution along with simulation. In our minds, there is a subtle difference between the two.  We refer to tracing as a means of stepping through code just as Karel would.  We refer to simulating as stepping through the code in the context of a particular world.  Section 2.6.1 has an annotated program that simulates in exacting detail what occurs in Karel's world as the program is executed.

In Section 2.8 we provide code with examples of each of the four types of errors discussed as in 2ed.

In Chapter 2 we develop a rather elaborate myth about what is going on in the Robot world.  It consists of a robot factory, a helicopter pilot, and a satelite.  The myth is there to make the following points clearer to students. 

a) A class is used to generate objects (robots) like a factory.  There can be many of the same kind. 

b) Most computers have only a single CPU.  Therefore only a single object (robot) can be active at a time.  If students get the idea that robots can move simultaneously then they won't be prepared for what they will find in C++.  Java does have threads, however, so multiple simultaneously active object is more realistic there. 

c)  Objects need to be initialized.  This is one of the main jobs of the helicopter pilot via the delivery spec.

d)  The main task block is different from the member functions/methods of the classes.  In C++ it is not a part of a class.  In Java it is a "static" method of some class, but still not "part of an object".  The pilot handles this task also. 

The helicopter pilot is responsible for main.  The robots are responsible for their own instructions.  Robots respond to instructions from outside--the pilot or another robot. 

Chapter Three  EXTENDING THE ROBOT VOCABULARY

The idea of boxing a program to verify syntactical legality is gone from the work.  It was very nice, but is too complicated with the new syntax. Sorry. 

In Section 3.5 we discuss an annotated program and a detailed discussion to aid students in tracing Karel's execution of new instructions.  One change from the first edition is that a Robot is read a program instead of memorizing the program.  In these first sections we explain that when a robot is read an instruction that is not part of the built-in set, it looks up the definition of the new instruction in its list of dictionary entries and performs the actions in the definition of the new instruction.  This parallels very nicely to the way we read a book and look up words we do not understand.  It also parallels how looking up one word can lead to looking up additional words and how we always return to the place we were reading to continue.

You need to emphasize that just as we remember where we were reading when we look up a word, a robot remembers where it is in the reading (execution) of the program and eventually (though not always directly) returns to the place, or as stated in the book, the focus, where it was reading before looking up the definition of the new instruction.

Section 3.8 is is carried from 2ed.  The first edition presented stepwise refinement as the only tool to use in the design of new instructions.  This edition adds new tools.  Some are in this section.  The original discussion of stepwise refined has been recast into a question/answer format to try and convey how we think about designing a program with new instructions. The actual program developed through this process is identical to the one in the first edition.

We have kept George Polya's model for problem solving from 2ed.  It is very useful when combined with the new ideas.  Part Six of this manual has a brief discussion of our version of Polya's model for problem solving.

The design tree of the second edition has been dropped here as it is more appropriate to procedural programming than to object oriented programming.  Stepwise refinement is used at the level of single instructions.  Designing one instruction often leads to writing of others, but these others don't affect the overall robot capabilities. 

Stepwise refinement begins with a plan that is analyzed and discarded.  We want to show the students that our first plan may not always be the best and must be analyzed carefully before accepting it.  The first plan is not in the original edition.  In the discussion, implementing means programming.  Some of the later discussions are very brief.  This is intentional and provides a place where you can engage your class in a question/answer discussion about the ideas presented.

The guidelines concerning the writing of robot programs that are easily read, easily debugged, and easily modified are stated, restated and emphasized.  The idea of identifying reusable new instructions is presented.  To emphasize these points we included a program without new instructions that accomplishes the task presented in the design tree and vertical slicing discussion.  We ask the students to think about having to modify this program or find a bug—there is an intent error in the program.

Robot teams and especially choreographers were introduced here to get to real object-orientation, with several interacting objects.  Without choreographers it is somewhat artificial because of the single CPU model.  With choreographers we can get interleaving of robot actions rather than one completing its task before the next begins.  High level OOP design involves selecting the right kinds of objects and the instructions with which they will interact.  Then stepwise refinement is used to design these instructions. 

Therefore when a complex task is encountered, the first job is to discover what robots will be needed and what their basic tasks will be. 

Chapter Four  CONDITIONALLY EXECUTING INSTRUCTIONS

This chapter presents several ideas and continues the question/answer method to demonstrate how we think about using conditional instructions.  The turnAroundOnlyIfBlocked instruction development has been replaced by a discussion using an instruction called faceNorthIfFacingSouth.  The discussion for the faceNorth instruction presents two different methods to solve the problem. 


Note that Robots now have only 8 predicates (conditions that can be tested) instead of 18 of the original. Usage of the not operator (!) gives 8 more.  The remaining two need to be built: rightIsClear and leftIsClear.  This is because the robots no longer have three cameras--only one and it is pointed straight ahead.  These new capabilities are features of a new class Robot, derived from ur_Robot.  A Robot is roughly equivalent to Pattis' original (except for the side cameras). 

A section has been added that discusses making more complex tests with the conditional instructions given Karel's lack of the conventional logical AND and OR operators. Note that robots do have a NOT instruction, represented by ! as in Java and C++. 

Each IF statement and each IF/ELSE statement requires a block for each statement part.  It is syntactically illegal to use a single statement.  This avoids the dangling else problem of C++ and Java.  You will need to take this up when you bridge to one of those languages.  Many programmers use blocks as a matter of course in any case. 

We retain the decision map, that can help guide the novice through the process of deciding when to use a conditional instruction and which one to use.  The decision map is discussed in detail in Part Seven of this manual.

Several reviewers suggested adding code examples for all of the transformations.  Those have been included.

One more note—from time to time we discuss the Lost Beeper Mine problem.  That problem is not in the book;  it is in this book.  The problem is not complex, just big.  Your simulator may or may not allow a world that is big enough to accommodate the problem.  We left the problem out of the book so you can have a chance to modify it in any way to make it suitable for your class.  More on this problem can be found in Part Eight of this manual.

Chapter Five  INSTRUCTIONS THAT REPEAT

Material for this chapter includes a four step process for building WHILE loops to aid novices in constructing correct loops.  The fence post problem is discussed and an example is developed.  Nesting is discussed with both a good and a bad example.  The question and answer pattern is used again and this time our plan has an error.  This planning error results in an intent error in our program.  We eventually find that a problem exists and we revisit the plan to find out where we went wrong.

The room escape problem was dropped from this version as it is more procedure oriented than object oriented.  It was replaced with a more OOP centered problem.  The escape problem was moved to the exercises however. (Problem 6 of Chapter 5).

A section concerning reasoning about loops introduces the idea of the loop invariant which fits in nicely with the discussion concerning large programs and beyond the horizon situations that was in the first edition.

Finally we bring back a complete version of the decision map that helps novices choose which control structure to use. 

Chapter Six  ADVANCED TECHNIQUES FOR KAREL

Most of the material in the first and second edition is here.  We begin with recursion recursion. There is a bit more here than was in 2ed as there is a section on tail recursion and the relationship between loops and recursion. Your simulator may or may not allow recursion.  Even if it does not, the discussion is clear and should be very helpful to you if you are going to do recursion later on in C++, Java, or another language. Pattis' original sections on doing arithmetic were shortened a bit and a section was added on doing arithmetic numerically with beepers. It shows a use of cooperating teams.  We close with an introduction to polymorphism. 

Part Two:  Overview and Thoughts

Chapter One

Our goal in this chapter is to introduce the students to Robots and their world.  There is no programming in this chapter.  The only problem solving that can easily be done is asking students to describe the location of Robots, some beepers, and some wall segments.

1.1  The Robot World

The world is flat—sometimes— unless we stand it upright so Robots can climb some steps or a mountain.  Some students have a very difficult time with the idea of an up direction when the world is flat.  We have encountered this confusion in junior high and high school students as well as undergraduates.  We think it is best to discuss this "transformation" of the world now.  One way that we do it is to take a flat piece of paper on the desk and, as a group mark it north, east, south, west.  Then tape the paper to the board and mark it up, right, down, and left.  It is simple but seems to help.

We have added the idea of remembering that avenues run north and south by the visual cue of the pointing of the letter "A" northward and the letter "v" southward.

We have added the idea of relative location as well as absolute location (street/avenue addresses).  You can use Figure 1-4 to expand on this idea.  We  found early on that using an absolute address lead some students to solve problems in later chapters in absolute terms for the sample world given in the problem statement.  We have seen new instruction names such as moveFrom_4thStreetTo_14thStreet when what was needed was an instruction called move_10Blocks. The idea of using relative location for Robots and the objects in the world seemed to parallel the idea of writing general instructions.

Concerning beepers, there can be an infinite number of beepers in a pile.  We mention this to you now because a problem in Chapter 5 uses this situation.  If you have written your own simulator (we have met several teachers that have) and are wondering how to code  an infinite number of beepers, try using -1.  Your simulator might have an integer overflow error but it will never have zero beepers.

There can also be several robots in the world simultaneously.  Each robot will have a name.  Not all robots are named Karel, though we usually use that name when there is only one robot.

1.2  Robot Capabilities

This is fairly straightforward.  We don't use the testing capabilities until Chapter 4 so you may want to touch them lightly here and save the details for later.

1.3  Tasks and Situations

At the request of reviewers, we have included Figure 1-4  that shows six different worlds as initial situations and briefly states a robot named Karel's task for each.  If you want to include some problem solving discussions in the course, you can ask students to make some assumptions about each world and the task it presents.  Making such assumptions is part of the redefining of the problem that is part of the problem solving process.  It is likely that your students will have no assumptions to make at this point.  That is OK.  Some may offer assumptions that Karel can move or can pick up a beeper.  You need to point out that these are not assumptions (because these are facts about the robot).  As an example, in Figure 1-4A it might be assumed by the student that Karel has no beepers.  This is OK, but does it have any bearing on the problem?

What about Figure D?  Does Karel have to pick the beeper?  There is nothing in the task that indicates this must be done.  If Karel does pick the beeper, is that an error?  We will let you decide the answer to this question.  Consider it carefully because similar situations will occur later.  Whatever you decide, be consistent throughout the course.

Chapter Two

This chapter introduces the students to programming the robot.   We show the students how to move and turn a robot and how to handle beepers. The need for the turnOff instruction is explained and we show a complete program for the first time.  The execution of this program is explained and the form of a robot program is explained.  Error shutoff and programming errors are discussed.

2.1  Changing Positions

Move is discussed and the idea of an error is introduced.  This is changed as explained in Part One above.  If you have not taught with Karel before, it does not matter, but die-hard robot fans should check the new description of move carefully.  If a robot attempts to move when its front is blocked it no longer executes the move by turning off.  It executes an error shutoff instead of a move.

2.2  Turning in Place

Turnleft is discussed and there is little change in this edition.

It is important when teaching both the move and turnLeft instructions that you emphasize where a robot must be.  You must stress that a robot is always on a corner or intersection and always facing one of the four directions.  Having experience with students ranging from junior high through graduate students and even school teachers, it helps to use visual aids.  In lecture, we have been known to play Robot and use chairs for walls and soda cans for beepers.

2.3  Finishing a Task

This is the same as the first edition.

2.4  Handling Beepers

Stress that they are on the same corner as the robot; the robot cannot reach over to an adjacent corner to pick a beeper.  Also stress that beepers do not block a robot's movement or turning.

2.5        Robot Descriptions

This is the introduction of the class concept.  A class describes the capabilities of a type of robot.

2.6  A Complete Program

This introduces the students to a complete program with the required reserved words and punctuation. 

You want to stress that there are few problems in programming that have only one correct solution.  Frequently there are many solutions to a problem and the goodness or badness of the solution is often subject to debate. Encourage these debates!

2.6.1  Executing a Program

The ideas of simulation and tracing are presented and an annotated program is included to walk the student though the tracing of a robot's execution of the program. For reinforcement, we suggest that you present a new world and a new task, ask for suggestions of a program to solve the task, write the program, and trace its execution.

2.6.2  The Form of Robot Program

This section presents the grammar rules for the robot programming language.  There are several kinds of things:  punctuation marks, robot descriptions, tasks, delivery specifications, instructions, messages, delimiters, and reserved words.  These are discussed in detail.

2.7  Error Shutoffs

Error shutoffs are discussed, justified and the three situations that can cause them are enumerated.    The absence of a turnOff instruction is discussed here.  There is a difference between the first edition and some of the simulators being used.  The first edition stated that a program without a turnOff instruction caused an error shutoff.  We know of one simulator at least that reports the missing turnOff prior to getting to the execution mode.  We now state that a missing turnOff results in reporting an error.  Please categorize this error appropriately for the simulator which you are using.

2.8  Programming Errors

At the request of reviewers, we have included examples of each of the programming errors discussed.  Some of these are annotated.  The discussion of an intent error includes an initial situation and a program that can be traced to find the error.  The last paragraph is very important and must emphasized now and later on as the problems become more complex.

2.8.1  Bugs and Debugging

This presents the idea of bugs.  We prefer to call them errors and would like to create the term deerroring but this sounds like another animal (deerroring).  There are some new ideas in Chapter Three that can help students reduce the number of errors.  One of these is stressing the need to plan and analyze thoroughly before implementing (keying in the program).  Many of our students (especially the hackers) feel they think best at the keyboard.  This attitude is just plain wrong.  For a novice such an attitude might be avoided if we begin stressing now the idea of, "Read in English, Think in English, Discuss in English, Plan in English, then, and only then, Program in the robot programming language."

Chapter Three

This chapter introduces the students to the new instruction mechanism and presents some ideas for using new instructions to plan implement and test robot programs.

3.1  Creating a More Natural Programming Language

This section sets up the need for new classes and instructions.  Ask your students to refer to the problems done in Chapter Two to identify any new instructions in addition to turnRight that would have been helpful.  Also, see part 4 of this guide. 

3.2        A Mechanism that Defines New Classes of Robots

This gives the syntax of a class and also explains its purpose.

3.3  Defining New Instructions

This is explains the structure of a new instruction definition.  Because we do no know about structured statements, the definitions are very limited. 

If you are using a simulator that has a text editor, you might find it helpful to stress to your students that they should type both delimiters { and } with several blank lines at the same time.  This will help them avoid looking for the "mismatched END" error that occurs so often with novices.   Part Four of this manual offers some hints for using text editors to write Robot programs.  This is a good time to stress the indenting of programs.  Feel free to use the format in the book as a good example if you like it or as a bad example if you don't.  The reviewers had very differing ideas about format;  it was obvious that no one style would suit everyone.  If our style of indenting offends you, we apologize.  Note that the style in this guide is slightly different from that in the book.  It saves a few lines without being less readable. 

You need to stress the following about instruction blocks:  1) a Robot treats an instruction block as a single instruction and 2) the Robot must execute every instruction within the instruction block before the program is finished unless an error shutoff or a turnOff is executed.  Caveat:  This will change when we introduce the return instruction in Chapter 4. 

3.4  The Meaning and Correctness of New Instructions

This chapter bring up a major point concerning the difference between "what we say and what we mean." In this case it is the difference between what we write as the definition of the new instruction and what we name the new instruction.  Strive to stamp out any idea your students might have about Karel or the computer on which Karel is running having any awareness of what is occurring.

3.5  Defining New Instructions in a Program

This section presents a complete program with new instruction definitions.  They are annotated to help students trace Karel's execution of the program.  Use the idea of looking up a word in a dictionary to explain how this works.  This program requires a robot to look up the definition of climbStair which then requires a robot to look up another definition of turnRight. 

3.6  Modifying Inherited Instructions

This gives an introduction to a topic that might be surprising to students--we can redefine an inherited instruction.  The new robots will use the new instruction.  The old robots will continue to use the original.  It all depends on which class they belong to. 

3.7 An Ungrammatical Program

This section explains the consequences of making various kinds of syntax errors. 

3.8  Tools for Designing and Writing Karel Programs

This is a long section that presents several methods for using new instructions.  Polya's  problem solving model is briefly introduced here.  We kept it brief because Polya's model is not the topic of concern.  Feel free to expand as you see fit.  It can only enhance the material. Part Six of this manual discusses our version of Polya's model for problem solving.  We also introduce the idea that programs must be easy to read, debug, and modify to perform a slightly different task.  This idea is very important and must be stressed over and over again.  Some of your hackers (and colleagues) will argue that speed of execution or shortest programs are important.  They are, but in our view, only after these three criteria are met!

3.8.1 through 3.8.4  Stepwise Refinement—a Technique for Planning, Implementing, and Analyzing Robot Programs

This follows almost the same path through the planning process as the first edition.  We have cast it into Polya's model and have added a question/answer format to try and show to beginners how we use stepwise refinement.  The only real difference between this discussion and the original is that we first present a plan for solving the program that is analyzed and discarded in favor of a different plan (which is the same as the one in the first edition).

Emphasis should be on thinking, discussing, planning, and analyzing at each step of the way.  Point out that most of the work should be mental and on paper.  The total time spent at the keyboard should be greatly reduced if this is done carefully and thoughtfully!

3.9  Advantages of Using New Instructions

This presents the ideas that using new instructions combined with stepwise refinement usually leads to programs that are easy to read and can help reduce the time spent fixing errors.  Programs written when this two framework is properly applied are usually quite easy to modify as shown in Section 3.9.2.

Section 3.9.3 remakes the points about program style and presents a solution to the problem using only primitive instructions.  There is an error in this code:   Karel executes three turnlefts after the last putBeeper instruction instead of just two.

3.10  Writing Understandable Programs

This section restates the idea of using good names for new instructions. We strongly urge the use of verbose names.

3.11      Robot Teams

This version of the work permits several robots to coexist--with the purpose of cooperating in a problem solution.  It is easy to get lots of robots working, but harder to interleave their work.  The main technique for interleaving is a choreographer that directs the operations of other robots.  In effect one robot behaves like the helicopter pilot with respect to other robots. 

3.12      Object-Oriented Design

This introduces the topic by examining the various robots (objects) that might cooperate in the solution of a large problem.  Overall design is not a decomposition of a complex OPERATION or process into sub-processes.  Instead it is the discovery of the ACTORS that can participate in the solution.  These actors are given (simple) tasks.  This means that when you get to decomposing procedures you are already working with smaller units. 

Chapter Four

This chapter introduces the conditional instructions IF and IF/ELSE.  The idea of a test that evaluates to either true or false is introduced.  Nesting conditionals is presented, some transformations are explained for simplifying code.  Note that there is no dangling else in the Robot programming language. 

4.1  The IF Instruction

This section presents the form of the IF instruction, discusses the <test>, and the THEN clause which must be a block in braces.


4.2  The Conditions Robots Can Test

The 8 conditions that Robots can test are listed.  The not operator is also introduced here. All is introduced via a new class Robot. 

4.2.1 Writing New Predicates

This is new to this version.  A predicate is similar to an instruction except that it returns a Boolean value (true or false).  The return statement is introduced as well.  Only predicates have return statements.  They can be used to effect short circuit evaluation of AND and OR constructs.    Note that return causes immediate termination of the predicate in which it appears. 

4.3  Simple Examples of the IF Instruction

Three examples are developed in this section and checking the correctness of the IF is explained.

4.3.1  The harvestOneRow Instruction

The harvesting problem from Chapter Three is revisited.  This time the field is missing some beepers.  The rationale for pickBeeperIfPresent is explained and the new instruction is developed using an IF instruction.

4.3.2  The faceNorthIfFacingSouth Instruction

A mythical problem called the Lost Beeper Mine is presented.  This problem is used as a recurrent framework for examples.  There is no such problem in the book.  It is at the end of this document in Part Eight.   Using the question/answer format, a plan is developed and analyzed and the new instruction written.  Again we use this pattern to try and show the novice how we think about using the IF instruction.

4.3.3  The faceNorth Instruction

Again we use the Lost Beeper Mine problem to generate the need for a new instruction.  The question/answer format is used to plan and analyze two completely different new instructions to solve the problem.

4.3.4  Determining the Correctness of the IF Instruction

Spend some time here.  It should help clear up any misconceptions your students might have concerning how a robot executes the IF instruction. It will be helpful when we add the ELSE clause.

4.4  The IF/ELSE Instruction

This section presents the form of the IF/ELSE instruction in terms of a hurdle race.

4.5  Nested IF Instructions

The idea of nesting is introduced and explained in terms of a beeper replanting problem.  The nested IF's are carefully discussed to show how a robot executes the instructions.  Again, we suggest that you spend some time on this part of the section.  We also suggest using a new instruction to "hide" the nested IF thus making the new instruction easier to read. 

Beginners often write something like

if( someTest() )
{   return true;
}
else
{   return false;
}

Show them that this is equivalent to

return someTest();

Similarly for a negated test. 

4.6  More Complex Tests

The Robot programming language lacks the AND and OR operator for making more complex tests.  This discussion returns to the Lost Beeper Mine and  shows a way to "simulate" the AND operator.  You may want to ask your students how to "simulate" the OR operator (put the disjunct in an ELSE clause).  AND and OR were purposely omitted to permit these discussions and a thorough examination of the ideas. 

4.7  When to use an IF Instruction

This section presents half of a paper tool we call the decision map.  The decision map is used after the plan is thoroughly developed and a student is trying to figure out which piece of the robot programming language to use.  Novices frequently say something like this, "I understand the syntax of the IF and how it works, but when do I use it?"  If a beginner has done a good job of planning, the decision map can help answer this question.  The map asks questions about what a robot needs to do and directs them along a series of branches until a particular language construct is reached.  You might want to look at the entire map which is printed at the end of Chapter Five.

4.8  Transformations for Simplifying IF Instructions

This section presents four transformations and code examples of the transformations.  Code such as this is seldom written on purpose.  It usually originates when students start fixing bugs.  They eventually get the program to run correctly but they are so involved in the code that they lose sight of the style issues.  Time spent here is will spent as the problems get more complex.

Note:  Some instructors might like to introduce recursion at this point, before iteration.  If there is interest in this I would be willing to produce a supplementary section here and publish it on the internet. 

Chapter Five

This chapter presents the LOOP and the WHILE loops.  The LOOP is only a small part of the chapter.  We spend most of our time on the WHILE loop.  Careful work with the sections on the four step process, errors to avoid, and the discussion of the loop invariant will be very useful for your students, especially those that will continue to take additional programming and computer science courses in the future.


5.1  The LOOP Instruction

This section explains the form and execution of the LOOP instruction within the context of the new instructions, turnRight and harvestOneRow (from Chapter Three). 

5.2  The WHILE Instruction

This section presents a need for the WHILE instruction, explains the form, and provides a four step process for building WHILE loops.

5.2.1  Why WHILE is Needed

The example of (a robot named) Karel having to walk forward to find a lone beeper somewhere directly ahead is presented.  Remember that the robot world is infinite to the east and north (theoretically) so an ITERATE will not always work, no matter how big the chosen number of repetitions.

5.2.2  The Form of the WHILE Instruction

The form of the WHILE instruction is shown in this section.  A robot's execution of the WHILE loop is also explained.  Careful attention to this section will pay off very soon.

5.2.3  Building a WHILE Loop - the Four Step Process

This section offers a guideline for building a WHILE loop.  You must emphasize that this works only if the planning has been thorough and careful.  Successfully building a WHILE loop requires that the students know exactly what a robot must do.

5.2.4  A More Interesting Problem

Using the question/answer format and the four step process we write another new instruction that uses a WHILE loop.  This instruction will be used for several sections as we modify the task which the robot must perform.  You can emphasize that our new instruction definitions must be easy to modify so they will work in an ever changing world.

5.3  Errors to Avoid with WHILE Loops

Two different errors and a common misconception are discussed in this section.

5.3.1  The Fence Post Problem

This problem is defined and then presented in a slightly modified version of the world used in Section 5.2.4.

5.3.2  Infinite Execution

The problem of infinite execution is explained in this section and some advice is offered for planning the body of WHILE loops.

5.3.3  When the Test of a WHILE is Checked

This section discusses a beginner/novice misconception that the test of the WHILE loop is continually checked as Karel executes the body of the WHILE loop.  This discussion provides a nice transition to the next section on nesting.

5.4  Nested WHILE Loops

This section examines a good example and a bad example of nesting WHILE loops.  The bad example is long and detailed but worth the time. It provides some good insight to the debugging process as well as how to carefully plan your loops.

5.4.1  A Good Example of Nesting

The question/answer format is used to build a new instruction that uses nested WHILE loops to good advantage.  We also show a better style of coding that "hides" the nested loop.  We recommend the style of hiding the nested loop justifying because, in our judgment, it is easier to read.

5.4.2  A Bad Example of Nesting

This section builds another new instruction using nested WHILE loops.  Our reasoning is faulty in several places and this leads us astray.  One error in our reasoning is assuming that a beeper is always in a corner of the room.  Using this implied assumption we go off on the wrong track.  The question/answer format works well here as it allows us to revisit our reasoning and see where the error was.  This is a long discussion but it is worth taking the time to go through it with your students to help prevent their making similar errors.

5.5  WHILE and IF Instructions

This section presents some common errors made by novice programmers when combining  these two instructions.

5.6  Reasoning about Loops

This is section was new in 2ed and retained here.  It restates the four step process and the informal way to reason about the correctness of WHILE loops.  Then a discussion about loop invariants is presented.  For simplification (from both the teacher's and the beginner/novice student's points of view) we have limited the definition of invariant to be, "an assertion which is true after each iteration of the loop."  You may wish to expand this, as is typically done, to include the state immediately before and after the loop, but we feel this limited definition is better for the novice crowd.  This section explains what we mean when we say we want to consider something that is "interesting" about the loop.  The entire discussion is a good prelude to the next section.

5.7  A Large Program Written by Stepwise Refinement

This section is new.  The problem has a more object-oriented flavor than the original. It opens up possibilities of robot teams in the solution.  It is a good discussion about building programs, making assumptions, and testing our programs.  This section is time well spent.

5.8  When to Use a Repeating Instruction

This is a continuation of the decision map tool introduced in Section 4.7.  First we revisit the original map, then we add the right side for repeating instructions and finally show the entire map.  Again, this is designed for beginners/novices that are having trouble "seeing" how to use these structures.

Chapter Six

This will be brief.  Few teachers use this chapter for many reasons.  There is some good stuff here.  We urge you to consider covering some or all of the topics.

6.1  Recursion

This was a completely new section in the 2nd edition.  The new Karel++ simulator developed at Carnegie Mellon, allows recursion.  We cannot speak for any other version.  Regardless, we feel that this is a good discussion about recursion and will benefit those students that are going to take additional computer science courses.  For them, it is worth covering, even if your simulator doesn't allow for recursion.  Some problems are extremely awkward without recursion and very natural with it. 

6.2  More on Recursion

This is new and gives a more complete treatment--similar to the four step analysis of loops. 

6.3  Tail Recursion and Looping

The relationship between the two is explained. 

6.4  Going Formal

A formal definition of WHILE is given in terms of recursion.  Hopefully this will elucidate both recursion and WHILE loops. 

6.5  Searching

This section is the same as in the first edition.

6.6  Doing Arithmetic

This section is the quite different from the first and second editions.  It treats arithmetic numerically rather than positionally.  It permits teams of robots to work together.  The original was also very valuable, however.  Get a copy of one of the earlier editions to see what can be done.  We moved some of the old material to the exercises in this version.

6.7        Polymorphism--Why Write Many Programs When One Will Do?

This is the barest introduction only, and requires some new syntax.  It introduces aliases (like pointers) for robots.  This can be used as a bridge--especially if you are going to teach Java next. 

WHAT NEXT

If your goal in teaching Karel++ was to introduce C++ or Java, you will now need to bridge to another book.  The early topics you will need to cover are:

The function main.

Objects (Robots).

Non-objects like int, float (beepers, walls...).

Variables, assignment, and explicit state. Consider introducing member variables rather than globals first. 

Parameters.

The dangling else problem.

Statements rather than blocks as bodies of IF and WHILE.

In Java the lack of the :: operator and the need to include instruction bodies within the class definition. 

In C++ you will eventually need to introduce free functions.  I would avoid this as long as possible myself.