CS 37

Clab 13: Multiple representations--Complex numbers

Last clab, we started to talk about complex numbers. Drscheme can deal with complex numbers and we will use drscheme to check our work. What we want to do is ultimately see how a language might provide a number package that can handle multiple represenataions and types of numbers. The techniques we will use can be used for many other situations where we might want flexibility in both how we represent things and what we want to do with them.

Start by putting the following in your definitions window.

(define z45 (make-rectangular 4 4)) (define z30 (make-rectangular (sqrt 3) 1)) (define z60 (make-rectangular 2 (* 2 (sqrt 3)))) (define m45 (magnitude z45)) (define a45 (angle z45)) (define m30 (magnitude z30)) (define a30 (angle z30)) (define m60 (magnitude z60)) (define a60 (angle z60)) You can check at your leisure that
z45 is a complex number whose real and imaginary parts are both 4, whose magnitude is 4 x sqrt(2) and whose angle is pi/4.
z30 is a complex number whose real and imaginary parts are sqrt(3) and 1 , whose magnitude is 2 and whose angle is pi/6.
z60 is a complex number whose real and imaginary parts are 2 and 2 x sqrt(3), whose magnitude is 4 and whose angle is pi/3.
Keep these definitions in a separate drscheme window for testing. Some of Ben's and Alyssa's functions will override the built-in scheme ones.

I'll say a few words about complex numbers. Then we'll work through some of the material on pp. 169-186 fairly rapidly. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-17.html#%_sec_2.4
At home, work more thoroughly with the material. Try things out. Ask any questions you have at the beginning of next clab. Do arithmetic on complex numbers in several of the representations.

Both Ben and Alyssa want to deliver to users a package that can do complex arithmetic so that the user gets the right answers without needing to know how the complex numbers are represented or how the operations are carried out. The user interfaces with the package using:
make-from-real-imag
make-from-mag-ang
add-complex
sub-complex
mul-complex
div-complex
real-part
imag-part
magnitude
angle


Let's start a new drscheme window for Ben's implementation. Here is some code to add and multiply complex numbers given in rectangular form. Also a couple of complex numbers and a definition of pi.

(define (make-from-real-imag x y) (cons x y)) (define (real-part z) (car z)) (define (imag-part z) (cdr z)) (define (add-complex z1 z2) (make-from-real-imag (+ (real-part z1) (real-part z2)) (+ (imag-part z1) (imag-part z2)))) (define (mul-complex2 z1 z2) (make-from-real-imag (- (* (real-part z1) (real-part z2)) (* (imag-part z1) (imag-part z2))) (+ (* (real-part z1) (imag-part z2)) (* (imag-part z1) (real-part z2))))) (define cpx45 (make-from-real-imag 4 4)) (define cpx30 (make-from-real-imag (sqrt 3) 1)) (define cpx60 (make-from-real-imag 2 (* 2 (sqrt 3)))) (define pi (* 2 (asin 1)))

now we'll add more from section 2.4.1

(define (sub-complex z1 z2) (make-from-real-imag (- (real-part z1) (real-part z2)) (- (imag-part z1) (imag-part z2)))) (define (mul-complex z1 z2) (make-from-mag-ang (* (magnitude z1) (magnitude z2)) (+ (angle z1) (angle z2)))) (define (div-complex z1 z2) (make-from-mag-ang (/ (magnitude z1) (magnitude z2)) (- (angle z1) (angle z2)))) add and subtract will work with rectangular form mul and div need polar form so Ben needs conversion functions (define (square x) (* x x)) (define (magnitude z) (sqrt (+ (square (real-part z)) (square (imag-part z))))) (define (angle z) (atan (imag-part z) (real-part z))) (define (make-from-mag-ang r a) (cons (* r (cos a)) (* r (sin a)))) Let's try Bens functions

Don't close Ben's window. But open a new window for Alyssa and put the following in her window.

;; the same implementation independent definitions of ;; add, sub, mult, div (define (add-complex z1 z2) (make-from-real-imag (+ (real-part z1) (real-part z2)) (+ (imag-part z1) (imag-part z2)))) (define (sub-complex z1 z2) (make-from-real-imag (- (real-part z1) (real-part z2)) (- (imag-part z1) (imag-part z2)))) (define (mul-complex z1 z2) (make-from-mag-ang (* (magnitude z1) (magnitude z2)) (+ (angle z1) (angle z2)))) (define (div-complex z1 z2) (make-from-mag-ang (/ (magnitude z1) (magnitude z2)) (- (angle z1) (angle z2)))) ;; add and subtract will work with rectangular form ;; mul and div need polar form so Alyssa also needs conversion ;; functions (define (square x) (* x x)) ;; these functions differ from Ben's functions of same name (define (real-part z) (* (magnitude z) (cos (angle z)))) (define (imag-part z) (* (magnitude z) (sin (angle z)))) (define (magnitude z) (car z)) (define (angle z) (cdr z)) (define (make-from-real-imag x y) (cons (sqrt (+ (square x) (square y))) (atan y x))) (define (make-from-mag-ang r a) (cons r a)) ;; try a couple of Alyssa's functions (define acpx30 (make-from-real-imag 1.7320508075688772 1)) (define acpx45 (make-from-real-imag 4 4)) (define acpx60 (make-from-real-imag 2 3.4641016151377544)) Let's try a couple of Alyssa's functions on numbers in polar form.

Before next clab, try the tagged system on pages 175-179. Use a third drscheme window. Put some numbers in in rectangular form and some in polar form and make sure you get the correct answers using the tagged functions. Also make sure you understand how the tags are being used. You might want to try:

(define tcpx45 (make-from-real-imag 4 4)) (define tcpx60 (make-from-mag-ang 4 1.0471975511965976)) and see if you can get real and imaginary parts, magnitude and angle, and that they multiply and add correctly.
Here is text code from those pages. ;;;SECTION 2.4.2 (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))) (define (rectangular? z) (eq? (type-tag z) 'rectangular)) (define (polar? z) (eq? (type-tag z) 'polar)) ;; Ben (rectangular) got to append -rectangular to not interfere ;; with Allyssa (define (real-part-rectangular z) (car z)) (define (imag-part-rectangular z) (cdr z)) (define (magnitude-rectangular z) (sqrt (+ (square (real-part-rectangular z)) (square (imag-part-rectangular z))))) (define (angle-rectangular z) (atan (imag-part-rectangular z) (real-part-rectangular z))) (define (make-from-real-imag-rectangular x y) (attach-tag 'rectangular (cons x y))) (define (make-from-mag-ang-rectangular r a) (attach-tag 'rectangular (cons (* r (cos a)) (* r (sin a))))) ;; Alyssa (polar) got to append polar to not interfere ;; with Ben (define (real-part-polar z) (* (magnitude-polar z) (cos (angle-polar z)))) (define (imag-part-polar z) (* (magnitude-polar z) (sin (angle-polar z)))) (define (magnitude-polar z) (car z)) (define (angle-polar z) (cdr z)) (define (make-from-real-imag-polar x y) (attach-tag 'polar (cons (sqrt (+ (square x) (square y))) (atan y x)))) (define (make-from-mag-ang-polar r a) (attach-tag 'polar (cons r a))) ;; Generic selectors--what the customer uses ;; oblivious to internal representation because of ;; our abstraction boundary (define (real-part z) (cond ((rectangular? z) (real-part-rectangular (contents z))) ((polar? z) (real-part-polar (contents z))) (else (error "Unknown type -- REAL-PART" z)))) (define (imag-part z) (cond ((rectangular? z) (imag-part-rectangular (contents z))) ((polar? z) (imag-part-polar (contents z))) (else (error "Unknown type -- IMAG-PART" z)))) (define (magnitude z) (cond ((rectangular? z) (magnitude-rectangular (contents z))) ((polar? z) (magnitude-polar (contents z))) (else (error "Unknown type -- MAGNITUDE" z)))) (define (angle z) (cond ((rectangular? z) (angle-rectangular (contents z))) ((polar? z) (angle-polar (contents z))) (else (error "Unknown type -- ANGLE" z)))) ;; same as before (define (add-complex z1 z2) (make-from-real-imag (+ (real-part z1) (real-part z2)) (+ (imag-part z1) (imag-part z2)))) ;; Constructors for complex numbers (define (make-from-real-imag x y) (make-from-real-imag-rectangular x y)) (define (make-from-mag-ang r a) (make-from-mag-ang-polar r a))

Ben and Alyssa's tagged data handling of complex numbers allows for the two representations that they chose, but it does not generalize easily. Adding new representations requires changing code already written and being alert to name conflicts. A table-driven system can get around these problems.

We will build a table of operations (i.e. functions) whose rows are indexed by the operation name and whose columns are indexed by the representation.

For now assume that

(put r c p) will put the object p into a table at row r and column c and that (get r c) will return whatever object is in the table at row r and column c.
get will return #f if there is nothing in the table at row r, column c. I am giving you code that will implement the table and give you put and get. In a week or so, we will look at how it works. For now, just trust the table implementation routines and work on what comes after ;; end table implementation routines.

Open a new drscheme window.

Let's install Ben's and Alyssa's tagged stuff with their original names in a table-driven system.

;;begin table implementation routines (define (assoc key records) (cond ((null? records) #f) ((equal? key (caar records)) (car records)) (else (assoc key (cdr records))))) (define (make-table) (let ((local-table (list '*table*))) (define (lookup key-1 key-2) (let ((subtable (assoc key-1 (cdr local-table)))) (if subtable (let ((record (assoc key-2 (cdr subtable)))) (if record (cdr record) #f)) #f))) (define (insert! key-1 key-2 value) (let ((subtable (assoc key-1 (cdr local-table)))) (if subtable (let ((record (assoc key-2 (cdr subtable)))) (if record (set-cdr! record value) (set-cdr! subtable (cons (cons key-2 value) (cdr subtable))))) (set-cdr! local-table (cons (list key-1 (cons key-2 value)) (cdr local-table))))) 'ok) (define peek (lambda () (display local-table))) (define (dispatch m) (cond ((eq? m 'lookup-proc) lookup) ((eq? m 'insert-proc!) insert!) ((eq? m 'peek) peek) (else (error "Unknown operation -- TABLE" m)))) dispatch)) (define operation-table (make-table)) (define get (operation-table 'lookup-proc)) (define put (operation-table 'insert-proc!)) (define peek (operation-table 'peek)) ;; end table implementation routines ;;;from SECTION 2.4.2 tag stuff (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))) ;; still need square (define (square x) (* x x)) ;;; this begins the table driven stuff (define (install-rectangular-package) ;; internal procedures Since these are internal ;; we do not have to worry about conflicts with names ;; internal to polar-pkg below (define (real-part z) (car z)) (define (imag-part z) (cdr z)) (define (make-from-real-imag x y) (cons x y)) (define (magnitude z) (sqrt (+ (square (real-part z)) (square (imag-part z))))) (define (angle z) (atan (imag-part z) (real-part z))) (define (make-from-mag-ang r a) (cons (* r (cos a)) (* r (sin a)))) ;; interface to the rest of the system (define (tag x) (attach-tag 'rectangular x)) (put 'real-part '(rectangular) real-part) (put 'imag-part '(rectangular) imag-part) (put 'magnitude '(rectangular) magnitude) (put 'angle '(rectangular) angle) (put 'make-from-real-imag 'rectangular (lambda (x y) (tag (make-from-real-imag x y)))) (put 'make-from-mag-ang 'rectangular (lambda (r a) (tag (make-from-mag-ang r a)))) 'done) (define (install-polar-package) ;; internal procedures (define (magnitude z) (car z)) (define (angle z) (cdr z)) (define (make-from-mag-ang r a) (cons r a)) (define (real-part z) (* (magnitude z) (cos (angle z)))) (define (imag-part z) (* (magnitude z) (sin (angle z)))) (define (make-from-real-imag x y) (cons (sqrt (+ (square x) (square y))) (atan y x))) ;; interface to the rest of the system (define (tag x) (attach-tag 'polar x)) (put 'real-part '(polar) real-part) (put 'imag-part '(polar) imag-part) (put 'magnitude '(polar) magnitude) (put 'angle '(polar) angle) (put 'make-from-real-imag 'polar (lambda (x y) (tag (make-from-real-imag x y)))) (put 'make-from-mag-ang 'polar (lambda (r a) (tag (make-from-mag-ang r a)))) 'done) (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)) (error "No method for these types -- APPLY-GENERIC" (list op type-tags)))))) ;; Generic selectors -- This is what we deliver ;; to users. These are abstraction barriers ;; that prevent the users from knowing or ;; depending on our implementation. (define (real-part z) (apply-generic 'real-part z)) (define (imag-part z) (apply-generic 'imag-part z)) (define (magnitude z) (apply-generic 'magnitude z)) (define (angle z) (apply-generic 'angle z)) ;; Constructors for complex numbers -- for users ;; They don't get to see these definitions. ;; They just get to use make-from-real-imag ;; or make-from-mag-ang (define (make-from-real-imag x y) ((get 'make-from-real-imag 'rectangular) x y)) (define (make-from-mag-ang r a) ((get 'make-from-mag-ang 'polar) r a)) ;; got to install em it you want em to work (install-rectangular-package) (install-polar-package) So we try it. >(define new30 (make-from-real-imag 1.7320508075688772 1)) > (define new45 (make-from-mag-ang 5.656854249492381 0.7853981633974483)) > new30 (rectangular 1.7320508075688772 . 1) > new45 (polar 5.656854249492381 . 0.7853981633974483) > (real-part new30) 1.7320508075688772 > (real-part new45) 4.000000000000001 This is looking good so let's do some arithmetic. > (define prod3045 (mul-complex new30 new45)) reference to undefined identifier: mul-complex OOPS. What is the problem? What do we need to do?
Fix this so I can do arithmetic. It should be easy and you should be able to get something like. > (define new30 (make-from-real-imag 1.7320508075688772 1)) > (define new45 (make-from-mag-ang 5.656854249492381 0.7853981633974483)) > (define prod3045 (mul-complex new30 new45)) > prod3045 (polar 11.31370849898476 . 1.3089969389957472) > Save your definitions in a file called tabcpx.scm and fix this at home.