2.6 · 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.

Lispex · SICP sourceScheme-compatible SICP syntax executed by the Lispex SICP profile.

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

Lispex learning runtimeLispex SICP profile 1.0.0

Loading Lispex SICP runtime

Lispex · SICP source1,188 / 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))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Visible execution0 / 0 trace events

This browser result is not a Lispex Vouch record or authority.wasm —

Expected observation

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 before you read the hint.

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

Show one hint

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