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:

deriv0

deriv1

deriv2

deriv3

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?

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

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:

deriv4

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.