Laboratory: Representing Images as Lists of Spots

a. Call the cons procedure to build a list of the value "red". The result of your call should be ("red").

b. Call the cons procedure to build a list of the value 5 followed by the value "red". The result of your call should be (5 "red"). Note that you will need to call cons twice to build this list.

c. Call the cons procedure to build a list of the value 2, followed by the value 5, followed by "red". The result of your call should be (2 5 "red"). Note that you will need to call cons three times to build this list.

d. Build the same list as in step c, using list rather than cons.

Consider the following list definition, which you can enter in the interactions pane of your work window.

(define letters (list 'a 'b 'c 'd 'e 'f 'g 'h 'i))

a. What do you expect the result of (car letters) to be? Check your answer experimentally.

b. What do you expect the result of (cdr letters) to be? Check your answer experimentally.

c. What do you expect the result of (car (cdr letters)) to be? Check your answer experimentally.

d. What do you expect the result of (cdr (cdr letters)) to be? Check your answer experimentally.

e. What do you expect the result of (cdr (car letters)) to be? Check your answer experimentally.

f. Write an expression that gets the sixth element of letters. (That is, your expression should extract the f.)

a. Create the list ("red" "orange" "yellow") and name it roy. Create the list ("green" "blue") and name it gb.

b. Determine what happens when you reverse roy with (reverse roy).

c. Determine what happens when you append the two lists together with (append roy gb).

d. Determine what happens when you append the two lists together with (append gb roy).

As you may recall, the cons procedure takes two parameters, a value and a list. It builds a new list by prepending the value to another list. However, it is also possible to apply cons to two non-list values. (You should not regularly do so at this point in your career, but some accidentally apply cons in this different way, so we want you to see what happens.)

Consider the following:

(define one-two (cons 1 2))
(define won-too (list 1 2))
(define want-to (cons 1 (cons 2 null)))

a. Enter these definitions in the interactions pane of your work window and then ask for the values of one-two, won-too, and want-to. Explain how they are and are not similar.

b. What do you expect to have happen when you apply the list? predicate to each value? Check your answer experimentally.

c. What do you expect to have happen when you call reverse on each? Check your answer experimentally.

d. What do you expect to have happen if you try to get the car and the cdr of each of these values? Check your answer experimentally.

e. What do you expect to have happen if you append the list (3 4) to each of these values, as in the following example?

> (append one-two (list 3 4))
?
> (append won-too (list 3 4))
?
> (append want-to (list 3 4))
?

Check your answer experimentally.

f. What do you expect to have happen if you append each of these values to the list (0 0), as in the following example?

> (append (list 0 0) one-two)
?
> (append (list 0 0) won-too)
?
> (append (list 0 0) want-to)
?

If you are confused by any of the results, please look at the notes on this problem.

We claimed that the reading and the lab were about representing images as lists of spots. However, up to this point, we've just worked with lists. Let's consider some procedures that work with spots. As you may recall, we've decided to represent each spot as a three element list, where the first element is the column, the second the row, and the third the color.

a. Look at the definition of spot-new. What do you expect the output of the following command to be?

> (spot-new 10 10 "red")

b. Check your answer experimentally.

c. Create a spot, named s1, that is at position (5,2) and is blue.

d. Look at the definition of spot-nudge-right. Then consider the following definition.

> (define s2 (spot-nudge-right s1))

What do you expect the value of s1 to be after that definition? What do you expect the value of s2 to be after that definition? Check your answers experimentally.

e. Look at the definition of spot-nudge-up. Then consider the following definition.

> (define s3 (spot-nudge-up (spot-nudge-right s1)))

What do you expect the value of s1 to be after that definition? What do you expect the value of s3 to be after that definition? Check your answers experimentally.

f. What do you expect the value of s4 to be after the following definition?

> (define s4 (spot-nudge-up (spot-nudge-up (spot-nudge-up s1))))

Check your answer experimentally.

a. As you've just noticed, it is possible to nudge a spot so far up that its row becomes less than 0. At times, we might find such behavior inappropriate. Rewrite spot-nudge-up so that you cannot nudge a spot up higher than row 0.

Hint: Remember that we learned about bounding numbers in a previous lab.

b. Is it possible to make a similar change to spot-nudge-right? If so, summarize (in English) what that change would be like. If not, explain why not.

c. You may have noted that we seem to have failed to define spot-nudge-left and spot-nudge-down. Write them now.

a. Create a new 100x100 image called canvas.

b. Consider the definition of image-render-spot!. Explain what the purpose of this procedure seems to be. (The purpose of a procedure explains what a procedure does, rather than how.)

c. What do you expect the result of the following commands to be?

> (image-render-spot! canvas s1)
> (context-update-displays!)

d. Check your answer experimentally. Note that you may have to zoom in to see the spot.

e. Consider the definition of image-scaled-render-spot!. Explain what the purpose of this procedure seems to be. (The purpose of a procedure explains what a procedure does, rather than how.)

f. What do you expect the result of the following commands to be?

> (image-scaled-render-spot! canvas s1 10)
> (image-scaled-render-spot! canvas s1 20)
> (image-scaled-render-spot! canvas (spot-nudge-right s1) 20)
> (image-scaled-render-spot! canvas (spot-nudge-down s1) 20)
> (image-scaled-render-spot! canvas (spot-nudge-up (spot-nudge-up s1)) 20)

g. Check your answer experimentally.

Consider the following procedure, which you should add to your library.

(define spot-flip
  (lambda (spot)
    (list (cadr spot) (car spot) (caddr spot))))

a. Determine what the procedure seems to do by creating a few spots and looking at the result of flipping those spots and/or by looking at what happens when you display spots and their flipped versions. For example,

> (define r1 (spot-new 10 1 "red"))
> (define b1 (spot-new 10 1 "blue"))
> (define r2 (spot-new 5 5 "red"))
> (define b2 (spot-new 5 5 "blue"))
> (define r3 (spot-new 6 17 "red"))
> (define b3 (spot-new 6 17 "blue"))
> (spot-flip b1)
> (spot-flip b2)
> (spot-flip b3)
> (image-render-spot! canvas r1)
> (image-render-spot! canvas (spot-flip b1))
> (image-render-spot! canvas r2)
> (image-render-spot! canvas (spot-flip b2))
> (image-render-spot! canvas r3)
> (image-render-spot! canvas (spot-flip b3))

b. As you've just determined, spot-flip “flips” a spot along the diagonal where the row equals the column. That is, in fact, the intended purpose of this procedure. Critique its design. In what ways does it succeed and in what ways does it fail?

If you're not sure about your answer, or have difficulty critiquing the design, you may want to read the notes on this exercise.

We started by representing spots as lists of three items: column, row, and color. Upon further reflection, it might be better to group the column and row into their own sublist, which makes the output a little clearer.

(define spot-new
  (lambda (col row color)
    (list color (list col row))))

> (spot-new 4 2 "red")
("red" (4 2))

But is it safe to make this change? If we change the underlying representation, we need to change spot-col, spot-row, and spot-color

a. Rewrite those three functions to use the new representation. For example, spot-color should take the car of a spot, and spot-col should take the the car of the cadr.

b. Test your code by entering the following expressions and seeing if you get the same results.

> (define y1 (spot-new 1 2 "yellow"))
y1
> (spot-row y1)
2
> (spot-col y1)
1
> (spot-color y1)
"yellow"

c. What effect do you expect your changes to have on spot-nudge-up and spot-nudge-right?

d. Check your answers by entering the following

> (spot-col (spot-nudge-up y1))
1
> (spot-row (spot-nudge-up y1))
1
> (spot-color (spot-nudge-up y1))
"yellow"
> (spot-col (spot-nudge-right y1))
2
> (spot-row (spot-nudge-right y1))
2
> (spot-color (spot-nudge-right y1))
"yellow"

e. What effect do you expect your changes to have on image-render-spot! and image-scaled-render-spot!?

f. Check your answer experimentally.

g. What effect do you expect your changes to have on spot-flip?

h. Check your answer experimentally.

i. It is likely that you discovered that spot-flip no longer works. Rewrite it so that it not only works, but will survive a future change to representation.

You may have noted that almost all of the time we used the drawings-as-values model, we named the drawing we created. We can, of course, also look at those values. Consider the following:

> drawing-unit-circle
(drawing ellipse 0 "" -0.5 -0.5 1 1)
> drawing-unit-circle
(drawing ellipse 0 "" -0.5 -0.5 1 1)
> (drawing-hscale (drawing-vscale drawing-unit-circle 10) 20)
(drawing ellipse 0 "" -10.0 -5.0 20 10)
> (drawing-hshift (drawing-vshift drawing-unit-square 30) 40)
(drawing rectangle 0 "" 39.5 29.5 1 1)
> (drawing-recolor drawing-unit-circle "red")
(drawing ellipse 16711680 "" -0.5 -0.5 1 1)
> (drawing-recolor drawing-unit-circle "yellow")
(drawing ellipse 16776960 "" -0.5 -0.5 1 1)

As this example suggests, drawings of shapes are currently represented as eight element lists. The first element is always the symbol drawing. The second element is either the symbol ellipse or the symbol rectangle. The third element is some strange number that seems to correspond to the color. We can safely assume that 0 represents the color black. The fourth never seems to change. (In fact, it's something we used in an older implementation of drawings, and has just refused to leave.) The sixth is the left edge, the sixth is the top edge, the seventh is the width, and the eighth is the height.

As you discovered earlier, it's dangerous to rely on the internal representation when you write procedures. However, let's suppose for the moment that you were willing to do so.

Write and test a procedure, (drawing-make-ellipse left top width height), that creates a new, filled, black ellipse with the specified edges and size.

As you might guess, won-two is the list (1 2). As you might not have guessed, one-two is the value (1 . 2). That value looks much like a list, but it has a period in the middle. The period is a signal to you that the value is not a list.

Since one-two is not a list, it is not possible to reverse it or to append it to another list.

However, like the typical implementation of cons, the typical implementation of append does not confirm that its second parameter is a list. And, like cons, when given a non-list as a second parameter, append returns a non-list. In this case, append returns (0 0 1 . 2). Once again, the period indicates “hey, that's not a list”.

Why does Scheme permit these non-lists? Because they are a generalization of lists (or at least of the techniques by which we process lists). As we'll see later in the semester, these non-lists can be quite useful.

Return to exercise 4.

Many students find this question puzzling. After all, spot-flip seems to work as advertised: The resulting spot is, indeed, flipped over the diagonal. So, part of the critique is positive: The procedure does what it claims to do.

However, the designer of spot-flip made a potentially unwise implementation choice: The implementation sidesteps the procedures that we've designed to build and use spots. Recall that we've already defined spot-new, spot-col, spot-row, and spot-color. However, the definition of spot-flip instead uses list, car, cadr and caddr. While this allows spot-list to work with the current representation, the decision to use these basic functions makes spot-flip fragile, as you'll discover in exercise 9: If we change the representation of spots, spot-flip will break, so we'll need to rewrite it.

Return to exercise 8.