CS212 Problem Sets

Exercises

SUBMISSION: There are two written exercises and five programming exercises. For problem 1 only, you must hand this in at section on Monday April 19. Problem 2 through 7 will be submitted on-line as usual.

Written Exercises

Problem 1: Environment Model

For this exercise, refer to your notes regarding the environment model rules.

Consider the following function:

(define mystery 
  (lambda (i)
    (let* ((x (* i 2))
           (f (lambda (i) (+ i x))))
         (set! x (* i 3))
         (let ((x (* i 4)))
           (f x)))))

1. What does (mystery 3) return? Determine this by tracing the call with the environment model. Hand in the environment model diagram for the point in time when (+ i x) is computed, and use this diagram to briefly justify your first answer.

   To give you an idea of what this looks like, here is a sample diagram with the first few frames added:

   

2. The first part of our current APPLY rule is as follows:

• Create a new environment by adding a new frame to the environment that is part of the procedure being applied.

Suppose we change this to

• Create a new environment by adding a new frame to the environment in which we are calling the procedure.

Under these new rules, what does (mystery 3) return? Again, briefly justify your answer.

Problem 2: Chains

The operations

(set! (head p) v)
(set! (tail p) v)

are effect-only functions that respectively set the head/tail of pair p to value v. (Contrast this with cons, which creates and returns a completely new pair.) For example, suppose x = (1 2 3) and y = (7 8 9). After (set! (tail y) (tail x)), the tail part of y points to the same thing as the tail part of x. Thus y now evaluates to (7 2 3).

We now define a new kind of structure, the chain. A chain is a list of elements in which the tail of the last element points to the first element. For example, z is a chain of length 4:

1. Write a function make-chain! that takes a non-empty list and makes it into a chain.

   In the next two problems, use the type specifier <chain> for chains. Assume all chains are non-empty.
   
   

2. Write a function chain-length that takes a chain and returns its length; that is, the number of pairs that make up the chain.
   
   
3. Consider this equality function for chains:

   (define (chain-equal-maybe? (c1 <chain>)
                               (c2 <chain>)
                               (remaining <integer>))
     (cond ((equals? 0 remaining) #t)
           ((not (equals? (head c1) (head c2))) #f)
           (else
             (chain-equal-maybe? (tail c1)
                                 (tail c2)
                                 (- remaining 1)))))

   One obvious problem is that this function only compares a certain number of elements before returning #t. The caller would need to determine and pass in a sufficiently large third argument.

   The second problem is the following. Because chains are circular, the notion of a ``first'' element is really not so important. (Consider rotating a necklace of beads; it remains the same necklace no matter which bead is on top.)

   We'll say that two chains are equal if they contain equal items in the same order, regardless of which items are first in the chains. For example, the result of (make-chain '(1 2 3)) is equal to the result of (make-chain '(2 3 1)). Also note that c is equal to (tail c) for any chain c.

   Using chain-equal-maybe? as a helper function, write a function chain-equal? that takes two chains and returns #t iff they are equal by our new definition. (Note: you must use the helper function exactly as provided.)

Programming Exercises

Problem 3: The Event Queue

Look at the code in queue.ss. This file provides an interface and implementation for a queue, minus a crucial function. To complete this implementation, you need to write a function dequeue, which, given a queue Q, removes and returns the first element in Q. (This is, incidentally, not a hard function to write - don't make it hard.)

Once you have completed this function, you should be able to run the game. Try it! You can actually play the entire game to the end!

What you should hand in: definition of dequeue

Problem 4: Ducks

Now that the game is working, we turn to problems that demonstrate the great advantage of object-oriented programming. For the remainder of this problem set you will be extending the game and giving it new functionality.

Create a class <mortal> extending <character>. <mortal>s have some finite lifetime, and die when that time expires - so <mortal> needs to store a lifespan.

Now, implement ducks, as follows:

• a duck is a mortal with a lifespan of 90 seconds.
• notice that <mortal> has <automated> as one of its super classes. Give the duck a plan such that it dies at the end of its lifetime.
• whenever a duck is in a location and a player enters the room, the duck picks a random exit and runs away.
• if anyone ever kills a duck, it produces a holy hand grenade and a duck body.
• when a duck dies of natural causes, there is a 50% probability that a duck body is produced, and there is a 50% probability that a duck body and two newborn ducklings will be produced.

What you should hand in: definition of the <mortal> class, the definition of the chr:duck instance, a specialization of fight, and a specialization of any method necessary to make ducks scared of players
NOTE: Since it is hard to show output that your code works, we would like you to write one to two sentences describing your observations and how you tested your code. These sentences must be clear, concise, objective, and short.

Problem 5: Wheelbarrows

Consider implementing an object like a wheelbarrow in this framework. This is obviously something that can be carried (or, at least, possessed), and something that can hold other objects. This makes it unlike any object which currently exists in the game.

A wheelbarrow is something that can be picked up (just like an <inanimate>), and something which can hold things (just like a <container>). Use multiple inheritance to accomplish this: wheelbarrows should be both containers and inanimates.

Your task is to add wheelbarrows to the game. You need to do the following:

• define the <wheelbarrow> class.
• modify the functionality of look in some manner such that when you look at the wheelbarrow it displays its description along with its inventory
• add commands for putting things into and taking things out of the wheelbarrow.
• add a command for dumping the entire contents of the wheelbarrow into any location that is adjacent to the owner of the wheelbarrow. (Note that an animate will possess the wheelbarrow, and places adjacent to the location of the animate is where the wheelbarrow can be dumped. Your function should check for this case.)
• create some wheelbarrow, and put it somewhere

What you should hand in: definition of the <wheelbarrow> type, any definition that modifies look's functionality, a put-in-cart command, a get-out-of-cart command, a dump command, and your definition of the obj:wheelbarrow instance. Also, describe in one to two clear, concise, objective, and short sentences how you tested your code to insure that obj:wheelbarrow worked.

Problem 6: The Grim Reaper

Remember in Problem Set #4 when we told you to think about how you would find an actual path from one location to another? Now's your chance. Write a function find-path which takes two locations, a location and an animate, or a location and object in the game, and finds some path between them, returning the next best step in the path.

Add a new character to the game, a Reaper. The reaper should have the following characteristics:

• If the Reaper doesn't have the wheelbarrow, his plan is to find it. He should determine a path to the wheelbarrow, and move towards it. Note that another character may possess the wheelbarrow.
• When the Reaper finds the wheelbarrow, he takes it. If someone else has the wheelbarrow, he attacks and kills the wheelbarrow's possessor.
• When the Reaper has the wheelbarrow, he picks some dead body somewhere in the world (other than in the Gorge of Eternal Peril or Microsoft -- he always ignores these bodies), and goes to get it. When he gets there, he puts the dead body in the wheelbarrow.
• The reaper doesn't have to kill someone to get a dead body that someone is holding, but you may implement this if you wish.
• If there are no dead bodies in the world, the Reaper moves toward the pub and gets totally blasted. He stays at the pub until a new dead body appears somewhere in the world.
• Whenever the Reaper passes next to the Gorge of Eternal Peril, he dumps whatever bodies he has in his wheelbarrow into the gorge. (Do not rely on the specifics of the current map -- do not hard code the locations that are presently adjacent to the Gorge, we might change the map when we test.)
• Whenever someone enters the location where the Reaper is (or when the Reaper enters a new location), he says "Bring out your dead!"
• Anyone who gets in a fight with the Reaper loses and dies. (You fight the Reaper, and you die. The Reaper always wins. Do not fight the power of the Reaper.)
• The Reaper never enters the Gorge or Microsoft himself. (This is already implemented for you - find out how!).

NOTE: there are two possible ways to solve the search for <corpse>s. You could do something similar to the path questions and do a breadth-first-search. This code is a little more complicated, but generally makes the reaper more efficient at collecting corpses. An alternative is to have a global queue of corpses. This code is simpler, but makes the reaper less effective at collecting corpses. You may implement either option. They are both correct. If you choose to implement the queue, you must include this definition in your solutions (as is - you cannot modify this code).

What you should hand in: all your definitions of find-path, a specialized fight method, and the definition of chr:reaper. And finally, in one to two clear, concise, objective, and short sentences, describe your observations of the reaper and how you know he does his job correctly.