CS 37

Clab 12: More Complexity Analysis, Abstraction Barriers, Complex Numbers,
and Multiple Representations

Copy file bstload.scm from /home/cfk/pub/cs37/week4. This is my solution to the prof. K database problem from Lab4. I'll start by saying a few words about it, especially assoc and the or-hack.
Last clab, we did a time-complexity analysis for tree->list-1. We'll start today with time-complexity analyses for tree->list-2 and partial-tree, the helper function for list->tree. (define tre1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))) (define tre2 '(3 (1 () ()) (7 (5 () ())(9 () (11 () ()))))) (define tre3 '(5 (3 (1 () () ) ()) (9 (7 () ()) (11 () ())))) Here is code from pages 155-159 define (entry tree) (car tree)) (define (left-branch tree) (cadr tree)) (define (right-branch tree) (caddr tree)) (define (make-tree entry left right) (list entry left right)) (define (element-of-set? x set) (cond ((null? set) #f) ((= x (entry set)) #t) ((< x (entry set)) (element-of-set? x (left-branch set))) ((> x (entry set)) (element-of-set? x (right-branch set))))) (define (adjoin-set x set) (cond ((null? set) (make-tree x '() '())) ((= x (entry set)) set) ((< x (entry set)) (make-tree (entry set) (adjoin-set x (left-branch set)) (right-branch set))) ((> x (entry set)) (make-tree (entry set) (left-branch set) (adjoin-set x (right-branch set)))))) ;; EXERCISE 2.63 (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 '())) ;; EXERCISE 2.64 (define (list->tree elements) (car (partial-tree elements (length elements)))) (define (partial-tree elts n) (if (= n 0) (cons '() elts) (let ((left-size (quotient (- n 1) 2))) (let ((left-result (partial-tree elts left-size))) (let ((left-tree (car left-result)) (non-left-elts (cdr left-result)) (right-size (- n (+ left-size 1)))) (let ((this-entry (car non-left-elts)) (right-result (partial-tree (cdr non-left-elts) right-size))) (let ((right-tree (car right-result)) (remaining-elts (cdr right-result))) (cons (make-tree this-entry left-tree right-tree) remaining-elts))))))))

ask any questions you may have.

I'll say a few words about complex numbers. Then we'll work through some of the material on pp. 169-175. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-17.html#%_sec_2.4
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.

ask any questions you may have.


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 both of the representations. 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) (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) (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 (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. As pointed out in the test, it uses both horizontal and vertical abstraction barriers. BUT ...