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).New Types and Type Checking
Before we start into raising types, we should note that the system we've been developing in sections 2.5.1 and 2.5.2 does not deal with the tower of types presented in figure 2.25. At the moment our system has the following tower of types:
complex
↑
rational
↑
scheme-number
One way of dealing with this is to note that Scheme itself has its own tower of types which matches the tower of types we need for this exercise and that the scheme-number package will work with any type of Scheme number, not just integers. As a result we can use scheme-number as the basis for any of the types required for this exercise by copying the scheme-number package, and then changing the name of the package and the type tag in use in the copy. To keep us on our toes we'll only represent the integer and real types in this manner, and leave the rational and complex types as they are.Of course the
scheme-number package doesn't restrict what type of Scheme number it can represent. So that in itself leaves our system open to abuse - if we were to create the integer package using just the steps above (i.e. without further changes) there would be nothing to stop an (ab)user of the system from using the integer package to make an "integer" using a rational, real or complex Scheme number as the "integer" value to be represented.In order to prevent such abuse, and to ensure that our system is well behaved, we'll need to make sure that the
integer package is only ever used to represent integers, while the real package is only ever used to represent real numbers. Thankfully Scheme provides the integer? and real? predicates (and the corresponding rational? and complex? predicates too) which perform the appropriate tests. We can use these to modify the procedures installed for 'make in the two packages so that they enforce the correct type.This gives us the following implementations for these packages:
;;;
;;; Integer package
;;;
(define (install-integer-package)
(define (tag x)
(attach-tag 'integer x))
(put 'add '(integer integer)
(lambda (x y) (tag (+ x y))))
(put 'sub '(integer integer)
(lambda (x y) (tag (- x y))))
(put 'mul '(integer integer)
(lambda (x y) (tag (* x y))))
(put 'div '(integer integer)
(lambda (x y) (make-rational x y)))
(put 'equ? '(integer integer) =)
(put '=zero? '(integer)
(lambda (x) (= 0 x)))
(put 'make 'integer
(lambda (x) (if (integer? x)
(tag x)
(error "non-integer value" x))))
'done)
(define (make-integer n)
((get 'make 'integer) n))
;;;
;;; Real package
;;;
(define (install-real-package)
(define (tag x)
(attach-tag 'real x))
(put 'add '(real real)
(lambda (x y) (tag (+ x y))))
(put 'sub '(real real)
(lambda (x y) (tag (- x y))))
(put 'mul '(real real)
(lambda (x y) (tag (* x y))))
(put 'div '(real real)
(lambda (x y) (tag (/ x y))))
(put 'equ? '(real real) =)
(put '=zero? '(real)
(lambda (x) (= 0 x)))
(put 'make 'real
(lambda (x) (if (real? x)
(tag x)
(error "non-real value" x))))
'done)
(define (make-real n)
((get 'make 'real) n))
While we're talking about type correctness, it's possibly also worth noting that we don't do anything to ensure that the numbers represented by our rational package conform to the definition of rational numbers. I.e. both the numerator and denominator must be integers in order for it to be a valid rational number. Nor do we do anything to enforce that a complex number's real and imaginary parts are real numbers.Of course, depending upon your Scheme interpreter, or the implementation of
gcd you're using, you might find that you're already prevented from creating rational representations with non-integer values. However, to be consistent with the integer and real packages we've created, and to ensure that type correctness is enforced regardless of interpreter, we'll also update the rational and complex packages to with the appropriate checks. In the case of the complex package we'll actually put the checks in the underlying rectangular and polar packages so that we're prevented from constructing invalid representations at as low a level as possible.Here are the updates:
(define (install-rational-package)
;; internal procedures
…
(define (make-rat n d)
(if (and (integer? n) (integer? d))
(let ((g (gcd n d)))
(cons (/ n g) (/ d g)))
(error "non-integer numerator or denominator"
(list n d))))
…
;; interface to rest of the system
…
'done)
(define (install-rectangular-package)
;; internal procedures
…
(define (make-from-real-imag x y)
(if (and (in-tower? x) (in-tower? y))
(cons x y)
(error "non-real real or imaginary value" (list x y))))
…
(define (make-from-mag-ang r a)
(if (and (real? r) (real? a))
(cons (* r (cos a)) (* r (sin a)))
(error "non-real magnitude or angle" (list r a))))
…
;; interface to the rest of the system
…
'done)
(define (install-polar-package)
;; internal procedures
…
(define (make-from-mag-ang r a)
(if (and (in-tower? r) (in-tower? a))
(cons r a)
(error "non-real magnitude or angle" (list r a))))
…
(define (make-from-real-imag x y)
(if (and (in-tower? x) (in-tower? y))
(cons (sqrt (+ (square x) (square y)))
(atan y x))
(error "non-real real or imaginary value" (list x y))))
…
;; interface to the rest of the system
…
'done)
Raising Types
Okay, so now onto the exercise itself. We need to design a procedure that will raise an object of a particular type one level in the tower. The section on Coercion gives the example coercion procedurescheme-number->complex. It seems logical that we want to introduce further coercion procedures that correspond to the steps in the type tower. Let's consider what each procedure should do:
integer->rationalshould convert an integer to a rational number by using the value of the integer as the numerator and, as 1 is the identity value for division, 1 as the denominator.rational->realshould convert a rational number to a real number by taking the numerator and denominator from the rational number and converting them to a single (real) number representing that rational number. Of course the simple way to achieve this is by dividing the numerator by the denominator.real->complexshould convert a real number to a complex number by using the value of the real number as the real component of the complex number and 0 as the imaginary component.
(define (integer->rational i) (make-rational i 1)) (define (rational->real r) (make-real (/ (numer r) (denom r)))) (define (real->complex r) (make-complex-from-real-imag r 0))Now what do we do with them?
We could simply install these procedures in the table under an appropriate key (such as
raise) and then define a generic raise procedure that dispatches using apply-generic in the normal manner:
(define (raise x) (apply-generic 'raise x))However, I feel that this approach has some issues:
- It doesn't cope well with
complex. We're not explicitly told the semantics forraisewhen dealing withcomplexrepresentations. We're simply told that it should be an "operation that will work for each type (except complex)." If we implementraiseusingapply-genericthen trying toraiseacomplexrepresentation will result in an error. We could work around this by implementing and installing the identity transform procedure,complex->complex, but this doesn't quite feel right. - We're using coercion procedures, but we're not making any use of the
get-coercionandput-coercionintroduced in the section on Coercion. - The type tower is expressed implicitly by the procedures installed under the
raisekey. If we assume that each coercion procedure is defined and installed in the corresponding package (i.e.integer->rationalis installed in theintegerpackage, and so on) then this further means that there is no central location from which the type tower can be deduced and maintained.
Let's install the coercion procedures using
put-coercion and define the tower of types explicitly, as a list of types ordered from subtype to supertype (i.e. with integer first and complex last). raise can then simply find the type in the list, get the next type from its list as its immediate supertype and then get and use the appropriate coercion procedure to perform the raise. We've then got three special conditions to deal with and we can now deal with each separately:
- If the type's not present in the list then we can raise an error indicating that we've been called with a type that's not in the tower of types. This may mean erroneous data, or it may mean that a new type has been introduced to the system that hasn't been properly incorporated into the tower of types yet.
- If the type is found in the list and it has a supertype but there's no corresponding coercion procedure, then this indicates a programming error. We've added the type to the tower of types, but failed to add all the necessary coercion procedures to support the tower.
- If the type is found in the list but it has no supertype then this indicates that the type is at the top of the tower of types. As noted before we're not told explicitly what to do with the top type. Let's just return the value unchanged as it's raised as high as it can be already.
integer->complex), so will still be possible for procedures to look for "shortcuts" in raising types, skipping intermediate types if an appropriate coercion procedure exists.Okay, given all that, let's implement it:
(define tower-of-types '(integer rational real complex))
(define (raise x)
(define (apply-raise types)
(cond ((null? types)
(error "Type not found in the tower-of-types"
(list x tower-of-types)))
((eq? (type-tag x) (car types))
(if (null? (cdr types))
x
(let ((raiser (get-coercion (type-tag x) (cadr types))))
(if raiser
(raiser (contents x))
(error "No coercion procedure found for types"
(list (type-tag x) (cadr types)))))))
(else (apply-raise (cdr types)))))
(apply-raise tower-of-types))
And, for completion's sake, here's the changes to the types:
(define (install-integer-package) … (define (integer->rational i) (make-rational i 1)) … (put-coercion 'integer 'rational integer->rational) … 'done) (define (install-rational-package) ;; internal procedures … (define (rational->real r) (make-real (/ (numer r) (denom r)))) … ;; interface to rest of the system … (put-coercion 'rational 'real rational->real) … 'done) (define (install-real-package) … (define (real->complex r) (make-complex-from-real-imag r 0)) … (put-coercion 'real 'complex real->complex) … 'done)Note that we don't need to make any changes to the
complex package.Let's see it in action:
> (raise (make-integer 2)) (rational 2 . 1) > (raise (make-rational 3 4)) (real . 3/4) > (raise (make-rational 5 3)) (real . 5/3) > (raise (make-real 3.14159)) (complex rectangular 3.14159 . 0) > (raise (make-real 1.234)) (complex rectangular 1.234 . 0) > (raise (make-real 3/4)) (complex rectangular 3/4 . 0)
Addendum
2013-02-14 - identified as part of exercise 2.93 work!Note that with the removal of support for the
'scheme-number primitive type we no longer need the tagging procedures attach-tag, type-tag and contents to cope with untagged types or with the 'scheme-number tag. As a result we can also revert these procedures to their pre-exercise 2.78 state:
(define (attach-tag type-tag contents)
(cons type-tag contents))
(define (type-tag datum)
(if (pair? datum)
(car datum)
(error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
(if (pair? datum)
(cdr datum)
(error "Bad tagged datum -- CONTENTS" datum)))
in-tower? should be real?
ReplyDelete