Structure and Interpretation of Computer Programs

24

 Equivalently, we could write 

(define flipped-pairs

  (square-of-four identity flip-vert identity flip-vert))

25

 

Rotate180

 rotates a painter by 180 degrees (see exercise 2.50). Instead of 

rotate180

 we

could say 

(compose flip-vert flip-horiz)

, using the 

compose

 procedure from 

exercise 1.42. 

26

 

Frame-coord-map

 uses the vector operations described in exercise 2.46 below, which we

assume have been implemented using some representation for vectors. Because of data abstraction, it

doesn’t matter what this vector representation is, so long as the vector operations behave correctly. 

27

 

Segments->painter

 uses the representation for line segments described in exercise 2.48

below. It also uses the 

for-each

 procedure described in exercise 2.23. 

28

 For example, the 

rogers

 painter of figure 2.11 was constructed from a gray-level image. For each

point in a given frame, the 

rogers

 painter determines the point in the image that is mapped to it

under the frame coordinate map, and shades it accordingly. By allowing different types of painters, we

are capitalizing on the abstract data idea discussed in section 2.1.3, where we argued that a

rational-number representation could be anything at all that satisfies an appropriate condition. Here

we’re using the fact that a painter can be implemented in any way at all, so long as it draws something

in the designated frame. Section 2.1.3 also showed how pairs could be implemented as procedures.

Painters are our second example of a procedural representation for data. 

29

 

Rotate90

 is a pure rotation only for square frames, because it also stretches and shrinks the

image to fit into the rotated frame. 

30

 The diamond-shaped images in figures 2.10 and 2.11 were created with 

squash-inwards

applied to 

wave

 and 

rogers

. 

31

 Section 3.3.4 describes one such language. 

[Go to first, previous, next page;   contents;   index]

---

[Go to first, previous, next page;   contents;   index]

2.3  Symbolic Data

All the compound data objects we have used so far were constructed ultimately from numbers. In this

section we extend the representational capability of our language by introducing the ability to work

with arbitrary symbols as data.

2.3.1  Quotation

If we can form compound data using symbols, we can have lists such as

(a b c d)

(23 45 17)

((Norah 12) (Molly 9) (Anna 7) (Lauren 6) (Charlotte 4))

Lists containing symbols can look just like the expressions of our language:

(* (+ 23 45) (+ x 9))

(define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))

In order to manipulate symbols we need a new element in our language: the ability to quote a data

object. Suppose we want to construct the list 

(a b)

. We can’t accomplish this with 

(list a b)

,

because this expression constructs a list of the values of 

a

 and 

b

 rather than the symbols themselves.

This issue is well known in the context of natural languages, where words and sentences may be

regarded either as semantic entities or as character strings (syntactic entities). The common practice in

natural languages is to use quotation marks to indicate that a word or a sentence is to be treated

literally as a string of characters. For instance, the first letter of ‘‘John’’ is clearly ‘‘J.’’ If we tell

somebody ‘‘say your name aloud,’’ we expect to hear that person’s name. However, if we tell

somebody ‘‘say ‘your name’ aloud,’’ we expect to hear the words ‘‘your name.’’ Note that we are

forced to nest quotation marks to describe what somebody else might say.

32

We can follow this same practice to identify lists and symbols that are to be treated as data objects

rather than as expressions to be evaluated. However, our format for quoting differs from that of natural

languages in that we place a quotation mark (traditionally, the single quote symbol 

’

) only at the

beginning of the object to be quoted. We can get away with this in Scheme syntax because we rely on

blanks and parentheses to delimit objects. Thus, the meaning of the single quote character is to quote

the next object.

33

Now we can distinguish between symbols and their values:

(define a 1)

(define b 2)

(list a b)

(1 2)

(list ’a ’b)

(a b)

(list ’a b)

(a 2)

---

Quotation also allows us to type in compound objects, using the conventional printed representation

for lists:

34

(car ’(a b c))

a

(cdr ’(a b c))

(b c)

In keeping with this, we can obtain the empty list by evaluating 

’()

, and thus dispense with the

variable 

nil

.

One additional primitive used in manipulating symbols is 

eq?

, which takes two symbols as arguments

and tests whether they are the same.

35

 Using 

eq?

, we can implement a useful procedure called 

memq

.

This takes two arguments, a symbol and a list. If the symbol is not contained in the list (i.e., is not 

eq?

to any item in the list), then 

memq

 returns false. Otherwise, it returns the sublist of the list beginning

with the first occurrence of the symbol:

(define (memq item x)

  (cond ((null? x) false)

        ((eq? item (car x)) x)

        (else (memq item (cdr x)))))

For example, the value of

(memq ’apple ’(pear banana prune))

is false, whereas the value of

(memq ’apple ’(x (apple sauce) y apple pear))

is 

(apple pear)

.

Exercise 2.53.  What would the interpreter print in response to evaluating each of the following 

expressions?

(list ’a ’b ’c)

(list (list ’george))

(cdr ’((x1 x2) (y1 y2)))

(cadr ’((x1 x2) (y1 y2)))

(pair? (car ’(a short list)))

(memq ’red ’((red shoes) (blue socks)))

(memq ’red ’(red shoes blue socks))

Exercise 2.54.  Two lists are said to be 

equal?

 if they contain equal elements arranged in the same

order. For example,

(equal? ’(this is a list) ’(this is a list))

is true, but

(equal? ’(this is a list) ’(this (is a) list))

---