SICP - Symbolic differentiation and quotation in LISP

This lecture looks at producing derivatives using algebraic notation and calculus rules rather than the numeric estimation we looked at in an earlier lecture.  One interesting point made was that LISP expressions actually exhibit a list structure.

This was a shorter lecture (45min instead of the usual 75min), so the notes are a bit shorter:



Symbolic Differentiation; Quotation

In order to build robust systems, it must be insensitive to small changes. Instead of solving every problem at every decomposed level of detail, you create solutions to neighbourhoods of problems. By creating a language to solve a class of problems, only small changes are necessary to solve multiple, slightly different problems.

We are going to look at creating programs that implement rules from calculus that calculate exact values instead of numerical approximations. 

In derivation, the right hand side is a proper sub expression of the left hand side. These are reduction rules. Producing integrals is difficult because multiple rules may match a given pattern and they don't easily terminate.

(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 (PRODUCT  (M1 EXP)
(DERIV (M2 EXP) VAR))
 (PRODUCT  (DERIV (M1 EXP) VAR)
(M2 EXP))))

Many of these representations have not yet been implemented... programming by "wishful thinking".
LISP expressions are expressed in a list structure.

(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) '+)))

The quote asks the interpreter to look for the sympolic representation of the addition operator, not the addition operator itself.

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

Representationally opaque concepts, of which quotations are a prime case, make a language more complex.

(DEFINE (MAKE-SUM A1 A2)
(LIST '+ A1 A2))
(DEFINE A1 CADR)
CADR is the CAR of the CDR of something.

Names CAR and CDR come from when the language was being developed and there were address and decriment registers where the values were stored.
(+ 3 5 )
[ | ] -- [ | ] -- [ |/]
 |        |        |
 '+       3        5

 (DEFINE (PRODECT? EXP)
(AND (NOT (ATOM? EXP))
(EQ? (CAR EXP) '*)))

(DEFINE (MAKE-PRODUCT M1 M2)
(LIST '* M1 M2))

(DEFINE M1 CADR)
(DEFINE M2 CADDR)

(DEFINE FOO          ; a*x*x + b*x + c
(+ (* (+ x x))
(+ (+ b x)
  c)))
  
=> (DERIV FOO X)    ; 2*a*x + b
(+ (+ (* A (+ (* X 1)(* 1 X)))
      (* 0 (* X X)))
   (+ (* (* B 1) (* 0 X))
      0))
The resulting expression is very messy and hard to read. 
This result is due to the "walk" that the procedure takes through the expression. Other expressions produce a nearly identical pattern in the result.

DERIV RULES
--------------------------------------
CONSTANT?, SUM? MAKE-SUM, A1, A2, ....
--------------------------------------
Representation as list structure

Because of abstraction layer, possible to change representation without changing the DERIV rules.

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

After changing constructor for expressions, get much better results:
(DERIV FOO 'X)
(+ (* A (+ X X)) B)