SICP 2.53 - 2.55: Symbolic Data

From SICP section 2.3.1 Quotation

This section of SICP introduces quotation, which gives us the ability to manipulate symbols as well as data values. When we quote a symbol the interpreter returns the literal symbol instead of the value that the symbol points to.

> (define a 1)
> a
1
> (quote a)
a

As a shorthand for quote we can place a single quote symbol at the beginning of the object to be quoted.

> 'a
a

We can also use quotation with compound objects.

> (define x '(a b c))
> x
(a b c)
> (car x)
a

Finally, we're introduced to the primitive eq?, which takes two symbols as arguments and tests whether they are the same (they consist of the same characters in the same order). We're also shown how we can use eq? to create a procedure memq that takes two arguments, a symbol and a list. If the symbol is not contained in the list, then memq returns false. Otherwise, it returns the sub-list that begins with the first occurrence of the symbol.


Exercise 2.53 asks us what the interpreter would print in response to evaluating each of the following expressions? See if you can predict what the output should be before trying each expression.

(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))

The first expression just creates a list containing three symbols, so it should evaluate the same as '(a b c).

> '(a b c)
(a b c)
> (list 'a 'b 'c)
(a b c)

The second expression creates a list that contains a list that contains a symbol.

> (list (list 'george))
((george))

The third expression gets the cdr of a list containing two lists of symbols. Remember from earlier sections that the car of a list is the first element in a list and the cdr is the remainder of the list.

> (cdr '((x1 x2) (y1 y2)))
((y1 y2))

The fourth expression gets the second element of the same list as above.

> (cadr '((x1 x2) (y1 y2)))
(y1 y2)

The fifth expression is checking to see if the car of a quoted list is a pair. You should be able to see that it's not, but try evaluating sub-expressions if you're unsure.

> '(a short list)
(a short list)
> (car '(a short list))
a
> (pair? (car '(a short list)))
#f

The sixth expression is using the memq procedure to see if a symbol is contained in a list. Remember that memq only checks the highest-level elements of the list, it doesn't recursively look inside any sub-lists.

> (memq 'red '((red shoes) (blue socks)))
#f

The final expression is also using memq to look for a symbol in a list, but this time with different results.

> (memq 'red '(red shoes blue socks))
(red shoes blue socks)

Exercise 2.54 asks us to define a procedure equal? that takes two parameters and returns true if they contain equal elements arranged in the same order. The parameters can be values, symbols, lists of symbols, or lists containing both symbols and nested lists. We are to define equal? recursively in terms of the basic eq? equality of symbols.

(define (equal? p1 p2)
  (cond ((and (null? p1) (null? p2)) #t)
        ((or (null? p1) (null? p2)) #f)
        ((and (pair? p1) (pair? p2))
         (and (equal? (car p1) (car p2))
              (equal? (cdr p1) (cdr p2))))
        ((or (pair? p1) (pair? p2)) #f)
        (else (eq? p1 p2))))

The procedure starts by checking to see if both parameters are null and returns #t if they are. It then checks to see if only one parameter but not the other is null. Next it checks to see if both parameters are pairs, and if they are it recursively checks to see if they have the same car and the same cdr. Next it checks to see if only one of the parameters is a pair and returns #f if that's the case. Finally, it checks to see if the two parameters are the same symbol or have the same value. We can run several tests to validate all the cases above.

> (equal? '() '())
#t
> (equal? '() 'a)
#f
> (equal? '((x1 x2) (y1 y2)) '((x1 x2) (y1 y2)))
#t
> (equal? '((x1 x2) (y1 y2)) '((x1 x2 x3) (y1 y2)))
#f
> (equal? '(x1 x2) 'y1)
#f
> (equal? 'abc 'abc)
#t
> (equal? 123 123)
#t

Exercise 2.55 asks us to explain why when a user types the expression

(car ''abracadabra)

the interpreter prints back quote.

Remember that ' is just shorthand for quote, so the expression above is equivalent to

(car (quote (quote abracadabra)))

The sub-expression (quote (quote abracadabra)) is equivalent to '(quote abracadabra), which is just the list containing the two symbols quote and abracadabra, making the car of that list simply the symbol quote.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.