Sunday, September 11, 2011

karel

Chapter 1
Introducing Karel the Robot


In the 1970s, a Stanford graduate student named Rich Pattis decided that it would be easier to teach the fundamentals of programming if students could somehow learn the basic ideas in a simple environment free from the complexities that characterize most programming languages. Drawing inspiration from the success of Seymour Papert’s LOGO project at MIT, Rich designed an introductory programming environment in which students teach a robot to solve simple problems. That robot was named Karel, after the Czech playwright Karel Capek, whose 1923 play R.U.R. (Rossum’s Universal Robots) gave the word robot to the English language.

Karel the Robot was quite a success. Karel was used in introductory computer science courses all across the country, to the point that Rich’s textbook sold well over 100,000 copies. Many generations of CS106A students learned how programming works by putting Karel through its paces. But nothing lasts forever. In the middle of the 1990s, the simulator we had been using for Karel the Robot stopped working. We were, however, soon able to get a version of Karel up and running in the Thetis interpreter we were using at the time. But then, a year ago, CS106A switched to Java, and Karel again vanished from the scene. For the last three quarters, the hole in the curriculum left by Karel’s departure has been competently filled by Nick Parlante’s Binky world, but it seems about time to bring Karel back. The new implementation of Karel is designed to be compatible with both Java and the Eclipse programming environment, which means that you’ll get to practice using the Eclipse editor and debugger from the very beginning of the course.

What is Karel?
Karel is a very simple robot living in a very simple world. By giving Karel a set of commands, you can direct it to perform certain tasks within its world. The process of specifying those commands is called programming. Initially, Karel understands only a very small number of predefined commands, but an important part of the programming process is teaching Karel new commands that extend its capabilities.

When you program Karel to perform a task, you must write out the necessary commands in a very precise way so that the robot can correctly interpret what you have told it to do. In particular, the programs you write must obey a set of syntactic rules that define what commands and language forms are legal. Taken together, the predefined commands and syntactic rules define the Karel programminlanguage. The Karel programming language is designed to be as similar as possible to Java so as to ease the transition to the language you will be using all quarter. Karel programs have much the same structure and involve the same fundamental elements as Java programs do. The critical difference is that Karel’s programming language is extremely small, in the sense that it has very few commands and rules. It is easy, for example, to teach the entire Karel language in just a couple of hours, which is precisely what we do in CS106A. At the end of that time, you will know everything that Karel can do and how to specify those actions in a program. The details are easy to master. Even so, you will discover that solving a problem can be extremely challenging. Problem solving is the essence of programming; the rules are just a minor concern along the way.

In sophisticated languages like Java, there are so many details that learning these details often becomes the focus of the course. When that happens, the much more critical issues of problem solving tend to get lost in the shuffle. By starting with Karel, you can concentrate on solving problems from the very beginning. And because Karel encourages imagination and creativity, you can have quite a lot of fun along the way.




Karel’s world
Karel’s world is defined by streets running horizontally (east-west) and avenues running vertically (north-south). The intersection of a street and an avenue is called a corner. Karel can only be positioned on corners and must be facing one of the four standard compass directions (north, south, east, west). A sample Karel world is shown below. Here Karel is located at the corner of 1st Street and 1st Avenue, facing east.








 




 
4

3

2

1

1         2          3         4          5          6

Several other components of Karel’s world can be seen in this example. The object in front of Karel is a beeper. As described in Rich Pattis’s book, beepers are “plastic cones which emit a quiet beeping noise. Karel can only detect a beeper if it is on the same corner. The solid lines in the diagram are walls. Walls serve as barriers within Karel’s world. Karel cannot walk through walls and must instead go around them. Karel’s world is always bounded by walls along the edges, but the world may have different dimensions depending on the specific problem Karel needs to solve.

What can Karel do?
When Karel is shipped from the factory, it responds to a very small set of commands:

move()       Asks Karel to move forward one block. Karel cannot respond to a
move() command if there is a wall blocking its way.
turnLeft()    Asks Karel to rotate 90 degrees to the left (counterclockwise).
pickBeeper() Asks Karel to pick up one beeper from a corner and stores the beeper in its beeper bag, which can hold an infinite number of beepers. Karel cannot respond to a pickBeeper() command unless there is a beeper on the current corner.
putBeeper()   Asks Karel to take a beeper from its beeper bag and put it down on the current corner. Karel cannot respond to a putBeeper() command unless there are beepers in its beeper bag.

The empty pair of parentheses that appears in each of these commands is part of the common syntax shared by Karel and Java and is used to specify the invocation of the command. Eventually, the programs you write will include additional information in the space between the parentheses, but such information is not part of the Karel’s primitive world. These parentheses will therefore be empty in standard Karel programs, but you must remember to include them nonetheless.

It is also important to recognize that several of these commands place restrictions on Karel’s activities. If Karel tries to do something illegal, such as moving through a wall or picking up a nonexistent beeper, an error condition occurs. At this point, Karel displays an error message and does not execute any remaining commands.

Karel’s commands, however, cannot be executed on their own. Before Karel can respond to any of these commands, you need to incorporate them into a Karel program.


3


You will have a chance to see a few simple Karel programs in Chapter 2, but before doing so, it is useful to make a few general remarks about the programming philosophy that underlies this particular implementation of the Karel programming language.

Karel and the object-oriented paradigm
When Karel was introduced in the 1970s, the prevailing approach to writing computer programs was the procedural paradigm. To a large extent, procedural programming is the process of decomposing a large programming problem into smaller, more manageable units called procedures that define the necessary operations. Although the strategy of breaking programs down into smaller units remains a vital part of any style of programming, modern languages like Java emphasize a different approach called the object-oriented paradigm. In object-oriented programming, the programmer’s attention shifts away from the procedural specification of operations and focuses instead on modeling the behavior of conceptually integrated units called objects. Objects in a programming language sometimes correspond to physical objects in the real world, but just as often represent more abstract concepts. The central feature of any object—real or abstract—is that it must make sense as a unified whole.

One of the primary advantages of the object-oriented paradigm is that it encourages programmers to recognize the fundamental relationship between the state of an object and its behavior. The state of an object consists of a set of attributes that pertain to that object and might change over time. For example, an object might be characterized by its location in space, its color, its name, and a host of other properties. The behavior of an object refers to the ways in which that object responds to events in its world or commands from other objects. In the language of object-oriented programming, the generic word for anything that triggers a particular behavior in an object is called a message (although it generally seems clearer to use the word command in the context of Karel). The response to a message typically involves changing the state of an object. For example, if one of the properties defining the state of an object is its color, then it would presumably respond to a setColor(BLUE) message by changing its color to blue.

In many ways, Karel represents an ideal environment for illustrating the object- oriented approach. Although no one has actually built a mechanical implementation of Karel, it is nonetheless easy to imagine Karel as a real-world object. Karel is, after all, a robot, and robots are real-world entities. The properties that define Karel’s state are its location in the world, the direction it is facing, and the number of beepers in its beeper bag. Karel’s behavior is defined by the commands to which it responds: move(), turnLeft(), pickBeeper(), and putBeeper(). The move() command changes Karel’s location, turnLeft() changes its direction, and the remaining two affect both the number of beepers in Karel’s bag and the number of beepers on the current corner.

The Karel environment also provides a useful framework for defining one of the central concepts of object-oriented programming. In both Karel and Java, it is essential to differentiate the notion of an object from that of a class. The easiest way to understand the distinction is to think about a class as a pattern or template for objects that share a common behavior and collection of state attributes. As you will see in the next chapter, the word Karel in a Karel program represents the entire class of robots that know how to respond to the move(), turnLeft(), pickBeeper(), and putBeeper() commands. Whenever you have an actual robot in the world, that robot is an object that represents a specific instance of the Karel class. Although you won’t have occasion to do so in CS 106A , it is possible to have more than one instance of the Karel class running in the same world. Even when there is only a single robot, however, it is important to remember that object and class are different concepts and to keep those ideas straight in your mind.




The importance of practical experience
Programming is very much a learn-by-doing activity. As you will continually discover in your study of computer science, reading about some programming concept is not the same thing as using that concept in a program. Things that seem very clear on the page can be difficult to put into practice.

Given the fact that writing programs on your own and getting them to run on the computer are essential to learning about programming, it may seem surprising to discover that this book does not include much discussion of the hands-on aspects of using Karel on your computer. The reason for that omission is that the steps you need to run a Karel program depend on the environment you’re using. Running Karel programs on a Macintosh is somewhat different from running it under Windows. Even though the programming environment you use has a great deal of influence on the nitty-gritty details you need to run programs, it has no influence whatsoever on the general concepts. This book describes the general concepts; the details pertinent to each platform will be distributed as handouts during the course.

The fact that this book omits the practical details, however, should in no sense be interpreted as minimizing their importance. If you want to understand how programming works—even in an environment as simple as that provided by Karel—it is essential to “get your hands dirty” and start using the computer. Doing so is by far the most effective introduction into the world of programming and the excitement that it holds.



0 comments: