CS 3
"Blocks World" project
Background
Robotics is a leading research area in computer science. A program that
controls a robot must represent the environment somehow, and be able to
sense changes and update its internal representation accordingly. It
must also be able to plan actions of the robot and anticipate possible
consequences of those actions. Robots are often programmed to act
autonomously; some, however, are guided through a user interface that
may involve complicated language processing. This project is intended
to give you a small taste of some of the programming techniques needed
to guide a robot.
Project overview
In this project, you complete a program that manipulates stacks of
blocks (all the same size) in a two-dimensional environment. In Scheme,
the environment is represented by a list of stacks. A stack is
represented by a list of blocks, which may be empty; the first block in
the stack is the top block, which rests upon the second block, and so
on; the last block in the stack rests on the table. A block is
represented by a two-word sentence. The first element is the block's id
number; no two blocks in the environment have the same id. The second
element is the block's color. (The display system provides eight
colors: black, blue , green, cyan, red, magenta, yellow, and white.
Cyan is blue-green. Black blocks won't show up on the display very
well.) An example appears below.
picture of environment
|
Scheme representation
|
|
(((1 red) (2 cyan)) () ((4 red) (3 green)))
|
The program will read and execute commands that move blocks in the
environment or request information about the environment. There are
three kinds of commands:
(quit)
The
quit
command writes the current blocks environment to a file named
blocks.out, and terminates the program.
(put
block-description1
on
block-description2
)
The
put
command clears the tops of two blocks, then moves the first block onto the second.
(what is
preposition block-description
)
The
what is
command is a question about the environment. ("On" and "under" are the prepositions that are legal in this command.)
(add block-description)
The
add command randomly adds a new block to an existing stack in the environment. Note, the block description in this command is a subset of the block description in other commands.
(remove block-description)
The
remove command with the above format will remove a single block, clearing blocks off the top of the target block as necessary.
(remove number multiple-block-description)
The
remove command, when followed by a number 2 or greater, should remove
number blocks matching
multiple-block-description from the environment.
Blocks are not described by their ids, but may be described by their
colors. Each block description is one of the following: "a block",
"it", "a color block", or "the color block", except in the add command, where it is one of "a block" or "a color block". A multiple block description (only used in the
remove n command) is one of the following: "color blocks" or "blocks". Block descriptions have
different meanings in the different
commands.
Block descriptions in the "put" command
In the
put command, each block description must refer
to exactly one block. For a block description that starts with "the",
the environment is searched for blocks that qualify. If there is
exactly one such block, that's the one that's referred to; otherwise,
the program should print an error message and ignore the command. In
the sample environment given previously, "the cyan block" refers to
block #2; "the red block" is ambiguous and "the yellow block" is
nonsense.
For a block description that starts with "a", the environment is
similarly searched for blocks that qualify. If there are one or more,
one of the blocks that qualify is chosen randomly but in such a way
that the block isn't moved on top of itself; otherwise, the program
should print an error message and ignore the command. That means, for
instance, that the command
(put a block on a block)
should always be legal in an environment with two or more blocks.
The block description "it" is described below.
Block descriptions in the "what is" command
In the
what is
command, a block description that starts with "the" is handled as in the
put
command. Thus the response to
(what is on the cyan block)
should be
(1 red)
while the response to
(what is on the red block)
should be the error message
(more than one red block exist)
A block description that starts with "a" may refer to more than one
block. For such a description, the response should include all the
relevant blocks. For example, the response to
(what is under a red block)
should be
(2 cyan)
(3 green)
It may happen that no blocks are on or under the specified block(s).
The appropriate response is "nothing". For example, the question
(what is under a green block)
produces the response
(nothing)
Block descriptions in the "add" command
In the
add command, a block description can only come in the form "a block" or "a color block". Descriptions starting with "the" or consisting of "it" should generate errors. Legal block descriptions to the
add command are handled the same way as in the corresponding descriptions in
put and
what is commands.
As a result, a call to
add should create a new block. The block should have a unique id -- that is, a positive integer different than any of the ids of the other blocks in the environment. When the block description is "a block" and a random color should be chosen from the possible colors. The location of the block should be in a randomly chosen stack, placing the block on the top of any existing blocks in the stack. If your environment is empty, with no stacks, you should create an empty stack and add the new block to it.
For example, the command
(add a green block)
given in the environment
(((1 green) (2 blue)) ((4 white))) can result in the following environments:
(((3 green) (1 green) (2 blue)) ((4 white)))
or
(((1 green) (2 blue)) ((3 green) (4 white)))
Note, the "id" of the added block need not be 3, but cannot be 1, 2, or 4.
Block descriptions in the "remove" (a single block) command
Block-description should be checked in the same manner as put command: the description should refer to a single block. The target block should be removed from the from the environment.
Block descriptions in the "remove" (multiple blocks) command
The
remove number command takes a multiple block-description, which is one of "blocks" or "color blocks". If there are not
number blocks that satisfy the description in the environment, the command should return
(there are fewer than number color blocks)
or
(there are fewer than number blocks)
if a color was specified or not.
What is "it"?
"It" essentially means the block most recently mentioned or asked
about. If this cannot be determined unambiguously, the program should
print an error message and ignore the command. In the command following
a successfully executed
put
command, "it" refers to the block moved. In the command following a
successfully executed question, "it" refers to the answer. If there are
more than one block in the answer, "it" is ambiguous in the following
command. "It" is undefined in the command following a command that
produced an error message.
Example
Given below is a sample dialog that illustrate how the program should
behave. It starts with the environment given on the previous page.
command
|
resulting environment
or response
|
notes
|
(put the cyan block on a red block)
|
|
Block #1 was moved to the table to clear the top of block #2. Then block #2 could be moved atop either of the red blocks.
|
(put it on the green block)
|
|
"It" means block #2 here. That block didn't need to be cleared, but block #3 did.
|
(put it on the red block)
|
(more than one red
block exist)
|
"It" still means block #2.
|
(put it on a red block)
|
(please explain what is meant by "it")
|
"It" was forgotten because of the error message.
|
(put the cyan block on a yellow block)
|
(no yellow block exists)
|
|
(put a cyan block on a cyan block)
|
(the cyan block cannot be moved onto itself)
|
Putting a red block on a red block would work; one of the red blocks would be randomly chosen and moved atop the other one.
|
(what is on a red block)
|
(nothing)
|
|
(put it on a cyan block)
|
(please explain what is meant by "it")
|
"It" is undefined here since nothing satisfied the preceding question.
|
(what is under the cyan block)
|
(3 green)
|
|
(put it on a red block)
|
|
"It" is now block #3. Block #2 is moved to the table to clear block #3,
and then one of the red blocks is randomly chosen for the destination.
|
(put the cyan block on the green block)
|
|
|
(what is on a block)
|
(3 green)
(2 cyan)
|
The blocks could be listed in the opposite order.
|
(what is under it)
|
(please explain what is meant by "it")
|
The previous question was answered with two blocks, so "it" is ambiguous.
|
(what is on a yellow block)
|
(no yellow block exists)
|
An error message resulted instead of "nothing".
|
(put the cyan block on the green block)
|
|
A clever program would notice that the cyan block is already on the
green block. Straightforward processing, however, would first move
block #2 to the table, then move it back on block #3.
|
(put a red block on it)
|
|
"It" is now the cyan block. Choosing the other red block, block #1,
would have required moving blocks #2 and #3 to the table before moving
block #1 atop block #2.
|
(remove a green block)
|
|
We find block #3, clear everything on top of it, and then remove it.
|
(add a block)
|
|
Any block could have been added, but we randomly generated block #5 and placed it on the third stack.
|
(remove 2 red blocks)
|
|
block #1 and block #4 are removed.
|
(remove 3 blocks)
|
(there are fewer than 3 blocks)
|
There are only 2 blocks in the environment, so removing 3 is impossible.
|
Code you are to provide
A framework for this program appears
here and in the file
~cs3/public_html/programs/blocks.fw.scm. It includes calls to two procedures that you are to write.
1.
analyzed
Given a command submitted by the user, a blocks environment, and the current value of "it" as arguments,
analyzed returns the result of translating the command to a form that's easier
to handle and resolving references to "the ... block", "a ... block",
and "it". If these references cannot be resolved successfully,
analyzed
returns
#f
.
- A
put
command should be translated to a three-element list whose first element is the word
put
and whose second and third elements are blocks.
- A
what is
command should be translated into a list of at least two elements whose first element is either
under
or
on
and whose remaining elements are blocks.
- A add command should be translated into a list of two elements whose first element is the word add and whose second element is a block.
- Either remove command should be translated into a list of at least two elements, whose first element is the word remove and whose remaining elements are blocks.
Analyzed is also where you should display error messages. Analyzed won't return an error message; rather, when there is an error, it will return #f. Within the body of the procedure, use the show function to display the appropriate error message.
command |
possible analyzed results |
(put the cyan block on a red block)
|
(put (2 cyan) (1 red))
(put (2 cyan) (4 red))
|
(put it on the green block)
|
(put (2 cyan) (3 green))
|
(put it on the red block)
|
#f
|
(put it on a red block)
|
#f
|
(put the cyan block on a yellow block)
|
#f
|
(put a cyan block on a cyan block)
|
#f
|
(what is on a red block)
|
(on (1 red) (4 red))
(on (4 red) (1 red))
|
(put it on a cyan block)
|
#f
|
(what is under the cyan block)
|
(under (2 cyan))
|
(put it on a red block)
|
(put (3 green) (1 red))
(put (3 green) (4 red))
|
(put the cyan block on the green block)
|
(put (2 cyan) (3 green))
|
(what is on a block)
|
(on (1 red) (2 cyan) (3 green) (4 red))
(The four blocks may appear in any sequence in the list.) |
(what is under it)
|
#f
|
(what is on a yellow block)
|
#f
|
(put the cyan block on the green block)
|
(put (2 cyan) (3 green))
|
(add a green block)
|
(add (5 green))
|
(remove it)
|
(remove (5 green))
|
(add a block)
|
(add (6 magenta))
|
(remove a magenta block)
|
(remove (6 magenta))
|
(remove 2 blocks)
|
(remove (2 cyan) (3 green))
|
(remove 2 red blocks)
|
(remove (1 red) (4 red))
|
2.
execute
Given an analyzed command, a blocks environment, and the current value of "it",
execute
executes the command by moving relevant blocks or answering the specified question.
Execute
then calls
handle-cmds with the updated blocks environment and "it" values.
3.
resolved-descr
Your code should include a procedure named
resolved-descr (short for "resolved description").
Resolved-descr
will take three arguments: a block description such as
(a red block) , a blocks environment, and the value of "it". It will return a list of
the blocks in the environment that satisfy the description. Thus
(resolved-descr
'(a red block)
'(((1 red) (2 cyan)) () ((4 red) (3 green)))
'( ) )
should return
((1 red) (4 red))
Miscellaneous requirements
In the
what is
command, "under" means "directly under" and "on" means "directly on". Thus in the environment
(((1 red) (2 green) (3 blue)))
the command
(what is under the red block)
should only list
(2 green)
, not
(3 blue)
. Similarly, the command
(what is on the blue block)
should list only the green block, not the red block.
The two versions of the
what is command—"what is on
..." and "what is under ..."—have almost identical behavior. You should
minimize the amount of duplicate code you use to implement these two
types of command.
In both the
analyzed
and the
execute
procedures (and in your helper procedures), "it" is to be represented
as a list of blocks. An undefined "it" is represented by the empty
list; an ambiguous "it" corresponds to a list that contains more than
one block.
In the situation where a block is to be moved to an empty stack and the
environment doesn't contain any empty stacks, an empty stack should be
added to the end of the list and the block moved there. For example,
moving block #2 to the table in the environment
(((1 red)) ((2 green) (3 blue)))
(which consists of a stack containing one red block and a stack
containing a green block and a blue block) should produce the
environment
(((1 red)) ((3 blue)) ((2 green)))
Don't rearrange the stacks while moving. Your program should simulate a
robot that moves single blocks from stack to stack; it shouldn't move
entire stacks at once.
You may assume that the environment read from the file is a legal and
reasonable one. That is, it's a list of stacks, each of which is a list
of blocks, with each block having a unique id number and a legal color,
and there are at least two blocks in the environment. You may also
assume that user commands are formatted correctly as described on the
previous page. The errors you must detect are the following:
referring to "the" block when there aren't any, or more than one;
trying to move a block on top of itself;
referring to "it" when it's not defined, or is ambiguous.
Any error message not involving "it" must name the color of the relevant block(s).
Don't change the framework code we provide. We will be testing
analyzed,
execute, and
resolved-descr in isolation so they
need to return values in a format exactly like the examples above.
Put your completed program in a file named
blocks.scm
in a directory named
finalproject. In a file named
blocks.tests
, include tests that exercise your program completely. (Also provide the file
partners.readme
if you're working in partnership.) Provide example runs in which all
the commands, block specifications, and error conditions appear. The
example dialog on the previous page is a good start. You should also
include commands such as
(put a red block on a red block)
and
(put it on a red block)
with environments that contain two red blocks and a red block
identified as "it". Test your procedures individually as well as in
combination, and include the results of these tests in your
blocks.tests
file.
Suggested approach
One possible approach to this project would be to design and test the
blocks movement procedures first. (Our solution uses three: one to
clear a block, another to move a block to the table, and a third to
move one block on top of another.) Since these procedures only involve
blocks environments—actually, they only involve lists of sentences—they
will be easy to test in isolation.
Another approach is to focus on the command analysis first. The
put
command can be implemented separately from
what is; the
resolved-descr
procedure, as mentioned above, will be useful for both.