MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Spring Semester, 1997
Problem Set 6
Issued: Tuesday, March 18, 1997
Due: In recitation on Friday, April 4 for recitations held at
9, 12, 1 and 2;
and on Wednesday, April, 2 for recitations held at 10 and 11.
Be careful to note this switch of wed-fri duedates
Reading: Through Section 3.3.3, plus attached code (objects.scm, world.scm, and game.scm).
Note: The overall object-oriented programming framework will be discussed in lecture on Thursday, March 20. and in the lecture notes for that day.
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 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 Thursday, March 20. In addition to the main objects of the simulation, the files objects.scm and game.scm define a number of other types of objects that 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 Thursday, March 20.
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 laziness 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.
(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*
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:
The second file, game.scm, contains the implementation of special-purpose objects that are part of our specific adventure game: our kind of persons and trolls, as well as the special location heaven. Finally, the third file, world.scm, contains code that initializes our particular imaginary world and installs jim, eric, and grendel.
(define make-inc ...) (define inc1 (make-inc)) (define inc2 (make-inc)) (inc1) -- 1 (inc1) -- 2 (inc2) -- 1 (inc1) -- 3 (inc2) -- 2
Assume that the following definitions are evaluated, using the procedure make-inc from the previous exercise:
(define inc! (make-inc)) (define thing1 (inc!)) (define (thing2) (inc!)) (define thing3 inc!) (define (thing4) inc!)
What is the value of each of the following expressions (evaluated in the order shown)?
thing1 thing2 thing3 thing4 (thing1) (thing2) (thing3) (thing4) thing1 (thing3) (thing2)
Consider the following code, taken from object.scm, very carefully:
(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))
Write a very short paragraph (no more than four sentences)
describing how this code works. You might look at the notes or past
problem sets for examples of good descriptive style; it should be
correct, concise, and complete. Your description should, in
particular, explain why one branch of code ends with me and
the other ends with (me message).
The lab is much easier to do if you have a complete list of the types of objects and the class structure (which object inherits from which other). Create a sheet with this information on it, bring it with you, and make a copy for your tutor. There are two ways to prepare this information, and the choice is yours. The first is to draw a table with rows for data types and columns for messages, with a check mark if an object of the data type can handle the message. You can alternatively draw a directed graph with data types for nodes, arrows for showing which type inherits from which other, and with each data-type indicating the messages it can handle by itself. In the latter case, the root of the tree would be named-object with messages NAMED-OBJECT?, NAME, SAY, and INSTALL.
The following exercises 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.
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 delegates an INSTALL message from its self to its internal mobile-object. The mobile-object's INSTALL method is responsible for adding the person to its birthplace. The relevant details of this situation are outlined in the code excerpts below:
(define (make-person name birthplace laziness)
;; Laziness determines how often the person will move
(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.
In one short paragraph (no more than five sentences) state when your code should delegate an action to an object rather than ask the object to perform that same action. There is a very specific, simple answer. You should be clear and concise in your written response. (Note: There is a one-sentence answer that is perfectly acceptable!)
When you load the code for problem set 6, 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 that you can invoke to act out the scenarios when testing your code. See the comments in world.scm for details.
You can inspect an environment structure using the show procedure from objects.scm. Show is a bit like the pp procedure for printing out procedures, but it prints things out so that they look more like parts of an environment diagram. It can be used like this:
(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]
Now you can inspect the environment of the procedure by calling show with the "hash number" of the environment. The hash number is the number after "compound-procedure" or "environment" in the usual printed representations of these objects. The system guarantees that all different (i.e. not eq?) objects have different hash numbers so you can tell if you get back to the same place.
(show 7) #[environment 7] Parent frame: #[environment 9] mobile-obj: #[compound-procedure 10] possessions: #f ;Value: #[unspecified-return-value]
This exercise is called meta-adventure because you are going to use the show procedure to explore and "map" the environment structure for eric and produce an environment diagram. Start with eric and follow all the hash numbers except those associated with direction names. There should be between 10 and 20 things to show. Print out the results and cut out the individual results. Arrange the pieces on a large blank piece of paper so that they are in the correct positions to make an environment diagram. Glue the pieces in place and draw in the arrows to make a complete environment diagram. Turn in your diagram. Warning: The environment in this game can get very large in a hurry. Thus we strongly suggest that you start with a clean Scheme system, and just load objects.scm, game.scm and world.scm, then answer this question. Be sure that *debugging-installation?* is set to #F.
After loading the system, make jim and eric move around by repeatedly calling clock (with no arguments).
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!)
One of the oft-proclaimed advantages of object-oriented programming is that you can re-use code easily by taking advantage of inheritance. This is typically done, as in Java, through the creation of subclasses derived from a class library. In our Scheme system, inheritance is done through a similar mechanism, called delegation
Take a look, carefully, at make-troll now. A troll is just like a person, but has a different way of ACTing and it can EAT-PERSON, which a normal person won't do. The fact that a troll should "do everything else just like a person" is encoded in the simple line
... (else (get-method message person))...
at the end of make-troll. This is one of the ways in which delegation takes place: when a troll is asked to produce a method for something it doesn't directly know how to do, it returns the method that belongs to the person it has created for this purpose. The other form of delegation occurs, for example, in the ACT method for the troll. Here, the troll explicitly calls delegate to ask its "inner person" to do the work.
Now imagine that we want to create a new kind of object, a rich-person. Basically, a rich person is just like any other person, except they don't walk from place to place -- they take cabs (we'll define a cab later; for now just think of it as a ":mobile place" -- a tasteful blend of mobile-object and a place). When a rich person decides to ACT, she starts hailing a cab and continues to do so until she manages to find one. Then she tells it where to go and stops hailing cabs until it's time to ACT again:
(define (make-rich-person name birthplace laziness)
(let ((my-poor-person (make-person name birthplace laziness))
(hailing? #F))
(install-shield
(lambda (message)
(case message
((RICH-PERSON?) (lambda (self) #T))
((HAIL-TAXI)
(lambda (self)
(set! hailing? #T)
(let ((taxis <find all taxis>)
(if (null? taxis)
'NO-TAXI-HERE
(let ((my-taxi (pick-random taxis)))
(let ((dest (pick-random *ALL-BUILDINGS*)))
<get in the cab, set the destination,
and stop hailing>
(ask self 'SAY
(list "Cabbie, take me to" (ask dest 'NAME)))
'FORWARD-HO!))))))
((ACT)
(lambda (self)
(if (is-a (ask self 'LOCATION) 'TAXI?)
'WAIT-TO-ARRIVE
(ask self 'HAIL-TAXI))))
((CLOCK-TICK)
(lambda (self)
(if hailing?
<stuff>
<more stuff>)))
(else (get-method message my-poor-person)))))))))
(define make&install-rich-person (installer make-rich-person))
Part A: (Note: you won't be able to test your code until you
complete Part C.)
Complete the definition of the CLOCK-TICK method by writing the expressions <stuff> and <more stuff>. <stuff> should simply arrange to have the HAIL-TAXI method be called, while <more stuff> should make the rich-person act like a normal person.
We've decided to build our taxi by first building an auto class. (We are being careful NOT to call it car because car is a necessary built in procedure and would really mess up cons pairs if we redefined it.) Both make-auto and make-taxi are included in the file game.scm. You should read the code for both carefully now. The most important single thing to notice is how we created that "tasteful blend" of a mobile-object and a place in make-auto.
Part B: Write down a list of all of the messages that a taxi will respond to, and state whether the method that handles the message comes from:Part C: Write the missing expression <find all taxis> and the expressions needed to <get in the cab, set the destination, and stop hailing>. Remember that you can only take a taxi that's empty (the mayor hasn't declared a state of emergency yet). If you find yourself writing more than 8 lines of code you will get no credit; it can be done in 4 lines or less if you think carefully about the problem.
Test your code by creating a rich-person and at least one taxi. You might want to make a very active rich-person. Then run the game for several rounds and watch the taxi wander around, the rich person hail it, the taxi take off and deliver the person (after even more wandering) to their destination. Turn in a transcript, remembering that your tutor will appreciate it if you make this as short and sweet as possible, and probably won't notice that you've omitted some of the clock ticks where nothing interesting happens...
Part D: On reflection, you may notice that a taxi awkwardly overrides some methods that are present in an auto. We've hidden this (sort of) by a bit of weak humor in the STOP and DRIVE methods of make-taxi. This situation crops up in "real" object-oriented systems, too, and it is a strong indication that the inheritance structure isn't quite right.
In our example, there are really two kinds of vehicles: those you can control, and those in which you are simply a passenger. Autos are examples of the first kind of vehicle. So are trucks (maybe), bicycles, motorcycles, and so forth. If you had the time (or if we thought you did...) the logical thing to do would be to create a vehicle class with two subclasses, controllable-vehicle and rideable-vehicle. Then you'd create auto and taxi classes that inherit from these.
But asking you to do all of that would be cruel. Instead, we'd like you to do the slightly easier task of creating a vehicle class that captures all of the behavior that is common to both our existing implementation of auto and of taxi but none of the behaviors that are peculiar to just one or just the other. Then write make-auto and make-taxi so that the inherit from this "generic" vehicle.
Hint: Create a list with all of the messages you mentioned in part B. For each message, indicate whether or not the message should be accepted by an auto, a taxi and/or a vehicle in the new structure (remember that a taxi should not accept the STOP and DRIVE messages in your new system). Then, for each message that can be accepted by a taxi, indicate whether the method comes from the taxi or is inherited from vehicle in the new structure (it can't come from an auto anymore, since taxi won't inherit from auto!). Repeat this, but assuming the message is sent to an auto. This new list should tell you precisely which messages are handling in each of the new classes make-vehicle, make-auto, and make-taxi.
Part E (extra credit): Java has a concept of an "abstract class." How does this relate to the work described in Part D? Write a short paragraph explaining whether or not the Java implementation of a vehicle should be an abstract class, and what that would imply.
Part F (more extra credit): Unlike most other object-oriented programming systems, our system allows a subclass to completely erase a method that it would otherwise inherit from its parent class. That is, objects of the subclass act as though the message were completely unimplemented by the new class. What would you do to completely remove the STOP method for the make-taxi procedure in game.scm (before you did the work in Part D)? Hint: you'd replace the ... in ((STOP) ...) with a very simple expression.
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:
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.