Updated March 8, 2005
Karel the Robot was originally written by Richard Pattis (Wiley, 1981) to introduce Structured Programming in Pascal to novices. It has since gone through several fundamental changes. Jim Roberts and Mark Stehlik did a second edition (with Pattis's help) in 1995 and added much material about structured program decomposition. I then wrote Karel++ with the help of the other three in 1997 and changed the book quite fundamentally so as to introduce object oriented programming in C++ and Java to novices. Since then I've written Karel J. Robot with a pure Java syntax and have also added material on concurrency to the mix. Karel J. Robot is currently published only on the web at : http://csis.pace.edu/~bergin/KarelJava2ed/Karel++JavaEdition.html. There are a set of Java classes (jar file) that can be used as a simulator
All versions of Karel are built on a set of pedagogical patterns (http://csis.pace.edu/~bergin/PedPat1.3.html), the most important of which is Early Bird. This pattern suggests that to design a course, examine the material to be taught, find the most important idea and begin with that. The advantage of this approach is that the Professor will have maximum opportunity to reinforce the key idea of the course and the students will have maximum exposure to it. In the original Karel the Robot, the most important idea was the use of procedural abstraction. Therefore, Karel the Robot begins with procedures. Students see procedures before they see anything else in the language. The primitives of the language are built-in procedures (without parameters) and the students very rapidly (page 21)begin to write their own procedures to solve problems.
Another key pedagogical pattern in the Karel series is Consistent Metaphor. The idea of a robot is well known to students and is easily cast into either a procedural or an object oriented view. Robots behave consistently with the associated metaphor, making it easy for students to grasp what is going on in a program. This is a much easier view for novices than that of a Von Neumann architecture and the post office metaphor of memory and variables that is often fundamental to teaching novices (using the procedural paradigm, at least).
In Karel++ and in Karel J. Robot, dynamic polymorphism is the key idea, but this depends largely (in the book) on subclassing. Therefore classes and subclasses are treated as the first subjects of the book. The first class is seen on page 10 and students begin writing their own classes on page 26. In between these points the book emphasizes the difficulty of programming without class based encapsulation. Polymorphism itself is introduced quite a bit later, but all of the discussion and all of the exercises are designed so that dynamic polymorphism will be easy to grasp and will seem completely natural. This is done primarily through emphasizing the encapsulation of the classes and that the robots (objects) are in control of their own code, so that a robot never has action imposed upon it, but only responds to messages. This is the strength of the robot metaphor. Note that interfaces have been added to Karel J Robot and polymorphism also works via this more powerful and useful mechanism.
Superficially, Karel++ and Karel J. Robot look a lot like Karel the Robot, but this constant emphasis on writing new classes to achieve new functionality and the active and independent nature of the robot, along with the possibility of multiple robots, gives the student a very different idea about the nature of abstraction than did the original.
Additionally, the new manuscript has introduced concurrency into the robot world. This actually makes a lot of sense, as the single thread of execution in Karel the Robot and in Karel++ needed a lot of explanation. In Karel the Robot, the problem was sidestepped as there was only ever one robot. In Karel++, however, multiple robots were introduced to emphasize the essential nature of objects. Concurrency is difficult in C++, however, and so Karel++ was left single threaded, but it required a somewhat artificial metaphor to make it seem natural. This restriction was dropped in Karel J. Robot.
Interestingly, the idea of mutable state is only implicit in the Karel philosophy. Robots wander around in the world populated by walls and beepers, but do not themselves have the notion of private state. Thus, robot programming is almost functional in nature as the only state is implicit in the world. In a few places, Karel J Robot uses state to hold references to other objects so that it can delegate actions to them.
Robots in the Karel J. Robot world live in a world that consists of the first quadrant of the Cartesian plane, with streets running horizontally (East-West) at the integer points and avenues running vertically (like New York City). The world can have walls between the streets and avenues and there is also a wall bounding on the south and on the west. The robots cannot penetrate walls. The world also contains beepers that the robots can pick up and carry. Here is a figure of a south facing robot in a world with two beepers. Theoretically the world extends infinitely to the north and east, though the implementation restricts it to a very large, but not infinite, space. We show only a small section here.
The simulation speed can be set with the slider and the simulation run can be paused and resumed at will. The simulator itself is just a jar file, and was developed in Java 1.1, so it should run anywhere. The simulation is shown running on a Macintosh.
The simplest kind of robot is an ur_Robot (built-in -- UrRobot in Karel J Robot) that can move, turn-off, and turn left, pick up and put down beepers. It will automatically (error) halt if it tries to move through a wall or pick up a beeper when there is none available on its corner or tries to put one down when it possesses none. The first three chapters of the book work only with ur_Robots.
Another built in class is Robot, which extends ur_Robot, and can additionally sense its direction, whether it is facing a wall, whether it has beepers in its beeper-bag, and whether there are beepers on the current corner. Finally, a Robot can sense the presence of other Robots on the current corner. All other conditions and actions (turnRight,…) must be programmed by the user.
A robot world with a single Robot and no beepers can be proved to be equivalent to a Turing Machine, and so problems of arbitrary complexity can be solved in this simple graphic world. Pattis proved this in the early 1980's.
Karel the Robot and Karel++ each have six chapters. The first five of each are fundamental. The third chapter is encapsulation, the fourth is selection and the fifth is iteration. Chapter 6 has traditionally been treated as advanced material. The original had advanced procedural decomposition in this chapter and Karel++ discussed recursion and polymorphism here. The book is intended for the first two weeks or so of an introduction to computer science or an introduction to computer programming. Note that Karel J Robot has been extended to eight chapters. Chapter four now covers polymorphism, and Chapter 8 introduces multi-threaded execution.
When some version of Karel is used to introduce programming, its metaphor can be useful in the later part of the course as well. It is often advantageous recall some earlier robot problem when introducing a later problem. Often the structure of a Java or C++ program can be shown to be identical to that of some earlier robot program. A simple example is that searching a sentence for its period, is the same as a robot looking down a street for a beeper, checking each corner as it moves.
Additionally, recursive programs of a rather deep nature can be easily described in the robot world that would be very difficult to explain and grasp outside it. One is to write a recursive program that will do one task a certain number of times until a sentinel is reached and then do a different task the same number of times. All of this to be achieved without a state counting variable. The ability to render recursive programs visible is an additional advantage.
Karel J. Robot has a webs site with additional chapters in which appear a transition to Java, including state, and to concurrency. There are currently eight chapters in the published version of Karel J. Robot, and it is being expanded to a full course text, with three additional "proto" chapters available on the web.
Karel J. Robot handles concurrency in two different ways, one of which is currently experimental. The first is simply to adopt Java concurrency primitives (Monitors and Synchronized methods). This is actually a good model for showing novice students some of the difficulties with concurrent programming such as race conditions and deadlock. One Robot task for two robots is to race to the origin from different directions and to pick up a beeper at that spot and then halt. The only way the Robot can know that it is at the origin is by finding the beeper. However the first robot to the origin will remove the beeper from the corner and so the second won't find it and will therefore crash into the wall. I use this to introduce the idea of a race condition.
Another simple example is Dining Robots in which the robots eat and think, requiring the usual shared forks in order to eat. The robot philosophers can be seen to think and eat by the differences in their actions. The program can be written to show or to avoid deadlock. Here are four Philosopher Robots and the "beeper forks" that they need to eat. They will move into the center to eat once they get two forks and will move backwards to think once they replace their forks.
The second method of doing concurrency (web site only) is to use something like Communicating Sequential Processes (CSP) with a form of message passing between threads. This is a fundamentally safer and easier to understand methodology, but the current implementation and interface design is experimental and has not yet been proven. This framework uses the Strategy Pattern which is an elementary design pattern discussed in Design Patterns by Gamma, Helm, Johnson, and Vlissides (Addison-Wesley, 1995).
Karel J. Robot can be an effective way to introduce object-oriented programming to novices. Its pedagogy was carefully designed and its graphic nature is appealing to students. It uses an easily understood metaphor that is quite consistent overall.
One of the main advantages of the Karel philosophy, however, is that it gives the students simple versions of a large number of tools that enable sophisticated problem solving. Thus, Karel forms the first cycle of a Spiral teaching approach, and students will have the ability to successively deepen their knowledge of many topics while having the tools to build exploratory programs from the very beginning of the course. This early overview of the programming process and its reinforcement of the most important ideas is its chief goal and the reason for its continuing success.
Finally, this author believes that if students are to easily achieve a high degree of skill in object oriented programming, then their programming practice must NOT begin with the procedural paradigm. Everything in the Karel++ and Karel J. Robot philosophy is designed to avoid this trap. This is because the mind set of the object-oriented programmer is very different than that of the procedural programmer and that these mind sets clash. For an exploration of this idea, see "Why Procedural is the Wrong First Paradigm if OOP is the Goal" at: http://csis.pace.edu/~bergin/papers/Whynotproceduralfirst.html
The original version of the above was presented in Workshop 8 (Tools and Environments for Understanding Object-Oriented Concepts) at ECOOP 2000. The workshop was held on June 8, 2000, in Sophia Antipolis, France.
Last Modified: March 8, 2005