MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001--Structure and Interpretation of Computer Programs
Fall Semester, 1998

Problem Set 4 Solutions

Tutorial Exercise 1

(a) square : Generic-Num -> Generic-Num

(b) Defining square as suggested would require the addition of a square procedure to the table for every possible type of generic number. Each of those procedures would have to be different, because they would receive the internal representation of the number as their argument rather than a generic number (e.g. RepNum rather than Generic-Num). Defining the square procedure in terms of the generic mul procedure allows it to handle all types of generic numbers, including any new ones we define later, with a minimum of hassle.

Ordinary Number Package

Tutorial Exercise 2

make-number : RepNum -> Generic-OrdNum
negate : RepNum -> Generic-OrdNum
zero? : RepNum -> SchBool

Tutorial Exercise 3

The list-of-type-tags representation is the requirement of the apply-generic procedure, since it always keeps its arguments in a list, and passes the type-tags to the get procedure after stripping them from the numbers using map. However, the table itself does not require its tags to be in any specific format. It compares tags using the Scheme equal? procedure, which works equally well on lists and symbols. Since we've defined the make operation on generic numbers using a type-tag which is not part of a list we cannot call it using apply-generic, but we can call it directly using get, which is exactly what we do when defining create-number.

PreLab/Lab Exercise 4

Since RepNum=SchNum, we can use the primitive Scheme procedure = as =number?. Implementing the equ? operation on generic numbers is as simple as inserting a few lines of code into the install-number-package definition:

  ;=number : (RepNum,RepNum) -> SchBool
  (define =number? =)
  (put 'equ? '(number number) =number?)

Rational Number Package

Tutorial Exercise 5A

second-try is an example of the correct way to define a rational number. Calling create-rational with numbers (rather than generic numbers) as its arguments results in a rational number whose components are not generic numbers. In this case, the attempts to use the generic add procedure on them will result in an error as apply-generic attempts to examine a non-existant type-tag.

PreLab Exercise 5B

After its definition is evaluated by the interpreter, rsq will print as follows:

rsq
;Value: (rational (number . 120) number . 100)

It's box-and-pointer representation is:

     _____      _____              _____
--->|  | ----->|  | ------------->|  | -----> 100
    || |  |    || |  |            || |  |
     |~~~~      |~~~~              |~~~~
     V          V_____             V
    'rational   |  | -----> 120   'number
                || |  |
                 |~~~~
                 V
                'number

Tutorial Exercise 6

A definition of add inside a package would override the top-level definition of add as the generic add operation. This would not affect the use of add outside the package, but it would make the generic add procedure unavailable within the procedure. Inside the Ordinary Number Package, which never uses generic add this is not a problem. In the Rational Number package, however, the generic add procedure is used, so overriding its definition would be a problem, one which using the name add-rational instead avoids.

PreLab/Lab Exercise 7

Implementing the negate, =zero?, and equ? operations for rational numbers requires simply adding a few procedures and calls to put to the definition of install-rational-package. To maintain the convention started in the Ordinary Number Package, we define separate procedures negate-rat and negate-rational which have return types of RepRat and Generic-Rational respectively. Since the other two operations are predicates, no such separation is needed.

  ;negate-rat : RepRat -> RepRat
  (define (negate-rat x)
    (make-rat (negate (numer x)) (denom x)))

  ;negate-rational : RepRat -> Generic-Rational
  (define (negate-rational x) (tag (negate-rat x)))

  ;=zero-rat? : RepRat -> SchBool
  (define (=zero-rational? x) (=zero? (numer x)))

  ;=rational? : (RepRat,RepRat) -> SchBool
  (define (=rational? x y) (=zero-rational? (sub-rat x y)))

  (put 'negate '(rational) negate-rational)
  (put '=zero? '(rational) =zero-rational?)
  (put 'equ? '(rational rational) =rational?)

PreLabExercise 8

repnum->reprat simply turns the number x into the rational number x/1.

  (define (repnum->reprat n)
    (make-rat (create-number n) (create-number 1)))

PreLabExercise 9

The RRmethod->RNmethod procedure simply reverses the treatment of the two arguments in RRmethod->NRmethod. It is important that the arguments remain in the same order, for the purposes of asymmetric operations line sub.

  (define (RRmethod->RNmethod method)
    (lambda (rat num)
      (method rat (repnum->reprat num))))

PreLab/Lab Exercise 10

Given the procedures we've already defined, implementing the new operations is simply a matter of constructing appropriate procedures to install in the table:

  (put 'add '(rational number) (RRmethod->RNmethod add-rational))
  (put 'sub '(rational number) (RRmethod->RNmethod sub-rational))
  (put 'mul '(rational number) (RRmethod->RNmethod mul-rational))
  (put 'div '(rational number) (RRmethod->RNmethod div-rational))
  (put 'equ? '(rational number) (RRmethod->RNmethod =rational?))
  (put 'add '(number rational) (RRmethod->NRmethod add-rational))
  (put 'sub '(number rational) (RRmethod->NRmethod sub-rational))
  (put 'mul '(number rational) (RRmethod->NRmethod mul-rational))
  (put 'div '(number rational) (RRmethod->NRmethod div-rational))
  (put 'equ? '(number rational) (RRmethod->NRmethod =rational?))

Complex Number Package

Tutorial Exercise 5A

second-try is an example of the correct way to define a complex number. Calling create-complex with numbers (rather than generic numbers) as its arguments results in a complex number whose components are not generic numbers. In this case, the attempts to use the generic add procedure on them will result in an error as apply-generic attempts to examine a non-existant type-tag.

PreLab Exercise 5B

After its definition is evaluated by the interpreter, csq will print as follows:

csq
;Value: (complex (number . -35) number . -12)

It's box-and-pointer representation is:

     _____      _____              _____
--->|  | ----->|  | ------------->|  | -----> -12
    || |  |    || |  |            || |  |
     |~~~~      |~~~~              |~~~~
     V          V_____             V
    'complex    |  | -----> -35   'number
                || |  |
                 |~~~~
                 V
                'number

Tutorial Exercise 6

A definition of add inside a package would override the top-level definition of add as the generic add operation. This would not affect the use of add outside the package, but it would make the generic add procedure unavailable within the procedure. Inside the Ordinary Number Package, which never uses generic add this is not a problem. In the Complex Number package, however, the generic add procedure is used, so overriding its definition would be a problem, one which using the name add-rational instead avoids.

PreLab/Lab Exercise 7

Implementing the negate, =zero?, and equ? operations for complex numbers requires simply adding a few procedures and calls to put to the definition of install-rational-package. To maintain the convention started in the Ordinary Number Package, we define separate procedures negate-com and negate-complex which have return types of RepCom and Generic-Complex respectively. Since the other two operations are predicates, no such separation is needed.

  ;negate-com : RepRat -> RepRat
  (define (negate-com x)
    (make-com (negate (real x)) (negate (imag x))))

  ;negate-complex : RepCom -> Generic-Complex
  (define (negate-complex x) (tag (negate-com x)))

  ;=zero-com? : RepCom -> SchBool
  (define (=zero-complex? x) (and (=zero? (real x)) (=zero? (imag x))))

  ;=Complex? : (RepCom,RepCom) -> SchBool
  (define (=complex? x y) (and (equ? (real x) (real y))
			       (equ? (imag x) (imag y))))

  (put 'negate '(complex) negate-complex)
  (put '=zero? '(complex) =zero-complex?)
  (put 'equ? '(complex complex) =complex?)

PreLabExercise 8

repnum->repcom simply turns the number x into the rational number x+0i.

  (define (repnum->repcom n)
    (make-com (create-number n) (create-number 0)))

PreLabExercise 9

The CCmethod->CNmethod procedure simply reverses the treatment of the two arguments in CCmethod->NCmethod. It is important that the arguments remain in the same order, for the purposes of asymmetric operations line sub.

  (define (CCmethod->CNmethod method)
    (lambda (com num)
      (method com (repnum->repcom num))))

PreLab/Lab Exercise 10

Given the procedures we've already defined, implementing the new operations is simply a matter of constructing appropriate procedures to install in the table:

  (put 'add '(complex number) (CCmethod->CNmethod add-complex))
  (put 'sub '(complex number) (CCmethod->CNmethod sub-complex))
  (put 'mul '(complex number) (CCmethod->CNmethod mul-complex))
  (put 'div '(complex number) (CCmethod->CNmethod div-complex))
  (put 'equ? '(complex number) (CCmethod->CNmethod =complex?))
  (put 'add '(number complex) (CCmethod->NCmethod add-complex))
  (put 'sub '(number complex) (CCmethod->NCmethod sub-complex))
  (put 'mul '(number complex) (CCmethod->NCmethod mul-complex))
  (put 'div '(number complex) (CCmethod->NCmethod div-complex))
  (put 'equ? '(number complex) (CCmethod->NCmethod =complex?))

Interfacing Packages

PreLab/Lab Exercise 11

Using only the complex number package, the division could be accomplished dividing two complex numbers c1+3i and c5+0i by calling (div c1+2i c5+0i). This results in the following value:

;Value: (complex (number . .2) number . .6)

This represents 1/5 + 3/5 i, which is the correct answer.

If we chose to use the rational number package to represent the dividend, we could do so by calling (create-rational c1+3i n5), and the result would be as follows:

;Value: (rational (complex (number . 1) number . 3) number . 5)

This represents the rational number (1+3i)/5. Also a correct answer, where no reduction has been performed.

PreLab/Lab Exercise 12

The call to (div c1+3i c1+2i) results in a call to the div-com procedure in the Complex Number Package. div-com performs the division by multiplying the numerator and denominator by the complex conjugate of the denominator. This results in a denominator which is purely real, allowing the resulting complex number to be easily separated into its real and imaginary parts.

PreLab/Lab Exercise 13B

There are several possible solutions to this. One is to add a new procedure within the Complex Number Package which handles division differently, producing real and imaginary parts which are rational numbers. This can be done simply by following the same pattern as the original div-com procedure, replacing calls to the generic div operation with calls to create-rational. Rather than naming the procedure (and thus conflicting with the previous definition

  (define (div-com-new x y)
    (let ((com-conj (complex-conjugate y)))
       (let ((x-times-com-conj (mul-com x com-conj))
	     (y-times-com-conj (mul-com y com-conj)))
	 (make-com (create-rational (real x-times-com-conj)
			            (real y-times-com-conj))
		   (create-rational (imag x-times-com-conj)
			            (real y-times-com-conj)))))))

  (put 'div '(complex complex) div-com-new)

Lab Exercise 14

Testing equality between complex and rational numbers is as simple as coercing both numbers into the same type, and then comparing them using the equ? operation for that type. We chose to coerce both of the numbers to rationals, and for good reason. There is a limitation in our handling of generic complex numbers. Specifically, it always assumes that the generic numbers which represent the real and imaginary parts of the numbers are themselves purely real. If we create a complex number with complex components, then that property is not guaranteed to hold. This will not result in any errors in the standard operations such as add and mul, but there are some operations which could cease to work. The div operation on complex numbers, for example, would provide incorrect answers in this case. This is because dividing complex numbers requires calculating the complex conjugate of the denominator. The div-com procedure calculates the complex conjucate by negating the "imaginary" part of the complex number. However, since it simply treats the second component of the number as its imaginary part, it will not produce the correct answer in the case when that "imaginary" part contains other complex numbers.

The equality operations as we have written them would also fail in the situation of nested complex numbers. This is because the complex =zero? operation depends on both the real and imaginary parts being zero. If those parts contained complex numbers themselves, that would not necessarily be true even when the complex number represented was zero. For instance, (1+i)+(-1-i)i is equal to zero, but our =zero? operation would not detect it as such.

Avoiding this limitation entirely would require a method of examining the two components of a complex number to separate them into real and imaginary parts. However, since those components are themselves generic numbers, finding any complex numbers which might be nested within them would be difficult, especially if we want to maintain support for new types of generic numbers other than the four defined in this probelm set. Instead, then, we simply coerce the two arguments to our rational-complex equality procedures into rational numbers, thus guaranteeing that we do not introduce any new complex numbers with complex components. Our code will still perform incorrectly if the user creates such numbers, but we must rely on the user not to do so.

Since these procedures bridge the Rational and Complex packages they do not fit particularly well into either one of them. Thus we put them in their own package called the Rational-Complex Equality Package:

(define (install-rational-complex-equality-package)

  (define (=rat-com rat com)
    (equ? (attach-tag 'rational rat)
	  (create-rational (attach-tag 'complex com)
			   (create-number 1))))

  (define (=com-rat com rat)
    (=rat-com rat com))

  (put 'equ? '(rational complex) =rat-com)
  (put 'equ? '(complex rational) =com-rat)

  'done)

Polynomial Package

Tutorial Exercise 15

+ is used instead of add because the orders of polynomial terms are representes as SchNums rather than as Generic-Numbers.

PreLab/Lab Exercise 16

The map-terms procedure is nearly identical to the standard map procedure, except that it uses the datastructure constructors, accessors, and predicates for termlists, rather than the primitive list operations.

(define (map-terms proc tlist)
  (if (empty-termlist? tlist)
      (make-empty-termlist)
      (adjoin-term
       (proc (first-term tlist))
       (map-terms proc (rest-terms tlist)))))

PreLab/Lab Exercise 17

create-numerical-polynomial performs a straightforward translation of its input list into terms. Since adjoin-term automatically throws away terms with coefficient 0, there is no need to check for them in create-numerical-polynomial.

(define (create-numerical-polynomial var coeffs)
  (define (add-orders clist order)
    (if (null? clist)
	(make-empty-termlist)
	(adjoin-term (make-term order
				(create-number (car clist)))
		     (add-orders (cdr clist) (- order 1)))))
  (create-polynomial var
		     (add-orders coeffs (- (length coeffs) 1))))

Once this procedure is defined we can use it to define p1 as follows:

(define p1 (create-numerical-polynomial 'x '(1 5 0 -2)))

PreLab/Lab Exercise 18

Polynomial negation is simple enough to implement simply by negating all of the polynomial's coefficeients:

  (define (negate-poly p)
    (make-poly (variable p)
	       (map-terms (lambda (term)
		      (make-term (order term)
				 (negate (coeff term))))
		    (term-list p))))
  (define (negate-polynomial p) (tag (negate-poly p)))
  (put 'negate '(polynomial) negate-polynomial)

With the negate operation defined, the polynomial sub operation is easy:

  (define (sub-polynomial p1 p2)
    (add-polynomial p1 (negate-poly p2)))
  
  (put 'sub '(polynomial polynomial) sub-polynomial)

The =zero? and equ? operations both depend on the ability to compare termlists, so we define a helper procedure to do so:

  (define (=termlist? t1 t2)
    (cond ((empty-termlist? t1) (empty-termlist? t2))
	  ((empty-termlist? t2) #f)
	  (else (and (and (= (order (first-term t1))
			     (order (first-term t2)))
			  (equ? (coeff (first-term t1))
				(coeff (first-term t2))))
		     (=termlist? (rest-terms t1)
				 (rest-terms t2))))))

Now the actual predicates are defined easily:

  (define (=zero-polynomial? p)
    (empty-termlist? (term-list p))) ;Thanks to adjoin-term

  (define (=polynomial? p1 p2)
    (if (same-variable? (variable p1) (variable p2))
	(=termlist? (term-list p1) (term-list p2))
	(error "Polys not in same var -- EQ-POLY"
	       (list p1 p2))))
  
  (put 'equ? '(polynomial polynomial) =polynomial?)
  (put '=zero? '(polynomial) =zero-polynomial?)

Note that two polynomials of different variables are treated as incomparable, such that comparing them with equ? causes an error. Treating them as always not equal would also be a valid approach.

PreLab/Lab Exercise 19

Making p2 squareable is as simple as creating the constant polynomials for its two constant terms. This can be done using create-numerical-polynomial:

(define p2
  (create-polynomial
   'z
   (adjoin-term 
      (make-term 2 p1)
      (adjoin-term
         (make-term 1 (create-numerical-polynomial 'x '(5)))
         (adjoin-term 
            (make-term 0 (create-numerical-polynomial 'x '(3)))
            (make-empty-termlist))))))

PreLab/Lab Exercise 20A/20B

apply-terms simply adds the results of applying the individual terms:

(define (apply-terms termlist generic-number)
  (if (empty-termlist? termlist)
      (create-number 0)
      (add (apply-term (first-term termlist) generic-number)
	   (apply-terms (rest-terms termlist) generic-number))))

Lab Exercise 20C

Attempting to substitute x+1 for z in p2 results in an error when the system attempts to multiply x+1 by the coefficients of p2, which are generic ordinary numbers. To fix this, we need to install methods for handling multiplication of polynomials by ordinary numbers. For general usefulness, we should probably install methods for the other arithmatic operations as well. Since ordinary numbers can be coerced into constant polynomials, we can implement these operations using higher-order procedures much as we did for complex numbers and rational numbers, by adding the following code to the definition of install-polynomial-package:

  (define (PPmethod->PNmethod proc)
    (lambda (p n)
      (proc p
	    (make-poly (variable p)
		       (adjoin-term
			(make-term 0
				   (attach-tag 'number n))
			(make-empty-termlist))))))
  (define (PPmethod->NPmethod proc)
    (lambda (n p)
      (proc (make-poly (variable p)
		       (adjoin-term
			(make-term 0
				   (attach-tag 'number n))
			(make-empty-termlist)))
	    p)))

  (put 'add '(polynomial number) (PPmethod->PNmethod add-polynomial))
  (put 'sub '(polynomial number) (PPmethod->PNmethod sub-polynomial))
  (put 'mul '(polynomial number) (PPmethod->PNmethod mul-polynomial))
  (put 'add '(number polynomial) (PPmethod->NPmethod add-polynomial))
  (put 'sub '(number polynomial) (PPmethod->NPmethod sub-polynomial))
  (put 'mul '(number polynomial) (PPmethod->NPmethod mul-polynomial))

Solutions by Andrew Twyman (kurgan@mit.edu)
Last modified: Thu Oct 15 1998