Department of Electrical Engineering and Computer Science
6.001 -- Structure and Interpretation of Computer Programs

Issued: ***fix***

Written solutions due: ***fix*** for EVEN numbered sections; ***fix*** for ODD numbered sections.

Note: The overall object-oriented programming framework will be discussed in lecture on ***fix***.

The programming assignment for this week explores two ideas: the simulation of a world in which objects are characterized by collections of state variables, and the use of object-oriented programming as a technique for modularizing worlds in which objects interact. These ideas are presented in the context of a simple simulation game like the ones available on many computers. Such games have provided an interesting waste of time for many computer lovers. In order not to waste too much of your own time, it is important to study the system and plan your work before coming to the lab.

This problem set begins by describing the overall structure of the simulation. The tutorial exercises in part 2 will help you to master the ideas involved. There is also a written homework exercise that you should do before coming to lab.

The overall object-oriented programming framework ***fix*** discussed in lecture on ***fix*** and in the lecture notes for that day.

Part 1: The 6.001 Adventure Game

The basic idea of simulation games is that the user assumes the role of a character in an imaginary world inhabited by other characters. The user plays the game by issuing commands to the computer that have the effect of moving the character about and performing acts in the imaginary world, such as picking up objects. The computer simulates the legal moves and rejects illegal ones. For example, it is illegal to move between places that are not connected (unless you have special powers). If a move is legal, the computer updates its model of the world and allows the next move to be considered.

Our game takes place in a strange, imaginary world called MIT, with imaginary places such as a computer lab, Building 36, and Tech Square. In order to get going, we need to establish the structure of this imaginary world: the objects that exist and the ways in which they relate to each other.

All objects in the system are implemented as message-accepting procedures, as described in lecture on ***fix***. In addition to the main objects of the simulation, the files objects.scm and game.scm define a number of other types of objects which are needed to construct our imaginary world. This is analogous to the "class library" that comes with most object-oriented development environments.

Initially, there are three procedures for creating objects:

  (make-place  name)
  (make-thing  name place)
  (make-person name birthplace restlessness)

In addition, there are procedures that make people, places and things and install them in the simulated world. The reason that we need to be able to create things separately from installing them will be discussed in one of the exercises later. For now, we note the existence of the procedures

  (make&install-place name)
  (make&install-thing  name place)
  (make&install-person name birthplace threshold)

Each time we make (or make and install) a person, place or a thing, we give it a name. People and things also are created at some initial place. In addition, a person has a restlessness factor that determines how often the person moves. For example, the procedure make&install-person may be used to create the two imaginary characters, jim and eric, and put them in their places, as it were.

  (define  jim-office (make-place  'jim-office))
  (define eric-office (make-place 'eric-office))

  (define  jim (make&install-person  'jim  jim-office 3))
  (define eric (make&install-person 'eric eric-office 2))

All objects in the system are implemented as message-accepting procedures, as described in lecture on ***fix***.

Once you load the system in the laboratory, you will be able to control jim and eric by sending them appropriate messages. As you enter each command, the computer reports what happens and where it is happening. For instance, imagine we had interconnected a few places so that the following scenario is feasible:

(ask jim 'look-around)
At jim-office : jim says -- I see nothing 
;Value: #f

(ask (ask jim 'location) 'exits)
:Value: (up down)

(ask jim 'go 'down)
jim moves from jim-office to tech-square 
;Value: #t

(ask jim 'go 'south)
jim moves from tech-square to building-36 
;Value: #t

(ask jim 'go 'up)
jim moves from building-36 to computer-lab 
;Value: #t

(ask eric 'look-around)
at eric-office : eric says -- I see nothing 
;Value: #f

(ask (ask eric 'location) 'exits)
;Value: (down)

(ask eric 'go 'down)
eric moves from eric-office to jim-office
;Value: #t

(ask eric 'go 'down)
eric moves from jim-office to tech-square
;Value: #t

(ask eric 'go 'south)
eric moves from tech-square to building-36 
;Value: #t

(ask eric 'go 'up)
eric moves from building-36 to computer-lab 
At computer-lab : eric says -- hi jim 
;Value: #t

In principle, you could run the system by issuing specific commands to each of the creatures in the world, but this defeats the intent of the game since that would give you explicit control over all the characters. Instead, we will structure our system so that any character can be manipulated automatically in some fashion by the computer. We do this by creating a list of all the characters to be moved by the computer and by simulating the passage of time by a special procedure, clock, that sends a clock-tick message to each creature in the list. A clock-tick message does not automatically imply that the creature receiving it will perform an action. Rather, like all of us, creatures hang about idly until they get bored enough to do something. To account for this, the third argument to make-person specifies the average number of clock intervals that the person will wait before doing something (the restlessness factor).

Before we trigger the clock to simulate a game, let's explore the properties of our world a bit more.

First, let's create a computer-manual and place it in the computer-lab (where jim and eric now are).

(define computer-manual (make&install-thing 'computer-manual computer-lab))

Next, we'll have jim look around. He sees the manual and eric. The manual looks useful, so we have jim take it and leave.

(ask jim 'look-around)
At computer-lab : jim says -- I see computer-manual eric 
;Value: (computer-manual eric)

(ask jim 'take computer-manual)
At computer-lab : jim says -- I take computer-manual 
;Value: #t

(ask jim 'go 'down)
jim moves from computer-lab to building-36 
;Value: #t

Eric had also noticed the manual; he follows jim and snatches the manual away. Angrily, jim sulks off to the EGG-Atrium:

(ask eric 'go 'down)
eric moves from computer-lab to building-36 
At building-36 : eric says -- Hi jim 
;Value: #t

(ask eric 'take computer-manual)
At building-36 : jim says -- I lose computer-manual 
At building-36 : jim says -- yaaaah! I am upset! 
At building-36 : eric says -- I take computer-manual 
;Value: #t

(ask jim 'go 'west)
jim moves from building-36 to egg-atrium
;Value: #t

Unfortunately for jim, beneath the EGG-Atrium is an inaccessible dungeon, inhabited by a troll named grendel. (Rumors that Grendel is a former 6.001 lecturer are wholly unfounded!) A troll is a kind of person; it can move around, take things, and so on. When a troll gets a clock-tick message from the clock, it acts just like an ordinary person -- unless someone else is in the room. When grendel decides to act, it's game over for jim:

(ask grendel 'clock-tick)
grendel moves from dungeon to egg-atrium 
At egg-atrium : grendel says -- Hi jim
;Value: #t

After a few more ticks, grendel acts again:

(ask grendel 'clock-tick)
At egg-atrium : grendel says -- Growl.... I'm going to eat you, jim 
At egg-atrium : jim says -- 
                   Grendel, now be still,
                   I kill'd not thee with half so good a will. 
jim moves from egg-atrium to heaven 
At egg-atrium : grendel says -- Chomp chomp. jim tastes yummy! 
;Value: *burp*

Implementation

The simulator for the world is contained in three files, which are attached to the end of the problem set. The first file, objects.scm, contains the basic object system:

• Procedures for extracting methods from objects, delegate-ing methods to other objects, and asking objects to perform actions.
• Procedures for handling the install messages.
• Procedures to implement the simplest objects (a "class library for adventure games").
• Procedures related to the clock.
• General utility procedures.

Part 2: Preparing for tutorial

Tutorial exercise 1:

1. Write a single define expression which defines a procedure inc! (with no parameters) that returns 1 the first time it is called, 2 the second time it is called, 3 the third time, 4 the fourth time, and so on. It should not depend on the values of any variables other than + (the procedure that does addition).
2. Now, define a procedure make-inc! that can be used to generate procedures that have the same behavior as inc! from part (1). That is, if you had written make-inc! before doing part (1), you could have implemented inc! as (define inc! (make-inc!)). It is important that each procedure created by calling make-inc! creates an independent incrementer -- the value of calling one of them does not depend on calling another.
3. Draw an environment diagram to illustrate the result of evaluating the following sequence of expressions. It should show the environment as it exists at the end of evaluating all these expressions.

   (define make-inc! ...)
   (define inc1 (make-inc!))
   (define inc2 (make-inc!))
   
   (inc1) --> 1
   (inc1) --> 2
   (inc2) --> 1
   (inc1) --> 3
   (inc2) --> 2
   

Tutorial exercise 2:

(define inc! (make-inc!))
(define inc1 (inc!))
(define (inc2) (inc!))
(define inc3 inc!)
(define (inc4) inc!)

inc1
inc2
inc3
inc4
(inc1)
(inc2)
(inc3)
(inc4)
inc1
(inc3)
(inc2)

Tutorial exercise 3:

(define (install-shield me)
  ;; The input, ME, is the core of an object (i.e. a procedure that
  ;; accepts a message telling it what to do and returning a method
  ;; for doing it).  INSTALL-SHIELD returns the actual object that
  ;; will do the work.  It just tests to see if the message is INSTALL
  ;; or not, and makes sure that the installation happens once and
  ;; only once.
  (if *Debugging-Installation?*
      (let ((installed? #F))
	(lambda (message)
	  (if (eq? message 'INSTALL)
	      (if installed?
		  (lambda (self)
		    (error "Already installed" me))
		  (set! installed? #T))
	      (if (not installed?)
		  (lambda (self . args)
		    (error "Not installed yet" me))
		  'OK))
	  (me message)))
      me))

Tutorial exercise 4:

Part 3: Pre-lab exercise

The following exercise should be written up and turned in at recitation. We suggest that you do them before coming to the lab, because it will alert you to a bug that is very easy to trip over when designing new kinds of objects.

(Pre)-lab exercise 1

Note how install is implemented as a method defined as part of physical-object and person. Notice that the person version puts the person on the clock list (this makes them "animated") then invokes the mobile-object version on self, which makes the birthplace where self is being installed aware that self thinks it is in that place. That is, it makes the self and birthplace consistent in their belief of where self is. The relevant details of this situation are outlined in the code excerpts below:

(define (make-person name birthplace threshold)
  (let ((mobile-obj (make-mobile-object name birthplace)) ...)
    ...
       (case message
         ...
	 ((INSTALL)
	  (lambda (self)
	    (add-to-clock-list self)
	    (delegate mobile-obj self 'INSTALL))) ; **
            ...)))

(define (make-physical-object name location)
  (let ((named-object (make-named-object name)))
    ...
	(case message
	  ((INSTALL)
	   (lambda (self) ; Install: synchronize thing and place
	     (let ((my-place (ask self 'LOCATION)))
             ...
       		   (begin
		     (ask my-place 'ADD-THING self)
                     (delegate named-object self 'INSTALL)))))
    ...))

Louis Reasoner suggests that it would be simpler if we change the last line of the make-person version of the install method to read:

               (ask mobile-obj 'install) ))   ; **

Alyssa P. Hacker points out that this would be a bug. "If you did that," she says, "then when you make&install-person Jim and Jim moves to a new place, he'll thereafter be in two places at once! The new place will claim that Jim is there, and Jim's place of birth will also claim that Jim is there."

What does Alyssa mean? Specifically, what goes wrong? You may need to draw an appropriate environment diagram to explain carefully.

(Pre-)lab exercise 2

Part 4: Lab Work

When you load the code for problem set 7, the system will load the files objects.scm and game.scm. The system will also set up a buffer with world.scm but will not load it into Scheme. Since the simulation model works by data mutation, it is possible to get your simulated world into an inconsistent state while debugging. To help you avoid this problem, we suggest the following discipline: any procedures you change or define should be placed in a new answer.scm file; any new characters or objects you make and install should be added to world.scm. This way, whenever you change some procedure you can make sure your world reflects these changes by simply reloading answer.scm and then world.scm file. Finally, to save you from retyping the same scenarios repeatedly -- for example, when debugging you may want to create a new character, move it to some interesting place, then ask it to act -- we suggest you define little test "script procedures" at the end of world.scm which you can invoke to act out the scenarios when testing your code. See the comments in world.scm for details.

Lab exercise 4: Meta-adventure

(show eric)
#[compound-procedure 6]
Frame:
  #[environment 7]
Body:
  (lambda (message)
    (cond ((eq? message ...) (lambda ... true))
          ((eq? message ...) (lambda ... ... ...))
          ((eq? message ...) (lambda ... possessions))
          ...))
;Value: #[unspecified-return-value]

(show 7)
#[environment 7]
Parent frame: #[environment 9]
mobile-obj:   #[compound-procedure 10]
possessions:  #f
;Value: #[unspecified-return-value]

Lab exercise 4:

After loading the system, make jim and eric move around by repeatedly calling clock (with no arguments).

• Which person is more restless?
• How often do both of them move at the same time?

Lab exercise 5:

Make and install a new character, yourself, with a high enough threshold (say, 100) so that you have "free will" and are not likely to be moved by the clock. Place yourself initially in the dormitory. Also make and install a thing called late-homework, so that it starts in the dormitory. Pick up the late-homework, find out where eric is, go there, and try to get eric to take the homework even though he is notoriously adamant in his stand against accepting tardy problem sets. Can you find a way to do this that does not leave you upset? Turn in a list of your definitions and actions. If you wish, you can intersperse your moves with calls to the clock to make things more interesting. (Watch out for grendel!)

Lab exercise 6:

Lab exercise 7:

For the rest of the problem set, you are on your own. We'd like to you design some non-trivial extension to this simulated world. The simulation can be as elaborate as you like. But don't go overboard -- this is meant to be a problem set, not a term project.

It's good to make your simulation revolve around some sort of theme. For example, you might want to pick a theme that involves some salient feature of the MIT environment, such as Food Services or Project Athena.

Whatever you choose to do, your simulation should include at least two new kinds of persons, places, or things, and at least one of these should have yet another kind of object that inherits from it. For example, you might implement a classroom as a new kind of place, and a lecture-hall as a kind of classroom. Your new objects should have some special methods or special properties in relation to other objects. For example, you might make new kinds of people called students, who go to sleep when they enter lecture halls.

In answering this problem, you should turn in:

1. One or two paragraphs, explaining the "story" behind your simulation. Describe your new objects and their behaviors. Say what kinds of things the simulation is meant to illustrate.
2. An inheritance diagram, extending the one you did for tutorial exercise 1, that shows your new kinds of objects and their methods.
3. Listings of any new procedures you write, or old procedures that you modify.
4. An annotated transcript that shows your simulation in action.

Prizes will be awarded for the cleverest ideas turned in for this problem set. Note that it's more impressive to implement a simple, elegant idea, than to just amass tons of new objects and places.