Structure and Interpretation of Computer Programs

is false. To be more precise, we can define 

equal?

 recursively in terms of the basic 

eq?

 equality of

symbols by saying that 

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)

. Using this idea, implement 

equal?

 as a procedure.

36

 

Exercise 2.55.  Eva Lu Ator types to the interpreter the expression 

(car ’’abracadabra)

To her surprise, the interpreter prints back 

quote

. Explain. 

2.3.2  Example: Symbolic Differentiation

As an illustration of symbol manipulation and a further illustration of data abstraction, consider the

design of a procedure that performs symbolic differentiation of algebraic expressions. We would like

the procedure to take as arguments an algebraic expression and a variable and to return the derivative

of the expression with respect to the variable. For example, if the arguments to the procedure are ax

2

+ bx + c and x, the procedure should return 2ax + b. Symbolic differentiation is of special historical

significance in Lisp. It was one of the motivating examples behind the development of a computer

language for symbol manipulation. Furthermore, it marked the beginning of the line of research that

led to the development of powerful systems for symbolic mathematical work, which are currently

being used by a growing number of applied mathematicians and physicists.

In developing the symbolic-differentiation program, we will follow the same strategy of data

abstraction that we followed in developing the rational-number system of section 2.1.1. That is, we

will first define a differentiation algorithm that operates on abstract objects such as ‘‘sums,’’

‘‘products,’’ and ‘‘variables’’ without worrying about how these are to be represented. Only afterward

will we address the representation problem.

The differentiation program with abstract data

In order to keep things simple, we will consider a very simple symbolic-differentiation program that

handles expressions that are built up using only the operations of addition and multiplication with two

arguments. Differentiation of any such expression can be carried out by applying the following

reduction rules:

Observe that the latter two rules are recursive in nature. That is, to obtain the derivative of a sum we

first find the derivatives of the terms and add them. Each of the terms may in turn be an expression

that needs to be decomposed. Decomposing into smaller and smaller pieces will eventually produce

pieces that are either constants or variables, whose derivatives will be either 0 or 1.

---

To embody these rules in a procedure we indulge in a little wishful thinking, as we did in designing

the rational-number implementation. If we had a means for representing algebraic expressions, we

should be able to tell whether an expression is a sum, a product, a constant, or a variable. We should

be able to extract the parts of an expression. For a sum, for example we want to be able to extract the

addend (first term) and the augend (second term). We should also be able to construct expressions

from parts. Let us assume that we already have procedures to implement the following selectors,

constructors, and predicates:

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

 

Addend 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

.

Using these, and the primitive predicate 

number?

, which identifies numbers, we can express the

differentiation rules as the following procedure:

(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 (deriv (multiplier exp) var)

                         (multiplicand exp))))

        (else

         (error "unknown expression type -- DERIV" exp))))

This 

deriv

 procedure incorporates the complete differentiation algorithm. Since it is expressed in

terms of abstract data, it will work no matter how we choose to represent algebraic expressions, as

long as we design a proper set of selectors and constructors. This is the issue we must address next.

---