SICP

Exercise 2.91.    A univariate polynomial can be divided by another one to produce a polynomial quotient and a polynomial remainder. For example, Division can be performed via long division. That is, divide the highest-order term of the dividend by the highest-order term of the divisor. The result is the first term of the quotient. Next, multiply the result by the divisor, subtract that from the dividend, and produce the rest of the answer by recursively dividing the difference by the divisor. Stop when the order of the divisor exceeds the order of the dividend and declare the dividend to be the remainder. Also, if the dividend ever becomes zero, return zero as both quotient and remainder. We can design a  div-poly  procedure on the model of  add-poly  and  mul-poly . The procedure checks to see if the two polys have the same variable. If so,  div-poly  strips off the variable and passes the problem to  div-terms , which performs...

Exercise 2.90.   Suppose we want to have a polynomial system that is efficient for both sparse and dense polynomials. One way to do this is to allow both kinds of term-list representations in our system. The situation is analogous to the complex-number example of section  2.4 , where we allowed both rectangular and polar representations. To do this we must distinguish different types of term lists and make the operations on term lists generic. Redesign the polynomial system to implement this generalization. This is a major effort, not a local change. SOLUTION The code and tests are here .

Exercise 2.89.   Define procedures that implement the term-list representation described above as appropriate for dense polynomials. SOLUTION The code and tests are here . Procedure 'adjoin-term' Structure of term-list: [OrderOfPolynomial, (list of coefficients)] Maintaining the order of the polynomial as the first element allows us to avoid repeated  expensive 'length' calls on the coefficient list.  We assume that term lists are represented as lists of terms,  arranged from highest-order to lowest-order term. Procedures 'first-term' and 'first-term' Since we are using the term-list representation that is appropriate for  dense polynomials (see SICP text), we need to do some extra processing  to retrieve both the order and coefficient.

Exercise 2.88.    Extend the polynomial system to include subtraction of polynomials. (Hint: You may find it helpful to define a generic negation operation.) SOLUTION The code and tests are here .

Exercise 2.87.    Install   =zero?   for polynomials in the generic arithmetic package. This will allow   adjoin-term   to work for polynomials with coefficients that are themselves polynomials. SOLUTION The code and tests are here .

Exercise 2.86.   Suppose we want to handle complex numbers whose real parts, imaginary parts, magnitudes, and angles can be either ordinary numbers, rational numbers, or other numbers we might wish to add to the system. Describe and implement the changes to the system needed to accommodate this. You will have to define operations such as   sine   and   cosine   that are generic over ordinary numbers and rational numbers. SOLUTION The code and tests are here . Here I have changed the generic procedures (real-part) and (imag-part) to (REAL-PART) and  (IMAG-PART) in order to avoid name-conflicts with the Racket primitives (real-part) and (imag-part). I  am using these primitives to understand more about Racket numbers.

Exercise 2.85.    This section mentioned a method for ``simplifying'' a data object by lowering it in the tower of types as far as possible. Design a procedure  drop  that accomplishes this for the tower described in exercise  2.83 . The key is to decide, in some general way, whether an object can be lowered. For example, the complex number 1.5 + 0 i  can be lowered as far as  real , the complex number 1 + 0 i  can be lowered as far as  integer , and the complex number 2 + 3 i cannot be lowered at all. Here is a plan for determining whether an object can be lowered: Begin by defining a generic operation  project  that ``pushes'' an object down in the tower. For example, projecting a complex number would involve throwing away the imaginary part. Then a number can be dropped if, when we  project  it and  raise  the result back to the type we started with, we end up with something equal to what we started with. Sho...

Exercise 2.84.    Using the  raise  operation of exercise  2.83 , modify the  apply-generic  procedure so that it coerces its arguments to have the same type by the method of successive raising, as discussed in this section. You will need to devise a way to test which of two types is higher in the tower. Do this in a manner that is ``compatible'' with the rest of the system and will not lead to problems in adding new levels to the tower. SOLUTION The code and tests are here .

Exercise 2.83.    Suppose you are designing a generic arithmetic system for dealing with the tower of types shown in figure  2.25 : integer, rational, real, complex. For each type (except complex), design a procedure that raises objects of that type one level in the tower. Show how to install a generic  raise  operation that will work for each type (except complex). SOLUTION The code and tests are here .

Exercise 2.82.    Show how to generalize  apply-generic  to handle coercion in the general case of multiple arguments. One strategy is to attempt to coerce all the arguments to the type of the first argument, then to the type of the second argument, and so on. Give an example of a situation where this strategy (and likewise the two-argument version given above) is not sufficiently general. (Hint: Consider the case where there are some suitable mixed-type operations present in the table that will not be tried.) SOLUTION The code and tests are here . Explanation of why this strategy is not sufficiently general Let's assume that we need to support the following operation on three arguments. This  function expects the first two arguments x and y to be of any types and the third one "factor"  to be an ordinary number. It multiples c1 and c2 and scales the result to the value of factor. Suppose the following implementations exist in the op-table fo...

Exercise 2.81.    Louis Reasoner has noticed that  apply-generic  may try to coerce the arguments to each other's type even if they already have the same type. Therefore, he reasons, we need to put procedures in the coercion table to "coerce" arguments of each type to their own type. For example, in addition to the  scheme-number->complex  coercion shown above, he would do: (define (scheme-number->scheme-number n) n) (define (complex->complex z) z) (put-coercion 'scheme-number 'scheme-number               scheme-number->scheme-number) (put-coercion 'complex 'complex complex->complex) a. With Louis's coercion procedures installed, what happens if  apply-generic  is called with two arguments of type  scheme-number  or two arguments of type  complex  for an operation that is not found in ...

Exercise 2.80.    Define a generic predicate   =zero?   that tests if its argument is zero, and install it in the generic arithmetic package. This operation should work for ordinary numbers, rational numbers, and complex numbers. SOLUTION The code and tests are here .

Exercise 2.79.    Define a generic equality predicate   equ?   that tests the equality of two numbers, and install it in the generic arithmetic package. This operation should work for ordinary numbers, rational numbers, and complex numbers. SOLUTION The code and tests are here .

Exercise 2.78.    The internal procedures in the  scheme-number  package are essentially nothing more than calls to the primitive procedures  + ,  - , etc. It was not possible to use the primitives of the language directly because our type-tag system requires that each data object have a type attached to it. In fact, however, all Lisp implementations do have a type system, which they use internally. Primitive predicates such as  symbol?  and  number?  determine whether data objects have particular types. Modify the definitions of  type-tag ,  contents , and  attach-tag  from section  2.4.2  so that our generic system takes advantage of Scheme's internal type system. That is to say, the system should work as before except that ordinary numbers should be represented simply as Scheme numbers rather than as pairs whose  car  is the symbol  scheme-number . SOLUTION The code and tests are here ...

Exercise 2.77.   Louis Reasoner tries to evaluate the expression  (magnitude z)  where  z  is the object shown in figure  2.24 . To his surprise, instead of the answer 5 he gets an error message from  apply-generic , saying there is no method for the operation  magnitude  on the types  (complex) . He shows this interaction to Alyssa P. Hacker, who says ``The problem is that the complex-number selectors were never defined for  complex  numbers, just for  polar  and  rectangular  numbers. All you have to do to make this work is add the following to the  complex  package:'' (put 'real-part '(complex) real-part) (put 'imag-part '(complex) imag-part) (put 'magnitude '(complex) magnitude) (put 'angle '(complex) angle) Describe in detail why this works. As an example, trace through all the procedures called in evaluating the expression...

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...