SICP 3b
Symbolic Differentiation Quotation

Table of Contents

1 Recap

In order to make a system that's robust, it has to be insensitive to small changes. A small change in the problem should lead to only a small change in the solution. There ought to be a continuity; the space of solutions ought to be continuous with respect to the space of problems.

Instead of solving a particular problem at every level of decomposition of the problem into subproblems, solve the class of problems by producing a language at that level of detail.

2 Rules of differentiation

  1. d c d x = c 𝑑 𝑐 𝑑 𝑥 𝑐 \dfrac{dc}{dx}=c where c 𝑐 c is a constant
  2. d x d x = 1 𝑑 𝑥 𝑑 𝑥 1 \dfrac{dx}{dx}=1
  3. d c u d x = c d u d x 𝑑 𝑐 𝑢 𝑑 𝑥 𝑐 𝑑 𝑢 𝑑 𝑥 \dfrac{dcu}{dx}=c\dfrac{du}{dx}
  4. d ( u + v ) d x = d u d x + d v d x 𝑑 𝑢 𝑣 𝑑 𝑥 𝑑 𝑢 𝑑 𝑥 𝑑 𝑣 𝑑 𝑥 \dfrac{d(u+v)}{dx}=\dfrac{du}{dx}+\dfrac{dv}{dx}
  5. d u v d x = u d v d x + d u d x v 𝑑 𝑢 𝑣 𝑑 𝑥 𝑢 𝑑 𝑣 𝑑 𝑥 𝑑 𝑢 𝑑 𝑥 𝑣 \dfrac{duv}{dx}=u\dfrac{dv}{dx}+\dfrac{du}{dx}v
  6. d u v d x = v d u d x - u d v d x v 2 𝑑 𝑢 𝑣 𝑑 𝑥 𝑣 𝑑 𝑢 𝑑 𝑥 𝑢 𝑑 𝑣 𝑑 𝑥 superscript 𝑣 2 \dfrac{d\frac{u}{v}}{dx}=\dfrac{v\frac{du}{dx}-u\frac{dv}{dx}}{v^{2}}
  7. d u n d x = n u n - 1 d u d x 𝑑 superscript 𝑢 𝑛 𝑑 𝑥 𝑛 superscript 𝑢 𝑛 1 𝑑 𝑢 𝑑 𝑥 \dfrac{du^{n}}{dx}=nu^{n-1}\dfrac{du}{dx}

Differentiation is easier than integration because differentiation abides to reduction rules.

3 Syntax

Differentiation in LISP.

(define (deriv exp var)
  (cond ((constant? exp var) 0)
       ((same-var? exp var) 1)
       ((sum? exp)
        (make-sum (deriv (a1 exp) var)
                  (deriv (a2 exp) var)))
       ((product? exp)
        (make-sum
         (make-product (m2 exp)
                       (deriv (m2 exp) var))
         (make-product (deriv (m1 exp) var)
                       (m2 exp))))
       ...
       ))

Note: ? is a convention for indicating a predicate procedure.

Implementing differentiation in LISP necessitates care with syntax. How should mathematical expressions be represented? Let's use the same syntax as LISP.

Let the following two expressions represent the same concept: a x 2 + b x + c 𝑎 superscript 𝑥 2 𝑏 𝑥 𝑐 ax^{2}+bx+c

(+ (* a (* x x))
   (+ (* b x) c))

4 Quotation

Having decided how expressions will be represented, implement the predicate procedures.

(define (constant? exp var)
  (and (atom? exp)
       (not (eq? exp var))))
(define (same-var? exp var)
  (and (atom? exp)
       (eq? exp var)))
(define (sum? exp)
  (and (not (atom? exp))
       (eq? (car exp) '+)))

'+ means the the symbol + as opposed to the operation +. The difference between the two is similar to the difference between the following two instructions:

  • say "your name".
  • say your name.

Quotation is an inherently complex concept. Adding it to a language causes a great deal of trouble.

"Chicago" has seven letters.
Chicago is the biggest city in Illinois.


=> "The biggest city in Illinois" has seven letters.

Evidently quotation introduces a flaw here. Quotation forbids substitution into referentially opaque contexts.

(define (make-sum a1 a2)
  (list '+ a1 a2))
(define a1 cadr)
(define a2 caddr)

Note: car: contents of address register. cdr: contents of decrement register.

(define (product? exp)
  (and (not (atom? exp))
       (eq? (car exp) '*)))
(define (make-product m1 m2)
  (list '* m1 m2))
(define m1 cadr)
(define m2 caddr)

Testing reveals a fly in the ointment in this implementation.

(define foo
  (+ (* a (* x x))
     (+ (* b x)
        c)))
(derive foo 'x)

Results in the following abomination.

(+ (+ (* a (+ (* x 1) (* 1 x)))
      (* 0 (* x x)))
   (+ (+ (* b 1) (* 0 x))
      0))

Solve this in the following section.

5 Rinse and repeat

There aren't too many good ideas… If something worked last time, it ought to work again.

The abstraction layer separating the differentiation rules from the representations as list structure consists of constant?, same-var?, sum?, make-sum, a1, a2 etc. So to make the answers prettier, make a change in the abstraction layer.

(define (make-sum a1 a2)
  (cond ((and (number? a1) (number? a2))
         (+ a1 a2))
        ((and (number? a1) (= a1 0))
         a2)
        ((and (number? a2) (= a2 0))
         a1)
        (else (list '+ a1 a2))))
(define (make-product m1 m2)
  ...)

The answers are now much better.

(deriv foo 'x)
(+ (* a (+ x x)) b)
(deriv foo 'a)
(* a a)
(deriv foo 'b)
x
(deriv foo 'c)
1

Quotation is necessitated by the choice to represent expressions in the same syntax as the underlying language.