SICP Section 2.5 Systems with Generic Operations

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 (magnitude z) where z is the object shown in figure 2.24. In particular, how many times is apply-generic invoked? What procedure is dispatched to in each case?

Answer: After making Alyssa's changes a call to (magnitude z) will be dispatched to the magnitude method defined for complex types. On invoking this the actual magnitude method for rectangular representation is looked up and invoked. Hence the solution works.

Apply-generic is invoked twice. First when (magnitude z) is called; the next time when the magnitude method defined for rectangular implementation is called.

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.

Answer:
(define (attach-tag type-tag contents) (if (number? contents) contents (cons type-tag contents))) (define (type-tag datum) (if (number? datum) 'scheme-number (if (pair? datum) (car datum) (error "Bad tagged datum -- TYPE-TAG" datum)))) (define (contents datum) (if (number? datum) datum (if (pair? datum) (cdr datum) (error "Bad tagged datum -- CONTENTS" datum))))
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.

Answer:
(define (equ? x y) (apply-generic 'equ? x y)) (define (install-scheme-number-equ) (put 'equ? '(scheme-number scheme-number) (lambda (x y) (= x y))) 'done) (define (install-rational-number-equ) (define (equal-rat? x y) (= (* (numer x) (denom y)) (* (numer y) (denom x)))) (put 'equ? '(rational rational) (lambda (x y) (equal-rat? x y))) 'done) (define (install-complex-number-equ) (define (equal-complex? x y) (and (= (magnitude x) (magnitude y)) (= (angle x) (angle y)))) (put 'equ? '(complex complex) (lambda (x y) (equal-complex? x y))) 'done)
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.

Answer:
(define (=zero? x) (apply-generic '=zero? x)) (define (install-scheme-number-equ-zero) (put '=zero? '(scheme-number) (lambda (x) (= x 0))) 'done) (define (install-rational-number-equ-zero) (define (=zero? x) (= (numer x) 0)) (put '=zero? '(rational) (lambda (x) (=zero? x))) 'done) (define (install-complex-number-equ-zero) (define (=zero? x) (and (= (real-part x) 0) (= (imag-part x) 0))) (put '=zero? '(complex) (lambda (x) (=zero? x))) 'done)
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 the table for those types? For example, assume that we've defined a generic exponentiation operation:
(define (exp x y) (apply-generic 'exp x y))
and have put a procedure for exponentiation in the Scheme-number package but not in any other package:
;; following added to Scheme-number package (put 'exp '(scheme-number scheme-number) (lambda (x y) (tag (expt x y)))) ; using primitive expt
What happens if we call exp with two complex numbers as arguments?

b. Is Louis correct that something had to be done about coercion with arguments of the same type, or does apply-generic work correctly as is?

c. Modify apply-generic so that it doesn't try coercion if the two arguments have the same type.

Answer: a. Louis' procedures doesn't help or add any new value with respect scheme numbers. His procedures actually create trouble in other cases - if apply-generic is called with two arguments of the same type for an operation that is not found in the table for those types, the procedure goes into an infinite loop.

b. Louis is incorrect; apply-generic is fine as is without his changes.

c. Changes to apply-generic:
(define (apply-generic op . args) (let ((type-tags (map type-tag args))) (let ((proc (get op type-tags))) (if proc (apply proc (map contents args)) (if (= (length args) 2) (let ((type1 (car type-tags)) (type2 (cadr type-tags)) (a1 (car args)) (a2 (cadr args))) (if (= type1 type2) (error "No method for these types" (list op type-tags)) (let ((t1->t2 (get-coercion type1 type2)) (t2->t1 (get-coercion type2 type1))) (cond (t1->t2 (apply-generic op (t1-t2 a1) a2)) (t2->t1 (apply-generic op a1 (t2->t1 a2))) (else (error "No method for these types" (list op type-tags))))))) (error "No method for these types" (list op type-tags)))))))
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).

Answer:
(define (install-generic-raise) (define (raise-integer i) (make-rat i 1)) (define (raise-rational r) (make-real (* (/ (numer r) (denom r)) 1.0))) (define (raise-real r) (make-from-real-imag r 0)) ;; interface (put '(integer) raise-integer) (put '(rational) raise-rational) (put '(real) raise-real) 'done) (define (raise number) (apply-generic 'raise number))
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.

Answer:
(define (apply-generic op . args) (define (raise-type s t) (let ((s-type (type-tag s)) (t-type (type-tag t))) (cond ((eq? s-type t-type) s) ((get 'raise (list s-type)) (raise-type ((get 'raise (list s-type)) (contents s)) t)) (else false)))) (let ((type-tags (map type-tag args))) (let ((proc (get op type-tags))) (if proc (apply proc (map contents args)) (if (= (length args) 2) (let ((type1 (car type-tags)) (type2 (cadr type-tags)) (a1 (car args)) (a2 (cadr args))) (if (= type1 type2) (error "No method for these types" (list op type-tags)) (cond ((raise-type type1 type2) (apply-generic op (raise-type type1 type2) type2)) ((raise-type type2 type1) (apply-generic op type1 (raise-type type2) type1)) (else (error "No method for these types" (list op type-tags)))))) (error "No method for these types" (list op type-tags)))))))
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 + 0i can be lowered as far as real, the complex number 1 + 0i can be lowered as far as integer, and the complex number 2 + 3i 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. Show how to implement this idea in detail, by writing a drop procedure that drops an object as far as possible. You will need to design the various projection operations53 and install project as a generic operation in the system. You will also need to make use of a generic equality predicate, such as described in exercise 2.79. Finally, use drop to rewrite apply-generic from exercise 2.84 so that it ``simplifies'' its answers.

Answer:
(define (install-type-projection) (define (project-complex->real c) (make-real (real-part c))) (define (project-real->rational r) (let ((ratio (inexact->exact r))) (make-real (numerator ratio) (denominator ratio)))) (define (project-rational->integer r) (round (/ (numer r) (denom r)))) (put 'project '(complex) project-complex->real) (put 'project '(real) project-real->rational) (put 'project '(rational) project-rational->integer) 'done) (define (project number) (apply-generic 'project number)) (define (drop x) (let ((projection (project x))) (if (not projection) x (if (equ? (raise projection) x) (drop projection) x)))) (define (apply-generic op . args) (define (raise-type s t) (let ((s-type (type-tag s)) (t-type (type-tag t))) (cond ((eq? s-type t-type) s) ((get 'raise (list s-type)) (raise-type ((get 'raise (list s-type)) (contents s)) t)) (else false)))) (let ((type-tags (map type-tag args))) (let ((proc (get op type-tags))) (if proc (drop (apply proc (map contents args))) ;; Only change. (if (= (length args) 2) (let ((type1 (car type-tags)) (type2 (cadr type-tags)) (a1 (car args)) (a2 (cadr args))) (if (= type1 type2) (error "No method for these types" (list op type-tags)) (cond ((raise-type type1 type2) (apply-generic op (raise-type type1 type2) type2)) ((raise-type type2 type1) (apply-generic op type1 (raise-type type2) type1)) (else (error "No method for these types" (list op type-tags)))))) (error "No method for these types" (list op type-tags)))))))
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.

Answer:
(define (install-poly-equal-zero) (define (=zero-poly? poly) (define (zero-terms? terms) (and (=zero? (coeff (first-term terms))) (zero-terms? (rest-terms terms)))) (or (empty-termlist? (term-list poly)) (zero-terms? (term-list poly)))) (put '=zero? '(polynomial) (lambda (p) (=zero-poly? p))) 'done)
Exercise 2.88. Extend the polynomial system to include subtraction of polynomials. (Hint: You may find it helpful to define a generic negation operation.)

Answer:
(define (install-number-negation) (define (negate-integer i) (- 0 i)) ;; interface (put 'negate '(integer) (lambda (i) (negate-integer i))) 'done) (define (negate i) (apply-generic 'negate i)) (define (install-poly-negation) (define (negate-terms terms) (if (empty-termlist? terms) terms (let ((first (first-term terms)) (rest (rest-terms terms))) (adjoin-terms (make-term (order first) (negate (coeff first))) (negate-terms rest))))) (define (negate-poly poly) (make-poly (variable poly) (negate-terms (terms poly)))) (define (subtract-poly p1 p2) (add-poly p1 (negate p2))) (put 'negate '(polynomial) (lambda (p) (negate-poly p))) (put 'sub '(polynomial polynomial) (lambda (p1 p2) (tag (subtract-poly p1 p2)))) 'done)
Exercise 2.89. Define procedures that implement the term-list representation described above as appropriate for dense polynomials.

Answer:
(define (adjoin-term term term-list) (define (pad-zero seq expected-length) (if (= expected-length (length seq)) seq (pad-zero (cons 0 seq) expected-length))) (define (add-terms S1 S2) (accumulate-n + 0 (list S1 S2))) (let ((L1 (length term)) (L2 (length term-list))) (cond ((= L1 L2) (add-terms term term-list)) ((> L1 L2) (add-terms term (pad-zero term-list L1))) (else (add-terms (pad term L2) term-list)))))
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 the division operation on term lists. Div-poly finally reattaches the variable to the result supplied by div-terms. It is convenient to design div-terms to compute both the quotient and the remainder of a division. Div-terms can take two term lists as arguments and return a list of the quotient term list and the remainder term list.

Complete the following definition of div-terms by filling in the missing expressions. Use this to implement div-poly, which takes two polys as arguments and returns a list of the quotient and remainder polys.
(define (div-terms L1 L2) (if (empty-termlist? L1) (list (the-empty-termlist) (the-empty-termlist)) (let ((t1 (first-term L1)) (t2 (first-term L2))) (if (> (order t2) (order t1)) (list (the-empty-termlist) L1) (let ((new-c (div (coeff t1) (coeff t2))) (new-o (- (order t1) (order t2)))) (let ((rest-of-result <compute rest of result recursively> )) <form complete result> ))))))
Answer:
(define (div-terms L1 L2) (if (empty-termlist? L1) (list (the-empty-termlist) (the-empty-termlist)) (let ((t1 (first-term L1)) (t2 (first-term L2))) (if (> (order t2) (order t1)) (list (the-empty-termlist) L1) (let ((new-c (div (coeff t1) (coeff t2))) (new-o (- (order t1) (order t2)))) (let ((rest-of-result (let ((new-term (make-term new-o new-c)) (let ((product (add L1 (negate (mul-terms (list new-term) L2))))) (div-terms product L2)))))) (list (cons new-term (car rest-of-result)) (cadr res-of-result)))))))) (define (div-poly P1 P2) (if (same-variable? P1 P2) (let ((L1 (term-list P1)) (L2 (term-list P2))) (let ((result (div-terms L1 L2))) (list (make-poly (variable P1) (car result)) (make-poly (variable P1) (cadr result))))) (error "Polys are not in the same variable -- DIV-POLY" (list P1 P2))))
Exercise 2.94. Using div-terms, implement the procedure remainder-terms and use this to define gcd-terms as above. Now write a procedure gcd-poly that computes the polynomial GCD of two polys. (The procedure should signal an error if the two polys are not in the same variable.) Install in the system a generic operation greatest-common-divisor that reduces to gcd-poly for polynomials and to ordinary gcd for ordinary numbers. As a test, try
(define p1 (make-polynomial 'x '((4 1) (3 -1) (2 -2) (1 2)))) (define p2 (make-polynomial 'x '((3 1) (1 -1)))) (greatest-common-divisor p1 p2)
and check your result by hand.

Answer:
(define (gcd-terms a b) (if (empty-termlist? b) a (gcd-terms (remainder-terms a b)))) (define (remainder-terms a b) (cadr (div-terms a b))) (define (gcd-poly P1 P2) (if (same-variable P1 P2) (make-poly (variable P1) (gcd-terms (term-list P1) (term-list P2))) (error "Polys are not in the same variable -- GCD-POLY" (list P1 P2))))
Exercise 2.96. a. Implement the procedure pseudoremainder-terms, which is just like remainder-terms except that it multiplies the dividend by the integerizing factor described above before calling div-terms. Modify gcd-terms to use pseudoremainder-terms, and verify that greatest-common-divisor now produces an answer with integer coefficients on the example in exercise 2.95.

b. The GCD now has integer coefficients, but they are larger than those of P1. Modify gcd-terms so that it removes common factors from the coefficients of the answer by dividing all the coefficients by their (integer) greatest common divisor.

Thus, here is how to reduce a rational function to lowest terms:

• Compute the GCD of the numerator and denominator, using the version of gcd-terms from exercise 2.96.,
• When you obtain the GCD, multiply both numerator and denominator by the same integerizing factor before dividing through by the GCD, so that division by the GCD will not introduce any noninteger coefficients. As the factor you can use the leading coefficient of the GCD raised to the power 1 + O1 - O2, where O2 is the order of the GCD and O1 is the maximum of the orders of the numerator and denominator. This will ensure that dividing the numerator and denominator by the GCD will not introduce any fractions.
• The result of this operation will be a numerator and denominator with integer coefficients. The coefficients will normally be very large because of all of the integerizing factors, so the last step is to remove the redundant factors by computing the (integer) greatest common divisor of all the coefficients of the numerator and the denominator and dividing through by this factor.

Answer:
;; a (define (pseudoremainder-terms a b) (let ((O1 (order (first-term a))) (O2 (order (first-term b))) (C (coeff (first-term a)))) (let ((i-factor (exp C (+ 1 (- O1 O2))))) (cadr (div-terms (map (lambda (t) (make-term (order t) (* i-factor (coeff t)))) a) b))))) (define (gcd-terms a b) (if (empty-termlist? b) a (gcd-terms b (pseudoremainder-terms a b))))

SICP Section 2.4 Multiple Representations for Abstract Data

Exercise 2.75. Implement the constructor make-from-mag-ang in message-passing style. This procedure should be analogous to the make-from-real-imag procedure given above.

Answer:
(define (make-from-mag-ang r a) (define (dispatch op) (cond ((eq? op 'real-part) (* r (cos a))) ((eq? op 'imag-part) (* r (sin a))) ((eq? op 'magnitude) r) ((eq? op 'angle) a) (else (error "Unknown op -- MAKE-FROM-MAG-ANG" op)))) dispatch)
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?

Answer:

• Generic operations with explicit dispatch: explicit dispatch is relatively easier to code. However adding new types would require that all existing functions be changed appropriately. For this reason makes explicit dispatch is less suited for a system in which new types must often be added
• Data-directed style: adding new types would not require extensive changes at the top level. However new packages would need to be added behind the scenes to facilitate operation.
• Message-passing-style: this requires the addition of a suitable type of procedure/object which can accept the messages as necessary. The top level does not need to change.

SICP Section 2.3 Symbolic Data

Exercise 2.53. What would the interpreter print in response to evaluating each of the following expressions?
(list 'a 'b 'c) (list (list 'george)) (cdr '((x1 x2) (y1 y2))) (cadr '((x1 x2) (y1 y2))) (pair? (car '(a short list))) (memq 'red '((red shoes) (blue socks))) (memq 'red '(red shoes blue socks))
Answer:
(list 'a 'b 'c) (a b c) (list (list 'george)) ((george)) (cdr '((x1 x2) (y1 y2))) ((y1 y2)) (cadr '((x1 x2) (y1 y2))) (y1 y2) (pair? (car '(a short list))) #f ;; Memq tries to match individual elements of the outer list. ;; Since no element of the outer list matches 'red, it returns false. (memq 'red '((red shoes) (blue socks))) #f (memq 'red '(red shoes blue socks)) (red shoes blue socks)
Exercise 2.54. Two lists are said to be equal? if they contain equal elements arranged in the same order. For example,
(equal? '(this is a list) '(this is a list))
is true, but
(equal? '(this is a list) '(this (is a) list))
is false. To be more precise, we can define equal? recursively in terms of the basic eq? equality of symbols by saying that a and b are equal? if they are both symbols and the symbols are eq?, or if they are both lists such that (car a) is equal? to (car b) and (cdr a) is equal? to (cdr b). Using this idea, implement equal? as a procedure.

Answer:
(define (equal? a b) (if (and (pair? a) (pair? b)) (if (not (equal? (car a) (car b))) false (equal? (cdr a) (cdr b))) (eq? a b)))
Exercise 2.55. Eva Lu Ator types to the interpreter the expression
(car ''abracadabra)
To her surprise, the interpreter prints back quote. Explain.

Answer: It is easier to understand what happens if we replace the inner ' character with the quote operation. The expression now becomes:
(car '(quote abracadabra))
This is possible since the ' character is just an easy abbreviation for quote. As the first entity in the list is quote, car returns quote.

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.

Answer:
(define (make-exponentiation base exponent) (cond ((=number? exponent 0) 1) ((=number? exponent 1) base) (else (list '^ base exponent)))) (define (exponentiation? x) (and (pair? x) (eq? (car x) '^))) (define (base e) (cadr e)) (define (exponent e) (caddr e)) (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)))) ((exponentiation? exp) (let ((n (exponent exp)) (u (base exp))) (make-product (make-product n (make-exponentiation u (- n 1))) (deriv u var)))) (else (display "Unknown expression type: ") (display exp))))
Exercise 2.57. Extend the differentiation program to handle sums and products of arbitrary numbers of (two or more) terms. Then the last example above could be expressed as
(deriv '(* x y (+ x 3)) 'x)
Try to do this by changing only the representation for sums and products, without changing the deriv procedure at all. For example, the addend of a sum would be the first term, and the augend would be the sum of the rest of the terms.

Answer:
(define (augend s) (let ((t (cddr s))) (if (pair? (cdr t)) (cons '+ t) (car t)))) (define (multiplicand p) (let ((t (cddr p))) (if (pair? (cdr t)) (cons '* t) (car t))))
Exercise 2.59. Implement the union-set operation for the unordered-list representation of sets.

Answer:
(define (element-of-set? x set) (cond ((null? set) false) ((equal? x (car set)) true) (else (element-of-set? x (cdr set))))) (define (adjoin-set x set) (if (element-of-set? x set) set (cons x set))) (define (union-set s1 s2) (cond ((and (null? s1) (null? s2)) '()) ((null? s1) s2) ((null? s2) s1) ((element-of-set? (car s1) s2) (union-set (cdr s1) s2)) (else (union-set (cdr s1) (adjoin-set (car s1) s2)))))
Exercise 2.60. We specified that a set would be represented as a list with no duplicates. Now suppose we allow duplicates. For instance, the set {1,2,3} could be represented as the list (2 3 2 1 3 2 2). Design procedures element-of-set?, adjoin-set, union-set, and intersection-set that operate on this representation. How does the efficiency of each compare with the corresponding procedure for the non-duplicate representation? Are there applications for which you would use this representation in preference to the non-duplicate one?

Answer: Element-of-set? is unchanged from above.

Adjoin-set no longer needs to check for element-of-set?. This version of adjoin-set is O(1) (compared to O(n) earlier).
(define (adjoin-set x set) (cons x set))
Union-set no longer needs to check for element-of-set?. This version of union-set is O(n) (compared to O(n^2) earlier)
(define (union-set s1 s2) (append s1 s2))
Intersection-set remains unchanged.

Exercise 2.61. Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation.

Answer:
(define (adjoin-set x set) (define (iter known unknown) (if (null? unknown) (append known (list x)) (let ((first (car unknown))) (cond ((= x first) set) ((< x first) (append known (list x) unknown)) ((> x first) (iter (append known (list first)) (cdr unknown))))))) (iter '() set))
Exercise 2.63. Each of the following two procedures converts a binary tree to a list.
(define (tree->list-1 tree) (if (null? tree) '() (append (tree->list-1 (left-branch tree)) (cons (entry tree) (tree->list-1 (right-branch tree)))))) (define (tree->list-2 tree) (define (copy-to-list tree result-list) (if (null? tree) result-list (copy-to-list (left-branch tree) (cons (entry tree) (copy-to-list (right-branch tree) result-list))))) (copy-to-list tree '()))
a. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?

b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?

Answer: a. Both procedures produce same results for all trees.

b. Both procedures have identical orders of growth. Both procedures solve the problem in O(n) steps.

Exercise 2.65. Use the results of exercises 2.63 and 2.64 to give (n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.

Answer:
(define (union-set-tree set1 set2) (let ((list1 (list->tree-1 set1)) (list2 (list->tree-1 set2))) (let ((union-list (union-set list1 list2))) (list->tree union-list)))) (define (intersection-set-tree set1 set2) (let ((list1 (list->tree-1 set1)) (list2 (list->tree-1 set2))) (let ((intersection-list (intersection-set list1 list2))) (list->tree intersection-list))))
Exercise 2.66. Implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys.

Answer:
(define (lookup key tree-set-of-records) (if (null? tree-set-of-records) nil (let ((root (entry tree-set-of-records)) (left (left-branch tree-set-of-records)) (right (right-branch tree-set-of-records))) (cond ((= key root) root) ((< key root) (lookup key left)) ((> key root) (lookup key right))))))
Exercise 2.67. Define an encoding tree and a sample message:
(define sample-tree (make-code-tree (make-leaf 'A 4) (make-code-tree (make-leaf 'B 2) (make-code-tree (make-leaf 'D 1) (make-leaf 'C 1))))) (define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
Use the decode procedure to decode the message, and give the result.

Answer:
(decode sample-message sample-tree) (A D A B B C A)
Exercise 2.68. The encode procedure takes as arguments a message and a tree and produces the list of bits that gives the encoded message.
(define (encode message tree) (if (null? message) '() (append (encode-symbol (car message) tree) (encode (cdr message) tree))))
Encode-symbol is a procedure, which you must write, that returns the list of bits that encodes a given symbol according to a given tree. You should design encode-symbol so that it signals an error if the symbol is not in the tree at all. Test your procedure by encoding the result you obtained in exercise 2.67 with the sample tree and seeing whether it is the same as the original sample message.

Answer:
(define (encode-symbol symbol tree) (define (iter object result) (if (leaf? object) result (let ((lb (left-branch object)) (rb (right-branch object))) (if (contains-symbol? symbol lb) (iter lb (append result (list 0))) (iter rb (append result (list 1))))))) (if (contains-symbol? symbol tree) (iter tree '()) (error "Tree does not contain symbol" tree))) (define (contains-symbol? symbol tree) (element-of-set? symbol (symbols tree)))
Exercise 2.69. The following procedure takes as its argument a list of symbol-frequency pairs (where no symbol appears in more than one pair) and generates a Huffman encoding tree according to the Huffman algorithm.
(define (generate-huffman-tree pairs) (successive-merge (make-leaf-set pairs)))
Make-leaf-set is the procedure given above that transforms the list of pairs into an ordered set of leaves. Successive-merge is the procedure you must write, using make-code-tree to successively merge the smallest-weight elements of the set until there is only one element left, which is the desired Huffman tree. (This procedure is slightly tricky, but not really complicated. If you find yourself designing a complex procedure, then you are almost certainly doing something wrong. You can take significant advantage of the fact that we are using an ordered set representation.)

Answer:
(define (adjoin-set x set) (cond ((null? set) (list x)) ((< (weight x) (weight (car set))) (cons x set)) (else (cons (car set) (adjoin-set x (cdr set)))))) (define (successive-merge leaf-set) (if (null? (cdr leaf-set)) (car leaf-set) (successive-merge (adjoin-set (make-code-tree (car leaf-set) (cadr leaf-set)) (cddr leaf-set)))))
Exercise 2.70. The following eight-symbol alphabet with associated relative frequencies was designed to efficiently encode the lyrics of 1950s rock songs. (Note that the ``symbols'' of an ``alphabet'' need not be individual letters.)

A 2 NA 16
BOOM 1 SHA 3
GET 2 YIP 9
JOB 2 WAH 1


Use generate-huffman-tree (exercise 2.69) to generate a corresponding Huffman tree, and use encode (exercise 2.68) to encode the following message:

Get a job
Sha na na na na na na na na
Get a job
Sha na na na na na na na na
Wah yip yip yip yip yip yip yip yip yip
Sha boom


How many bits are required for the encoding? What is the smallest number of bits that would be needed to encode this song if we used a fixed-length code for the eight-symbol alphabet?

Answer:
(define rock-alphabet-pairs '((a 2) (boom 1) (get 2) (job 2) (na 16) (sha 3) (yip 9) (wah 1))) (define rock-message '(get a job sha na na na na na na na na get a job sha na na na na na na na na wah yip yip yip yip yip yip yip yip yip sha boom)) (encode rock-message (generate-huffman-tree rock-alphabet-pairs)) (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)
As there are 8 different symbols we will need log2(8) = 3 bits per alphabet for encoding. There are 36 different alphabets in the message which require 36 * 3 = 108 bits for encoding.

SICP Section 2.2 Hierarchical Data and the Closure Property - Part 2

Exercise 2.44. Define the procedure up-split used by corner-split. It is similar to right-split, except that it switches the roles of below and beside.
(define (up-split painter n) (if (= n 0) painter (let ((up (up-split painter (- n 1)))) (below painter (beside up up)))))
Exercise 2.45. Right-split and up-split can be expressed as instances of a general splitting operation. Define a procedure split with the property that evaluating
(define right-split (split beside below)) (define up-split (split below beside))
produces procedures right-split and up-split with the same behaviors as the ones already defined.

Answer:
(define (split orig-placer split-placer) (lambda (painter n) (if (= n 0) painter (let ((smaller ((split orig-placer split-placer) painter (- n 1)))) (orig-placer smaller (split-placer smaller smaller))))))
Exercise 2.46. A two-dimensional vector v running from the origin to a point can be represented as a pair consisting of an x-coordinate and a y-coordinate. Implement a data abstraction for vectors by giving a constructor make-vect and corresponding selectors xcor-vect and ycor-vect. In terms of your selectors and constructor, implement procedures add-vect, sub-vect, and scale-vect that perform the operations vector addition, vector subtraction, and multiplying a vector by a scalar:



Answer:
(define (make-vect x-cord y-cord) (cons x-cord y-cord)) (define (xcor-vect vector) (car vector)) (define (ycor-vect vector) (cdr vector)) (define (add-vect v1 v2) (make-vect (+ (xcor-vect v1) (xcor-vect v2)) (+ (ycor-vect v1) (ycor-vect v2)))) (define (sub-vect v1 v2) (make-vect (- (xcor-vect v1) (xcor-vect v2)) (- (ycor-vect v1) (ycor-vect v2)))) (define (scale-vect s v) (make-vect (* s (xcor-vect v)) (* s (ycor-vect v))))
Exercise 2.47. Here are two possible constructors for frames:
(define (make-frame origin edge1 edge2) (list origin edge1 edge2)) (define (make-frame origin edge1 edge2) (cons origin (cons edge1 edge2)))
For each constructor supply the appropriate selectors to produce an implementation for frames.

Answer:
;; Option 1 and selectors (define (make-frame origin edge1 edge2) (list origin edge1 edge2)) (define (origin-frame frame) (car frame)) (define (edge1-frame frame) (cadr frame)) (define (edge2-frame frame) (caddr frame)) ;; Option 2 and selectors (define (make-frame origin edge1 edge2) (cons origin (cons edge1 edge2))) (define (origin-frame frame) (car frame)) (define (edge1-frame frame) (cadr frame)) (define (edge2-frame frame) (cddr frame))
Exercise 2.48. A directed line segment in the plane can be represented as a pair of vectors -- the vector running from the origin to the start-point of the segment, and the vector running from the origin to the end-point of the segment. Use your vector representation from exercise 2.46 to define a representation for segments with a constructor make-segment and selectors start-segment and end-segment.

Answer:
(define (make-segment start-point-vector end-point-vector) (cons start-point-vector end-point-vector)) (define (start-segment segment) (car segment)) (define (end-segment segment) (cdr segment))
Exercise 2.49. Use segments->painter to define the following primitive painters:

a. The painter that draws the outline of the designated frame.

b. The painter that draws an ``X'' by connecting opposite corners of the frame.

c. The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.

d. The wave painter.

Answer: a. The painter that draws the outline of the designated frame. This is done by connecting the four corners of the frame. Translated to the unit frame the corners are the points (0, 0), (1, 0), (0, 1) and (1, 1).
(define outline-segments (let ((origin (make-vect 0.0 0.0)) (one-zero (make-vect 1.0 0.0)) (zero-one (make-vect 0.0 1.0)) (one-one (make-vect 1.0 1.0))) (list (make-segment origin zero-one) (make-segment origin one-zero) (make-segment one-zero one-one) (make-segment one-one zero-one)))) (define outline-painter (segments->painter outline-segments))
b. Painting an x is accomplished by connecting opposite corners of the frame. This means drawing a line connecting (0, 0) to (1, 1) and (0, 1) to (1, 0) respectively.
(define diagonal-segments (let ((origin (make-vect 0.0 0.0)) (one-zero (make-vect 1.0 0.0)) (zero-one (make-vect 0.0 1.0)) (one-one (make-vect 1.0 1.0))) (list (make-segment origin one-one) (make-segment zero-one one-zero)))) (define x-painter (segments->painter diagonal-segments))
c. A diamond shape is created by connecting the midpoints of the sides of the unit square.
(define midpoint-segments (let ((m1 (make-vect 0.5 0.0)) (m2 (make-vect 1.0 0.5)) (m3 (make-vect 0.5 1.0)) (m4 (make-vect 0.0 0.5))) (list (make-segment m1 m2) (make-segment m2 m3) (make-segment m3 m4) (make-segment m4 m1)))) (define diamond-painter (segments->painter midpoint-segments))
d. I'll skip the wave painter. Too many line segments!

Exercise 2.50. Define the transformation flip-horiz, which flips painters horizontally, and transformations that rotate painters counterclockwise by 180 degrees and 270 degrees.

Answer:
(define (flip-horiz painter) (transform-painter painter (make-vect 1.0 0.0) (make-vect 0.0 0.0) (make-vect 1.0 1.0))) (define (rotate-ccw-180 painter) (transform-painter painter (make-vect 1.0 1.0) (make-vect 0.0 1.0) (make-vect 1.0 0.0))) (define (rotate-ccw-270 painter) (transform-painter painter (make-vect 0.0 1.0) (make-vect 0.0 0.0) (make-vect 1.0 1.0)))
Exercise 2.51. Define the below operation for painters. Below takes two painters as arguments. The resulting painter, given a frame, draws with the first painter in the bottom of the frame and with the second painter in the top. Define below in two different ways -- first by writing a procedure that is analogous to the beside procedure given above, and again in terms of beside and suitable rotation operations (from exercise 2.50).

Answer:
;; below - analogous to beside (define (below painter-bottom painter-top) (let ((split-point (make-vect 0 0.5))) (let ((paint-top (transform-painter painter-top split-point (make-vect 1.0 0.5) (make-vect 0.0 1.0))) (paint-bottom (transform-painter painter-bottom (make-vect 0.0 0.0) (make-vect 1.0 0.0) split-point))) (lambda (frame) (paint-top frame) (paint-bottom frame))))) ;; below in terms of beside and rotation operations from Exercise 2.50 (define (below painter-bottom painter-top) (lambda (frame) (rotate-ccw-90 (beside (rotate-ccw-270 painter-bottom) (rotate-ccw-270 painter-top))) frame))
Exercise 2.52. Make changes to the square limit of wave shown in figure 2.9 by working at each of the levels described above. In particular:

a. Add some segments to the primitive wave painter of exercise 2.49 (to add a smile, for example).

b. Change the pattern constructed by corner-split (for example, by using only one copy of the up-split and right-split images instead of two).

c. Modify the version of square-limit that uses square-of-four so as to assemble the corners in a different pattern. (For example, you might make the big Mr. Rogers look outward from each corner of the square.)

Answer: I am skipping the smiley part.
;; b. change pattern used by corner-split (define (corner-split painter n) (if (= n 0) painter (let ((up (up-split painter (- n 1))) (right (right-split painter (- n 1)))) (let ((corner (corner-split (painter (- n 1))))) (beside (below painter up) (below right corner)))))) ;; c. modify square-limit (define (square-limit painter n) (let ((quarter (corner-split painter n))) (let ((half (beside quarter (flip-horiz quarter)))) (below (flip-vert half) half))))

SICP Section 2.2 Hierarchical Data and the Closure Property - Part 1

Exercise 2.17. Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list:
(last-pair (list 23 72 149 34)) (34)
Answer: This solution uses the length and list-ref functions described in the text. Here is a simpler solution which does not use length or list-ref.
(define (last-pair items) (cond ((null? items) '()) ((null? (cdr items)) items) (else (last-pair (cdr items)))))
Exercise 2.18. Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:
(reverse (list 1 4 9 16 25)) (25 16 9 4 1)
Answer:
(define (reverse items) (if (null? items) '() (append (reverse (cdr items)) (list (car items)))))
Exercise 2.19. Consider the change-counting program of section 1.2.2. It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure first-denomination and partly into the procedure count-change (which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change.

We want to rewrite the procedure cc so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency:
(define us-coins (list 50 25 10 5 1)) (define uk-coins (list 100 50 20 10 5 2 1 0.5))
We could then call cc as follows:
(cc 100 us-coins) 292
To do this will require changing the program cc somewhat. It will still have the same form, but it will access its second argument differently, as follows:
(define (cc amount coin-values) (cond ((= amount 0) 1) ((or (< amount 0) (no-more? coin-values)) 0) (else (+ (cc amount (except-first-denomination coin-values)) (cc (- amount (first-denomination coin-values)) coin-values)))))
Define the procedures first-denomination, except-first-denomination, and no-more? in terms of primitive operations on list structures. Does the order of the list coin-values affect the answer produced by cc? Why or why not?

Answer:
(define (first-denomination coin-values) (car coin-values)) (define (except-first-denomination coin-values) (cdr coin-values)) (define (no-more? coin-values) (null? coin-values))
Order of the list coin-values will not matter. This owes to the way cc is structured. The first recursive call to cc tries to compare the amount with *all* denominations irrespective of their order in the list.

Exercise 2.20. The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a list of any remaining arguments. For instance, given the definition
(define (f x y . z) <body>)
the procedure f can be called with two or more arguments. If we evaluate
(f 1 2 3 4 5 6)
then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition
(define (g . w) <body>)
the procedure g can be called with zero or more arguments. If we evaluate
(g 1 2 3 4 5 6)
then in the body of g, w will be the list (1 2 3 4 5 6).

Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example,
(same-parity 1 2 3 4 5 6 7) (1 3 5 7) (same-parity 2 3 4 5 6 7) (2 4 6)
Answer:
(define (same-parity . items) (define (parity-type n) (if (= (modulo n 2) 0) even? odd?)) (define (iter has-expected-parity? items result) (if (null? items) result (let ((first (car items)) (rest (cdr items))) (if (has-expected-parity? first) (iter has-expected-parity? rest (append result (list first))) (iter has-expected-parity? rest result))))) (iter (parity-type (car items)) items '()))
Exercise 2.21. The procedure square-list takes a list of numbers as argument and returns a list of the squares of those numbers.
(square-list (list 1 2 3 4)) (1 4 9 16)
Here are two different definitions of square-list. Complete both of them by filling in the missing expressions:
(define (square-list items) (if (null? items) nil (cons <??> <??>))) (define (square-list items) (map <??> <??>))
Answer:
(define (square-list items) (if (null? items) '() (cons (* (car items) (car items)) (square-list (cdr items))))) (define (square-list items) (map (lambda (x) (* x x)) items))
Exercise 2.22. Louis Reasoner tries to rewrite the first square-list procedure of exercise 2.21 so that it evolves an iterative process:
(define (square-list items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons (square (car things)) answer)))) (iter items nil))
Unfortunately, defining square-list this way produces the answer list in the reverse order of the one desired. Why?

Louis then tries to fix his bug by interchanging the arguments to cons:
(define (square-list items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons answer (square (car things)))))) (iter items nil))
This doesn't work either. Explain.

Answer: In the first procedure iter starts by attaching the first item from the input list to answers. Subsequent items are consed to answers, thereby ending up *before* the first. Hence answers ends up having the square of the items in reverse order.

The second approach tried by Louis gets the order right. However the end result is not a plain list as he expects. Here the cons operation starts by attaching the empty answer list to the square of the first item. This yields (() . 1) and not (1). Further iterations repeat the same operation with similar results.

Exercise 2.23. The procedure for-each is similar to map. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, for-each just applies the procedure to each of the elements in turn, from left to right. The values returned by applying the procedure to the elements are not used at all -- for-each is used with procedures that perform an action, such as printing. For example,
(for-each (lambda (x) (newline) (display x)) (list 57 321 88)) 57 321 88
The value returned by the call to for-each (not illustrated above) can be something arbitrary, such as true. Give an implementation of for-each.

Answer:
(define (for-each proc items) (cond ((not (null? items)) (proc (car items)) (for-each proc (cdr items)))))
Exercise 2.24. Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in figure 2.6). Answer: The interpreter prints (1 (2 (3 4))). I'll add the pictures once I draw them out using GIMP.

Exercise 2.25. Give combinations of cars and cdrs that will pick 7 from each of the following lists:
(1 3 (5 7) 9) ((7)) (1 (2 (3 (4 (5 (6 7))))))
Answer:
(define x '(1 3 (5 7) 9)) (car (cdr (car (cdr (cdr x))))) 7 (define x '((7))) (car (car x)) 7 (define x '(1 (2 (3 (4 (5 (6 7))))))) (cadr (cadr (cadr (cadr (cadr (cadr x)))))) 7
Exercise 2.26. Suppose we define x and y to be two lists:
(define x (list 1 2 3)) (define y (list 4 5 6))
What result is printed by the interpreter in response to evaluating each of the following expressions:
(append x y) (cons x y) (list x y)
Answer:
(append x y) (1 2 3 4 5 6) (cons x y) ((1 2 3) 4 5 6) (list x y) ((1 2 3) (4 5 6))
Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,
(define x (list (list 1 2) (list 3 4))) x ((1 2) (3 4)) (reverse x) ((3 4) (1 2)) (deep-reverse x) ((4 3) (2 1))
Answer:
(define (deep-reverse tree) (cond ((null? tree) nil) ((pair? (car tree)) (append (deep-reverse (cdr tree)) (list (deep-reverse (car tree))))) (else (append (deep-reverse (cdr tree)) (list (car tree)))))) (deep-reverse (list (list 1 2) (list 3 4))) ((4 3) (2 1))
Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,
(define x (list (list 1 2) (list 3 4))) (fringe x) (1 2 3 4) (fringe (list x x)) (1 2 3 4 1 2 3 4)
Answer:
(define (fringe tree) (cond ((null? tree) nil) ((pair? (car tree)) (append (fringe (car tree)) (fringe (cdr tree)))) (else (append (list (car tree)) (fringe (cdr tree))))))
Exercise 2.29. A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):
(define (make-mobile left right) (list left right))
A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:
(define (make-branch length structure) (list length structure))
a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.

b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.

c. A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.

d. Suppose we change the representation of mobiles so that the constructors are
(define (make-mobile left right) (cons left right)) (define (make-branch length structure) (cons length structure))
How much do you need to change your programs to convert to the new representation?

Answer: a. As the mobile is represented as a list the selectors are straight forward to implement.
;; (a) Selectors (define (left-branch mobile) (car mobile)) (define (right-branch mobile) (car (cdr mobile))) (define (branch-length branch) (car branch)) (define (branch-structure branch) (car (cdr branch)))
b. Calculation of total weight is made easier by an utility procedure which calculates the weight of a given branch. These procedure use mutual recursion to calculate the total weight of a given mobile.
;; (b) total-weight (define (branch-weight branch) (if (pair? (branch-structure branch)) (total-weight (branch-structure branch)) (branch-structure branch))) (define (total-weight mobile) (+ (branch-weight (left-branch mobile)) (branch-weight (right-branch mobile))))
c. The test to find out if a mobile is balanced can be similarly written with the help of an utility procedure to find out if its sub-mobiles are balanced.
;; (c) balanced? (define (balanced? mobile) (let ((left (left-branch mobile)) (right (right-branch mobile))) (and (= (torque left) (torque right)) (submobiles-balanced? left) (submobiles-balanced? right)))) (define (torque branch) (* (branch-length branch) (branch-weight branch))) (define (submobiles-balanced? branch) (let ((structure (branch-structure branch))) (or (not (pair? structure)) (balanced? structure))))
d. Only the selectors need to be changed. For instance the right-branch can use (cdr mobile) instead of (car (cadr mobile)).

Exercise 2.30. Define a procedure square-tree analogous to the square-list procedure of exercise 2.21. That is, square-list should behave as follows:
(square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))) (1 (4 (9 16) 25) (36 49))
Define square-tree both directly (i.e., without using any higher-order procedures) and also by using map and recursion.

Answer:
(define (square-tree tree) (cond ((null? tree) nil) ((not (pair? tree)) (* tree tree)) (else (cons (square-tree (car tree)) (square-tree (cdr tree)))))) ;; using map (define (square-tree tree) (map (lambda (sub-tree) (if (pair? sub-tree) (square-tree sub-tree) (* sub-tree sub-tree))) tree))
Exercise 2.31. Abstract your answer to exercise 2.30 to produce a procedure tree-map with the property that square-tree could be defined as
(define (square-tree tree) (tree-map square tree))
Answer:
(define (tree-map proc tree) (map (lambda (sub-tree) (if (pair? sub-tree) (tree-map proc sub-tree) (proc sub-tree))) tree)) (define (square-tree tree) (tree-map square tree)) ;; another use (define (inc-tree tree) (tree-map inc tree))
Exercise 2.32. We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:
(define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map <??> rest)))))
Answer:
(define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map (lambda (x) (cons (car s) x)) rest)))))
Exercise 2.33. Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:
(define (map p sequence) (accumulate (lambda (x y) <??>) nil sequence)) (define (append seq1 seq2) (accumulate cons <??> <??>)) (define (length sequence) (accumulate <??> 0 sequence))
Answer:
(define (a-map p sequence) (accumulate (lambda (x y) (cons (p x) y)) nil sequence)) (a-map inc (list 1 2 3 4)) (2 3 4 5) (define (a-append seq1 seq2) (accumulate cons seq2 seq1)) (a-append (list 1) (list 3 4)) (1 3 4) (define (length sequence) (accumulate (lambda (x y) (+ y 1)) 0 sequence)) (length (list 1 (list 3 4))) 2
Exercise 2.34. Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial

using a well-known algorithm called Horner's rule, which structures the computation as

In other words, we start with an, multiply by x, add an-1, multiply by x, and so on, until we reach a0.16 Fill in the following template to produce a procedure that evaluates a polynomial using Horner's rule. Assume that the coefficients of the polynomial are arranged in a sequence, from a0 through an.
(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) <??>) 0 coefficient-sequence))
For example, to compute 1 + 3x + 5x³ + x⁵ at x = 2 you would evaluate
(horner-eval 2 (list 1 3 0 5 0 1))
Answer:
(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* higher-terms x))) 0 coefficient-sequence))
Exercise 2.35. Redefine count-leaves from section 2.2.2 as an accumulation:
(define (count-leaves t) (accumulate <??> <??> (map <??> <??>)))
Answer:
(define (count-leaves t) (accumulate + 0 (map (lambda (x) 1) (fringe t))))
Exercise 2.36. The procedure accumulate-n is similar to accumulate except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if s is a sequence containing four sequences, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), then the value of (accumulate-n + 0 s) should be the sequence (22 26 30). Fill in the missing expressions in the following definition of accumulate-n:
(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init <??>) (accumulate-n op init <??>))))
Answer:
(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init (map (lambda (x) (car x)) seqs)) (accumulate-n op init (map (lambda (x) (cdr x)) seqs)))))
Exercise 2.37. Suppose we represent vectors v = (vi) as sequences of numbers, and matrices m = (mij) as sequences of vectors (the rows of the matrix). For example, the matrix

is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following:

We can define the dot product as
(define (dot-product v w) (accumulate + 0 (map * v w)))
Fill in the missing expressions in the following procedures for computing the other matrix operations. (The procedure accumulate-n is defined in exercise 2.36.)
(define (matrix-*-vector m v) (map <??> m)) (define (transpose mat) (accumulate-n <??> <??> mat)) (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map <??> m)))
Answer:
;; Matrix * Vector (define (matrix-*-vector m v) (map (lambda (x) (dot-product x v)) m)) ;; Transpose Matrix (define (transpose mat) (accumulate-n cons nil mat)) ;; Matrix * Matrix (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map (lambda (x) (map (lambda (y) (accumulate + 0 (accumulate-n * 1 (list x y)))) cols)) m)))
Exercise 2.38. The accumulate procedure is also known as fold-right, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a fold-left, which is similar to fold-right, except that it combines elements working in the opposite direction:
(define (fold-left op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence))
What are the values of
(fold-right / 1 (list 1 2 3)) (fold-left / 1 (list 1 2 3)) (fold-right list nil (list 1 2 3)) (fold-left list nil (list 1 2 3))
Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

Answer:
(fold-right / 1 (list 1 2 3)) 1 1/2 (fold-left / 1 (list 1 2 3)) 1/6 (fold-right list nil (list 1 2 3)) (1 (2 (3 ()))) (fold-left list nil (list 1 2 3)) (((() 1) 2) 3)
In order for fold-right and fold-left to yield identical results op should be associative. For instance take the + operator.
(fold-right + 1 (list 1 2 3)) 7 (fold-left + 1 (list 1 2 3)) 7
Exercise 2.39. Complete the following definitions of reverse (exercise 2.18) in terms of fold-right and fold-left from exercise 2.38:
(define (reverse sequence) (fold-right (lambda (x y) <??>) nil sequence)) (define (reverse sequence) (fold-left (lambda (x y) <??>) nil sequence))
Answer:
(define (reverse sequence) (fold-right (lambda (x y) (if (null? y) (list x) (append y (list x)))) nil sequence)) (define (reverse sequence) (fold-left (lambda (x y) (if (null? x) (list y) (append (list y) x))) nil sequence))
Exercise 2.40. Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i,j) with 1< j< i< n. Use unique-pairs to simplify the definition of prime-sum-pairs given above.

Answer:
(define (unique-pairs n) (flatmap (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n)))
Exercise 2.41. Write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s.

Answer:
(define (generate-triples n) (flatmap (lambda (i) (flatmap (lambda (j) (map (lambda (k) (list i j k)) (enumerate-interval 1 (- j 1)))) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n))) (define (find-triples n s) (define (sum-equal-s? triple) (let ((a (car triple)) (b (cadr triple)) (c (caddr triple))) (= (+ a b c) s))) (filter sum-equal-s? (generate-triples n)))
Exercise 2.42.

Figure 2.8: A solution to the eight-queens puzzle.

The ``eight-queens puzzle'' asks how to place eight queens on a chessboard so that no queen is in check from any other (i.e., no two queens are in the same row, column, or diagonal). One possible solution is shown in figure 2.8. One way to solve the puzzle is to work across the board, placing a queen in each column. Once we have placed k - 1 queens, we must place the kth queen in a position where it does not check any of the queens already on the board. We can formulate this approach recursively: Assume that we have already generated the sequence of all possible ways to place k - 1 queens in the first k - 1 columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of the kth column. Now filter these, keeping only the positions for which the queen in the kth column is safe with respect to the other queens. This produces the sequence of all ways to place k queens in the first k columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle.

We implement this solution as a procedure queens, which returns a sequence of all solutions to the problem of placing n queens on an n× n chessboard. Queens has an internal procedure queen-cols that returns the sequence of all ways to place queens in the first k columns of the board.
(define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size))
In this procedure rest-of-queens is a way to place k - 1 queens in the first k - 1 columns, and new-row is a proposed row in which to place the queen for the kth column. Complete the program by implementing the representation for sets of board positions, including the procedure adjoin-position, which adjoins a new row-column position to a set of positions, and empty-board, which represents an empty set of positions. You must also write the procedure safe?, which determines for a set of positions, whether the queen in the kth column is safe with respect to the others. (Note that we need only check whether the new queen is safe -- the other queens are already guaranteed safe with respect to each other.)

Answer:
(define empty-board (list nil)) (define (adjoin-position new-row k rest-of-queens) (if (null? (car rest-of-queens)) (list (list k new-row)) (cons (list k new-row) rest-of-queens))) (define (safe? k positions) (define (iter new-pos others) (if (null? others) #t (let ((other-pos (car others))) (if (row-col-or-dia-matches? new-pos other-pos) #f (iter new-pos (cdr others)))))) (if (= k 1) #t (iter (car positions) (cdr positions)))) (define (row-col-or-dia-matches? new-position other-position) (or (same-row? new-position other-position) (same-col? new-position other-position) (same-diagonal? new-position other-position))) (define (same-row? pos1 pos2) (= (cadr pos1) (cadr pos2))) (define (same-col? pos1 pos2) (= (car pos1) (car pos2))) (define (same-diagonal? pos1 pos2) (let ((k1 (car pos1)) (k2 (car pos2)) (r1 (cadr pos1)) (r2 (cadr pos2))) (= (abs (- k1 k2)) (abs (- r1 r2)))))
Exercise 2.43. Louis Reasoner is having a terrible time doing exercise 2.42. His queens procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the 6× 6 case.) When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order of the nested mappings in the flatmap, writing it as
(flatmap (lambda (new-row) (map (lambda (rest-of-queens) (adjoin-position new-row k rest-of-queens)) (queen-cols (- k 1)))) (enumerate-interval 1 board-size))
Explain why this interchange makes the program run slowly. Estimate how long it will take Louis's program to solve the eight-queens puzzle, assuming that the program in exercise 2.42 solves the puzzle in time T.

Answer: Louis is breaking a well known rule of thumb in programming - namely to avoid expensive operations in inner loops. His code is calling the expensive recursive call to queen-cols in the inner loop.

I am not able to figure out how much time Louis' procedure will take to run in terms of T. If you have an answer/explanation do let me know.

SICP Section 2.1 Introduction to Data Abstraction

Exercise 2.1. Define a better version of make-rat that handles both positive and negative arguments. Make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

Answer:
(define (make-rat n d) (let ((g (gcd n d)) (ratio (/ n d))) (if (> ratio 0.0) (cons (/ n g) (/ d g)) (cons (- (abs (/ n g))) (abs (/ d g))))))
Exercise 2.2. Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points:
(define (print-point p) (newline) (display "(") (display (x-point p)) (display ",") (display (y-point p)) (display ")"))
Answer:
;; Point (define (make-point x y) (cons x y)) (define (x-point p) (car p)) (define (y-point p) (cdr p)) ;; Line segment (define (make-segment start end) (cons start end)) (define (start-segment seg) (car seg)) (define (end-segment seg) (cdr seg)) (define (print-point p) (display "(") (display (x-point p)) (display ",") (display (y-point p)) (display ")")) (define (midpoint-segment seg) (let ((start (start-segment seg)) (end (end-segment seg))) (let ((x1 (x-point start)) (y1 (y-point start)) (x2 (x-point end)) (y2 (y-point end))) (make-point (average x1 x2) (average y1 y2))))) ;; (define seg (make-segment (make-point 0 1) (make-point 2 1))) ;; (print-point (midpoint-segment seg)) ;; (1,1)
Exercise 2.3. Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

Answer:
(define (make-rect p1 p2 p3 p4) (cons (cons p1 p2) (cons p3 p4))) (define (length-seg seg) (let ((start (start-segment seg)) (end (end-segment seg))) (let ((x1 (x-point start)) (y1 (y-point start)) (x2 (x-point end)) (y2 (y-point end))) (sqrt (+ (square (- x2 x1)) (square (- y2 y1))))))) (define (rect-length r) (let ((p1 (car (car r))) (p2 (cdr (car r)))) (let ((side (make-segment p1 p2))) (length-seg side)))) (define (rect-breadth r) (let ((p1 (car (car r))) (p4 (cdr (cdr r)))) (let ((side (make-segment p1 p4))) (length-seg side)))) (define (perimeter r) (* 2 (+ (rect-length r) (rect-breadth r)))) (define (area r) (* (rect-length r) (rect-breadth r))) ;; (define r (make-rect ;; (make-point 0 0) ;; (make-point 0 1) ;; (make-point 2 1) ;; (make-point 2 0))) ;; (perimeter r) ;; 6 ;; (area r) ;; 2
Exercise 2.4. Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.
(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p)))
What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

Answer:
(define (cons1 x y) (lambda (m) (m x y))) (define (car1 z) (z (lambda (p q) p))) ;; cdr (define (cdr1 z) (z (lambda (p q) q))) ;; (car1 (cons1 2 1)) ;; 2 ;; (cdr1 (cons1 2 1)) ;; 1
Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2a 3b. Give the corresponding definitions of the procedures cons, car, and cdr.

Answer:
(define (count-powers-of-n number n) (define (iter count number) (if (and (= (remainder number n) 0) (>= number n)) (iter (+ 1 count) (/ number n)) count)) (iter 0 number)) (define (count-powers-of-2 number) (count-powers-of-n number 2)) (define (count-powers-of-3 number) (count-powers-of-n number 3)) (define (n-cons a b) (* (expt 2 a) (expt 3 b))) (define (n-car z) (count-powers-of-2 z)) (define (n-cdr z) (count-powers-of-3 z)) ;; (n-car (n-cons 10 11)) ;; 10 ;; (n-cdr (n-cons 10 11)) ;; 11
Exercise 2.6. In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

Answer:
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x))))) ;; one (define one (lambda (f) (lambda (x) (f x)))) ;; two (define two (lambda (f) (lambda (x) (f (f x))))) ;; + (define (church+ m n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))
Exercise 2.7. Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor:
(define (make-interval a b) (cons a b))
Define selectors upper-bound and lower-bound to complete the implementation.

Answer:
;; selectors (define (lower-bound interval) (car interval)) (define (upper-bound interval) (cdr interval))
Exercise 2.8. Using reasoning analogous to Alyssa's, describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called sub-interval.

Answer:
(define (sub-interval x y) (make-interval (- (lower-bound x) (upper-bound y)) (- (upper-bound x) (lower-bound y))))
Exercise 2.10. Ben Bitdiddle, an expert systems programmer, looks over Alyssa's shoulder and comments that it is not clear what it means to divide by an interval that spans zero. Modify Alyssa's code to check for this condition and to signal an error if it occurs.


(define (spans-zero? interval) (and (< (lower-bound interval) 0) (> (upper-bound interval) 0))) (define (div-interval x y) (if (spans-zero? y) (error "Denominator interval spans zero" y) (mul-interval x (make-interval (/ 1.0 (upper-bound y)) (/ 1.0 (lower-bound y))))))
Exercise 2.11. In passing, Ben also cryptically comments: ``By testing the signs of the endpoints of the intervals, it is possible to break mul-interval into nine cases, only one of which requires more than two multiplications.'' Rewrite this procedure using Ben's suggestion.

After debugging her program, Alyssa shows it to a potential user, who complains that her program solves the wrong problem. He wants a program that can deal with numbers represented as a center value and an additive tolerance; for example, he wants to work with intervals such as 3.5± 0.15 rather than [3.35, 3.65]. Alyssa returns to her desk and fixes this problem by supplying an alternate constructor and alternate selectors:
(define (make-center-width c w) (make-interval (- c w) (+ c w))) (define (center i) (/ (+ (lower-bound i) (upper-bound i)) 2)) (define (width i) (/ (- (upper-bound i) (lower-bound i)) 2))
Unfortunately, most of Alyssa's users are engineers. Real engineering situations usually involve measurements with only a small uncertainty, measured as the ratio of the width of the interval to the midpoint of the interval. Engineers usually specify percentage tolerances on the parameters of devices, as in the resistor specifications given earlier.

Answer:
(define (above-zero? interval) (and (> (lower-bound interval) 0) (> (upper-bound interval) 0))) (define (below-zero? interval) (and (< (lower-bound interval) 0) (< (upper-bound interval) 0))) (define (mul-interval x y) (let ((l1l2 (* (lower-bound x) (lower-bound y))) (l1u2 (* (lower-bound x) (upper-bound y))) (u1l2 (* (upper-bound x) (lower-bound y))) (u1u2 (* (upper-bound x) (upper-bound y)))) (cond ((and (above-zero? x) (above-zero? y)) (make-interval l1l2 u1u2)) ((and (above-zero? x) (spans-zero? y)) (make-interval u1l2 u1u2)) ((and (spans-zero? x) (above-zero? y)) (make-interval l1u2 u1u2)) ((and (above-zero? x) (below-zero? y)) (make-interval u1u2 l1l2)) ((and (below-zero? x) (above-zero? y)) (make-interval u1u2 l1l2)) ((and (below-zero? x) (spans-zero? y)) (make-interval l1u2 l1l2)) ((and (spans-zero? x) (below-zero? y)) (make-interval u1l2 l1l2)) ((and (below-zero? x) (below-zero? y)) (make-interval u1u2 l1l2)) ((and (spans-zero? x) (spans-zero? y)) (make-interval (min l1u2 u1l2) (min l1l2 u1u2))))))
Exercise 2.12. Define a constructor make-center-percent that takes a center and a percentage tolerance and produces the desired interval. You must also define a selector percent that produces the percentage tolerance for a given interval. The center selector is the same as the one shown above.

Answer:
(define (center i) (/ (+ (lower-bound i) (upper-bound i)) 2)) (define (make-center-percent c p) (let ((p-value (/ (* c p) 100))) (make-interval (- c p-value) (+ c p-value))))
Exercise 2.13. Show that under the assumption of small percentage tolerances there is a simple formula for the approximate percentage tolerance of the product of two intervals in terms of the tolerances of the factors. You may simplify the problem by assuming that all numbers are positive.

After considerable work, Alyssa P. Hacker delivers her finished system. Several years later, after she has forgotten all about it, she gets a frenzied call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that the formula for parallel resistors can be written in two algebraically equivalent ways:

and

He has written the following two programs, each of which computes the parallel-resistors formula differently:
(define (par1 r1 r2) (div-interval (mul-interval r1 r2) (add-interval r1 r2))) (define (par2 r1 r2) (let ((one (make-interval 1 1))) (div-interval one (add-interval (div-interval one r1) (div-interval one r2)))))
Lem complains that Alyssa's program gives different answers for the two ways of computing. This is a serious complaint.

Answer: Let x and y be two intervals and dx and dy their respective tolerances. Their product can be calculated as (x + dx) * (y + dy). Expanding this we get xy + xdy + ydx + dxdy. As dx and dy are small to begin with their product will be very small and can be ignored without losing much accuracy. The equation then becomes xy + xdy + ydx.

If we call the product z, with a tolerance dz, then z + dz = xy + xdy + ydx. Separating z and dz, we get dz = xdy + ydx. This is the relation between the tolerance of the product the individual tolerances.

Exercise 2.14. Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals A and B, and use them in computing the expressions A/A and A/B. You will get the most insight by using intervals whose width is a small percentage of the center value. Examine the results of the computation in center-percent form (see exercise 2.12).

Answer: Lem's hypothesis is easily proven right. Take the example below.
(define (par1 r1 r2) (div-interval (mul-interval r1 r2) (add-interval r1 r2))) (define (par2 r1 r2) (let ((one (make-interval 1 1))) (div-interval one (add-interval (div-interval one r1) (div-interval one r2))))) (define x (make-center-percent 3 0.1)) (define y (make-center-percent 7 0.1)) (par1 x y) ;; (2.0937083916083914 . 2.1063084084084083) (par2 x y) ;; (2.0979 . 2.1021)
The problem stems from the fact that the formulae do not take intervals into consideration whereas the code does. For instance the interval one implicitly assumes that R1/R1 = R2/R2 = 1. However this is only true when intervals are not involved. Hence the two formulae give two different results.

Exercise 2.15. Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, par2 is a ``better'' program for parallel resistances than par1. Is she right? Why?

Answer: Eva is correct. As we are operating with intervals rather than whole numbers it is better to reduce the "occurrence" of intervals in any given formula to a minimum. This reduces the number of ways in which errors can creep in and thereby produces tighter bounds. As the second formula has fewer occurrences of the intervals it will produce tighter bounds.

Exercise 2.16. Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

Answer: The answer is similar those of the two previous questions. The main reason is the difference between using whole numbers and intervals. Normal properties and rules of algebra that apply to whole numbers do not hold true when intervals are used. For instance, while x/x = 1 when x and y are non zero whole numbers this is not so for cases when x is an interval. Likewise x - x need not be zero and so on.

It *might* be possible to develop a package provided such concepts as inverse can be defined for an interval. I am not sure how to go about the definitions though.