1. Introduction

As an illustration of symbol manipulation and data abstraction, consider the design of a function that performs symbolic differentiation of algebraic expressions. We would like the function 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 function are ax2+bx+c and x, the function 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 a data abstraction strategy. 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.

2. 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:

deriv0

deriv1

deriv2

deriv3

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 function we indulge in a little wishful thinking. 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 functions 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 function:

(defn 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            (throw
                       (IllegalArgumentException.
                         (str "unknown expression type - DERIV "
                              exp)))))

This deriv function 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.

3. 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?:

    (defn variable? [x] (symbol? x))

  • Two variables are the same if the symbols representing them are the same:

    (defn same-variable?
  [v1 v2]
  (and (variable? v1) (variable? v2) (= v1 v2)))

  • Sums and products are constructed as lists:

    (defn make-sum
  [a1 a2]
  (list '+ a1 a2))

(defn make-product
  [m1 m2]
  (list '* m1 m2))

  • A sum is a list whose first element is the symbol +:

    (defn sum?
  [x]
  (and (list? x) (= (first x) '+)))

  • The addend is the second item of the sum list:

    (defn addend [s] (nth s 1))

  • The augend is the third item of the sum list:

    (defn augend [s] (nth s 2))

  • A product is a list whose first element is the symbol '*:

    (defn product?
  [x]
  (and (list? x) (= (first x) '*)))

  • The multiplier is the second item of the product list:

    (defn multiplier [p] (nth p 1))

  • The multiplicand is the third item of the product list:

    (defn multiplicand [p] (nth p 2))

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

deriv4

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 that we haven’t reduced answers to its simplest form. To accomplish the reduction, we need to change only the constructors and the selectors of the implementation. 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.

(defn make-sum
  [a1 a2]
  (cond
    (= a1 0)            a2

    (= a2 0)            a1

    (and (number? a1)
         (number? a2))  (+ a1 a2)

    :else               (list '+ a1 a2)))

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:

(defn make-product
  [m1 m2]
  (cond
    (or (= m1 0)
        (= m2 0))       0

    (= m1 1)            m2

    (= 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.

3.1. Exercise A

Extend the basic differentiator in order to implement the differentiation rule

deriv5

by adding a new clause to the deriv function and defining appropriate functions 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.

3.2. Exercise B

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 function 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.

3.3. Exercise C

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.

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.

4. Credits

This document’s text was taken from chapter 2, section 2.3.2, of “Structure and Interpretation of Computer Programs”, second edition, by Harold Abelson, Gerald Jay Sussman, and Julie Sussman, published by The MIT Press.

The source code was ported from Scheme to Clojure and the text content was transferred to AsciiDoctor by Ariel Ortiz.