kumard@sunybcs.UUCP (Deepak Kumar) (07/26/86)
Sometime back, there was a request for sample Modula2
class projects. I taught a Programming Language Concepts
class (Junior CS) this summer and assigned this project to the
class.
The project is a partial implementation of Rich Pattis' Karel,
the Robot (refer to the book by that title by Pattis).
Students take this course after doing two intro courses
in Pascal (now they are being switched to Modula2), a course
in Data Structures. It focuses on illustrating the Data
Abstraction facilities of the language. The project was
assigned for several reasons :
. To make them implement an off-beat Abstract Data Type
(something other than the standard examples like stacks
and lists etc [they already did those in an earlier course])
. Students in this course did Karel, The Robot in their first
programming course, so they'd find it exciting to actually
implement it by themselves.
As a part of the project, they also had to write an essay
on "How Modula-2 Compares against Kernighan's objections
to Pascal" in the paper "Why Pascal is Not My Favorite
Programming Language" by Brian Kernighan.
Students thoroughly enjoyed the project and the results
were outstanding. I think it gave a proper introduction
to Modula-2 to people who have been exposed to Pascal and
other languages prior to this.
Here is the description of the project. Students had
21/2 weeks to submit the project. They did it on the
VAX/UNIX using the DECWRL compiler.
--------->
CS 305 - PROGRAMMING LANGUAGES
SUMMER 1986
PROJECT #1 : KAREL THE ROBOT
(Due on July 2, 1986)
_T_h_e _R_o_b_o_t _W_o_r_l_d
Karel lives in a world that is unexciting by present-day
standards (there are no volcanoes, Chinese restaurants, or
symphony orchestras), but it does include enough variety to
allow him to perform simply stated, yet interesting tasks.
Informally, the world is a grid of streets that Karel can
traverse. It also contains special objects that Karel can
sense and manipulate.
Fig 1 is a map illustrating the structure of Karel's world,
whose shape is a great flat plane with the standard North,
south, east, and west compass points. The world is bounded
on its west side by an infinitely long horizontal wall
extending eastward. These boundary walls are made of solid
Neutronium, an impenetrable metal that restrains Karel from
falling over the edges of his world.
Crisscrossing Karel's world are horizontal _s_t_r_e_e_t_s (running
east-west) and vertical _a_v_e_n_u_e_s (running north-south) at
regular, one block intervals. A _c_o_r_n_e_r, sometimes referred
to as a street corner, is located wherever a street and an
avenue intersect. Karel can be positioned on any corner,
facing one of the four compass points. Both streets and ave-
nues are numbered; consequently, each corner is identified
uniquely by its street and avenue numbers. The corner where
1st street and 1st Avenue intersect is named the _o_r_i_g_i_n.
Besides Karel, there are two other types of objects that can
occupy his world. The first type of object is a _w_a_l_l _s_e_c_-
_t_i_o_n. Wall sections are also fabricated from the impenetr-
able metal Neutronium, and they can be manufactured in any
desired length. They are positioned sideways between adja-
cent street corners, effectively blocking Karel's direct
path from one corner to the next. Wall sections are used to
represent obstacles that Karel must navigate around, such as
hurdles and mountains. Enclosed rooms, mazes, and other bar-
riers can also be constructed from wall sections.
The second type of object in Karel's world is a _b_e_e_p_e_r.
Beepers are small plastic cones that emit a quiet beeping
noise. They are situated on street corners and can be
picked up, carried, and put down by Karel. Some of Karel's
tasks involve picking up or putting down patterns made from
beepers, or finding and transporting beepers.
_K_a_r_e_l'_s _C_a_p_a_b_i_l_i_t_i_e_s
Let's now shift our attention away from Karel's world and
concentrate on Karel himself. Karel is a mobile robot: he
can move forward, in the direction he is facing, and he can
turn in place. He can also perceive his immediate surround-
ings: Karel posesses a rudimentary sense of sight, sound,
direction, and touch.
Karel sees by using any one of his three TV cameras, which
point straight ahead, to his left, and to his right. These
three cameras are focused to detect walls exactly one block
away from Karel. Karel also has the ability to hear a
beeper, but only if he and the beeper are on the same
corner; the beepers beep that quietly. By consulting his
internal compass, Karel can determine which direction he is
facing. Finally, Karel is equipped with a mechanical arm
that he can use to pick up and put down beepers. To carry
these beepers, Karel wears a soundproof _b_e_e_p_e_r-_b_a_g around
his waist. Karel can also determine if he is carrying any
beepers in this bag by probing it with his arm.
Whenever we want Karel to accomplish a task in his world, we
must supply him with a detailed set of instructions that
explains how to perform the task. Karel is able to recieve,
memorize, and follow such a set of instructions, which is
called a _p_r_o_g_r_a_m.
What language do we use to program Karel? Instead of pro-
gramming Karel in English, a natural language for us, we
program him in a special programming language, which was
designed to be useful for writing robot programs. Karel's
robot programming language-like any other natural language-
has a vocabulary, punctuation marks, and rules of grammar.
But this language, unlike English, for example-is simple
enough for Karel to understand; yet it is a powerful and
concise language that allows us to write brief and unambigu-
ous programs for Karel.
9
9
|||||||||||||||||||||| 1..9 : number of beepers
20|....................| at any point
19|.....|||||||||......|
18|.....|.4.....|......|
17|.....|..............| > : Karel facing east
16|.....|.......|......|
15|.....|.......|......| ^ : Karel facing North
14|.....|||||||||......|
13|....................| < : Karel facing west
12|....................|
11|....................| v : Karel facing south
10|....................|
9|....................| | : wall section
8|...|||||............|
7|.......|2...........|
6|.......||||||||.....|
5|..............|.....| north
4|.............3|.....| ^
3|..............|.....| |
2|.>.1................| west<----->east
1|....................| |
|||||||||||||||||||||| v
12345678911111111112 south
01234567890
_F_i_g _1 : _T_h_e _s_t_r_u_c_t_u_r_e _o_f _K_a_r_e_l'_s _w_o_r_l_d
9
9
_P_r_i_m_i_t_i_v_e _I_n_s_t_r_u_c_t_i_o_n_s _a_n_d _S_i_m_p_l_e _P_r_o_g_r_a_m_s :
_1. _C_h_a_n_g_i_n_g _P_o_s_i_t_i_o_n
Karel understands two primitive instructions that change his
position. The first of these instructions is move, which
changes Karel's location.
_m_o_v_e - When Karel executes a _m_o_v_e instruction, he moves
forward one block; he continues to face the same
direction. To avoid damaging himself, Karel will
not move forward if he sees a wall section or
boundary wall at the next corner that he would
move toward. Instead, karel executes a _m_o_v_e
instruction in this situation by turning himself
off. This action, called an _e_r_r_o_r _s_h_u_t_o_f_f, will be
explained in a further section.
From this definition, we see that Karel executes a _m_o_v_e
instruction by either moving forward (when his front is
clear to the next corner) or performing an error shutoff
(when his front is blocked).
The second primitive instruction that changes Karel's posi-
tion is _t_u_r_n_l_e_f_t. This instruction changes the direction
that Karel is facing, but does not alter his location.
_t_u_r_n_l_e_f_t - Karel executes a _t_u_r_n_l_e_f_t instruction by
pivoting 90 degrees to the left; thus Karel
remains on the same street corner while executing
a _t_u_r_n_l_e_f_t instruction. Because it is impossible
for a wall section to block Karel's turn, _t_u_r_n_l_e_f_t
cannot cause an error shutoff.
Karel always starts his task from some corner, facing either
north, south, east, or west. He cannot travel fractions of a
block or turn at other than 90 degree angles. Therefore,
although both _m_o_v_e and _t_u_r_n_l_e_f_t change his position, after
executing either of these instructions, Karel is still on
some corner and still is facing one of the four compass
points.
_H_a_n_d_l_i_n_g _B_e_e_p_e_r_s
Karel understands two primitive instructions that permit him
to handle beepers. These two instructions preform opposite
actions.
_p_i_c_k_b_e_e_p_e_r - When Karel executes a _p_i_c_k_b_e_e_p_e_r instruc-
tion, he picks up a beeper from the corner he is
standing on and then deposits it in his beeper-
bag. If he executes a _p_i_c_k_b_e_e_p_e_r instruction on a
beeperless corner, Karel performs an error shut-
off. On a corner with more than one beeper, Karel
randomly picks up one-and only one-of the beepers
and the places it in his beeper-bag.
_p_u_t_b_e_e_p_e_r - Karel executes a _p_u_t_b_e_e_p_e_r instruction by
extracting a beeper from his beeper-bag and plac-
ing it on his current street corner. If Karel
tries to execute a _p_u_t_b_e_e_p_e_r instruction with an
empty beeper-bag, he performs an error shutoff.
Beepers are so small that Karel can move right by them; only
wall sections and boundary walls can block his movement.
_3. _P_r_i_n_t_i_n_g _S_t_a_t_u_s
We will simulate Karel and his world inside a computer, so
we'll need a way of finding out what he is up to. The _p_r_i_n_t
_i_n_s_t_r_u_c_t_i_o_n _f_u_l_f_i_l_l_s _t_h_i_s _r_e_q_u_i_r_e_m_e_n_t.
_p_r_i_n_t - When executed, a print out of Karel's world is
generated on the standard output device.
_4. _F_i_n_i_s_h_i_n_g _a _T_a_s_k
Finally, we need a way to tell Karel that he is finished
with his task. The _t_u_r_n_o_f_f instruction fulfills this
requirement.
_t_u_r_n_o_f_f - When Karel executes a _t_u_r_n_o_f_f instruction, he
turns himself off and is incapable of executing
any more instructions until he is restarted on
another task. The last instruction in every robot
program must be a _t_u_r_n_o_f_f instruction.
_A _C_o_m_p_l_e_t_e _P_r_o_g_r_a_m
9
9
As an example, we now pose a task for Karel and then exhibit
a complete program that instructs him to perform the task
correctly. Karel's task, illustrated in Fig 2, is to tran-
sport the beeper from 2nd St. & 4th Ave. to 4th St. & 5th
Ave. After he has put down the beeper, Karel must move one
block farther north before turning himself off.
|||||||||||||||||||||| ||||||||||||||||||||||
20|....................| 20|....................|
19|....................| 19|....................|
18|....................| 18|....................|
17|....................| 17|....................|
16|....................| 16|....................|
15|....................| 15|....................|
14|....................| 14|....................|
13|....................| 13|....................|
12|....................| 12|....................|
11|....................| 11|....................|
10|....................| 10|....................|
9|....................| 9|....................|
8|....................| 8|....................|
7|....................| 7|....................|
6|....................| 6|....................|
5|....................| 5|....^...............|
4|....................| 4|....1...............|
3|....................| 3|....................|
2|.>.1................| 2|....................|
1|....................| 1|....................|
|||||||||||||||||||||| ||||||||||||||||||||||
12345678911111111112 12345678911111111112
01234567890 01234567890
_F_i_g _2.
The following robot program instructions correctly instruct
Karel to perform this task.
begin
print
move
move
pickbeeper
move
turnleft
move
move
putbeeper
move
print
turnoff
end
_T_h_e _S_i_m_u_l_a_t_i_o_n
Implement an Abstract Data Type called _w_o_r_l_d and another one
called _r_o_b_o_t in a module called _R_o_b_o_t_W_o_r_l_d. Various
instructions correspond to various operations that you can
perform on these two structures. A main module will declare
a variable called Karel (type Robot) and a variable called
WorldOfKarel (type World). Your program begins by reading in
the initial status of Karel and its world. Thereafter, it
reads a Karel program, interprets the instruction, and per-
forms the desired action.
The structure of one of the modules may look something like
this:
DEFINITION MODULE RobotWorld;
EXPORT Robot, World, readworld, print, move, turnleft, turnoff.
TYPE Robot = (* definition of the type Robot *);
World = (* definition of the type World *);
PROCEDURE readworld (VAR w : World; VAR r : Robot);
(* Reads in the initial status of the given World and Robot *)
PROCEDURE print (w: World; r : Robot);
(* prints the world and the position of r in this world *)
PROCEDURE move (VAR w : World; VAR r : Robot);
(* performs a move instruction for robot r in world w *)
PROCEDURE turnleft (VAR w : World; VAR r : Robot);
(* performs a turnleft instruction for r in w *)
PROCEDURE turnoff ();
(* performs a turnoff *)
END RobotWorld.
9
9