SICP 03B - Symbolic Differentiation

Lecture Info

In this lecture we have approached the problem of symbolic differentiation by introducing the quotation operator, a crucial operator offered by the LISP language.

1 Robust Systems

When we talk about robust systems we are referring to systems that have a certain level of insensitiveness to small change. That is, we want to build our systems so that a small change in the problem should be reflected with only a small cahnge in the solution (in the system).

We would also like to have a sort of continuity property. That is, the space solution ought to be continuous in the space of problems.

2 Differentiation

In one of the first lecture we saw a numerical approximation for the value of the derivative of a function that could be implemented with a procedure such as 

(define deriv
  (lambda (f)
    (lambda (x)
      (/ (- (f (+ x dx))
            (f x))
         dx))))

Let us now consider the problem of differentiation from a different point of view. In particular we would like to talk about algebraic manipulations for finding the derivative of expressions that one might write in an algebraic language.

To proceed, let us use our usual strategy: wishful thinking. Indeed, let us assume we have some way of representing algebraic expressions and some way of understanding whether a given expression is a constant, or a variable, or a sum or a product. Then we could write the following procedure, which simply executes the typical derivation rules 

(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 (m1 exp)
                        (deriv (m2 exp) var))
          (make-product (deriv (m1 exp) var)
                        (m2 exp))))))

3 The Quotation Operator

To represent algebraic expression we will have to make use of a particular operator offered by the LISP language, which is called the qutation operator and represented as the symbol ' . This operator has the same meaning as it does in natural languages. For example, the expression 'Say your name', is interpreted as asking you so say your name, but the expression 'Say "your name"', is interpreted as asking you to say "your name".

Quotation is a very complex concept. The quotation mark allows us to talk about the syntactical nature of a word, and not what it represents. When we add the usage of quotation we cannot then just substitute equals for equals when working with referential opaque contexts, of which a quotation is a prototipical type of a referencial opaque contexts.

4 Representing Algebraic Expressions

How do we represent algebraic expressions? Well, an idea could be to simply represent them by using the same language as I'm writing my program in, which in our case is LISP.

Consider for example the following algebraic expression

\[a \cdot x^2 + b \cdot x + c\]

using the LISP syntax, I could write it as follows 

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

This notation is very conveniente since I don't have to parse it: the interpreter of the language is already built to parse such notation!

Let us now define the procedure that work on this kind of representation:

4.1 Constants and Variables

In our notation something is a constant if it cannot be broken down into pieces, that is, if its not a list, and its not equal to the var we're integerating with respect to. In code this translates into 

(define (constant? exp var)
  (and (atom? exp)
       (not (eq? exp var))))

Something then is same-var when it is not a list and it is equal to the var 

(define (same-var? exp var)
  (and (atom? exp)
       (eq? exp var)))

4.2 Sums

The sum predicate then is implemented by making use of the quotation operator 

(define (sum? exp)
  (and (not (atom? exp))
       (eq (car exp) '+)))

By using ' we are able to see the symbol + in two different ways:

  1. Without the quote + represents the atomic sum procedure.

  2. With the quote + represents the symbol plus itself, that is, we devode it of any interpretation and we just consider its syntactical and symbolical nature.

To make a sum then we do the following 

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

while to get the first and second element of the sum we use the cadr and caddr operator, which respective compute the car of the cdr of a list and the car of the cdr of the cdr of a list. 

(define a1 cadr)
(define a2 caddr)

4.3 Products

What we did for the sums can also be applied directly for the products as follows.

  • Check if something is a product 

    (define (product? exp)
  (and (not (atom? exp))
       (eq? (car exp) '*)))

  • Make a product 

    (define (make-product m1 m2)
  (list '* m1 m2))

  • Get first/second element from a product 

    (define m1 cadr)
(define m2 caddr)

4.4 Simplifying

With the represention we have defined so far, if we apply the deriv procedure we get realy complex expressions really fast.

To solve this problem we could change the representation and add steps that simplify the various expressions. For example the make-sum procedure could understand that if we are summing two numbers and one of them is \(0\), then the sum is equal to the other number. 

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

Notice that we can do this because we have the divided the world in derivation rules and representation of algebraic expresions.

As we can see, the quotation mark is very important, because it allows us to write representations that share the same syntatical represention of the program those representaiton are executed in, meaning that we can parse the expression without writing any additional code.