SICP 2.3.1 Solutions

February 8, 2015 11:14

Ex 2.53

There’s little to figure out here, and the answers are found by observation. One concept apparently emphasized here is that quotation ends up applying to everything within its expression. It makes nested lists easy to write (as in the cadr and memq examples) without having to repeat the quote marks.

Ex 2.54

The problem statement itself can be converted almost directly, namely this part:

a and b are equal? if they are both symbols and the symbols are eq?, or if they are both lists such that (car a) is equal? to (car b) and (cdr a) is equal? to (cdr b).

Writing that out (in pseudo-Scheme, using prefix notation):

(or (and (symbols? a b) (eq? a b))
    (and (lists? a b) (and (equal? (car a) (car b)) (equal? (cdr a) (cdr b))))

That’s a sufficient implementation, as long as those predicates exist. My working version has some slight differences. For one, cond is used effectively as an exclusive or, instead of the Boolean operator. That’s fine here, as the two ‘types’ of items checked will be distinct. Additionally, the check for symbols is dispensed with, allowing anything that works with eq? to fit. Finally, pair? is used instead of checking only for lists. These adjustments from the skeleton above make the function slightly more generic, and potentially more broadly useful.

Ex 2.55

Figuring out this one can be difficult if you missed the book’s footnote about quote, or didn’t check another Scheme reference. In short, the single-quote ' is a special form for the quote procedure (aka ‘syntactic sugar’ — another phrase mentioned in an earlier footnote). An expression such as 'a is equivalent to (quote a). What Eva discovered is that this is in fact what the interpreter uses internally. Here’s how the expression is processed in that form:

(car (quote (quote abracadabra)))
(car (quote abracadabra))    ; The list (quote abracadabra) is a list of *symbols* here
quote                        ; The car of that list is the symbol quote

Note that, at least in the Dr. Racket environment, a quotation mark will be used to indicate quoted expressions when they are a result. For example, removing the car operation in this exercise will give the result 'abracadabra . That means the interpreter can use special forms to make the output look nicer too. The fact that this is actually a conversion made for displaying output can be verified; see the solutions file for the proof.

Solutions 2.3.1