((product? exp) (make-sum

(make-product (multiplier exp)

(deriv (multiplicand exp) var)) (make-product (deriv (multiplier exp) var) (multiplicand exp))))

(else

(error "неизвестный тип выражения -- DERIV" exp))))

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

Представление алгебраических выражений

Можно представить себе множество способов представления алгебраических выражений с помощью списковых структур. Например, можно использовать списки символов, которые отражали бы обычную алгебраическую нотацию, так что ax + b представлялось бы как список (a * x + b). Однако естественней всего использовать ту же скобочную префиксную запись, с помощью которой в Лиспе представляются комбинации; то есть представлять ax + b в виде (+ (* a x) b) . Тогда наше представление данных для задачи дифференцирования будет следующим:

•Переменные - это символы. Они распознаются элементарным предикатом symbol?:

(define (variable? x) (symbol? x))

•Две переменные одинаковы, если для представляющих их символов выполняется eq?:

(define (same-variable? v1 v2)

(and (variable? v1) (variable? v2) (eq? v1 v2)))

•Суммы и произведения конструируются как списки: (define (make-sum a1 a2) (list + a1 a2)) (define (make-product m1 m2) (list * m1 m2))

•Сумма - это список, первый элемент которого символ +:

(define (sum? x)

(and (pair? x) (eq? (car x) +)))

•Первое слагаемое - это второй элемент списка, представляющего сумму: (define (addend s) (cadr s))

• Второе слагаемое - это третий элемент списка, представляющего сумму:

(define (augend s) (caddr s))

•Произведение - это список, первый элемент которого символ *:

(define (product? x)

(and (pair? x) (eq? (car x) *)))

•Первый множитель - это второй элемент списка, представляющего произведение:

(define (multiplier p) (cadr p))

•Второй множитель - это третий элемент списка, представляющего произведение:

(define (multiplicand p) (caddr p))

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

(deriv (+ x 3) x) (+ 1 0)

(deriv (* x y) x) (+ (* x 0) (* 1 y))

(deriv (* (* x y) (+ x 3)) x)

(+ (* (* x y) (+ 1 0)) (* (+ (* x 0) (* 1 y)) (+ x 3)))

Ответы, которые выдает программа, правильны; однако их нужно упрощать. Верно, что

d(xy) п , ,

-:- = X 0 + 1 • у

dx

но нам хотелось бы, чтобы программа знала, что x • 0 = 0, 1 • y = y, а 0 + y = y. Ответом на второй пример должно быть просто у. Как видно из третьего примера, при усложнении выражений упрощение превращается в серьезную проблему.

Наши теперешние затруднения очень похожи на те, с которыми мы столкнулись при реализации рациональных чисел: мы не привели ответы к простейшей форме. Чтобы произвести приведение рациональных чисел, нам потребовалось изменить только конструкторы и селекторы в нашей реализации. Здесь мы можем применить подобную же стратегию. Процедуру deriv мы не будем изменять вовсе. Вместо этого мы изменим make-sum так, что если оба слагаемых являются числами, она их сложит и вернет их сумму. Кроме того, если одно из слагаемых равно 0, то make-sum вернет другое.

(define (make-sum al a2) (cond ((=number? al 0) a2) ((=number? a2 0) al)

((and (number? al) (number? a2)) (+ al a2)) (else (list + al a2))))

Здесь используется процедура =number?, которая проверяет, не равно ли выражение определенному числу:

(define (=number? exp num)

(and (number? exp) (= exp num)))

Подобным же образом мы изменим и make-product, так. чтобы встроить в него правила, что нечто, умноженное на 0, есть 0, а умноженное на 1 равно самому себе:

(define (make-product ml m2)

(cond ((or (=number? ml 0) (=number? m2 0)) 0) ((=number? ml l) m2) ((=number? m2 l) ml)

((and (number? ml) (number? m2)) (* ml m2)) (else (list * ml m2))))

Вот как эта версия работает на наших трех примерах:

(deriv (+ x 3) x) 1

(deriv (* x y) x)

y

(deriv (* (* x y) (+ x 3)) x) (+ (* x y) (* y (+ x 3)))

Хотя это заметное улучшение, третий пример показывает, что нужно многое еще сделать, прежде чем мы получим программу, приводящую выражения к форме, которую мы согласимся считать «простейшей». Задача алгебраического упрощения сложна, среди прочего, еще и потому, что форма, которая является простейшей для одних целей, может таковой не являться для других.

Упражнение 2.56.

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

d(un) nun-i,du-, dxdx;

добавив еще одну проверку к программе deriv и определив соответствующие процедуры exponentiation?, base, exponent и make-exponentiation (обозначать возведение в степень можно символом **). Встройте правила, что любое выражение, возведенное в степень 0, дает 1, а возведенное в степень 1 равно самому себе.

Упражнение 2.57.

Расширьте программу дифференцирования так, чтобы она работала с суммами и произведениями любого (больше двух) количества термов. Тогда последний из приведенных выше примеров мог бы быть записан как