cs150  Spring 2009

classes book syllabus ps exams guides forum

---

---

Problem Set 6: Adventures in Charlottansville

Collaboration Policy - Read Carefully

If you wish to be assigned a partner for this assignment, send me an email by 11:59 pm, Thursday, 12 March. Otherwise, you may work on this assignment alone or with one partner of your choice.

Regardless of whether or not you have a partner for the problem set, for the final question, you may combine efforts with as many students as you wish.

You may consult any outside resources, including books, papers, web sites and people, you wish except for materials from previous CS150 courses. You may consult an outside person (e.g., another friend who is a CS major but is not in this class, or a CS prof, etc.) who is not a member of the course staff, but that person cannot type anything in for you and all work must remain your own. That is, you can ask general questions such as "can you explain recursion to me?" or "how do lists work in Scheme?", but outside sources should never tell you what to type. If you use resources other than the class materials, lectures and course staff, define a sources list to indicate what you used and what you learned — as in this example:

(define sources (list "seymour cray, my roommate, explained parallelism"
"I found the shortest-path algorithm on Wikipedia"
"I asked Professor Robins about divide and conquer"))

You are strongly encouraged to take advantage of the Structured Lab Hours, Staffed Lab Hours and Office & Lab Hours for this course.

Purpose

• Understand an object system
• Learn how to program with objects
• Develop and use methods
• Understand and use inheritance
• Reason about the computability of a (semi-)practical problem
• Make an entertaining adventure game

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

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.

Objects

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, so we will need classes that implement each kind of object.

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 (see Chapter 11) for names. The three constructors are:

• (make-place name) — create a place object with the name symbol. Places cannot move.
• (make-thing name) — create a thing object with the name name. Things can move and act, but they are not sentient.
• (make-person name) — create a person object with the name name.

To put a new thing or person in our fictional world, we must install it in a place. The procedure install-object takes two parameter, an object and a place, and installs the object in the place.

• (install-object object place) — installs the object passed as the first parameter in the place passed as the second parameter.

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

• (ask object message operands) — invoke the method identified by message on the object. The operands is zero of more operands to the method. These are passed to the method as parameters.

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

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.

• (ask Person 'look) — Report on the immediate surroundings.
• (ask Person 'say String) — Say the words in the String (something in double quotes) parameter.
• (ask Person 'have-fit) — Throw a temper tantrum.
• (ask Place 'exits) — Report the directions you can move from a given place.
• (ask Person 'go Direction) — Move in the indicated direction. The Direction is a symbol such as 'north, 'west, 'up or 'down (the valid directions depend on the place the person is currently).

In adventure.scm we define some places in our imaginary world. The procedure set-up-charlottansville 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-charlottansville, 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.scm 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

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

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

> (install-object JT Cabal-Hall)

Installing jeffus-thomerson at cabal-hall

installed

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

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

> (install-object sandwich Cabal-Hall)

Installing sandwich at cabal-hall

installed

> (ask JT 'look)

At cabal-hall: jeffus-thomerson says -- I see sandwich
At cabal-hall: jeffus-thomerson says -- I can go down north

(sandwich)

> (ask JT 'take sandwich)

At cabal-hall : jeffus-thomerson says -- I take sandwich

#t

Try playing the adventure game. Load ps6.scm 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-sim-object creates a new object. Here is make-sim-object without using any syntactic sugar:

(define make-sim-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))
			(void))
		      (if (eq? message 'install)
			  (lambda (self . args) 'installed)
			  #f))))))))

The name make-sim-object refers to a procedure that takes one parameter, name. It evaluates to a procedure that takes one parameter, message.

All those (if (eq? ...)) expressions in make-sim-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-sim-object — it means exactly the same thing as the previous definition:

(define (make-sim-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))
          (void)))
      ((install) (lambda (self . args) 'installed))
      (else #f)))) ;; no method defined for message

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 zero or more arguments)

(define (ask object message . args)
  (apply (get-method object message) object args))

(Note: the ask procedure in object.scm is a bit different to produce better error messages.)

Inheritance

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

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

> (define bill (make-sim-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)
  (make-sub-object
   (make-sim-object name)
   (lambda (message)
     (if (eq? message 'lecture)
         (lambda (self stuff)
           (ask self 'say stuff)
           (ask self 'say (list "you should be taking notes")))
	 #f))))

See Chapter 11 for an explanation of the make-sub-object procedure. When a message is sent to an object created by make-lecturer, the implementation procedure checks if the message is 'lecture. If it is, it evaluates to the procedure that lectures. If it is not, it evaluates to #f, and the superclass method is found.

Your professor should work like this:

> (define ww (make-professor 'Weim-Wesser))

> (ask ww '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

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

smalltalk is cool
you should be taking notes

> (ask ww 'name)

weim-wesser

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

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.scm. 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)
  (make-sub-object (make-mobile-object name))
  (let ;; 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 #f))))))

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 possessions a person is holding.

Your student should work like this:

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

> (install-object alyssa Green)

Installing alyssa-p-hacker at green

added

> (ask alyssa 'is-dressed?)

#t

> (ask alyssa 'name)

alyssa-p-hacker

> (ask alyssa 'get-undressed!)

At green: alyssa-p-hacker says -- Brr! It's cold!

> (ask alyssa 'is-dressed?)

#f

> (ask alyssa 'get-dressed!)

At green: 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.scm) creates a world-clock object. 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.scm, 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.

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

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.

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 (or on the green). 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.

[an error occurred while processing this directive]