2.3.2 · Symbolic data

A differentiation rule can transform an expression tree.

When sums and products are represented as lists, recursive selectors and constructors can derive a new expression without evaluating the original one.

Guiding question

How do data constructors keep algebraic simplification separate from differentiation rules?

Classify numbers, variables, sums, and products as expression data
Apply sum and product differentiation rules recursively
Simplify zero, one, and numeric cases in constructors
Read the returned derivative as a new expression tree

deriv dispatches on the shape of expression data. Numbers produce 0, the selected variable produces 1, and sum or product lists recursively derive their operands.

make-sum and make-product own representation cleanup. They remove additions by zero, multiplications by zero or one, and combine numeric operands, so the differentiation cases state their mathematical rules without repeating simplification details.

SICP code1,188 of 1,048,576 UTF-8 bytes

(begin
  (define (=number? expression number)
    (and (number? expression) (= expression number)))
  (define (make-sum left right)
    (cond ((=number? left 0) right)
          ((=number? right 0) left)
          ((and (number? left) (number? right)) (+ left right))
          (else (list '+ left right))))
  (define (make-product left right)
    (cond ((or (=number? left 0) (=number? right 0)) 0)
          ((=number? left 1) right)
          ((=number? right 1) left)
          ((and (number? left) (number? right)) (* left right))
          (else (list '* left right))))
  (define (deriv expression variable)
    (cond ((number? expression) 0)
          ((symbol? expression)
           (if (eq? expression variable) 1 0))
          ((eq? (car expression) '+)
           (make-sum (deriv (cadr expression) variable)
                     (deriv (caddr expression) variable)))
          ((eq? (car expression) '*)
           (make-sum
             (make-product (cadr expression)
                           (deriv (caddr expression) variable))
             (make-product (deriv (cadr expression) variable)
                           (caddr expression))))))
  (deriv '(* x (+ x 3)) 'x))

(begin
  (define (=number? expression number)
    (and (number? expression) (= expression number)))
  (define (make-sum left right)
    (cond ((=number? left 0) right)
          ((=number? right 0) left)
          ((and (number? left) (number? right)) (+ left right))
          (else (list '+ left right))))
  (define (make-product left right)
    (cond ((or (=number? left 0) (=number? right 0)) 0)
          ((=number? left 1) right)
          ((=number? right 1) left)
          ((and (number? left) (number? right)) (* left right))
          (else (list '* left right))))
  (define (deriv expression variable)
    (cond ((number? expression) 0)
          ((symbol? expression)
           (if (eq? expression variable) 1 0))
          ((eq? (car expression) '+)
           (make-sum (deriv (cadr expression) variable)
                     (deriv (caddr expression) variable)))
          ((eq? (car expression) '*)
           (make-sum
             (make-product (cadr expression)
                           (deriv (caddr expression) variable))
             (make-product (deriv (cadr expression) variable)
                           (caddr expression))))))
  (deriv '(* x (+ x 3)) 'x))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns (+ x (+ x 3)). The second returns (+ 3 (+ x x)).

Trace focus

Follow deriv down the quoted tree, then watch make-sum and make-product remove zero and one cases while rebuilding the result. The returned list is expression data, not an evaluated numeric derivative.

Try it yourself

Change the program and compare the result.

Differentiate '(* x (* x x)) with respect to x. Predict the unsimplified repeated terms that these constructors retain.

Show hint

Apply the product rule at both product nodes. These constructors simplify only zero, one, and two numeric operands.

Complete this lesson

0 of 20 lessons complete in this chapter0%