Symbolic Differentiation with Lisp
2021-08-19
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 its 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 expression
EXPR and variable VAR with respect to which differentiation has to be
performed.
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:
See Wikipedia's page on Computer Algebra.
SICP is an introductory computer science textbook by professors Harold Abelson and Gerald Jay Sussman with Julie Sussman. Also see its offical website.