University of Virginia, Department of Computer Science
CS200: Computer Science, Spring 2004

Problem Set 6: Adventures in Charlottansville Out: 5 March 2004
Due: Monday, 22 March 2004

Collaboration Policy - Read Carefully

For this problem set, you may either work alone and turn in a problem set with just your name on it, or work with one other student in the class of your choice. If you work with a partner, you and your partner should turn in one assignment with both of your names on it. For the final question (Question 8), you may combine efforts with as many students as you wish.

Regardless of whether you work alone or with a partner, you are encouraged to discuss this assignment with other students in the class and ask and provide help in useful ways. You may consult any outside resources you wish including books, papers, web sites and people (except for CS200 problem sets and comments from previous years). If you use resources other than the class materials, indicate what you used along with your answer.

Purpose

Download: Download ps6.zip to your machine and unzip it into your home directory J:\cs200\ps6. This file contains:
  • ps6.ss — A template for your answers. You should do the problem set by editing this file.
  • objects.ss — code that defines objects. Defines classes for people, places and things.
  • adventure.ss — code describing the imaginary world of the game and playing
  • listprocs.ss — the list procedures we have defined so far in class

Background

In the 1961, Digital Equipment Corporation (later part of Compaq, which is now part of Hewlett-Packard) donated a PDP-1 mini-computer to MIT, hoping they would use it to solve important scientific problems. Instead, Steve Russell invented the first computer game: Spacewar!. Ten years later, Will Crowther produced the first interactive fiction game, Colossal Cave Adventure (or Adventure for short). Inspired by Adventure, a group of MIT students created Zork and released a version for the Apple II. The game became wildly popular, and was the cause of many students failing out of school.

For this problem set, you will create your own adventure game. Our game takes place in a far-off fictional land known as the University in Charlottansville, East Virginia. Set on bucolic grounds of rolling hills, grassy fields, and red-brick buildings, the characters in our adventure game will take us to imaginary places like the Cabal Hall, Cdrs Hill, the Recursa, and Oldbrushe Hall. Programming an adventure game involves modeling objects in a fictional world. Hence, you will build your adventure game using techniques known as object-oriented programming.

Q: So some of the locations in the game are based on real places?
A: Except for a few. As far as I know, there is no eldricth altar at which students are sacrificed to nameless gods. But then, I was never a professor, so I can't be sure.
Dave Lebling, on The Lurking Horror adventure game


Note: All of the places and characters in our game are purely fictional (although most are not purely functional, since they use mutation). Any similarity to real persons or places is purely coincidental.

Object-Oriented Programming

By the word operation, we mean any process which alters the mutual relation of two or more things, be this relation of what kind it may. This is the most general definition, and would include all subjects in the universe. Again, it might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations, and which should be also susceptible of adaptations to the action of the operating notation and mechanism of the engine... Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.

Ada Byron, Countess of Lovelace, 1843 (from Lecture 1)

In all of the previous assignments, we solved problems by dividing them into procedures that could be combined to solve the problem. This is known as procedural programming. Another way of solving problems it to model them using objects. This approach is particularly well-suited to problems that involve simulating a real (or imagined) world such as a graphical user interface (a simulation of a desktop with objects like files and documents), an astrophysics experiment (a simulation of the universe with objects like stars and galaxies), or an adventure game (a simulation of a fictional world with objects like people and donuts).

An object is an entity that packages state and procedures. We call the state that is part of an object instance variables, and the procedures that are part of an object methods. Methods may give information about the state of an object, modify the state of an object, or direct the object to interact with other objects. We also need procedures for creating objects. We call these procedures constructors. Once an object is created, it is only manipulated by using the object's methods. We call a method of an object by sending the object a message.

For our game, we need to represent three basic kinds of things: people, places and things. Every object we make will be a person, a place or a thing. We call kinds of objects classes.

We have provided a constructor procedure called make-class for creating an object of each class. All objects in our fictional world have names (rumors about a Nameless Field are as yet unsubstantiated), so each of our constructor procedures will take a name parameter. We use quoted symbols for names (see SICP, p. 142 for details on quotation). The three constructors are:

To put a new thing or person in our fictional world, we must install it in a place. The procedure
   (install-object Object Place)
installs object Object (which must not be a place) in the place Place (which must be a place).

Once an object is installed, we interact with it using ask to send a message to an object that invokes a method:

All objects in the system are manipulated using message-accepting procedures. Procedures defining our objects are defined in objects.ss.

Different objects handle different messages. Here is a partial list of messages you can use. The ask procedure is used to implement each of these. Note that some of the messages have parameters.

In adventure.ss we define some places in our imaginary world. The procedure set-up-charlantansville installs those places and sets up connections between them. For example, the definitions 
(define Cabal-Hall (make-place 'Cabal-Hall))
(define Bart-Statue (make-place 'Bart-Statue))
make two places, Cabal-Hall and Bart-Statue. In set-up-charalatansville, we use can-go-both-ways to connect Cabal-Hall and Bart-Statue: 
    (can-go-both-ways Bart-Statue 'south 'north Cabal-Hall)
We can experiment with our world by evaluating (set-up-charlottansville) and then asking objects in our world to do things. (The provided file ps6.ss does this when you load it.) For example:

> (set-up-charlottansville)

welcome-to-charlottansville

> (ask Cabal-Hall 'exits)

(down north)

> (ask Cabal-Hall 'name)

cabal-hall

> (ask Cabal-Hall 'neighbor-towards 'down)

#<procedure>

> (ask (ask Cabal-Hall 'neighbor-towards 'down) 'name)

steam-tunnel


Question 1: Why does (ask Cabal-Hall 'neighbor-towards 'down) evaluate to a procedure?

Our world needs some people in it, so let's create one, and install him in our world:

> (define JT (make-person 'Jeffus-Thomasson))

> (install-object JT Cabal-Hall)

Installing jeffus-thomasson at cabal-hall

installed

We can also make things and add them to our world. For example, let's create a donut and place it in Cabal-Hall (where JT is now). Mr. Thomasson looks around, sees the donut and takes it:

> (define donut (make-thing 'donut))

> (install-object donut Cabal-Hall)

Installing donut at cabal-hall

installed

> (ask JT 'look)

At cabal-hall: jeffus-thomasson says -- I see donut
At cabal-hall: jeffus-thomasson says -- I can go down north

(donut)

> (ask JT 'take donut)

At cabal-hall : jeffus-thomasson says -- I take donut

#t

Try playing the adventure game. Load ps6.ss in DrScheme. Then, in the interactions window, start making people and moving them around. Get a feel for how objects work before moving on.

Defining Objects

All the people, places and things in our adventure are objects. The procedure make-object creates a new object. Here is make-object without using any syntactic sugar: 
(define make-object 
  (lambda (name)
    (lambda (message)
      (if (eq? message 'object?)
	  (lambda (self) #t)
	  (if (eq? message 'class)
	      (lambda (self) 'object)
	      (if (eq? message 'name)
		  (lambda (self) name)
		  (if (eq? message 'say)
		      (lambda (self list-of-stuff)
			(if (not (null? list-of-stuff))
			    (display-message list-of-stuff))
			'nuf-said)
		      (if (eq? message 'install)
			  (lambda (self . args) 'installed)
			  #f))))))))
The name make-object is a procedure that takes one parameter, name. It evaluates to a procedure that takes one parameter, message.

All those (if (eq? ...)) expressions in make-object get pretty hard to read, so Scheme provides the case syntactic sugar to write this more conveniently (see the DrScheme help for the details on case, but you can probably figure out what you need to know from this example). Here is the sugary version of make-object — it means exactly the same thing as the previous definition: 

(define no-method #f)

(define (make-object-sugared name)
  (lambda (message)
    (case message
      ((object?) (lambda (self) #t))
      ((class) (lambda (self) 'object))
      ((name) (lambda (self) name))
      ((say)
        (lambda (self list-of-stuff)
          (if (not (null? list-of-stuff))
              (display-message list-of-stuff))
          'nuf-said))
      ((install) (lambda (self . args) 'installed))
      (else no-method))))
Question 2: For each of the Scheme expressions below, predict what they will evaluate to. Then, try evaluating them in your interactions window. Write an explanation that explains clearly why evaluate the way they do. In particular, if an expression evaluates to a procedure, you should explain what procedure it is.

a. (make-object 'book)
b. ((make-object 'book) 'name)
c. ((make-object 'book) 'fly)
d. (((make-object 'book) 'name) (make-object 'donkey))
e. (((make-object 'book) 'say) (make-object 'donkey) (list 'hello))
        Is the book talking or the donkey?
f. (eq? (make-object 'book) (make-object 'book))

Interacting with objects by calling them is awkward, so we want to define an ask procedure that sends a message to an object. You should be able to figure out these definitions yourself: 
(define (get-method object message)
  (object message))

;;; Send a message to an object (with optional arguments)
;;; (The ask in object.ss is a bit different to produce better error messages.)

(define (ask object message . args) ;;; The . args means to allow zero or
                                    ;;; more parameters here, and use
                                    ;;; args to refer to all of them.
  (apply (get-method object message) object args))
Question 3: The say method of make-object takes a list as its second parameter and says everything in that list. Instead of saying a whole list, we might want a method that says just one thing. Define an utter method of make-object that behaves like this:
> (define dog (make-object 'spot))
> (ask dog 'utter 'wuff)

wuff

You can use (display sym) to output one symbol. The output in this example would be produced by (display 'wuff).

Inheritance

Generic people, places and things are okay, but for an interesting game we need to have people and things that can do special things.

Our basic object (procedures produced by applying make-object) provides a say method:

> (define bill (make-object 'bill))

> (ask bill 'say '(to apply or to eval, that is the question))

(to apply or to eval, that is the question)

What if we have lots of different kinds of speakers and we want to make them speak different ways. For example, a lecturer is a kind of speaker, except that she can lecture as well as say. When lecturing, the lecturer follows every comment with “you should be taking notes”.

We can make a lecturer a special kind of object: 
(define (make-lecturer name)
  (let ((super (make-object name)))
    (lambda (message)
      (if (eq? message 'lecture)
	  (lambda (self stuff)
	    (ask self 'say stuff)
	    (ask self 'say (list "you should be taking notes")))
	  (get-method super message)))))
When a message is sent to an object created by make-lecturer, it first checks if the message is 'lecture. If it is, it evaluates to the procedure that lectures. If it is not, it evaluates (get-method super message) to get the method in the superclass. The name super is a place in the frame defined by the let (which desugars to lambda) that has the value of (make-object name).

Question 4: A professor is even more arrogant than a lecturer. Define a procedure (make-professor name) that produces a professor object. It should inherit from make-lecturer, so it will be able to respond to the lecture message. It should also have a method profess that is like lecturing, but precedes every statement with “it is intuitively obvious that”.

Your professor should work like this:

> (define ed (make-professor 'Evan-Davis))

> (ask ed 'profess (list "(lambda (n) ((lambda (f) (f f n)) (lambda (f k) (if (= k 1) 1 (* k (f f (- k 1))))))) is a familiar function"))

it is intuitively obvious that
(lambda (n) ((lambda (f) (f f n)) (lambda (f k) (if (= k 1) 1 (* k (f f (- k 1))))))) is a familiar function
you should be taking notes

nuf-said

> (ask ed 'lecture (list "smalltalk is cool"))

smalltalk is cool
you should be taking notes

nuf-said

> (ask ed 'name)

evan-davis

Note that the lecture method is inherited from lecturer and the name method is inherited from lecturer, which inherits it from object. Your make-professor procedure should fit on 8 or fewer reasonably short lines.

State

Objects package procedures and state. The method you added in Question 3 and the professor class you defined in Question 4 didn't use any state. Every time we do (ask ed 'lecture (list "smalltalk is cool")) the same thing should happen.

Recall the counter from Class 22 (March 15): 

(define (make-counter)
  (let ((count 0))
    (lambda (message)
      (if (eq? message 'reset) (set! count 0)
	  (if (eq? message 'next) 
	      (set! count (+ 1 count))
	      (if (eq? message 'how-many)
		  count)))))
  )
Remember that the let is just syntactic sugar for an application of a lambda.

The counter object packages the state count with the methods reset, next and how-many. We call places associated with objects instance variables. Each time we evaluate (make-counter) a new object is created. We call objects created by constructors instances of the class. Hence, (define mycounter (make-counter)) defines mycounter as an object that is an instance of the counter class. The object state variables are known as instance variables because they name a place associated with a particular instance of the class. That is, if we do: 

> (define counter1 (make-counter))
> (define counter2 (make-counter))
both counter1 and counter2 will be counter objects. Each will have its own frame, containing a place named count. Changing the value of the count place in the frame of counter1 will not change the value of the count place in the frame of counter2. Hence: 
> (ask counter1 'next)
> (ask counter2 'how-many)
0
More interesting objects in our game will need to use state to keep track of things that might change during an execution. Look at the make-person procedure defined in objects.ss. Its pretty long because a person has many methods. Here we show some of the code, but leave out some methods: 
(define (make-person name)
       ;; person inherits from mobile-object
  (let ((super (make-mobile-object name)) 
        ;; Instance variables
        (possessions '())  ;;; What the person is carrying (a list of Objects that are things
        (restlessness 0))  ;;; How likely the person is to move randomly
    (lambda (message)
      (case message
        ((person?) (lambda (self) #t))
        ((install) (lambda (self where)
		     (ask super 'install where)))
        ((get-possessions) (lambda (self) possessions))
        ... Other methods not shown
        (else (get-method super message))))))

A person has an instance variable possessions that is a list of objects the person is carrying (we'll get to the restlessness instance variable later). The method get-possessions can be used to see what a person is holding. Other methods use (set! possessions ...) to change the possesions a person is holding.

Question 5: A student is a special kind of person (this doesn't necessarily mean all students are special or kind). Define a procedure make-student that creates a student object. It should inherit from person.

Some of the students in Charlottansville have a strange habit of getting undressed and running around the Green, so students have an instance variable is-dressesed that indicates whether or not the student is clothed. Initally, all students are dressed. The get-undressed that changes the state of is-dressed to #f. A student also has a method get-dressed that changes the state of is-dressed to #t. A student also has a method is-dressed? that evaluates to #t if the student is dressed and #f otherwise.

Your student should work like this:

> (define alyssa (make-student 'alyssa-p-hacker))

> (ask alyssa 'is-dressed?)

#t

> (ask alyssa 'name)

alyssa-p-hacker

> (ask alyssa 'get-undressed)

At not-yet-installed: alyssa-p-hacker says -- brrrrr...its cold!

> (ask alyssa 'is-dressed?)

#f

> (ask alyssa 'get-dressed)

At not-yet-installed: alyssa-p-hacker says -- I feel much better now.

> (ask alyssa 'is-dressed?)

#t

Automating Objects

This kind of world doesn't make for a very challenging or interesting game. All the people and things only do what the player tells them to. For a more interesting game, we need to have people and things that act autonomously.

We do this by creating a list of all the characters to be moved by the computer and by simulating the passage of time with an world-clock object. The make-world-clock procedure (defined in objects.ss) creates a world-clock. It has two instance variables: global-time, for keeping track of the time, and clock-list for keeping track of the objects that should be sent clock-tick messages when the clock advances.

The methods add and remove that have object parameters and add or remove objects from the clock-list. When the clock receives a clock-tick message it means time has passed. It sends a clock-tick message to each object in its clock-list. This doesn't necessarily do something every time, but for some objects it will lead to an action.

In adventure.ss, we create a clock and add all objects installed using install-object to the clock: 

(define clock (make-world-clock))

(define (install-object object place)
  (ask object 'install place)
  (ask clock 'add object))
We can advance the clock by doing (ask clock 'tick).

People hang about idly until they get bored enough to do something. To account for this, we give people a restlessness instance variable that indicates how likely they are to get bored enough to move randomly. If restlessness is not #f, a person will move in a random direction with restlessness probability with each clock tick. For example, if restlessness is 1.0, the person will move randomly every clock tick. If restlessness is 0.5, the person will move half the time (but not necessarily every other tick, since the decision whether to move or not is random). If restlessness is 0.0, the person will not move randomly. A person object has a method make-restless that take a parameter and sets the restlessness instance variable to that value.

The University administration does not condone streaking, and has decided to strategically place police officers on the Green to apprehend streakers.

Question 6: Define a procedure make-police-officer that inherits from person. A police officer behaves differently from a person since a police office can arrest other people. So, it has an additional method:
  • (ask 'arrest Person) — A police officer can arrest a person if they are in the same place. The arrestee is sent to jail (you can do this with (ask Person 'move-to Jail)) and the police officer takes all of the arrestees. possessions.
The clock-tick method for a police officer should automatically arrest anyone streaking in the same place as the police officer. If no one is streaking, the police officer will act like a normal person — that is, it should invoke the super class (person) clock-tick method. You may find the other-people-at-place procedure (defined in objects.ss) useful.

Try playing the game to see that your police-officer works correctly. We have provided a procedure
   (play-interactively-as character)
that provides a better interface to playing the game. The play-game procedure (defined in ps6.ss) installs two students and one restless police officier in our world, and starts playing interactively as one of the students.

Here's what a typical game might look like:

> (play-game)

At not-yet-installed: alyssa-p-hacker says -- Installing alyssa-p-hacker at green
At not-yet-installed: ben-bitdiddle says -- Installing ben-bitdiddle at cdrs-hill
At not-yet-installed: officer-krumpke says -- Installing officer-krumpke at bart-statue
what now? > name
< Result: alyssa-p-hacker>
[Clock] Tick 1
At bart-statue: officer-krumpke says -- No one to arrest. Must find donuts.
officer-krumpke moves from bart-statue to steam-tunnel
officer-krumpke is no longer at bart-statue
what now? > get-undressed
At green: alyssa-p-hacker says -- brrrrr...its cold!
[Clock] Tick 2
At steam-tunnel: officer-krumpke says -- No one to arrest. Must find donuts.
ben-bitdiddle moves from cdrs-hill to cricket-street
what now? > look
At green: alyssa-p-hacker says -- I see nothing
At green: alyssa-p-hacker says -- I can go down west north south
< Result: ()>
[Clock] Tick 3
At steam-tunnel: officer-krumpke says -- No one to arrest. Must find donuts.
what now? > go north
alyssa-p-hacker moves from green to recursa
< Result: #t>
[Clock] Tick 4
At steam-tunnel: officer-krumpke says -- No one to arrest. Must find donuts.
officer-krumpke moves from steam-tunnel to bart-statue
ben-bitdiddle moves from cricket-street to cdrs-hill
what now? > go south
alyssa-p-hacker moves from recursa to green
< Result: #t>
[Clock] Tick 5
At bart-statue: officer-krumpke says -- No one to arrest. Must find donuts.
what now? > go south
alyssa-p-hacker moves from green to bart-statue
At bart-statue: alyssa-p-hacker says -- Hi officer-krumpke
< Result: #t>
[Clock] Tick 6
At bart-statue: officer-krumpke says -- alyssa-p-hacker, you are under arrest!
alyssa-p-hacker moves from bart-statue to jail
At bart-statue: officer-krumpke says -- You have the right to remain silent, call methods and mutate instance variables.
what now? > look
At jail: alyssa-p-hacker says -- I see nothing
At jail: alyssa-p-hacker says -- I can go
< Result: ()>
[Clock] Tick 7
At bart-statue: officer-krumpke says -- No one to arrest. Must find donuts.
officer-krumpke moves from bart-statue to green
what now? > quit
Better luck next time. Play again soon!

Decidability

Consider the streakability problem defined below:
Input: An initial state consisting of a set places in the Charlottansville world, a student object (as described in Question 5) and a police officer object (whose clock-tick method may contain any code).

Output: If there is any sequence of actions the student object can take to streak from the Recursa to the Bart Statue without getting arrested at any time during the game, output true. Otherwise, output false.

You should assume the results of random are completely determined (that is, you can always predict what an application of random evaluates to).

Question 7: Is the streakability problem decidable or undecidable? If you claim it is decidable, you should argue convincingly that you could define a procedure that solves it for all possible inputs. If you claim it is undecidable, you should argue convincingly that it is undecidable by showing how a solution to the streakability problem could be used to solve another problem that is already known to be undecidable.

Extensions

With a full command of message-accepting procedures, object-oriented programming, and inheritance, you are now ready to start making an addictive game. Keep in mind that, historically, computer games have been a colossal waste of time for humankind. As simple as this game is, it's easy to get lost (especially in the steam tunnels). Spend your time on the problems, not the game.

Question 8: Design a non-trivial extension to this simulated world. Use your imagination! You can do what you want (so long as it is in good taste, of course). (As you may have noticed, the course staff has a fairly liberal notion of "good taste", but if you aren't sure, its best to ask.)

A good extension will use inheritance to create new types of objects in your game. For example, you may want to create a new types of people, places and things that have new behaviors.

Your answer to this question should include:

  1. A short explanation of your extenstions that describes the objects you added.
  2. An inheritance diagram showing your new classes and the classes they inherit from.
  3. Code for all new procedures you write, or old procedures that you modify.
  4. A transcript that shows your game in action.

Now invite a friend over and teach them how to play. But, remember that this is a fictional world. Don't try anything from the game at home. If you do get a chance to visit Charlottansville, make sure to see Monty's Viola, the favorite instrument of the founder of the University and author of the influential 1976 treatise, The Ultimate Declarative, which led many Schemers to revolt.

Code Submission
Submit your final ps6.ss code using the form at http://www.cs.virginia.edu/cs200/ps/ps6/submit.html.

Credits: This problem set was developed by Portman Wills and David Evans for CS200 Spring 2002 and slightly revised for CS200 Spring 2003 by David Evans. Portman is solely responsible for all the streaking references, however. It is based on a problem set first used in MIT 6.001 Fall 1989, and subsequently in many other years including 1997, on which we based some of our code. The MIT version of the adventure game involved Deans smashing beer and party-troll's eating Deans. A course at UC Berkeley also had an adventure game problem set. Their acknowledgment was,
This assignment is loosely based on an MIT homework assignment in their version of this course. But since this is Berkeley we've changed it to be politically correct; instead of killing each other, the characters go around eating gourmet food all the time. N.B.: Unless you are a diehard yuppie you may feel that eating gourmet food does not express appropriate sensitivity to the plight of the homeless. But it's a start.
We like our Deans much more than they do at MIT, and UVA students don't eat much gourmet food. We thought about making our adventure game about eating Berkeley students, but were worried that might improve their student-faculty ratio and ruin our chances of ever surpassing them in the US News rankings.

CS 200


CS 200: Computer Science
Department of Computer Science
The University
Charlottansville, East Virginia

 cs200-staff@cs.virginia.edu
Using these Materials