SICP Exercise 2.76 Comparison of the Three Strategies

Exercise 2.76.  As a large system with generic operations evolves, new types of data objects or new operations may be needed. For each of the three strategies -- generic operations with explicit dispatch, data-directed style, and message-passing-style -- describe the changes that must be made to a system in order to add new types or new operations. Which organization would be most appropriate for a system in which new types must often be added? Which would be most appropriate for a system in which new operations must often be added?

SOLUTION
Generic Operations with Explicit Dispatch
Data-Directed Style
Message-Passing Style
Add New Types (as in polar, rectangular etc. in the case of complex numbers)
1.     Implement all the supported operations including the constructors under the new representation and tag the data with the new type. Make sure that these operation names do not conflict with any of the existing representations
2.     Add predicate for the new type (just like rectangular?)
3.     Modify every generic selector to test for the new type (in addition to the existing types) and call the newly implemented operation that handles the new type
Implement an ‘install’ package for the new type that contains all the operations, a tag procedure that attaches the new tag (that represents this type) to the data that is supplied to it and a series of ‘put’ calls to add entries to the op-table

(This is an additive process. No existing code needs to be changed.)
Write a new constructor that returns a procedure that dispatches based on the operation name supplied

(This is an additive process.)
Add New Operations (as in real-part, imag-part, magnitude, angle etc. in the case of complex numbers)
1.     Implement the new operation under each existing representation while avoiding name-conflicts between representations
2.     Implement a new generic procedure that, based on the data type dispatches to one of the newly implemented operations above.
1.     The new operation needs to be implemented in each the existing representations
2.     A ‘put’ call needs to be added to each package so that the new operation is added to the operations table.

(This is also additive.)
All existing constructors need to be changed so that their dispatch procedures check for the newly added operation also. And the implementation for the new operation should be added to the new conditional check clause


Clearly, data-directed style and the message-passing style are both better options than generic operations with explicit dispatch. Much less work needs to be done in these approaches.

If new types need to be added often, the message-passing style is more suitable.

If new operations are added often, both data-directed style and message-passing style are equally good.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 2.56 differentiation rule

Image
Exercise 2.56.    Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule by adding a new clause to the  deriv  program and defining appropriate procedures  exponentiation? ,  base ,  exponent , and  make-exponentiation . (You may use the symbol  **  to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself. SOLUTION The code and tests are here .
Read more

SICP Exercise 1.28 (Miller-Rabin Test)

Exercise 1.28.    One variant of the Fermat test that cannot be fooled is called the  Miller-Rabin test  (Miller 1976; Rabin 1980). This starts from  an alternate form of Fermat's Little Theorem, which states that if  n  is a prime number and  a  is any positive integer less than  n , then  a  raised to the ( n  - 1)st power is congruent to 1 modulo  n . To test the primality of a number  n  by the Miller-Rabin test, we pick a random number  a < n  and raise  a  to the ( n  - 1)st power modulo  n  using the  expmod  procedure. However, whenever we perform the squaring step in  expmod , we check to see if we have discovered a ``nontrivial square root of 1 modulo  n ,'' that is, a number not equal to 1 or  n  - 1 whose square is equal to 1 modulo  n . It is possible to prove that if such a nontrivial square root of 1 exists, then  n  is not prime. It is also possible to prove that if  n  is an odd number that is not prime, then, for at least half the numbers a < n , co
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 procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain. SOLUTION & DISCUSSION The streams based procedure 'solve' in this exercise exposed several issues in my metacircular evaluator implementation. I discovered that streams are not at all handled properly by my evaluator. Moreover, the &
Read more