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.

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 represented. Only afterward will we address the representation problem.

2. Basic Program

We want a Clojure function (deriv exp var) that allows doing symbolic differentiation using the following reduction rules:

\[\frac{dc}{dx} = 0\]

Where \(c\) is a constant or a variable different from \(x\).
\[\frac{dx}{dx} = 1\]
\[\frac{d(u+v)}{dx}=\frac{du}{dx}+\frac{dv}{dx}\]
\[\frac{d(u\cdot v)}{dx}=u \left ( \frac{dv}{dx} \right ) + v \left ( \frac{du}{dx} \right )\]

We’ll use and define the following helper functions:

(variable? e)

Is e a variable?

(same-variable? v1 v2)

Are v1 and v2 the same variable?

(sum? e)

Is e a sum?

(augend e)

Augend of the sum e.

(addend e)

Addend of the sum e.

(make-sum a1 a2)

Construct the sum of a1 and a2.

(product? e)

Is e a product?

(multiplicand e)

Multiplicand of the product e.

(multiplier e)

Multiplier of the product e.

(make-product m1 m2)

Construct the product of m1 and m2.

This is how the deriv function should work:

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

(deriv '(* x y) 'x)
=> (+ (* x 0) (* y 1))

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

Modify the make-sum and make-product functions in order to reduce their answers to its simplest form. Here’s how this new version should work on the three previous examples:

(deriv '(+ x 3) 'x)
=> 1

(deriv '(* x y) 'x)
=> y

(deriv '(* (* x y) (+ x 3)) 'x)
=> (+ (* x y) (* (+ x 3) y))

3. Extended Program

Extend the basic program in order to implement the differentiation rule:

\[\frac{d(u^n)}{dx} = n \cdot u^{n-1} \left ( \frac{du}{dx} \right )\]

Add a new clause to the deriv function and define 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.

4. Credits

This exercise 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.