CS 3 project choice 2"Blocks World"

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 asks the user for a file name, writes the current blocks environment to the file, 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.)

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". Block descriptions have different meanings in the put and what is 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)

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.

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. Analyzed should return the following values for the commands in the example on the previous page.

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))

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.

Put your completed program in a file named blocks.scm in your submissions directory. 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.