CS212Structure and Interpretation
of Computer Programs
CS212Contents:
As usual, for these problems, please turn in
Failure to follow these instructions will result in loss of points.
For this exercise, refer to your notes regarding the environment model rules.
Consider the following function:
(define mystery
(method ((i <integer>))
(bind (((x <integer>) (* i 2))
((f <function>) (method ((i <integer>)) (+ i x))))
(set! x (* i 3))
(bind (((x <integer>) (* i 4)))
(f x)))))
A. What does (mystery 3) return? Determine this by tracing the call with the environment model. Hand in the environment model diagram for the point in time when (+ i x) is computed, and use this diagram to briefly justify your first answer.
To give you an idea of what this looks like, here is a sample diagram with the first few frames added:
B. The first part of our current APPLY rule is as follows:
Create a new environment by adding a new frame to the environment that is part of the procedure being applied.
Suppose we change this to
Create a new environment by adding a new frame to the environment in which we are calling the procedure.
Under these new rules, what does (mystery 3) return? Again, briefly justify your answer.
The operations
(head-setter v p) (tail-setter v p)
are effect-only functions that respectively set the head/tail of pair p to value v. (Contrast this with cons, which creates and returns a completely new pair.) For example, suppose x = (1 2 3) and y = (7 8 9). After (tail-setter (tail x) y), the tail part of y points to the same thing as the tail part of x. Thus y now evaluates to (7 2 3). We now define a new kind of structure, the chain. A chain is a list of elements in which the tail of the last element points to the first element. For example, z is a chain of length 4:
A. Write a function make-chain! that takes a non-empty list and makes it into a chain.
Warning: Be careful with your new data structure. Dylan does not attempt to recognize circular chains, and many list functions will be useless for dealing with them.
In the next two problems, use the type specifier <chain> for chains. Assume all chains are non-empty.
B. Write a function chain-length that takes a chain and returns its length; that is, the number of pairs that make up the chain.
C. Consider this equality function for chains:
(define (chain-equal-maybe? <method>)
(method ((c1 <chain>) (c2 <chain>) (remaining <integer>))
(cond ((= 0 remaining) #t)
((not (= (car c1) (car c2))) #f)
(else:
(chain-equal-maybe? (cdr c1) (cdr c2) (- remaining 1))))))
One obvious problem is that this function only compares a certain number of elements before returning #t. The caller would need to determine and pass in a sufficiently large third argument.
The second problem is the following. Because chains are circular, the notion of a ``first'' element is really not so important. (Consider rotating a necklace of beads; it remains the same necklace no matter which bead is on top.)
We'll say that two chains are equal if they contain equal items in the same order, regardless of which items are first in the chains. For example, the result of (make-chain '(1 2 3)) is equal to the result of (make-chain '(2 3 1)). Also note that c is equal to (tail c) for any chain c.
Using chain-equal-maybe? as a helper function, write a function chain-equal? that takes two chains and returns #t iff they are equal by our new definition. (Note: you must use the helper function exactly as provided.)
The purpose of this programming assignment is to gain experience with the use of advanced object-oriented programming techniques. We will develop a substantial application in which we will draw heavily on technology developed in previous problem sets and handouts:
In addition, we will make significant use of some powerful new techniques:
Most of the code for this assignment is given to you in ps5.dyl. It is a bit longer than the code for the previous assignments, but don't be intimidated by its length--you have seen most of the ideas before in previous problem sets, so it should be familiar.
As in Problem Set 1, the last problem is optional and open-ended. This problem will not be graded, but a prize will be given for the best solution as judged by the course staff.
If you believe that you've found a bug in ps5.dyl, send us (cs212@cs.cornell.edu) a description of the bug and the corrected code. You will probably receive some extra credit for bugs you've fixed.
The game takes place on an 8-by-8 grid known as the *main-board* (Note: by convention, all non-function global variables have asterisks around them. You are expected to follow this convention.) The top left corner of board (0, 0) and the bottom right corner (7, 7) are cities in competition, called "London" and "Paris" respectively.
The goal in the game is to increase the size of your city, while decreasing the size of the competing city. The largest city wins. By default, you are London, and the computer is Paris, but you will be asked to change this in the course of the problem set. The game ends when the time you have allotted for the game has been used up, or one city is completely dead.
The main objects you will work with in the game are builders and attackers. Each city will build its walls, as well as airplane and tanks. Once objects are built, the city will be able to send them to attack the other city, or even other airplanes and tanks.
There are two ways of starting the game. The function (start-game) will set up the world, initialize the cities, and play the game for 100 "days". There is also a function called (play-game! n) which will play the initialized game for n "days". If you would like to continue the game which has just finished, you can call play-game! again (do not call start-game!, since that will rebuild the world.) Note: In order for play-game! to work, you need to initialize the world first, by either calling start-game or by calling init-game!. Both start-game and init-game! will ask you which cities you wish to play interactively (which gives you finer control over your city). Just type in a list with the names of the cit(ies) you want to control in quotes. (ex. ("London"))
The game will not work until you have done Problem 1. In addition, you will be implementing the interactive capabilities. Once you have done the first two problems you will be able to start playing the game.
Now we will go over the organization of the program ps5.dyl section by section. You should have access to an online or printed copy of the program to refer to while you are reading this. Not everything is documented here, so you should read the code after you've read these explanations.
Lots of different constants are defined in the beginning on the ps5.dyl. Feel free to redefine them if you think it can make the game better. You may have to reinitialize the game after redefining the constants
There is a fairly extensive class hierarchy consisting of the following classes:
Each class represents a collection of objects with common properties and has an associated set of slots:
The world is represented by a two-dimensional vector of <place>s indexed pair of coordinates each ranging from 0 to *brd-size*. The top left corner of board (0, 0) and the bottom right corner (7, 7) are cities in competition, with "owners" set to *london* and *paris*, respectively. You can read the location at coordinates x,y by calling (board x y), and you can change the location at coordinates x,y to place by calling (set-board! x y place). Both functions will produce an error message if coordinates are out of range.
The event loop works like this: as long as there are events to be processed, and time has not run out, the event loop will continue to process events, otherwise, it will end the game. On each recursion step run-game! takes the earliest event from the queue, sets the *date* to the date of that event, processes the event and (tail-)recurses.
(define (run-game! <function>)
(method ((game-length <number>))
(if (= (index *events* 0) 0)
(end-game #f)
(bind (((next <event>) (extract-min! *events*))
((next-date <number>) (date next)))
(if (> next-date game-length)
(begin
(prioq-insert! *events* next)
(end-game #t))
(begin (set! *date* next-date)
(process-event next (target next))
(run-game! game-length)))))))
The event queue is implemented as a heap. A heap is basically an ordered binary tree. In this case, any given parent has a date smaller than or equal to its two children. All objects in our priority queue (of type <prioq>) are of type <event>, which, you should recall, has a slot for date.
Look carefully at the code for priority queues, and make sure you understand it. Notice that we are storing all of the events in a vector. The first item in the vector is the total number of objects in the heap. It starts out as zero, because we have not yet inserted anything.
prioq-insert! puts the new item into the last place on the tree, then "pushes" it up so that it is in a legal position. In other words, pushes the item up until the tree is once again a heap. The binary tree is only considered a heap if it satisfies the heap property, meaning that every given node has a date less than its two children. push-up! compares a node with its parent, and swaps them if the node has a smaller value than the parent.
extract-min! takes out the "top" node of the heap, also known as the "root". Since there is now a hole there, it must be filled, so we take the last element of the heap and stick it on top. Obviously, unless all of the events have the same date, the tree now violates the heap property, so we must push the event down using push-down! until the heap property is satisfied. This involves comparing the node with its two children, and placing the smallest of the three on the top. This must be repeated until the parent node is the smaller than the two children before switching them.
You will be using push-down! and push-up! in Problem 1. Be sure to ask questions if you don't understand.
The event queue (*events*) contains the <event>s for everything that happens during the game: moving, attacking, producing new units, walls, etc. To execute the event, the event-loop calls the generic function process-event. process-event dispatches on the type of the event as well as the receiver of the event, the target.
This is the type hierarchy for <event>s
Each time the events is processed the next event for the same target is inserted (unless the target is already destroyed), so we usually have one event in the queue for each unit (either <move-event> or <attack-event>) and two events for each city (<city-grow-event> and either <build-event> or <wall-event>). The processing of each of the events is described in sections below.
When a <move-event> is processed, its target unit makes a move to one of four adjacent locations (according to its strategy or randomly towards the enemy city). Once the direction of the move (x,y) is determined, unit is removed from its old location using (remove-unit! unit) and (move-unit-to! unit x y) is called. move-unit-to! :
The combat takes place whenever an army unit tries to enter the place occupied by enemy units or a place that is an enemy city. If both sides survive the combat, a new <attack-event> with the original attacker as target (the slot name is a little bit confusing here) is scheduled in *attack-time* days.
The combat consists of several attacks when some attacker attacks some defender. Each of these attacks is completed by a function make-attack!. make-attack! :
During the combat:
When <city-grow-event> is processed, the city size is increased by 1 and
a next <city-grow-event> is scheduled in
(/ *city-time* (size city)) days.
When <wall-event> is processed, the wall size is increased by 1 and choose-new-task is called
When <build-event> is processed, the new <army-unit> is created, the unit immediately makes a move and than choose-new-task is called
Choose-new-task chooses what city is going to build next - a wall, an air corps or a tank corps. When the choice is made, the new event (<wall-event>, <build-event> or <build-event>) is scheduled in (/ *city-time* (size city)), (/ *city-time* (size city)) or (/ *city-time* (size city)) days, respectively
Principle: heap manipulations
When a unit gets destroyed, we would like to remove it from the game. This is done in the function kill-unit!. Currently, the function remove-unit! handles correctly all the membership issues (it erases the item from the troops of its location), but clearly that is not enough. There may still be some events in the event queue which belong to the object which was just destroyed. These events need to be removed from the heap, otherwise when they will get processed the destroyed unit will come back to life.
In this part, you are supposed to modify the procedure prioq-remove! which takes a <prioq> data and a <unit> unit, and removes from the queue all the events which are addressed to unit. You may find some of the helper functions in the heap section extremely useful for this section. You should be careful - you should remove all events which are addressed to unit, not to some unit equal to unit (different units of the same type may be stationed at the same location and have the same speed and strength, but they are still two different units).
For this problem, hand in the code for prioq-remove!, and sample output
showing that events addressed to a particular object actually are removed from the event
queue.
You may want to test you soultion using our test code.
Principle: Generic Functions
Currently, interactive cities just repeatedly build and send out tanks. Of course, that is not much fun -- interactives should actually be interactive! Modify the generic function choose-new-task for interactive cities so that it reads in the user command and does that task. You will want to take out the last two lines from the code below and replace it with your code. You will also need to add methods to the generic function command.
(add-method choose-new-task
(method ((city <interactive-city>))
(print-board)
(princ (owner city))
(princ "? ")
(print "(tank)")
(command 'tank city)))
Interactive characters should accept the following commands:
Submit a listing of all code that you write or modify, and sample output showing your using the interactive functions. Make sure you look through all of the code we provide, as the code we provide will be very useful in doing this problem.
Principle: Object Oriented Programming, next-method
So far, all you can do is decide what to build. Although that is better than what you could originally do, it is still pretty boring. All the troops you build do is head towards the city randomly, and attack whatever they encounter on the way. Modify the command interpreter (Problem 2) so that you can give the tank-corps strategies as you build them.
Add new methods to make your tank-corps behave accordingly. One of your methods should make a call to tank-move. You are not allowed to modify any code to do this problem. Everything can be done using entirely new methods. Make sure that units will never walk out of the board or reenter their home cities.
Submit all of the code you write for this problem, as output showing that it works. Sample output would be printouts of the board, with tanks gathering at the appropriate places. Another way to check your code is to look at the locations directly in the *main-board* by calling board, and operating on the location returned.
Principle: Object-Oriented Programming
Suppose that while the two cities are busy attacking each other, a natural disaster occurs. Everything on the board will be attacked, so to speak, by the natural disaster. You are to implement this scenario. Create a class <natural-disaster> as a subclass of <event>. Also create a class <disaster>, inheriting from <game-object>. The <disaster> has the default owner of "none". It should have a slot for the name of the disaster (ie. Godzilla, Rainstorm, Earthquake, God, etc), as well as a probability of occurring at any given time, and the severity of the disaster when it occurs. Sample slot values are given in the global variable *natural-disasters*, listing name, probability, and severity in that order. Write the corresponding make function for this event, giving it an initial time of *start-time*. Make-natural-disaster should take a string, a float, and another float (in that order) and produce a <natural-disaster> that has a <disaster> with corresponding name, probability and severity as its target. Add the following line to init-game!:
(map
(method ((o <list>))
(prioq-insert! *events*
(apply make-natural-disaster o)))
*natural-disasters*)
Add a method to process-event that will handle this new <event>. It should decide whether the disaster is going to occur based on the probability. If it does not occur, then the <natural-disaster> gets placed back on the queue. The event should reappear after *disaster-delay* days. If disaster is supposed to strike, then every object on the board should be attacked immediately by the <disaster>. The damage for each target is a random value, calculated based on the severity. A message should be printed when the disaster occurs saying which disaster happened (mention its name and severity).
Submit listings of all code you write. Do NOT make any modifications to the code beyond the addition of the line above to init-game! You may add your own disasters if you like. Also submit output showing your code in action.
Principle
: Multiple InheritanceA <mobile-factory> has properties of both a <city> and a <unit>. As a <city> it can produce <army-units>, but as a <unit> it can move around. The advantage is that the factory can produce <army-unit>s closer to the opposing city, helping them arrive and attack faster. Implement the <mobile-factory> with the following properties:
Submit listings of all code you create and modify, as well as output showing that the factory conforms to the specifications. Any details not specified can be done however you would like, as long as the specifications are met. Do not modify code unless you absolutely have to. Unnecessary modifications will be penalized.
We hope you have had as much fun doing this assignment as we had putting it together. Now is your chance to show off your newly acquired skill in object-oriented programming and your creativity. For this contest, we would like you to enhance the program in any way you wish by implementing some feature of your own design. Here are some ideas:
You can do anything you want here. The sky is the limit! Please hand in listings and a short written description of what you did, sample runs, and a complete stand-alone program on a disk (or e-mail it to cs212@cs.cornell.edu) so we can try it out. Make sure that you mark the code you submit for this portion of the problem set clearly. As before, programs will be judged by the CS212 staff, and the winner will receive a prize.
Last modified: 01/19/00 11:36 PM by AN