Structure and Interpretation of Computer Programs

Representing algebraic expressions

We can imagine many ways to use list structure to represent algebraic expressions. For example, we

could use lists of symbols that mirror the usual algebraic notation, representing ax + b as the list 

(a *

x + b)

. However, one especially straightforward choice is to use the same parenthesized prefix

notation that Lisp uses for combinations; that is, to represent ax + b as 

(+ (* a x) b)

. Then our

data representation for the differentiation problem is as follows:

The variables are symbols. They are identified by the primitive predicate 

symbol?

:

(define (variable? x) (symbol? x))

Two variables are the same if the symbols representing them are 

eq?

:

(define (same-variable? v1 v2)

  (and (variable? v1) (variable? v2) (eq? v1 v2)))

Sums and products are constructed as lists:

(define (make-sum a1 a2) (list ’+ a1 a2))

(define (make-product m1 m2) (list ’* m1 m2))

A sum is a list whose first element is the symbol 

+

:

(define (sum? x)

  (and (pair? x) (eq? (car x) ’+)))

The addend is the second item of the sum list:

(define (addend s) (cadr s))

The augend is the third item of the sum list:

(define (augend s) (caddr s))

A product is a list whose first element is the symbol 

*

:

(define (product? x)

  (and (pair? x) (eq? (car x) ’*)))

The multiplier is the second item of the product list:

(define (multiplier p) (cadr p))

The multiplicand is the third item of the product list:

(define (multiplicand p) (caddr p))

Thus, we need only combine these with the algorithm as embodied by 

deriv

 in order to have a

working symbolic-differentiation program. Let us look at some examples of its behavior:

---

(deriv ’(+ x 3) ’x)

(+ 1 0)

(deriv ’(* x y) ’x)

(+ (* x 0) (* 1 y))

(deriv ’(* (* x y) (+ x 3)) ’x)

(+ (* (* x y) (+ 1 0))

   (* (+ (* x 0) (* 1 y))

      (+  x 3)))

The program produces answers that are correct; however, they are unsimplified. It is true that

but we would like the program to know that x · 0 = 0, 1 · y = y, and 0 + y = y. The answer for the

second example should have been simply 

y

. As the third example shows, this becomes a serious issue

when the expressions are complex.

Our difficulty is much like the one we encountered with the rational-number implementation: we

haven’t reduced answers to simplest form. To accomplish the rational-number reduction, we needed to

change only the constructors and the selectors of the implementation. We can adopt a similar strategy

here. We won’t change 

deriv

 at all. Instead, we will change 

make-sum

 so that if both summands

are numbers, 

make-sum

 will add them and return their sum. Also, if one of the summands is 0, then 

make-sum

 will return the other summand.

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

This uses the procedure 

=number?

, which checks whether an expression is equal to a given number:

(define (=number? exp num)

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

Similarly, we will change 

make-product

 to build in the rules that 0 times anything is 0 and 1 times

anything is the thing itself:

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

Here is how this version works on our three examples:

(deriv ’(+ x 3) ’x)

1

(deriv ’(* x y) ’x)

y

---

(deriv ’(* (* x y) (+ x 3)) ’x)

(+ (* x y) (* y (+ x 3)))

Although this is quite an improvement, the third example shows that there is still a long way to go

before we get a program that puts expressions into a form that we might agree is ‘‘simplest.’’ The

problem of algebraic simplification is complex because, among other reasons, a form that may be

simplest for one purpose may not be for another. 

Exercise 2.56.  Show how to extend the basic differentiator to handle more kinds of expressions. For

instance, implement the differentiation rule

by adding a new clause to the 

deriv

 program and defining appropriate procedures 

exponentiation?

, 

base

, 

exponent

, and 

make-exponentiation

. (You may use the

symbol 

**

 to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and

anything raised to the power 1 is the thing itself. 

Exercise 2.57.  Extend the differentiation program to handle sums and products of arbitrary numbers

of (two or more) terms. Then the last example above could be expressed as 

(deriv ’(* x y (+ x 3)) ’x)

Try to do this by changing only the representation for sums and products, without changing the 

deriv

 procedure at all. For example, the 

addend

 of a sum would be the first term, and the 

augend

would be the sum of the rest of the terms. 

Exercise 2.58.  Suppose we want to modify the differentiation program so that it works with ordinary

mathematical notation, in which 

+

 and 

*

 are infix rather than prefix operators. Since the differentiation

program is defined in terms of abstract data, we can modify it to work with different representations of

expressions solely by changing the predicates, selectors, and constructors that define the representation

of the algebraic expressions on which the differentiator is to operate.

a. Show how to do this in order to differentiate algebraic expressions presented in infix form, such as 

(x + (3 * (x + (y + 2))))

. To simplify the task, assume that 

+

 and 

*

 always take two

arguments and that expressions are fully parenthesized.

b. The problem becomes substantially harder if we allow standard algebraic notation, such as 

(x + 3

* (x + y + 2))

, which drops unnecessary parentheses and assumes that multiplication is done

before addition. Can you design appropriate predicates, selectors, and constructors for this notation

such that our derivative program still works? 

2.3.3  Example: Representing Sets

In the previous examples we built representations for two kinds of compound data objects: rational

numbers and algebraic expressions. In one of these examples we had the choice of simplifying

(reducing) the expressions at either construction time or selection time, but other than that the choice

of a representation for these structures in terms of lists was straightforward. When we turn to the

representation of sets, the choice of a representation is not so obvious. Indeed, there are a number of

possible representations, and they differ significantly from one another in several ways.

---