SICP Exercise 2.73 a (dispatch for symbolic differentiation)

Exercise 2.73.  Section 2.3.2 described a program that performs symbolic differentiation:

 (define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp) (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        <more rules can be added here>
        (else (error "unknown expression type -- DERIV" exp))))

 We can regard this program as performing a dispatch on the type of the expression to be
differentiated. In this situation the ''type tag'' of the datum is the algebraic operator
symbol (such as +) and the operation being performed is deriv. We can transform this
program into data-directed style by rewriting the basic derivative procedure as

 (define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) (if (same-variable? exp var) 1 0))
         (else ((get 'deriv (operator exp)) (operands exp)
                                            var))))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))

 a.  Explain what was done above. Why can't we assimilate the predicates number? and same-variable? into the data-directed dispatch?

 Answer:

 The conditional statements in the original implementation have been replaced with the
dispatch method in which the type of arithmetic operation (+, * or **) is used as a key to
index into the table of operations/procedures, and the found procedure is called with the
arguments it expects. This is data-directed programming applied to different 'deriv'
procedures that implement the rules of differentiation and calling the correct one using
the entries in the table. 

 The table of operations is this:

 -------------------------------------------------------------------------------
| + | * | ^
-------------------------------------------------------------------------------
deriv | deriv-of-sum | deriv-of-product | deriv-of-exponentiation
-------------------------------------------------------------------------------

 We cannot assimilate number? and same-variable? because the structure of this procedure allows for
dispatches based on specific operators like +, *, ** etc. The dispatch process depends on the call to
the procedure named 'operator' which expects the first element in the list to be an operator. Moreover, it
expects 'exp' to be a pair. But exp may be a number or just a variable in which case it will not be a pair.
So number? and same-variable? need to be handled before the dispatch happens

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 1.22 search-for-primes

Image
Exercise 1.22.    Most Lisp implementations include a primitive called  runtime  that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following  timed-prime-test  procedure, when called with an integer  n , prints  n  and checks to see if  n  is prime. If  n  is prime, the procedure prints three asterisks followed by the amount of time used in performing the test. (define (timed-prime-test n)   (newline)   (display n)   (start-prime-test n (runtime))) (define (start-prime-test n start-time)   (if (prime? n)       (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time)   (display " *** ")   (display elapsed-time)) Using this procedure, ...
Read more

SICP Exercise 3.45 deadlock

Exercise 3.45.   Louis Reasoner thinks our bank-account system is unnecessarily complex and error-prone now that deposits and withdrawals aren't automatically serialized. He suggests that  make-account-and-serializer  should have exported the serializer (for use by such procedures as  serialized-exchange ) in addition to (rather than instead of) using it to serialize accounts and deposits as  make-account  did. He proposes to redefine accounts as follows: (define (make-account-and-serializer balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amoun...
Read more

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this ...
Read more