Before you begin, here are a few things to keep in mind:
First and foremost, DON'T PANIC!. The exam may look long, but you have six hours, and you'll find that some problems that take a long time to describe will not take a long time to solve, especially if you heed the advice we give below.
We recommend that you read through the entire exam before beginning, so that you can figure out how best to spend your time. In particular, since the environment diagram section is handed in separately, you don't have to do Part B immediately after Part A (you could do Part C first and then come back and do Part B later). If you don't like environment diagrams, this might be a good way to go.
Each section of each problem will be annotated with the number of marks that the section is worth, in boldface type.
There are some useful Scheme functions listed at the end of the exam. Also, you can consult the Scheme reference documentation here if you need to look up the definition of a built-in Scheme function.
If you run out of time, remember that you can always "draw a line" in your answers and indicate that that was when you ran out of time, and then you can continue. We may award partial credit for answers done after the exam is over. However, don't overdo it: if you find you need to spend more than one extra hour, you're probably wasting your time and should just hand in what you have.
In this problem we will implement a simple web log, usually known as a "blog". It will keep track of blog entries and allow the user to search for a particular entry, edit or remove an entry, and select all entries that have a specific tag for export into a different blog.
You do not have to write out contracts for your functions in this section, though it's OK if you do.
NOTE: Even though the examples in this section are long, the functions you need to write are not; in the solution set, none of our functions in the section are more than 20 lines long, and most are considerably shorter.
[0.5] We start by writing a helper function that will be used later. In
lab 9, we saw copy-list which makes a copy of a particular list. However,
if some elements of that list were also lists, it didn't make a copy of those
sub-lists. You must implement the function deep-copy-list, which makes a
copy of a given list and all of its sub-lists (and their sub-lists, etc).
NOTE: You do not have to handle lists that are circular or which have multiple references to the same cons cell.
Function prototype:
(define (deep-copy-list input-list)
...)
Examples:
(define w '(1 2 3 (4 5)))
w => (1 2 3 (4 5))
(define x (deep-copy-list a))
x => (1 2 3 (4 5))
(equal? w x) => #t
(eq? w x) => #f
(eq? (car (cdddr w)) (car (cdddr x))) => #f
;; the sublist (4 5) has also been copied.
(define y '(((1))))
y => (((1)))
(define z (deep-copy-list a))
z => (((1)))
(equal? y z) => #t
(eq? y z) => #f
(eq? (car y) (car z)) => #f
(eq? (car (car y)) (car (car z))) => #f
[0.5] Next you must implement the function make-blog-entry,
which creates a new blog entry object. It takes a date/time object created by the
function make-time (which you do not have to write), a name (a symbol),
the text of the entry (a string), and a list of tags (each of which is a symbol; these
are used to tag some aspect of the entry for later searching and retrieving), and puts
them together into a list with the tag 'blog-entry. You should also create the
accessors get-time, get-name, get-text, and
get-tag-list that return the appropriate part from a blog entry object.
Prototypes for these functions are given below, as well as example usage. You may
assume that the function make-time is already written (and returns a list
containing the symbol 'time and the string representing the time that was
passed to it), and you do not need to do any error checking on the input.
Function prototypes:
(define (make-blog-entry time name text tags)
...)
(define (get-time blog-entry)
...)
(define (get-name blog-entry)
...)
(define (get-text blog-entry)
...)
(define (get-tag-list blog-entry)
...)
Examples:
(define a (make-blog-entry
(make-time "Dec 5 2008 14:50")
'bored
"Nothing planned today. I'm so bored. Maybe I should go get more
sleep? Is anyone even reading this?"
(list 'boring 'is-anyone-reading-this)))
a => (blog-entry
(time "Sep 5 2008 14:50")
bored
"Nothing planned today. I'm so bored. Maybe I should go get more
sleep? Is anyone even reading this?"
(boring is-anyone-reading-this))
(define b (make-blog-entry
(make-time "Apr 15 2008 12:00")
'birthdayparty
"Went to a birthday party today. There were lots of board games. I
rocked at Settlers of Catan. If anyone is reading this, I want a copy of that
game for my birthday."
(list 'birthdays 'is-anyone-reading-this)))
b => (blog-entry
(time "Apr 15 2008 12:00")
birthdayparty
"Went to a birthday party today. There were lots of board games. I
rocked at Settlers of Catan. If anyone is reading this, I want a copy of that
game for my birthday."
(birthdays is-anyone-reading-this))
(get-name a) => bored
(get-time a) => (time "Dec 5 2008 14:50")
(get-text a) => "Nothing planned today. I'm so bored. Maybe I should go get more sleep? Is anyone even reading this?"
(get-tag-list a) => (boring is-anyone-reading-this)
[0.5] Next we need to write the constructor make-blog which
returns a blog object. It should take a blog title (a string) and the author's name
(also a string), and return a list containing the tag 'blog, the title,
the author's name, and a list of blog entries (which should start out empty). You
should also write the functions get-blog-title,
get-blog-author and get-blog-entries-list, which access the
appropriate parts of a blog object.
Function prototypes:
(define (make-blog title author)
...)
(define (get-blog-title blog)
...)
(define (get-blog-author blog)
...)
(define (get-blog-entries-list blog)
...)
Examples:
(define my-blog (make-blog "Coordinated Insanity" "Joseph S")) my-blog => (blog "Coordinated Insanity" "Joseph S" ()) (get-blog-title my-blog) => "Coordinated Insanity" (get-blog-author my-blog) => "Joseph S" (get-blog-entries-list my-blog) => ()
[1.0] Now that we can create an empty blog, we need to be able to add
entries to it. You should now write add-entry-to-blog!, which takes a
blog and an entry, and inserts the entry into the blog's list of entries. Furthermore,
the insertion should be sorted based on the entry's time (with later entries coming
later in the entry list). You can assume there exists a function
time-greater-than? that takes two time objects and returns #t if the
first's time is after the second's, and #f otherwise.
NOTE: Make sure that you use the abstraction layer you defined above wherever appropriate instead of directly manipulating the list structures of the data structures. Of course, if you need to do something that requires that you manipulate the list structure directly, you can, but don't do it when an accessor already exists that does the same thing.
Function prototype:
(define (add-entry-to-blog! entry blog)
...)
Examples: (recall a, b, and my-blog were
defined above)
(define c
(make-blog-entry
(make-time "Dec 12 2008 04:00")
'flight
"Can't wait. Almost done with finals and ready for my plane flight home. Five
hours napping on a plane never sounded so good."
(list 'done-with-homework 'yay 'is-anyone-reading-this)))
(add-entry-to-blog! c my-blog)
my-blog =>
(blog
"Coordinated Insanity"
"Joseph S"
((blog-entry
(time "Dec 12 2008 04:00")
flight
"Can't wait. Almost done with finals and ready for my plane flight home.
Five hours napping on a plane never sounded so good."
(done-with-homework yay is-anyone-reading-this))))
(add-entry-to-blog! b my-blog)
(add-entry-to-blog! a my-blog)
my-blog =>
(blog
"Coordinated Insanity"
"Joseph S"
((blog-entry
(time "Apr 15 2008 12:00")
birthdayparty
"Went to a birthday party today. There were lots of board games. I
rocked at Settlers of Catan. If anyone is reading this, I want a copy of that
game for my birthday."
(birthdays is-anyone-reading-this))
(blog-entry
(time "Dec 5 2008 14:50")
bored
"Nothing planned today. I'm so bored. Maybe I should go get more sleep?
Is anyone even reading this?"
(boring is-anyone-reading-this))
(blog-entry
(time "Dec 12 2008 04:00")
flight
"Can't wait. Almost done with finals and ready for my plane flight home.
Five hours napping on a plane never sounded so good."
(done-with-homework yay is-anyone-reading-this))))
[0.5] Next you need to write find-entry, which takes a blog
and an entry name, and returns the first entry in the blog that has the matching name,
or an empty list if none are found that match.
Function prototype:
(define (find-entry blog entry-name)
...)
Examples:
(define birthday-entry (find-entry my-blog 'birthdayparty))
birthday-entry =>
(blog-entry
(time "Apr 15 2008 12:00")
birthdayparty
"Went to a birthday party today. There were lots of board games. I rocked
at Settlers of Catan. If anyone is reading this, I want a copy of that game
for my birthday."
(birthdays is-anyone-reading-this))
(define amusing-entry (find-entry my-blog 'amusing))
amusing-entry => ()
[1.0] Next you need to write a function which can remove an entry from a
blog based on the entry's name. After all, you may regret that blog post later and
need to remove it. delete-entry-from-blog! should take an entry's name (a
symbol), and the blog it should be removed from. The function should remove the first
entry from the blog that has that name and return the entry that got removed, or
signal an error (using the error function) if there were no entries with
that name.
NOTE: Again, use your abstraction layer where appropriate.
Function prototype:
(define (delete-entry-from-blog! entry-name blog)
...)
Examples:
(delete-entry-from-blog! 'toast my-blog) =>
ERROR! Could not find the entry you wanted to delete.
(delete-entry-from-blog! 'bored my-blog) =>
(blog-entry
(time "Dec 5 2008 14:50")
bored
"Nothing planned today. I'm so bored. Maybe I should go get more sleep? Is
anyone even reading this?"
(boring is-anyone-reading-this))
my-blog =>
(blog
"Coordinated Insanity"
"Joseph S"
((blog-entry
(time "Apr 15 2008 12:00")
birthdayparty
"Went to a birthday party today. There were lots of board games. I
rocked at Settlers of Catan. If anyone is reading this, I want a copy of that
game for my birthday."
(birthdays is-anyone-reading-this))
(blog-entry
(time "Dec 12 2008 04:00")
flight
"Can't wait. Almost done with finals and ready for my plane flight home.
Five hours napping on a plane never sounded so good."
(done-with-homework yay is-anyone-reading-this))))
[1.0] Now we need a way of editing a blog entry that's already in our
blog. Write a function edit-blog-entry! which takes a blog, an entry name
(a symbol), and the editing parameters: a new time (a time object from
make-time), a new text block (a string), and a new set of tags (a list of
symbols). These editing parameters should either be the specified type, or #f if that
part of the entry should not be changed. Your function should return the newly edited
entry. If there is no entry with the specified name, the function should signal an
error using the error function. You do not need to re-sort the list of
entries if the time is changed on the edited entry.
NOTE: Again, use your abstraction layer where appropriate. Also, it's OK to
use an if expression without an else-clause (the Scheme standard allows
this, though most DrScheme language levels don't). In such an expression, the else
clause is implicitly a do-nothing operation.
Function prototype:
(define (edit-blog-entry! blog entry-name newtime newtext newtags)
...)
Examples:
(edit-blog-entry! my-blog 'toast
(make-time "Dec 5 2008 15:00") "Yummy Toast!" #f)
=>
ERROR: No blog entry with that name found, cannot edit a blog entry that isn't
there!
;; Just change the tags:
(edit-blog-entry! my-blog 'flight #f #f
(list 'done-with-homework 'is-anyone-reading-this 'i-like-flying-on-planes))
=>
(blog-entry
(time "Dec 12 2008 04:00")
flight
"Can't wait. Almost done with finals and ready for my plane flight home.
Five hours napping on a plane never sounded so good."
(done-with-homework is-anyone-reading-this i-like-flying-on-planes))
my-blog =>
(blog
"Coordinated Insanity"
"Joseph S"
((blog-entry
(time "Apr 15 2008 12:00")
birthdayparty
"Went to a birthday party today. There were lots of board games. I
rocked at Settlers of Catan. If anyone is reading this, I want a copy of that
game for my birthday."
(birthdays is-anyone-reading-this))
(blog-entry
(time "Dec 12 2008 04:00")
flight
"Can't wait. Almost done with finals and ready for my plane flight home.
Five hours napping on a plane never sounded so good."
(done-with-homework
is-anyone-reading-this
i-like-flying-on-planes))))
;; Replace time, text, and tags:
(edit-blog-entry! my-blog 'flight (make-time "Dec 12 17:00")
"Ugh. Final took longer than I thought. Replacing my previous entry with
this one. I have to reschedule my plane flight now, too."
(list 'i-hate-finals 'is-anyone-reading-this))
=>
(blog-entry
(time "Dec 12 17:00")
flight
"Ugh. Final took longer than I thought. Replacing my previous entry
with this one. I have to reschedule my plane flight now, too."
(i-hate-finals is-anyone-reading-this))
my-blog =>
(blog
"Coordinated Insanity"
"Joseph S"
((blog-entry
(time "Apr 15 2008 12:00")
birthdayparty
"Went to a birthday party today. There were lots of board games. I
rocked at Settlers of Catan. If anyone is reading this, I want a copy of that
game for my birthday."
(birthdays is-anyone-reading-this))
(blog-entry
(time "Dec 12 17:00")
flight
"Ugh. Final took longer than I thought. Replacing my previous entry with
this one. I have to reschedule my plane flight now, too."
(i-hate-finals is-anyone-reading-this))))
[1.0] Finally, you need to write export-tagged-entries, a
function that takes a blog and a tag (a symbol), and returns a list of all entries in
the blog which have that tag in their tag-list. These entries should be copies
of those in the blog, so that they can be used later without affecting the blog.
NOTE: Again, use your abstraction layer where appropriate.
Function prototype:
(define (export-tagged-entries blog tag)
...)
Examples:
(export-tagged-entries my-blog 'argh) => ()
;; no entries were tagged with the symbol argh
(export-tagged-entries my-blog 'i-hate-finals) =>
((blog-entry
(time "Dec 12 17:00")
flight
"Ugh. Final took longer than I thought. Replacing my previous entry with
this one. I have to reschedule my plane flight now, too."
(i-hate-finals is-anyone-reading-this)))
(define anyone-reading-entries
(export-tagged-entries my-blog 'is-anyone-reading-this))
anyone-reading-entries =>
((blog-entry
(time "Apr 15 2008 12:00")
birthdayparty
"Went to a birthday party today. There were lots of board games. I rocked
at Settlers of Catan. If anyone is reading this, I want a copy of that game
for my birthday."
(birthdays is-anyone-reading-this))
(blog-entry
(time "Dec 12 17:00")
flight
"Ugh. Final took longer than I thought. Replacing my previous entry with
this one. I have to reschedule my plane flight now, too."
(i-hate-finals is-anyone-reading-this)))
;; Now we check to make sure that the objects have been fully copied.
(define birthday-entry (car anyone-reading-entries))
birthday-entry =>
(blog-entry
(time "Apr 15 2008 12:00")
birthdayparty
"Went to a birthday party today. There were lots of board games. I rocked
at Settlers of Catan. If anyone is reading this, I want a copy of that game
for my birthday."
(birthdays is-anyone-reading-this))
(eq? birthday-entry (find-entry my-blog 'birthdayparty)) => #f
(equal? birthday-entry (find-entry my-blog 'birthdayparty)) => #t
(eq? (get-tag-list birthday-entry)
(get-tag-list (find-entry my-blog 'birthdayparty))) => #f
End of part A.
Draw environment diagrams that result from evaluating each of these blocks
of code. Draw the diagram representing the environment at the end of
the computation, except that you should leave all intermediate frames in your
drawing (even if you know they would be discarded as temporaries at the end
of the computation). You do not need to draw any frames for primitive
function application, where "primitive" means any function already built into
Scheme. If a function body is too long, you do not need to try to fit all of
it into your diagram; one or two lines and an ellipsis ("...")
will more than suffice. Also, please make your diagrams neat and
readable; unreadable or barely-readable diagrams will lose marks.
Make sure you write out all lists in box-and-pointer form, and not the way
Scheme would print them i.e.. don't write a list as (1 2 3
4); write out the box-and-pointer version of this. There aren't any
long lists in these problems anyway.
A useful tip: when you create a new frame (other than the global
environment), write the piece of code that caused the frame to be created
immediately above the frame (using ellipses ("...") if the code
is too large, of course). Usually this will be a function call or a
let expression. Doing this will help you organize your work.
This is not a requirement, but we recommend it.
[2.0]
(define (f g x) (* x (g x))) (define (h x) (f (lambda (x) (+ x 3)) (* 2 x))) (h 5)
[2.0]
(define (make-sandwich bread price)
;; Sandwich contents start out as just two pieces of bread. Ingredients
;; are added to the sandwich using the 'add message, which also updates
;; the price of the sandwich.
(let ((contents (list bread bread)))
(lambda (op . args)
(cond ((eq? op 'add) ;; Add new ingredient, then update & return price.
(set-cdr! contents (cons (car args) (cdr contents)))
(set! price (+ price (cadr args)))
price)
((eq? op 'get-price) price) ;; Retrieve current price.
((eq? op 'get-contents) contents) ;; List of sandwich contents.
(else (error "Sandwich don't take that:" op))))))
;; Mmm, tuna and swiss on rye...
(define s (make-sandwich 'rye 0.85))
(s 'add 'tuna 1.0)
(s 'add 'swiss 0.55)
(s 'get-price)
[2.0]
(define (f g x)
(let ((x (cddr x))
(f (lambda (y) (set! x (g y)))))
(f x))
x)
(define x (list 4 3 2 1))
(f (lambda (x)
(set-car! x (cons (car x) (cadr x)))
x)
x)
End of part B.
A very simple but enjoyable solitaire puzzle game is the game known as "Lights Out" (also known as "Lights Off"). The game is played on a 5x5 square grid of lights which can be either "on" or "off". Initially, some of the lights will be on, and the goal of the game is to turn all the lights off. On each turn, you toggle the on/off state of any light in the grid. However, this has an unexpected side-effect: all of the lights that are orthogonally adjacent to the light you toggled (i.e. the light immediately above, the light immediately below, the light to the immediate left, and the light to the immediate right) will have their on/off states toggled as well. So even though you only toggled the state of one light yourself, it led to the states of four other lights being toggled as well. This makes it hard to turn all the lights off, since lights keep flipping from off to on and back to off every time you flip an adjacent light. The easiest way to get a feel for this is to play the game, so we encourage you to turn your stopwatch off and to go to this site and play the game for a few minutes (not for too long, though, as it can be somewhat addictive). You can also read this Wikipedia page to learn more about the game.
In this section, we will build a message-passing implementation of a Lights Out game.
Here is an example of the working code in action:
;; Create a new game with a board whose lights are all off.
(define game (make-game))
;; Initialize the board so that lights at certain coordinates are on.
;; Each cons pair is a row/column coordinate (with indices starting
;; from 0) which indicates which light to turn on.
(game 'initialize! '((0 . 0) (0 . 1) (0 . 2) (1 . 1) (2 . 1)
(3 . 0) (3 . 1) (3 . 2) (3 . 3)
(4 . 1) (4 . 2) (4 . 3) (4 . 4)))
;; Display the current state of the board:
(game 'display)
+-----+-----+-----+-----+-----+
| ON | ON | ON | off | off |
+-----+-----+-----+-----+-----+
| off | ON | off | off | off |
+-----+-----+-----+-----+-----+
| off | ON | off | off | off |
+-----+-----+-----+-----+-----+
| ON | ON | ON | ON | off |
+-----+-----+-----+-----+-----+
| off | ON | ON | ON | ON |
+-----+-----+-----+-----+-----+
;; Flip the state of a cell (i.e. a light) at a particular row/column
;; position; here, it's row 0 and column 1. This will also toggle
;; the states of all the orthogonally adjacent lights, which in this
;; case means those at coordinates (0, 0), (0, 2), and (1, 1).
(game 'flip-cell! 0 1)
;; Display the board again.
(game 'display)
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
| off | ON | off | off | off |
+-----+-----+-----+-----+-----+
| ON | ON | ON | ON | off |
+-----+-----+-----+-----+-----+
| off | ON | ON | ON | ON |
+-----+-----+-----+-----+-----+
;; Flip the state of another light.
(game 'flip-cell! 3 1)
;; Display the board again.
(game 'display)
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
| off | off | off | ON | off |
+-----+-----+-----+-----+-----+
| off | off | ON | ON | ON |
+-----+-----+-----+-----+-----+
;; Flip the state of another light.
(game 'flip-cell! 4 3)
;; Flip the state of another light.
(game 'display)
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
| off | off | off | off | off |
+-----+-----+-----+-----+-----+
;; All the lights are off, so we win! Woo hoo!
The code to implement the Lights Out game will be comprised of two kinds of message-passing object:
We'll give you detailed design advice as we go along. Each part is worth 3.0 marks, for a total of 6.0 marks for this section.
The lights themselves are called "cells" in our implementation, and an individual light is a cell object. Here is a template of the Scheme code for this object:
;; make-cell: [nothing] -> (cell message-passing object)
(define (make-cell)
;; Helper functions.
;; valid-state?: symbol -> boolean
(define (valid-state? state)
(or (eq? state 'on) (eq? state 'off)))
;; toggle-neighbors!: (list-of cells) -> 'done
;; This function toggles the states of all the neighbors of a given cell.
;; It returns the symbol 'done to indicate that it has completed.
(define (toggle-neighbors! neighbors)
...)
;; State variables.
(let ((state 'off) ;; The cell state is initially off.
(neighbors (list))) ;; Initially, there are no neighbors.
;; dispatch: symbol [optional arguments] -> [various possible results]
;; The message-passing object itself, as a dispatch function.
(define (dispatch op . args)
(cond ((eq? op 'type) 'cell)
((eq? op 'get-state) ...)
((eq? op 'set-state!) ...)
((eq? op 'add-neighbor!) ...)
((eq? op 'toggle-state!) ...)
((eq? op 'toggle-state-and-neighbors!) ...)
(else (error "cell object: message not understood: " op))))
;; Return the dispatch function, which is the cell object.
dispatch))
Much of the code has been supplied for you, and your job is just to fill in
the missing parts, which are indicated with ellipses (...).
Here is a description of the messages that the cell object can respond to:
'type: This returns the type of the object, which
is the symbol 'cell.
'get-state: This returns the current state value,
which is either 'on or 'off.
'set-state!: This takes one argument, checks
that it is either 'on or 'off, and sets the state
to that value. If the argument is not a valid state an error is signalled
using the error function.
'add-neighbor!: This takes one argument, which
should be another cell object. It checks this by sending the
'type message to the argument, and signals an error if the
argument isn't a cell. If it is, it gets added to the list of neighbors (the
neighbors state variable), which gets mutated as a
result.
'toggle-state!: As the name suggests, this
message's code changes the state variable of the cell object
from 'on to 'off or vice-versa. It has no effect
on the cell's neighbors.
'toggle-state-and-neighbors!: This is like
'toggle-state, but it also toggles the state of all the cells
in the neighbors list.
We've also included a skeleton for some helper functions, which we recommend you complete and use in your message-passing implementation. If you do, the code in your message-passing implementation will be very short and readable. You can include other helper functions in your solution if you like.
For the game code, we first define a useful coordinate abstraction:
;; Game coordinates as row-column pairs.
;; Note that a list of coordinates can be conveniently written as e.g.
;; '((1 . 0) (0 . 1) (2 . 2) (3 . 5)) etc. without having to explicitly use
;; make-coord. Note that coordinate indices start from 0.
(define (make-coord row col) (cons row col))
(define (get-row c) (car c))
(define (get-col c) (cdr c))
;; valid-coord: coord -> boolean
;; Row and column coordinates must be in the range (0 to 4),
;; because the board is 5x5.
(define (valid-coord? c)
(not (or (< (get-row c) 0) (< (get-col c) 0)
(> (get-row c) 4) (> (get-col c) 4))))
Then we have the following template code for the game message-passing object:
;; make-game: [nothing] -> (game message-passing object)
(define (make-game)
;; Helper functions:
;; make-empty-board: [nothing] -> (list-of (list-of cells))
;; Create the game board representation, as a list of lists of cells.
;; Each cell starts off empty.
(define (make-empty-board)
(list (list (make-cell) (make-cell) (make-cell) (make-cell) (make-cell))
(list (make-cell) (make-cell) (make-cell) (make-cell) (make-cell))
(list (make-cell) (make-cell) (make-cell) (make-cell) (make-cell))
(list (make-cell) (make-cell) (make-cell) (make-cell) (make-cell))
(list (make-cell) (make-cell) (make-cell) (make-cell) (make-cell))))
;; get-cell: (list-of (list-of cells)) coord -> cell
;; This function gets the cell located at location (row, col) in the board
;; and returns it. If the (row, col) position isn't valid, the function
;; signals an error.
(define (get-cell board coord)
...)
;; set-initial-states!: (list-of (list-of cells)) (list-of coords) -> [nothing]
;; Set the initial states of all the cells whose coordinates are in the list
;; of coordinates to the ON state.
;; Example: (set-initial-states! board '((0 . 0) (1 . 1) (2 . 2) (3 . 3) (4 . 4)))
;; would set all of the cells on one main diagonal to be ON.
;; This function signals an error if any coordinate is invalid.
(define (set-initial-states! board coords)
...)
;; connect-cell!: (list-of (list-of cells)) coord -> [nothing]
;; This function gets the cell located at a particular (row, column)
;; coordinate and connects it to all of the cells at the orthogonally adjacent
;; locations, i.e. at locations (row-1, col), (row+1, col), (row, col-1), and
;; (row, col+1), but only if there is a cell at those locations (otherwise
;; it does nothing for that coordinate).
(define (connect-cell! board coord)
...)
;; connect-all-cells!: (list-of (list-of cells)) -> [nothing]
;; This function connects all of the board cells with their orthogonally
;; adjacent neighbors.
(define (connect-all-cells! board)
...)
;; flip-cell!: (list-of (list-of cells)) row column -> [nothing]
;; This function makes a game move (toggle the cell and all of its neighbors)
;; on a particular cell in the board, as identified by its coordinate location
;; in the board.
(define (flip-cell! board row col)
...)
;; display-board: (list-of (list-of cells)) -> [nothing]
;; This function displays the board as a grid of "ON"s and "off"s.
;; YOU DO NOT NEED TO DEFINE THIS FUNCTION.
;; YOU MAY ASSUME THAT IT HAS BEEN DEFINED FOR YOU AND WORKS CORRECTLY.
(define (display-board board)
...)
;; This is the message-passing object itself.
(let ((board (make-empty-board))) ;; start with an empty board
(lambda (op . args)
(cond ((eq? op 'initialize!)
;; (car args) should be the initial coordinate list
...)
((eq? op 'flip-cell!)
;; (car args) is the row, (cadr args) is the column
...)
((eq? op 'display)
...)
(else (error "board object: message not understood: " op))))))
Once again, much of the code (and contracts, and comments) have been supplied for
you, and all you have to do is to fill in the parts marked with ellipses
(...). To see how the code is intended to be used, go back to the "User
Interface" section above.
This code contains a lot of helper functions, for a very good reason: once you have written them, the code for the message-passing object itself is almost trivial (just a few lines of code). So the majority of your time should be spent implementing the helper functions. Use the contracts and comments to guide your implementation. Naturally, since the game board stores cell objects, you will need to send messages to these objects in at least some of the helper functions. None of the helper functions in our implementation is longer than 15 lines of code, and most are considerably shorter than that. You can also define other helper functions if you like.
Here is a description of the messages the game object can respond to:
'initialize: This takes one argument, which is a list of
cons pairs representing the row/column indices of coordinates of the board where the
corresponding cells (lights) are to be turned on. The code for this message does two
things:
This message is intended to be invoked the beginning of the game, right after the object has been created. See the "User Interface" section above for an example of how it is used. The game itself isn't ready to be played until this message is invoked.
'display: This takes no arguments, and prints out the
contents of the board (the on/off states of all cells). Again, see the "User
Interface" section above to see how it's used and what the output is supposed to
look like. You are allowed to use a helper function to implement this message's
code, and you can assume that the helper function works as desired.
'flip-cell: This takes two arguments: a row index and a
column index, which together indicate the location of a cell in the board. It
toggles the state of the given cell and all of its neighbors.
That's all there is for this implementation.
End of part C.
pair?: This function returns #t if its argument is a
cons pair and #f otherwise.
memq: (memq item lst) returns #f if
item is not in the list lst; if it is, it returns the portion
of the list starting with item.
list-ref: (list-ref lst n) returns the
nth element of the list lst, or signals an error if
there is no such element. Note that the indexing starts with n =
0, so the car of the list is the 0th element. Example: (list-ref 3 '(1 2 3 4 5)) returns 4.
procedure?: (procedure? x) returns #t if
x is a procedure.
(End of final.) Have a relaxing winter break!