2.3.2 · Символьные данные

Символьное дифференцирование дерева выражений

Когда суммы и произведения представлены в виде списков, рекурсивные селекторы и конструкторы могут получить новое выражение без вычисления исходного.

Вопрос для размышления

Как конструкторы данных отделяют алгебраическое упрощение от правил дифференцирования?

Классификация чисел, переменных, сумм и произведений как данных выражений
Рекурсивное применение правил дифференцирования суммы и произведения
Упрощение случаев с нулем, единицей и числами в конструкторах
Чтение возвращенной производной как нового дерева выражений

deriv выполняет диспетчеризацию по форме данных выражения. Числа дают 0, выбранная переменная дает 1, а списки сумм или произведений рекурсивно дифференцируют свои операнды.

make-sum и make-product отвечают за очистку представления. Они удаляют сложение с нулем, умножение на ноль или единицу и объединяют числовые операнды, поэтому ветви дифференцирования формулируют математические правила без повторения деталей упрощения.

Код SICP1,188 из 1,048,576 байт UTF-8

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

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Первая программа возвращает (+ x (+ x 3)). Вторая программа возвращает (+ 3 (+ x x)).

На что обратить внимание в трассе

Проследите за тем, как deriv спускается по цитированному дереву, а затем наблюдайте, как make-sum и make-product удаляют случаи с нулем и единицей при повторном построении результата. Возвращаемый список представляет собой данные выражения, а не вычисленную числовую производную.

Попробуйте сами

Измените программу и сравните результат.

Продифференцируйте '(* x (* x x)) по x. Заранее определите неупрощенные повторяющиеся члены, которые сохранят эти конструкторы.

Показать подсказку

Примените правило дифференцирования произведения в обоих узлах произведения. Эти конструкторы упрощают только ноль, единицу и два числовых операнда.

Завершить этот урок

В этой главе пройдено 0 из 20 уроков0%