Chapter 2.3 (Symbolic Data)

June 11, 2025

Symbolic Data

So far, everything has been numbers. Now we will extend the representational capability of Lisp by introducing symbols as data, so we can can construct things like

(a b c d)
((a 4) (b 2) (c 5))

They might look pretty similar to what we have already been building, but there is one key difference. Say we want to construct the list (a b), the following won’t work:

(list a b)

That is because Lisp tries to evaluate a and b instead. If we want to treat these symbols as the data objects that they are, we are required to do the following:

(list 'a 'b)

The single quote tells the compiler we want to use this symbol as is, and to not evaluate it to any value it might represent. Some more examples:

(car '(a b c))
a

(cdr '(a b c))
(b c)

One primitive that is very useful when dealing with symbols is called eq?. It takes two symbols as arguments and tests whether they are “equal”. Where equal means: having the same characters in the same order. Using eq? you can built the following helpful procedure:

(define (memq item x)
    (cond ((null? x) false)
          ((eq? item (car x)) x)
          (else (memq item (cdr x)))))

This basically checks if the item exists in the list x. It returns False if not, otherwise it returns the sublist of x starting with the first occurence of item.

Exercise 2.53 What would the interpreter print in response to the following expressions?

(list 'a 'b 'c) -> (a b c)
(list (list 'george)) -> ((george))
(cdr '((x1 x2) (y1 y2))) -> ((y1 y2))
(cadr '((x1 x2) (y1 y2))) -> (y1 y2)
(pair? (car '(a short list))) -> #f
(memq 'red '((red shoes) (blue socks))) -> #f
(memq 'red '(red shoes blue socks)) -> (red shoes blue socks)

Exercise 2.54 Two lists are said to be equal? if they contain equal elements arranged in the same order. Implement equal as a procedure

(define (equal? list1 list2)
  (cond ((null? list1) (null? list2))
        ((not (pair? list1)) (eq? list1 list2))
        (else (and (pair? list2)
                   (equal? (car list1) (car list2))
                   (equal? (cdr list1) (cdr list2))))))

Exercise 2.55 If you give the interpreter the following code

(car ''abracadabra)

Why does it print quote?

That is because the first quote indicates the following string is a symbol, to be taken as is, which is 'abracadabra. Taking the first element of that string with car returns ' or quote.

Example: Symbolic Differentation

As a further illustration of data abstraction, consider the design of a procedure that performs symbolic differentiation of algebraic expressions. We want the procedure to take an algebraic expression, and return the derivative with respect to the variable. For example, given: $ax^2 + bx + c$ and $x$ it should return $2ax + b$.

Differentiation has a couple simple rules, which are complicated by mathematical notation, but boil down to the following:

$\frac{dc}{dx} = 0$ or the result of differentiating a constant with regards to $x$ = 0

$\frac{dx}{dx} = 1$ or the result of differentiating $x$ with regards to $x$ = 1

$\frac{d(u + v)}{dx} = \frac{du}{dx} + \frac{dv}{dx}$ or the result of differentiating a sum with regards to $x$ is the result of differentiating the terms and adding the results

$\frac{d(uv)}{dx} = u\frac{dv}{dx} + v\frac{du}{dx}$ or *the result of differentiating a multiplication of 2 terms is the result of adding the value of the first term times the result of differentiating the term to the value of the second term times the result of differentiating that term.

Notice that the last 2 rules are recursive in nature (the individual terms can themselves exist of multiple expressions again), but these basic rules still hold. That means that all derivations eventually result in either a 0 or a 1.

To embody this problem into procedures, we again employ wishful thinking by assuming the following selectors, constructors and predicates already exist: (variable? e) Is e a variable? (same-variable? v1 v2) Are v1 and v2 the same variable? (sum? e) Is e a sum? (addend e) Added of the sum e. (augend e) Augend of the sum e. (make-sum a1 a2) Construct the sum of a1 and a2 (product? e) Is e a product? (multiplier e) Multiplier of the product e (multiplicand e) Multiplicand of the product e (make-product m1 m2) Construct the product of m1 and m2 (number? e) Is e a number?

Using these we can construct the following procedure that captures all the above differentiation rules

(define (deriv exp var)
    (cond ((number? exp) 0)
    ((variable? exp) (if (same-variable? exp var) 1 0))
    ((sum? exp) (make-sum (deriv (addend exp) var)
                          (deriv (augend exp) var)))
    ((product? exp)
        (make-sum
            (make-product (multiplier exp)
                          (deriv (multiplicand exp) var))
            (make-product (multiplicand exp)
                          (deriv (multiplier exp) var))))
    (else
        (error "unknown expression type: DERIV" exp))))

This is the COMPLETE differentiation algorithm. Because it is expressed in terms of abstract data, it will work, as long as we design a proper set of selectors and constructors. So lets implement those

Representing algebraic expressions

While there can be many ways with which to represent algebraic data structures, one specifically straight-forward notation is to basically use the same notation Lisp uses, $ax + b$ is represented as (+ (* a x) b). Then the data representation for this problem will become as follows:

Variables are defined by symbols, so checking if something is a variable is the same as checking if it is a symbol:

(define (variable? e)
    (symbol? e))

Two variables are the same if they are both symbols and they are the same symbol:

(define (same-variable? v1 v2)
    (and (variable? v1) (variable? v2) (eq? v1 v2)))

Sums and Products are defined as lists:

(define (make-sum a1 a2)
    (list '+ a1 a2))
(define (make-product m1 m2)
    (list '* m1 m2))

Something is a Sum if the first element in the list is '+:

The pair? check is needed as a safety guard to prevent runtime errors when calling car on the argument x when it is not a list

(define (sum? x)
    (and (pair? x) (eq? (car x) '+)))

and similar for a product:

(define (product? x)
    (and (pair? x) (eq? (car x) '*)))

And all the getter just return the second and third elements of the lists:

(define (addend s) (cadr s))
(define (augend s) (caddr s))

(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))

So now, the deriv procedure just works:

(deriv '(+ x 3) 'x) -> (+ 1 0)

However, it does not simplify just yet:

(deriv '(* (* x y) (+ x 3)) 'x) ->
    (+ (* (* x y) (+ 1 0))
    (* (+ (* x 0) (* 1 y))
    (+ x 3)))

This makes the result correct, but utterly unreadable. However, we once again have a choice as to where we want to put this “simplification”. We can make deriv be responsible for the simplification, leaving just simple getters and constructors. On the other hand we can leave deriv alone, opting for slightly more complicated constructors, but keeping deriv much more readable.

for example, make-sum now becomes:

(define (make-sum a1 a2)
    (cond ((=number? a1 0) a2)
          ((=number? a2 0) a1)
          ((and (number? a1) (number? a2)) (+ a1 a2))
          (else (list '+ a1 a2))))

make-sum now performs the simplification, that if it is given 2 numbers, it adds them and returns the result. It uses =number? to check if an expression is equal to a given number:

(define (=number? exp num)
    (and (number? exp) (= exp num)))

make-product can do the same thing:

(define (make-product m1 m2)
    (cond ((or (=number? m1 0)(=number? m2 0)) 0)
          ((=number? m1 1) m2)
          ((=number? m2 1) m1)
          ((and (number? m1) (number? m2)) (* m1 m2))
          (else (list '* m1 m2))))