Collaboration Policy - Read Carefully

We will follow a similar collaboration policy as with Problem Set 5:

If you wish to work on this assignment alone or with any one student of your choice, you need to send me an email by 11:59 pm, Thursday, 20 October containing who you want to work with (or that you want to work along), and your answer to Question 4. (As long as you send evidence of a reasonable effort, you will be permitted to work with your selected partner or alone. It doesn't matter if your answer is correct.) Please use PS6 Request as the subject line for your message.

If you don't send me such an email, you will be arbitrarily assigned a partner for PS6.

Regardless of whether or not you have a partner for the problem set, 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.

• Program with objects
• Develop and use methods
• Understand and use inheritance
• Reason about the computability of a (semi-)practical problem
• Make an adventure game

Background

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.

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

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:

• (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 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:

• (ask Object Message Arguments) — invoke the method identified by Message on the Object. The Arguments may be zero of more arguments to the method. These are passed to the method as parameters.

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

(define Cabal-Hall (make-place 'Cabal-Hall))
(define Bart-Statue (make-place 'Bart-Statue))      

    (can-go-both-ways Bart-Statue 'south 'north Cabal-Hall)

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

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

Defining Objects

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

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

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

Inheritance

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

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

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

State

Recall the counter from Class 20:

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

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

> (ask counter1 'next)
> (ask counter2 'how-many)
0

(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

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

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

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.

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

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

Credits: This problem set was developed by Portman Wills and David Evans for CS200 Spring 2002 and slightly revised for CS200 Spring 2003 and CS150 Fall 2005 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 150: Computer Science Department of Computer Science The University Charlottansville, East Virginia	cs150-staff@cs.virginia.edu Using these Materials