(Under revision -- may change frequently)
"May all your objects be small, and all your messages polymorphic."
This currenent version of Karel J Robot goes beyond the original Karel the Robot and even Karel++ in two ways. First it is much more Object-Oriented than Karel++. Second, it has additional material that moves the student from the Karel World to a richer universe of programming. For an instructor learning to be an object-oriented programmer while teaching, the fourth chapter is critical, including the optional section on linked lists. The first four chapters show something of the power of object-oriented thinking. Note that the IF statement has not yet been introduced or used and yet we can show various kinds of behavioral differences and even changes in behavior. We can even see a linked list implemented entirely without IF statements.
Throughout its history, from Richard Pattis' first edition to the current one, the authors have striven to make Karel as simple as possible while still teaching the essential idea of the time. The original was nearly perfectly designed to teach procedural programming using the key idea (procedures) by introducing them first among all the topics so that students have maximum exposure to them and maximum opportunity to gain skill in their use. The book was written at a time in which there was still some controversy as to whether it was good or even possible to teach procedures early. Rich showed that it was not only possible, but desirable to do so. This version takes the same approach to object-oriented (OO) programming. The key ideas here are encapsulation, message passing, and polymorphism. These three ideas are taught together from the very beginning of the book. The authors know that there is still some controversy about this as well: can/should we teach polymorphism early? The answer is yes, and Karel J. Robot shows how it can be done, without terminology overload. (For some thoughts and examples on the differences between procedural and object-oriented programming, see http://csis.pace.edu/~bergin/patterns/ppoop.html)
We did not go quite as far as this in Karel++ due to the nature of C++ which we were working towards at the time. It is rather difficult to get polymorphic action in C++ as you need both virtual methods and pointers. C++ is used more as a data encapsulation language (Abstract Data Types) than it is as a true OO language, though you can do OO there. Java, on the other hand, uses references ubiquitously for objects and only virtual methods (non-static ones, anyway -- static stuff is never polymorphic). So polymorphism and OO is natural in Java so we exploit it. Classes are not just Abstract Data Types. Polymorphism is the difference.
While we did not use the term Design Pattern, chapter four introduces five (at least) important, but elementary, design patterns that have proven to be both useful generally and also used within the Java libraries that we assume will be studied later. These are
| Pattern: | How Used Here: | Java Libraries: |
| Null Object | NullStrategy class | |
| Strategy | Strategy class | java.util.zip CRC32 |
| Decorator | StrategyDecorator class | Java I/O Libraries |
| Observer | RobotListener class | Listener Structure, Buttons... |
| Iterator | Enumeration (neighbors method of UrRobot) | Enumeration, Iterator, Collections |
Most of these are discussed in Design Patterns, by Gamma, Helm, Johnson, and Vlissides (Addison-Wesley), the original book on software patterns, though the treatment, along with a fuller treatment of object-orientation suitable for instructors, may be found in Design Patterns Explained, by Shalloway and Trott (Addison-Wesley). While we have not used the word "pattern" in the text, you may want to with your students after some period of study yourself. I sometimes describe the difference between naive and sophisticated object-oriented design as being precisely design patterns. Naive OO design looks for objects and hence classes at the level of nouns in the problem description. While this is a useful way to begin, it is design patterns that let us refine those initial attempts and create a truly usable, maintainable, and extendable program or system. We note for completeness, that the Swing libraries of Java are based on Model-View-Controller (MVC) architecture, which is a form of Observer. (For more on Strategy and Decorator see http://csis.pace.edu/~bergin/patterns/strategydecorator.html. For more on observer and MVC, see http://csis.pace.edu/~bergin/mvc/mvcgui.html and for the use of observers in Java Event handling, see http://csis.pace.edu/~bergin/Java/javaeventsummary.html.)
We have included these, not to present material on design patterns to the students, but because they are all generally useful and lead to good, maintainable, and extendable programs. They are "big ideas" that can be leveraged at other parts of the curriculum to teach other things. In particular, the StrategyDecorator makes it possible to do some interesting things early, but also makes the Java I/O libraries less opaque. Instead of looking on those libraries as a problem, think of them as embodying good design decisions that can and should be emulated.
Karel J. Robot's core (the first six or seven chapters) is intended for only the first few weeks of an introductory course. There are two optional sections there that should be attempted only with care. The first introduces linked lists of strategies using something like a null object (rather than the null value) to terminate lists naturally. This material is more advanced and may be difficult to grasp for novices in their second week. It is, however, the right way to build a list in the OO style, without pervasive IF tests for the end. The second optional section is there just for those instructors who prefer to teach recursion immediately after IF and before any discussion of iteration. This material is presented again, slightly differently, in Chapter 7.
Even before starting Karel J. Robot, you can spend a few days teaching ideas of objects by building metaphors that the students can rely on to guide their thinking. You can use Role Play exercises to show how objects interact with each other, send polymorphic messages, and enforce encapsulation. (See http://csis.pace.edu/~bergin/Java/RolePlay.html) You can try to solve some "design" problems at the nouns and verbs level, looking for "object candidates" in a problem statement. If you do this, you can depend less on terminology and much less on technical details. It can all feel very natural when based on good metaphor. Section 9.1 is actually an attempt to work on building such a metaphor, but this can come much earlier.(See http://csis.pace.edu/~bergin/Java/OOStory.html)
Karel J. Robot alone is probably not yet suitable for a complete course and would need to be supplemented with additional material. Be aware that many introductory text books are not especially compatible with this approach, as many treat object-orientation incorrectly (as an add-on to procedural programming), incompletely (giving to little attention to dynamic polymorphism), or late. There is evidence from industry as well as education that these strategies fail to develop the skills needed to be an object-oriented programmer in modern languages. Some suggestions about companion materials can be found below.
Karel J. Robot is best used with a teaching philosophy that admits Spiral teaching. In this style, you do not try to teach everything about any given topic at the first introduction. Instead, you teach enough to enable problem solving, knowing that you can return to the topic later at a deeper level showing more variations. So, while Karel J. Robot collects most of what it has to say about IF in a single chapter, that chapter does not discuss switch statements at all. Additionally, the chapter is intended to be covered relatively quickly (two hours, say, of class room time) permitting students to get started integrating the IF with other material (polymorphism, say). Note that a long chapter of a book that collects everything about IF in one place is usually pretty boring and does not permit interesting problems to be solved. The combination of IF and polymorphism is much richer, and you will soon take up iteration in another short chapter, so that you can solve really interesting problems.
Some of the ideas here are deep, but we have also striven hard for simplicity. In particular, we try to make each class very simple. We want each class as a whole, and each method in a class to be very simple. We want each object to have a single purpose: supply a single service that other objects can use. Complexity and sophistication comes from simple things used in combination, not from building complex things.
Karel J. Robot, like its predecessors does not try to introduce the complete language; Java in this case. We have been very careful to leave things out. However, Karel J. Robot is still a universal computing machine: a Turing Machine. Theoretically, any computational problem whatever can be solved using this system, though it is not especially convenient to to so in some ways. However, this has a distinct advantage if you want to teach students how to solve problems, and not just teach them the syntax of some language.
In particular, there is very little use of either assignment statements or of the built in data types in Java, such as int and char. We don't touch on integer arithmetic, for example, nor do we permit the programmer to ask a robot what its street number is, nor how many beepers it has in its beeper bag. To permit these things would lessen the pedagogical benefits of using Karel, not increase them. We shall explain below.
Note that in earlier versions of the Karel system we used a specialized application to simulate the robot behavior. This made it easy to control what students were able to do and not do. This time, however, we have used pure Java for the simulator. Therefore the instructor is free to introduce additional material as he or she chooses, such as integer valued fields within the robots. We firmly believe that it is a serious mistake to do so, however.
Fundamentally, Karel J. Robot, like its predecessors, is about problem solving, not about language syntax. We ask the students to program in a system with only a small but complete set of tools so that they can increase their mental capabilities in solving problems in a restricted world. At some level, every language has this characteristic, of course. In Karel J. Robot we just make the tool set as small as possible while teaching the essential problem solving concepts: Object-Oriented problem solving concepts, actually. Karel is actually more about thinking than programming.
We think that integer fields, and the associated integer arithmetic, is an especially dangerous tool to introduce early. For one thing, integers are not objects and so have nothing to tell you about object-oriented programming. Even Integer objects, being final, do not permit polymorphic programming; an essential lesson of the book. Moreover, many of the most interesting exercises in the book become trivial if the student has integer fields to work with. This doesn't help them to think deeply. On the other hand, many instructors are thoroughly familiar with int fields and so it seems natural to introduce them early. We strongly suggest that you do not, and that doing so actually gets in the way of student learning.
Polymorphism should not be thought of as a difficult topic. At base, it only means that the object sent a message determines what to do. Actually, it doesn't decide. It just does what its own class definition says it should do. In Java, as in most (not all) object oriented languages, objects get their type when they are created (new UrRobot(...) ) and that type can never change. Independent of this type is the type of reference variables used to point to objects. The rules are simple. The variable needs the same type or a superclass (or super interface) type of the object. It is the type of the object, NOT the type of the reference that determines what is done. That is pretty much the complete definition of polymorphism. In particular, if I say:
UrRobot karel = new Mile_Mover(...); ... karel.move();
then karel will move a mile, since move was overridden in Mile_Mover, even though the reference variable has type UrRobot.
To exploit and teach polymorphism does not depend on having students memorizing this definition, however. It appears nowhere in Karel J. Robot. But understanding it does depend on having lots of objects with interesting interactions, in which you can mostly forget about the actual type of the objects you point to and just use interface names to declare references. In addition to making polymorphism natural, it also makes the software flexible. In many ways Java interfaces are far superior to inheritance. If I give a parameter a class type, I am restricted in what I can pass to that method by the type of the class and its subclasses. If I use an interface, however, any class that implements the interface, though completely unrelated to others that also implement it, can be passed. For this to make sense, of course, the interface has to have some semantic content.
This need for having lots of interacting objects led us to introduce Strategy objects as defined by the Strategy interface. This is in addition to Robots, which are, at the time Strategy is introduced, the only other kind of object in the Karel World. But then Robots can interact in some ways with each other and with Strategies, and Strategies can interact with each other, etc.
Additionally, Chapter 4 shows how many uses of IF statements in procedural programs can be (should be) replaced by polymorphism in OO programs. We don't need to test things to switch back and forth between two behavioral states, and we should not. If we start to do so, then our programs will quickly become hard to maintain as these kinds of IF statements tend to be replicated throughout programs, wherever we need to distinguish between the states. Once they are replicated, program maintenance becomes a nightmare, since program updates require these IF statements to be revisited individually to see if they need change, and the tools we use typically give us no help in finding the points in the program that require change. Instead, the polymorphic OO way, captures the difference between the behaviors in an object (like a Strategy) and delegates all action to whichever object is current. We can add new behaviors by creating new classes and we can modify old behaviors by changing (or preferably extending) old classes.
The reason that Chapter 4 appears where it does is that polymorphism is more fundamental to OO than are IF statements. Therefore it is useful to teach it early so that students both become familiar with it and have maximum opportunity to learn, practice, and exploit it. If they first learn to solve all such problems with IF statements they will have almost no incentive to learn polymorphism since few students work on programs large enough, or long enough, for polymorphism to become essential. And by that time they will have ingrained habits that will inhibit their easy absorption of the OO way. While people with little OO experience often dispute this last claim, it is well recognized in the OO community and often used to explain the difficulty of, and length of time needed for, training good procedural programmers to become OO programmers. So Chapter 4 tries to short circuit this difficulty by starting students with a good grounding in polymorphic thinking before they begin solving problems with ad-hoc selection methods.
Another good reason for this chapter here is that it emphasizes programming with objects and object interactions. We write quite a few classes here and the classes are all simple. The objects, then, are simple as well and they interact. This is a good lesson about what real OO programs look like and gives the students additional practice with it. An OO program is a swarm of interacting objects. Like a swarm of bees. Not like Godzilla meets King Kong. It brings the three main ideas (encapsulation, message passing, and polymorphism) together and starts to build good thought habits with them. In your own programming and class preparation, I suggest the following. When you prepare code to show your students, find any if statements in it and see if you can find a way to remove them using polymorphism before you show it to your students. You can't always do this, and it will take you a while to get used to it. You can't do it if you are programming with (non-object) primitives like int. They aren't objects so can't behave behaviorally. The wrapper classes (Integer, Boolean...) can't either since they are final classes and so non-polymorphic. But if you program with interesting things (objects) then you can usually remove the if statements and you usually get a better program. (Another trick is to see if you can't make a class you are writing smaller and more "single purpose" by delegating some of its work to other objects.)
In particular, if you are writing GUI code, look for if statements in your button ... listeners. These can always be removed by creating one listener for each button. You will need to write more classes, unless you can parameterize the listeners, but that is a good thing and emphasizes the main point of OO programming.
Again, we admit that Chapter 4 introduces deep ideas and some complexity, we have tried to manage this by keeping each of the classes and methods very small. This is desirable in any case, but notice how even trivial classes can introduce deep and important ideas. For example, the LinkStrategy class (in the optional section) is almost completely trivial, and yet is the basis of a linked list--a deep idea. Combine this with the idea of a Null Object terminating the list and we have polymorphic behavior rather than testing for end. Each node in the list gets the same message. LinkStrategy nodes do something and pass it on. At the end is another strategy that just fails to pass it on without any test necessary.
Some may argue that we leave the program open to error without the test. It IS possible, for example to create a new MoveStrategy passing null for the parameter, rather than a real strategy. In this case, we maintain, the program is broken, and this flaw will appear on the first test, when we try to send null a message, though it refers to no object. The program should therefore be fixed, and we supply the NullStrategy for this purpose if there is no better choice. If you DO want to put the test for null into the constructor, what will it do when the user passes null? The program is broken, so you inform the user, of course, but do you do this with a message sent to System.out? But this is just exactly what the system will do without the IF when the exception is thrown. Is it good to protect the students from seeing the system provided effect of program errors: exceptions? Most likely not, since even if you try hard to protect them, they will see them eventually on their own and if you don't show them what to do, they will be puzzled. Better you show them what can occur and then what it means, and then what to do about it. In this case, replace the null with a NullObject. Replace the IF with polymorphism. It makes a better program anyway. After all, how many if statements do you typically need in a linked list built procedurally? Generally it is more than one and therfore introduces maintenance problems in a growing program.
Actually, there is one thing you can do with an IF in the above situation. When the user passes null, test for this and set the instance variable to a new NullStrategy instead of the passed value. You are, in effect, correcting a programmers mistake here. You should carefully consider whether this is a good idea and whether to teach it to novices, however. Most of the software I use thinks it is smarter than I am, and tries, on occasion, to do something "for" me. Unfortunately it is almost always wrong, and then I need to figure out how to make the thing do what I really wanted, rather than what its programmer thought I "must have" wanted. Formatting in word processors is a frequent villain in this regard, of course.
One of the reasons for using the design patterns we did was that they appear in the Java libraries as noted above. The Java I/O libraries are based on decorator. Each class in the library is designed to do only one task. So a FileReader is really only capable of connecting to a file and nothing else. To do more, you decorate it, perhaps with a BufferedReader, which is just a reader decorator.
Likewise the event structure of Java is based on observers. I chose method names in the manuscript to emphasize this, actually. An ActionListener is an observer of things like buttons and text fields. So this chapter teaches ideas that are useful in themselves, but also gets the student ready to better understand the Java libraries.
Java interfaces are a really good idea. An interface defines a type. You can declare variables of interface type. Any object that implements the interface can be assigned to the variable. An interface is actually the first Java code I show my students (during a Role Play exercise before we begin programming). Conceptually it is key to abstract thinking about programming, since it is completely free of implementation. In some ways UrRobot should be an interface, but is not. The reason is that I need to hide lots of implementation for UrRobot to make the graphic simulator work. Since it is a class, I can do the implementation of this rather than having students need to repeat it. Mostly we work through inheritance in Karel J. Robot, but actually in Java, polymorphism is even more powerful when done via interfaces than inheritance. Remember this when you move beyond Karel. A good Java style, in fact, is to have every parameter of every method be an interface type. You are then not restricted to any given hierarchy when choosing obects to pass to that method. For the same reason, fields benefit from having interface, rather than class, types. You get much more flexibility.
As proof of this, notice that, aside from naming, there is no difference between the Controller interface and the Strategy interface. The only difference is in intent. Yet we can cover these rather different ideas with the same structure. Likewise, our decorators and the opional LinkStrategy are identical in structure. This is alluded to in one of the exercises. We give different diagrams for the two ideas, but they are equivalent, as your best students will probably grasp immediately. In fact, the kind of linked list we build in the optional section can be fruitfully thought of as a nested structure, since we don't show any way to get access to the individual nodes. In this regard it is like a list in Scheme. If you use TeachScheme! before Karel J. Robot, you can exploit this, perhaps.
In the optional section on Linked Lists, the doIt method of the LinkStrategy calls doIt. The question arises whether this is recursion or not. I usually take the position that it is not. In this case doIt is a message to another object. By the principle of polymorphism we therefore don't know what code will be executed. It might be this same code, executed by another object, or it might be different code altogether. Indeed it must be different code eventually if the sequence of messages is to end. I usually only call it recursion if a method sends the same message to the same object (this). In reality this doesn't matter, since you need to guard against infinite execution in all circumstances anyway. Here we don't need an if to guard, since we just guarantee that eventually we execute code that doesn't try to pass on the message.
Here is the code I built for Chapter 4. Better yet, here is the code for the entire book (8 chapters).
I'd like to think that the book puts students on the road to becoming good object-oriented programmers, while giving them an interesting world in which to play and learn. But the instructor should have some idea about where this road leads. To program naturally in an OO way requires a different way of thinking than that of a typical C or Pascal programmer. Let me point out some of the characteristics.
We do not give "default" constructors to our robot classes. They have no meaning. A robot must be somewhere. In Java, you don't need default constructors as you do in C++ where there are interactions with arrays. Only supply them if you can provide sensible initializations of all instance variables. We generally prefer things to be explicitly stated by the programmer, rather than implicit.
In Chapter 4, where we introduce instance variables, note that we are very careful never to construct an object that has an unusable state. In particular, we initialize reference variables to null only when the constructors provide a better value, so that no object is ever created with this null value in place. Alternatively, we will initialize this variable with a Null Object (like a NullStrategy) which provides empty or default behavior. While our purpose here was to avoid if tests for null later, this has other benefits as well, such as simple but safe construction. Of course it IS possible for a user to pass null as a constructor parameter and defeat our careful plans. This is one situation in which a null test would be preferable in production code, but at this point we are trying to build the habit of supplying objects not null for parameters and have not mentioned the possiblity of passing null to the student. Our position on this would be that doing this breaks the program and it should be fixed. The NullPointerException that will be thrown will indicate the error and a NullStrategy or other Null Object can then be used instead of null to fix the problem.
Notice that we always give intial values to references and other variables we create. This is just a good habit. Don't assume the system will do the right thing. In Java it generally does, but you won't be programming in Java forever. Oddly, it actually slows down the virtual machine, but not enough to matter.
One of the teaching styles used in the book is Metaphor. In many cases a new topic is introduced via a metaphor that attempts to give the key features of the new idea in a familiar way. Care is taken to choose metaphors that aren't misleading, and to point out the limitations of metaphors we choose. For example, the term Observer (Chapter 4) can be misleading as the usual meaning isn't just what we actually build in Java. Therefore both the usual meaning and the actual meaning needed here are explained with a real-world example that we hope is meaningful to students. Generally this metaphor is given before the technical details. Robots themselves are an elaborate metaphor for objects, actually. And physical robots are a metaphor for our robots as well.
There are other teaching styles, however. One that we have seen to be effective is to introduce a new topic by showing how the currently known skills don't quite solve some new problem. They might almost do so, but not quite. In this teaching style, a new topic is introduced with an example and a solution is attempted. The solution can be shown to have flaws. The students and instructor can discuss the good and bad points of the proposed solution. Then the instructor can introduce some new material that improves the solution. Eugene Wallingford uses this technique frequently and effectively. By preparing some material ahead, you can do this too. For example, we have introduced some extra material on abstract classes, that is pointed to from the manuscript. You can actually use this to motivate abstract classes if you wish with just a bit of rearrangement of the material. We give it later than you would if you want to use it as an introduction and motivation. See the extra material here.
If you want to use this manuscript and its simulator in your own teaching, we ask that you have a few copies of the printed Karel ++ text available for your students -- say one for every three students. This will give them access to the exercises and will also serve to repay the authors and publisher for our efforts.
There has been a change in the language from its earliest version. The directions used to be an int. Now they are elements of a class: Direction. You still implement Directions (plural) but the direction parameter to a constructor has type Direction (singular). Its values are still North, South, East, and West. See the JavaDoc
Shalloway and Trott, Design Patterns Explained: A New Perspective on Object-Oriented Design, Addison-Wesley, 2002
Gamma, Helm, Johnson, and Vlissides, Design Patterns, Addison-Wesley, 1995
Hunt, Java for Practitioners, Springer, 1999
Fowler, Refactoring: Improving the Design of Existing Code, Addison-Wesley, 2000
Possible textbooks (unordered):
Objects First With Java : A Practical Introduction Using BlueJ (2nd Edition) by David Barnes, Michael Kolling, Prentice-Hall, 2004
Lewis and Loftus, Java Software Solutions, Addison-Wesley, 2002
Riley, The Object of Java, Addison-Wesley, 2003
Winder and Roberts, Developing Java Software, Wiley, 2000
Horstmann, VanCleave, Computing Concepts with Java Essentials, Wiley, 2002
Mercer, Computing Fundamentals with Java, Franklin Beedle, 2002
Some textbooks should not be considered. Some do objects too late. Some do Java GUI programming using procedural programming (lots of if statements in the listeners, rather than separate listeners -- or even hide the listeners altogether and just use if statements to dispatch or hide events.). Some authors have serious misconceptions about how objects and especially inheritance should be used. In particular, Circle is NOT a proper subclass of Point, and Cylinder is NOT a proper subclass of Circle. Don't use books that suggest these as examples.
Many people have the misconception that OO is all about Classes. It is not. It is about polymorphic run time dispatch. Many people have the misconception that OO is all about code reuse. It is not. It is all about piecemeal growth of programs. To write a big program, write a small program first and then grow the big one. To do this well requires that you use polymorphic techniques and design patterns. See the Refactoring book for more. You can design a sequence of exercises for your students that teach this, by the way. Early exercises yield parts of the solution of larger problems. Even better, have your students solve these problems in groups. Still better is to have them exchange early work for later extensions. There are additional suggestions about such things in the pedagogical patterns papers on Bergin's web site. See especially Active Learning (http://csis.pace.edu/~bergin/patterns/ActiveLearningV24.html), and Feedback (http://csis.pace.edu/~bergin/patterns/FeedbackPatterns.html).
More on Elementary Patterns, Pedagogical Patterns, and teaching and using Objects can be found on Bergin's home page: http://csis.pace.edu/~bergin. All of the papers pointed to above are directly linked from this home page.
You are encouraged to submit ideas on good teaching practice to the Pedagogical Patterns Project. The author will be happy to show you how good ideas are turned into patterns and then verified by the community as good practice. All pedagogical patterns (as other patterns) require an extensive peer review process before being accepted. All good ideas require an abstraction process to enhance usability by others in contexts beyond what any one user may envision. Thus good patterns are not specific to a certain time/place/course, but can be transferred.
Note. Bergin is the principle author of Karel J. Robot and made the key decisions on its form. The "we" above, usually means Bergin. However, the ideas presented are widely shared in the OO community and also in the Elementary Patterns Working Group and the Pedagogical Patterns Project. This is not Bergin's sole work, however, as it is built on a firm foundation begun by Rich Pattis and extended by Mark Stehlik and Jim Roberts. Pattis provided a key core for teaching procedures properly and simply and Stehlik and Roberts added nice pedagogy. Bergin's contribution has been to morph the concepts so they fairly and completely represent OO programming.
"As simple as possible, but no simpler."
Prior to publication this manuscript may undergo some changes. Some that are contemplated are listed here. The authors are open to suggestions here.
Some things are unlikely to be introduced or expanded here. Some of these are not germane to teaching object-oriented principles, though they are part of Java. Others would just take us too far afield.
Last Updated: February 18, 2005