Решение упражнения 2.73 из SICP

20 February, 2008 (21:22) | Решения упражнений

Выполнять это упражнение не очень удобно, так как операции put и get пока что для нас виртуальны, а значит опробовать код на практике не удастся. Тем не менее начнем.

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

Предикаты number? и variable? не содержат операцию, по которой собственно и происходит диспетчеризация. Таким образом включать их в общую схему выбора, управляемого данными, не имеет смысла.

б. Код для операций дифференцирования для сумм и произведений оформлен в виде пакета и представлен ниже:

(define (install-sum-product-package) 
  (define (make-sum a1 a2) 
    (list '+ a1 a2)) 
  (define (addend s) (car s)) 
  (define (augend s) (cadr s)) 
  (define (deriv-sum exp var) 
    (make-sum (deriv (addend exp) var) 
              (deriv (augend exp) var))) 
  (define (make-product m1 m2) 
    (list '* m1 m2)) 
  (define (multiplier p) (car p)) 
  (define (multiplicand p) (cadr p)) 
  (define (deriv-product exp var) 
    (make-sum 
      (make-product (multiplier exp) 
                    (deriv (multiplicand exp) var)) 
      (make-product (deriv (multiplier exp) var) 
                           (multiplicand exp)))) 
  (put 'deriv '+ deriv-sum) 
  (put 'deriv '* deriv-product) 
  'done)

Операции put просто задают значения элементов таблицы. В таблицу помещаются сами символы + и *, обозначающие тип операции, а не списки, поскольку этого достаточно для решения задачи.

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

(define (make-exponentiation base exp) 
  (list '** base exp)) 
(define (base e) (car e)) 
(define (exponent e) (cadr e)) 
(define (deriv-exponentiation  exp var) 
  (make-product 
    (make-product 
      (exponent exp) 
      (make-exponentiation (base exp) 
                           (- (exponent exp) 1))) 
      (deriv (base exp) var))) 
(put 'deriv '** deriv-exponentiation)

Этот вариант добавления нового правила для вычисления производной имеет тот минус, что нам нужно изменять старый пакет. Вместо этого мы могли бы создать отдельный новый пакет, содержащий только определение производной для возведения в степень, и не затрагивающий пакет для производных сумм и произведений. Но тогда мы столкнемся с некоторыми трудностями, так как конструктор make-product, который используется при построении производной экспоненты, определен внутри другого пакета и недоступен. Можно вынести конструкторы и селекторы за пределы пакетов, что решит узкую проблему, но не является удачным выходом, поскольку теперь части определений не сгруппированы в пакеты и не скрывают имена.

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

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

Comments

Comment from anton0xf
Date: September 20, 2009, 2:28 pm

>тогда мы столкнемся с некоторыми трудностями, так как конструктор make-product, который используется при построении производной экспоненты, определен внутри другого пакета и недоступен.

можно еще положить операции make-sum и make-product в ту же таблицу (например (put 'math-operation '* make-product)) и брать оттуда

Comment from Denis Larionov
Date: January 11, 2017, 12:00 pm

put и get

(define *op-table* (make-hash))
(define (put op type proc)
  (hash-set! *op-table* (list op type) proc))
(define (get op type)
  (hash-ref *op-table* (list op type) '()))

1.конструкторы и селекторы для операций оставил во вне, они ведь служат универсальной абстракцией, скрывающей устройство выражений.
2.вместо того, что бы менять устройство селекторов выражений, заменил в deriv (operands exp) на exp, так что они по прежнему принимают целые выражения (в любом виде)
3.каждую операцию реализовал в виде отдельного пакета

(define (operator exp) (car exp))

(define (deriv exp var)
  (install-sum-package)
  (install-product-package)
  (install-expt-package)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        (else
         ((get 'deriv (operator exp)) exp var))))

(define (install-sum-package)
  (define (deriv-sum exp var)
    (make-sum
     (deriv (addend exp) var)
     (deriv (augend exp) var)))
  (put 'deriv '+ deriv-sum))

(define (install-product-package)
  (define (deriv-product exp var)
    (make-sum
     (make-product (multiplier exp)
                   (deriv (multiplicand exp) var))
     (make-product (deriv (multiplier exp) var)
                   (multiplicand exp))))
  (put 'deriv '* deriv-product))

(define (install-expt-package)
  (define (deriv-expt exp var)
    (let ((b (base exp))
          (n (power exp)))
      (make-product
       (make-product n (make-exp b (- n 1)))
       (deriv b var))))
  (put 'deriv '^ deriv-expt))

(deriv '(+ (^ x 3) (* x 2 x) (* x x y x x) (+ 1 2 3 x)) 'x)

Write a comment