Symbolic Differentiation with Lisp

Full Source Code: Exercise 2.58

Introduction

In Mathematics, differentiation is a process of calculating a derivative, which is instantaneous rate of change of a function with respect to a input value. In Computer Science, symbolic computation refers to development of programs for manipulating mathematical expressions1. In this post I will try to cover my symbolic differentiation program written as a part of SICP exercises2.

Differentiation

In this section I will try to cover the program on the basis of fundamental mathematical operations. Each sub-section will be divided into three parts: Derivative Rule, Lisp Code and REPL (Read Eval Print Loop) session. REPL itself is divided into two parts: input (denoted by >) and output.

Since differentiation is a reduction problem it is a perfect place for recursion to work, which means we will only have to exploit those rules to reduce problems into sub-problems. Procedure deriv will play a central role in our differentiation, which takes a infix expression and a variable (symbol) and outputs in derivative expression (prefix form).

Addition and Subtraction

  • Rule for addition: d(u+x)/dx = du/dx + dv/dx
  • Rule for subtraction: d(u-x)/dx = du/dx - dv/dx
(make-sum (deriv (addend expr) var)
          (deriv (augend expr) var))

(make-difference (deriv (minuend expr) var)
                 (deriv (subtrahend expr) var))

> (deriv '(x + 2) 'x)
1

> (deriv '(10 - x) 'x)
'(- 1)

Multiplication

  • Rule for multiplication: d(uv)/dx = u*dv/dx + v*du/dx
(let ((m1 (multiplier expr))
      (m2 (multiplicand expr)))
  (make-sum
   (make-product m1 (deriv m2 var))
   (make-product m2 (deriv m1 var))))

> (deriv '(10 * x + (20 - 30) * x) 'x)
0

> (deriv '(10 * x * x) 'x)
'(+ (* 10 x) (* x 10))

> (deriv '(x * x * x * x) 'x)           ; Don't worry!
'(+ (* (* x x) x) (* x (+ (* x x) (* x (+ x x)))))

Exponentiation

  • Rule for exponentiation: d(un)/dx = n*u(n-1) * du/dx
(let ((b (base expr))
      (e (exponent expr)))
  (make-product
   (make-product e (make-exponentiation b (make-sum e -1)))
   (deriv b var)))

> (deriv '(x ^ 4) 'x)
'(* 4 (^ x 3))

> (deriv '(x ^ (3 + 2)) 'x)
'(* 5 (^ x 4))

> (deriv '((x ^ (3 + 2)) + 3 * x + (x ^ 10)) 'x)
'(+ (* 5 (^ x 4)) (+ 3 (* 10 (^ x 9))))

Division

  • Rule for division: d(u/v)/dx = (v*du/dx - u*dv/dx) / v2
(let ((d1 (dividend expr))
      (d2 (divisor expr)))
  (make-ratio
   (make-difference (make-product d2 (deriv d1 var))
                    (make-product d1 (deriv d2 var)))
   (make-exponentiation d2 2)))

> (deriv '(2 / x) 'x)
'(/ (- 2) (^ x 2))

> (deriv '(2 / (x + 1)) 'x)
'(/ (- 2) (^ (+ x 1) 2))

> (deriv '( (x ^ 2) / (3 * x - 1)) 'x)
'(/ (- (* (- (* 3 x) 1) (* 2 x)) (* (^ x 2) 3)) (^ (- (* 3 x) 1) 2))

Unary operations

  • Chain rule: d(f(g(x)))/dx = df/dx * d(g(x))/dx
(make-product
 (deriv-unary expr)
 (deriv-prefix (argument expr) var))

> (deriv '(sin x) 'x)
'(cos x)

> (deriv '(sin (2 * x + 1)) 'x)
'(* (cos (+ (* 2 x) 1)) 2)

> (deriv '(sin (3 * x + 1) ^ (1 / 2)) 'x)
'(* (cos (^ (+ (* 3 x) 1) (/ 1 2))) (* (* (/ 1 2) (^ (+ (* 3 x) 1) (+ (/ 1 2) -1))) 3))

Conclusion

This program is prefect in no-regards such as it cannot transform x * x * x into x ^ 3, 0 / x into 0, etc. But anyway, I really enjoyed writing the program and Lisp was really helpful in the process.

Thank you!

Footnotes:

1

See Wikipedia's page on Computer Algebra.

2

SICP is a computer science textbook by Massachusetts Institute of Technology by professors Harold Abelson and Gerald Jay Sussman with Julie Sussman. Also see its offical website.