Learn faster and stay on-track by joining this free class with other self-learners.
Register for Structure and Interpretation of Computer Programs now.
|
Structure and Interpretation of Computer ProgramsClass length: 13 weeks. Start anytime. Creator: kday Status: Established |
Join this class! |
|
Lesson 4: Assignment 1Section 2.1 Exercises:Do all exercises 2.1 through 2.16 in section 2.1. Homework Submissions5 total
;Exercise 2.1
(define (make-rat x y)
(let ((g (gcd x y)))
(let ((numer (abs (/ x g)))
(denom (abs (/ y g))))
(cons (if (< (* x y) 0)
(- numer)
numer)
denom))))
;Exercise 2.2
(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))
(define (make-segment p1 p2) (cons p1 p2))
(define (start-segment s) (car s))
(define (end-segment s) (cdr s))
(define (midpoint-segment s)
(let ((x1 (x-point (start-segment s)))
(y1 (y-point (start-segment s)))
(x2 (x-point (end-segment s)))
(y2 (y-point (end-segment s))))
(make-point (avg x1 x2)
(avg y1 y2))))
;Exercise 2.3
(define (area rect)
(* (width rect)
(height rect)))
(define (perim rect)
(* 2 (+ (width rect)
(height rect))))
;a segment representing the diagonal is used
(define (make-rectangle p1 p2)
(make-segment p1 p2))
(define (width rect)
(abs (- (x-point (start-segment rect))
(x-point (end-segment rect)))))
(define (height rect)
(abs (- (y-point (start-segment rect))
(y-point (end-segment rect)))))
;the upper-left and lower-right points are used here
(define (make-rectangle p1 p2)
(cons p1 p2))
(define (width rect)
(abs (- (x-point (car rect))
(x-point (cdr rect)))))
(define (height rect)
(abs (- (y-point (car rect))
(y-point (cdr rect)))))
(define rect (make-rectangle (make-point 0 2)
(make-point 4 0)))
(area rect)
(perim rect)
;Exercise 2.4
(define (cdr z)
(z (lambda (p q) q)))
(cdr (cons 2 3))
(cdr (lambda (m) (m 2 3)))
(cdr (lambda (2 3) 3))
(3) ;it returned the second element
;Exercise 2.5
(define (divide n by cnt)
(if (= (remainder n by) 0)
(divide (/ n by)
by
(+ cnt 1))
cnt))
(define (cons a b)
(* (exp-fast 2 a)
(exp-fast 3 b)))
(define (car n)
(divide n 2 0))
(define (cdr n)
(divide n 3 0))
;Exercise 2.7
(define (make-interval a b) (cons a b))
(define (lower-bound iv) (car iv))
(define (upper-bound iv) (cdr iv))
;Exercise 2.8
(define (sub-interval x y)
(make-interval (- (lower-bound x) (upper-bound y))
(- (upper-bound x) (lower-bound y))))
;Exercise 2.9
(define (width-interval x)
(/ (- (upper-bound x) (lower-bound x)) 2.0))
(define iv1 (make-interval 2 3))
(define iv2 (make-interval 5 8))
(width-interval iv1)
(width-interval iv2)
(width-interval (add-interval iv1 iv2)) ;sum of widths iv1 and iv2
(width-interval (sub-interval iv1 iv2)) ;sum of widths iv1 and iv2
(width-interval (mul-interval iv1 iv2)) ;not a function
(width-interval (div-interval iv1 iv2)) ;not a function
;Exercise 2.10
(define (div-interval x y)
(if (and (>= (upper-bound y) 0) (<= (lower-bound y) 0))
(error "Cannot divide by an interval that spans zero")
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))
;Exercise 2.11
(define (mul-interval x y)
(define x-sign (cond ((and (< (lower-bound x) 0) (< (upper-bound x) 0)) (- 1))
((and (< (lower-bound x) 0) (> (upper-bound x) 0)) 0)
((and (> (lower-bound x) 0) (> (upper-bound x) 0)) 1)))
(define y-sign (cond ((and (< (lower-bound y) 0) (< (upper-bound y) 0)) (- 1))
((and (< (lower-bound y) 0) (> (upper-bound y) 0)) 0)
((and (> (lower-bound y) 0) (> (upper-bound y) 0)) 1)))
(cond ((< x-sign 0)
(cond ((< y-sign 0) (make-interval (* (upper-bound x) (upper-bound y))
(* (lower-bound x) (lower-bound y))))
((= y-sign 0) (make-interval (* (lower-bound x) (upper-bound y))
(* (lower-bound x) (lower-bound y))))
(else (make-interval (* (lower-bound x) (upper-bound y))
(* (upper-bound x) (lower-bound y))))))
((= x-sign 0)
(cond ((< y-sign 0) (make-interval (* (upper-bound x) (lower-bound y))
(* (lower-bound x) (lower-bound y))))
((= y-sign 0) (make-interval ((min (* (upper-bound x) (lower-bound y))
(* (lower-bound x) (upper-bound y)))
(max (* (upper-bound x) (upper-bound y))
(* (lower-bound x) (lower-bound y))))))
(else (make-interval (* (lower-bound x) (upper-bound y))
(* (upper-bound x) (upper-bound y))))))
(else
(cond ((< y-sign 0) (make-interval (* (upper-bound x) (lower-bound y))
(* (lower-bound x) (upper-bound y))))
((= y-sign 0) (make-interval (* (upper-bound x) (lower-bound y))
(* (upper-bound x) (upper-bound y))))
(else (make-interval (* (lower-bound x) (lower-bound y))
(* (upper-bound x) (upper-bound y))))))))
;Exercise 2.12
(define (make-center-percent c p)
(define width (* (/ p 100.0) c))
(make-interval (- c width)
(+ c width)))
(define (center i)
(/ (+ (upper-bound i) (lower-bound i)) 2.0))
(define (percent i)
(* (/ (lower-bound i) (center i)) 100))
I didn't even attempt 2.13 2.15 or 2.16. Part lack of time, part lack of enthusiasm :( #lang planet neil/sicp
;; Supporting procedures
(define (average a b) (/ (+ a b) 2))
(define (square x) (* x x))
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
(define (numer rat) (car rat))
(define (denom rat) (cdr rat))
(define (print-rat x)
(newline)
(display (numer x))
(display "/")
(display (denom x)))
(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (sub-rat x y)
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (mul-rat x y)
(make-rat (* (numer x) (numer y))
(* (denom x) (denom y))))
(define (div-rat x y)
(make-rat (* (numer x) (denom y))
(* (denom x) (numer y))))
(define (equal-rat? x y)
(= (* (numer x) (denom y))
(* (numer y) (denom x))))
;;; Ex 2.1
;;;
(define (bh-make-rat n d)
(let ((g (abs (gcd n d)))
(signed-n (if (negative? d) (- n) n))
(signed-d (abs d)))
(cons (/ signed-n g) (/ signed-d g))))
;;; Ex 2.2
;;;
(define (make-segment start-segment end-segment)
(cons start-segment end-segment))
(define (start-segment segment)
(car segment))
(define (end-segment segment)
(cdr segment))
(define (segment-length segment)
(let ((a (start-segment segment))
(b (end-segment segment)))
(sqrt (+ (square (- (x-point b)
(x-point a)))
(square (- (y-point b)
(y-point a)))))))
(define (make-point x y)
(cons x y))
(define (x-point point)
(car point))
(define (y-point point)
(cdr point))
(define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
(define (midpoint-segment segment)
(make-point (average (x-point (start-segment segment))
(x-point (end-segment segment)))
(average (y-point (start-segment segment))
(y-point (end-segment segment)))))
;;; Ex 2.3
;;;
;; utilities
(define (perimiter rectangle)
(* 2 (+ (rect-width rectangle)
(rect-height rectangle))))
(define (area rectangle)
(* (rect-width rectangle)
(rect-height rectangle)))
;; representation 1
;;
;; .------------------------.
;; | |
;; |<--left-segment |
;; | |
;; .------------------------.
;; ^
;; |
;; |
;; bottom-segment
;;
(define (make-rectangle left-segment bottom-segment)
(cons left-segment bottom-segment))
;; selectors
(define (left-segment rectangle)
(car rectangle))
(define (bottom-segment rectangle)
(cdr rectangle))
;; utilities
(define (rect-width rectangle)
(segment-length (bottom-segment rectangle)))
(define (rect-height rectangle)
(segment-length (left-segment rectangle)))
;
;;
;;(b).------------------------------.(top-right)
;; | |
;; | |
;; | |
;; | |
;; | |
;; .------------------------------.(d)
;; (bottom-left)
; hmmm the SICP language doesn't allow redefinition of existing procedures
; so these all have a unique suffix
(define (make-rectangle-2 bottom-left top-right)
(cons bottom-left top-right))
;; selectors
(define (bottom-left-2 rectangle)
(car rectangle))
(define (top-right-2 rectangle)
(cdr rectangle))
; not necessary but they make the utilities easier to read
(define (top-left-2 rectangle)
(make-point (x-point (bottom-left-2 rectangle))
(y-point (top-right-2 rectangle))))
(define (bottom-right-2 rectangle)
(make-point (x-point (top-right-2 rectangle))
(y-point (bottom-left-2 rectangle))))
;; utilities
(define (rect-width-2 rectangle)
(segment-length (make-segment (bottom-left-2 rectangle)
(bottom-right-2 rectangle))))
(define (rect-height-2 rectangle)
(segment-length (make-segment (bottom-left-2 rectangle)
(top-left-2 rectangle))))
; Ex 2.4
;
; again - can't redefine existing procedures
;
(define (cons-2 x y)
(lambda (m) (m x y)))
(define (car-2 z)
(z (lambda (p q) p)))
(define (cdr-2 z)
(z (lambda (p q) q)))
;(car-2 (cons-2 x y))
;-> ((cons x y) (lambda (p q) p))
;-> ((lambda (m) (m x y)) (lambda (p q) p))
;-> ((lambda (p q) p) x y)
;-> x
;; Ex 2.5
;;
(define (cons-int x y)
(* (expt 2 x)
(expt 3 y)))
(define (log-reduce n base)
(cond ((not (zero? (remainder n base))) 0)
(else (+ (log-reduce (/ n base) base) 1))))
(define (car-int z)
(log-reduce z 2))
(define (cdr-int z)
(log-reduce z 3))
;; Ex 2.5
;;
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
;-> (add-1 zero)
;(lambda (f) (lambda (x) (f ((zero f) x))))
;(lambda (f) (lambda (x) (f (((lambda (g) (lambda (y) y)) f) x))))
;(lambda (f) (lambda (x) (f ((lambda (y) y) x))))
;(lambda (f) (lambda (x) (f x)))
(define one (lambda (f) (lambda (x) (f x))))
;(add-1 one)
;(lambda (f) (lambda (x) (f ((one f) x))))
;(lambda (f) (lambda (x) (f (((lambda (g) (lambda (y) (g y))) f) x))))
;(lambda (f) (lambda (x) (f ((lambda (y) (f y)) x))))
;(lambda (f) (lambda (x) (f (f x))))
;(define two (lambda (x) (f (f x))))
; no idea how to do this so I looked up a solution on the internet
; and I still donlt understand it
;(define (add a b)
; (lambda (f)
; (lambda (x)
; ((a f) ((b f) x)))))
;; Ex 2.7
;;
(define (make-interval a b) (cons a b))
(define (lower-bound i) (car i))
(define (upper-bound i) (cdr i))
(define (add-interval x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (div-interval x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
;; Ex 2.8
;;
; X = (lX uX)
; Y = (lY uY)
; lZ = lX - uY => the min point possible subtracting Y's range from X
; uZ = uX - lY => the max point possible subtracting Y's range from X
(define (sub-interval x y)
(make-interval (- (lower-bound x) (upper-bound y))
(- (upper-bound x) (lower-bound y))))
;; Ex 2.9
;;
(define (width-interval x)
(/ ( - (upper-bound x) (lower-bound x))
2))
(define ia (make-interval 20 22))
(define ib (make-interval 37 43))
(define wa (width-interval ia)) ; => 1
(define wb (width-interval ib)) ; => 3
(define wa+b (width-interval (add-interval ia ib))) ; => 4 : wa + wb = wa+b
(define wa-b (width-interval (sub-interval ia ib))) ; => 4 : wa + wb = wa+b
(define wa*b (width-interval (mul-interval ia ib))) ; => 103
(define wa/b (width-interval (div-interval ia ib))) ; => 0.0647391577624136
;; Ex 2.10
;;
(define (spans-zero? interval)
(and (>= (upper-bound interval) 0)
(<= (lower-bound interval) 0)))
(define (bh-div-interval x y)
(if (spans-zero? y)
(error "div-interval cannot divide by an interval that spans 0")
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))
;; Ex 2.11
;;
(define (mul-interval-signs x y)
(define (-ve-interval? x) (< (upper-bound x) 0))
(define (+ve-interval? x) (> (lower-bound x) 0))
(let ((lx (lower-bound x))
(ux (upper-bound x))
(ly (lower-bound y))
(uy (upper-bound y)))
(cond ((and (-ve-interval? x)
(-ve-interval? y)) (make-interval (* ux uy) (* lx ly)))
((and (+ve-interval? x)
(+ve-interval? y)) (make-interval (* lx ly) (* ux uy)))
((and (-ve-interval? x)
(+ve-interval? y)) (make-interval (* lx uy) (* ux ly)))
((and (+ve-interval? x)
(-ve-interval? y)) (make-interval (* ux ly) (* lx uy)))
((and (+ve-interval? x)
(spans-zero? y)) (make-interval (* ux ly) (* ux uy)))
((and (-ve-interval? x)
(spans-zero? y)) (make-interval (* lx uy) (* lx ly)))
((and (spans-zero? x)
(+ve-interval? y)) (make-interval (* lx uy) (* ux uy)))
((and (spans-zero? x)
(-ve-interval? y)) (make-interval (* ux ly) (* lx ly)))
(else (make-interval (* (min lx ly) (max ux uy))
(max (* ux uy) (* lx ly)))))))
;; Ex 2.12
;;
(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))
(define (make-center-percent c tolerance)
(make-center-width c (* c (/ tolerance 100))))
(define (percent interval)
(/ (* 100 (width interval))
(center interval)))
;; Ex 2.14
;;
(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 ina (make-center-percent 10 1))
;(define inb (make-center-percent 20 2))
;(define inc (make-center-percent 20 0))
;
;(par1 ina inb)
; => (6.361967213114754 . 6.9844067796610165)
;(par2 ina inb)
; => (6.5776271186440685 . 6.7554098360655725)
;(center (div-interval ina ina))
; => 1.0002000200020003
;(percent (div-interval ina ina))
; => 1.9998000199979906
No comments. Sign up or log in to comment 
;; Exercise 2.3 The two representations for a rectangle are as two segments, or as four points. The perimeter and area procedures will work with either representation because I have selectors, rect-length-side1 and rect-length-side2, that hide the details of how the rectangles are represented. ;; Exercise 2.5 3 is not divisible by 2. The square of 3 isn't divisible by 2, if it was, then there would be some factor of the square of 3 that was divisible by 2. However the square of 3 is uniquely factorized as 33, and neither factor is divisible by 2. The cube of three is uniquely factorized as 3(33), and neither 3 nor (33) is divisible by 2. We can continue the argument for any nth-power of 3. ;; Exercise 2.9 let the upper bound of interval 1 be U1 and the lower bound of interval 1 be L1 For summing two intervals: interval = L1 + L2, U1 + U2 width = ((U1 + U2) - (L1 + L2))/2 = ((U1 - L1)/2 + (U2 - L2)/2 = sum of the widths of the intervals For subtracting two intervals interval = L1 - U2, U1 - L2 width = ((U1- L2) - (L1 - U2))/2 = ((U1 - L1)/2 + (U2 - L2)/2 = sum of the widths of the intervals For multiplication Let interval 1 = 3 +/- 1 and width = 1 interval 2 = 5 +/- 2 and width = 2 (mul-interval (make-interval 2 4) (make-interval 3 7)) ; Value (6,28) has width (28-6)/2 = 11 which is greater than the sum of 1 and 2 (div-interval (make-interval 2 4) (make-interval 3 7)) ; Value (0.2857, 1.3333) has width -.5238 which is less than than the sum of 1 and 2 ;; Exercise 2.13 let a = [Ca(1 - Ta), Ca(1 + Ta)] let b = [Cb(1 - Tb), Cb(1 + Tb)] ab = CaCb[(1 - Ta)(1 - Tb), (1 + Ta)(1 + Tb)] which is approximately CaCb[(1 - Ta - Tb), (1 + Ta + Tb)] The tolerance of the product is approximately the sum of the factors. Every time an interval is multiplied (or divided) the percentage tolerance of that interval is summed into the total interval. For our example, in par1 we have multiplied two intervals (r1 * r2) which totals (5% + 5%), and then divide by another interval (r1 + r2) which adds another 5%. Giving a total tolerance of 15%! The upper limit on our calculation (r1 r2)/(r1 + r2), is 3 times the tolerance of the factors. The case of addition and subtraction is better, where the width of the interval isn't the sum of the percentage tolerance of each of the intervals, but rather only the sum of the widths of the intervals. ;; Exercise 2.15 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. Why? We are trying to get some upper (and lower) limit to the error of our combined approximate quantities, but every time we combine another interval we need to re-evaluate the goodness of the total interval, and this will always increase. That is, each uncertain value used in an interval computation increases the uncertainty of the answer. If we can design our calculations so that no variable that represents an uncertain number is repeated, then the measure of the error in our answer, the width of the interval, will be be less. ;; Exercise 2.1
;; This forces the denominator to be positive by making g
;; (which is (gcd n d)) the same sign as d
(define (make-rat n d)
(let ((g (if (< d 0) - +) (gcd n d)))
(cons (/ n g) (/ d g))))
(print-rat (make-rat 2 -6))
;; Exercise 2.2
(define (make-segment p1 p2)
(cons p1 p2))
(define (start-segment s)
(car s))
(define (end-segment s)
(cdr s))
(define (make-point x y)
(cons x y))
(define (x-point p)
(car p))
(define (y-point p)
(cdr p))
(define (average x y)
(/ (+ x y) 2))
(define (midpoint-segment s)
(make-point (average (x-point (start-segment s))
(x-point (end-segment s)))
(average (y-point (start-segment s))
(y-point (end-segment s)))))
(define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
;; Exercise 2.3
(define epsilon 0.00001)
(define (make-point x y)
(cons x y))
(define (x-point p)
(car p))
(define (y-point p)
(cdr p))
(define (equal-points? p1 p2)
(and (> epsilon (abs (- (x-point p1) (x-point p2))))
(> epsilon (abs (- (y-point p1) (y-point p2))))))
;; p1 is less than p2 if p1 is to the left
;; or if the x points are equal then below
(define (lessthan-points? p1 p2)
(if (> epsilon (abs (- (x-point p1) (x-point p2))))
(< (y-point p1) (y-point p2))
(< (x-point p1) (x-point p2))))
(define (square x) (* x x))
(define (length-points p1 p2)
(sqrt (+ (square (- (x-point p1) (x-point p2)))
(square (- (y-point p1) (y-point p2))))))
(define (make-segment p1 p2)
(if (equal-points? p1 p2)
(error "make-segment: p1 and p2 are identical")
(cons p1 p2)))
(define (start-segment s)
(car s))
(define (end-segment s)
(cdr s))
(define (equal-segments? s1 s2)
(and (equal-points? (start-segment s1)
(start-segment s2))
(equal-points? (end-segment s1)
(end-segment s2))))
;; have all segments pointing left to right
(define (normalize-segment s)
(if (lessthan-points? (start-segment s) (end-segment s))
s
(make-segment (end-segment s) (start-segment s))))
(define (common-endpt? s1 s2)
(or (equal-points? (start-segment s1) (start-segment s2))
(equal-points? (start-segment s1) (end-segment s2))
(equal-points? (end-segment s1) (start-segment s2))
(equal-points? (end-segment s1) (end-segment s2))))
(define (x-length s)
(- (x-point (end-segment s)) (x-point (start-segment s))))
(define (y-length s)
(- (y-point (end-segment s)) (y-point (start-segment s))))
(define (length-segment s)
(length-points (start-segment s) (end-segment s)))
;; let m1 and m2 be the slopes of two lines. Lines are perpendicular
;; if (m1)(m2) = -1.
(define (perp? s1 s2)
(cond ((> epsilon (abs (x-length s1))) (> epsilon (abs (y-length s2))))
((> epsilon (abs (x-length s2))) (> epsilon (abs (y-length s1))))
(else (> epsilon (abs (+ 1 (* (/ (y-length s1) (x-length s1))
(/ (y-length s2) (x-length s2)))))))))
;; let m1 and m2 be the slopes of two lines. Lines are parallel
;; if (m1) = (m2) (Also checks for divide by zero)
(define (parallel? s1 s2)
(cond ((> epsilon (abs (x-length s1))) (> epsilon (abs (x-length s2))))
((> epsilon (abs (x-length s2))) (> epsilon (abs (x-length s1))))
(else (> epsilon (abs (- (/ (y-length s1) (x-length s1))
(/ (y-length s2) (x-length s2))))))))
;; Given two line segments. They describe a rectangle, if the segments
;; are parallel and the same size, and a line drawn from the start point of
;; of one segment to the start point of the other line segment is
;; perpendicular to the given segments. Or, if the segments are
;; perpendicular to each other and they have a common endpoint.
(define (rectangle? s1 s2)
(let ((sg1 (normalize-segment s1))
(sg2 (normalize-segment s2)))
(and (not (equal-segments? s1 s2))
(or (and (parallel? sg1 sg2)
(= (length-segment sg1) (length-segment sg2))
(perp? sg1 (make-segment (start-segment sg1)
(start-segment sg2))))
(and (perp? sg1 sg2) (common-endpt? sg1 sg2))))))
;; make a rectangle from two line segments --
;; store as two perpendicular segments.
(define (make-rect-2segs s1 s2)
(if (rectangle? s1 s2)
(let ((sg1 (normalize-segment s1))
(sg2 (normalize-segment s2)))
(if (perp? sg1 sg2)
(cons sg1 sg2)
(cons sg1
(make-segment (start-segment sg1)
(start-segment sg2)))))
(error "make-rect-2segs: Not a rectangle")))
(define (rect-seg1 r)
(car r))
(define (rect-seg2 r)
(cdr r))
(define (rect-2segs-length-side1 r)
(length-segment (rect-seg1 r)))
(define (rect-2segs-length-side2 r)
(length-segment (rect-seg2 r)))
(define (rect-area r)
(* (rect-length-side1 r) (rect-length-side2 r)))
(define (rect-perim r)
(* 2 (+ (rect-length-side1 r) (rect-length-side2 r))))
;; make a rectangle from four points
(define (make-rect-4pts p1 p2 p3 p4)
(if (rectangle? (make-segment p1 p2)
(make-segment p3 p4))
(cons (cons (cons p1 p2) p3) p4)
(error "make-rect-4pts: Not a rectangle")))
(define (rect-p1 r)
(caaar r))
(define (rect-p2 r)
(cdaar r))
(define (rect-p3 r)
(cdar r))
(define (rect-p4 r)
(cdr r))
(define (rect-4pts-length-side1 r)
(length-points (rect-p1 r) (rect-p2 r)))
(define (rect-4pts-length-side2 r)
(length-points (rect-p2 r) (rect-p3 r)))
;; Not a rectangle
(define p1 (make-point 0 0))
(define p2 (make-point 12 5))
(define p3 (make-point 9 9))
(define p4 (make-point 1 3))
(define s1 (make-segment p1 p2))
(define s2 (make-segment p3 p4))
(rectangle? s1 s2) ; #f
;; Rectangle of sides 13 and 5 using 2 segs representation
(define p1 (make-point 0 0))
(define p2 (make-point 12 5))
(define p3 (make-point (- 12 25/13) (+ 5 60/13)))
(define p4 (make-point -25/13 60/13))
(define s1 (make-segment p1 p2))
(define s2 (make-segment p3 p4))
(define r-2segs (make-rect-2segs s1 s2))
(define rect-length-side1 rect-2segs-length-side1)
(define rect-length-side2 rect-2segs-length-side2)
(rect-area r-2segs)
(rect-perim r-2segs)
;; Rectangle of sides 4 and 3 using 4 pts representation
(define p5 (make-point 0 0))
(define p6 (make-point 4 0))
(define p7 (make-point 4 3))
(define p8 (make-point 0 3))
(define r-4pts (make-rect-4pts p5 p6 p7 p8))
(define rect-length-side1 rect-4pts-length-side1)
(define rect-length-side2 rect-4pts-length-side2)
(rect-area r-4pts)
(rect-perim r-4pts)
;; Exercise 2.4
(define z (lambda(m) (m x y)))
(define (car z) (z (lambda (p q) p)))
;; substituting for z in (car z)
(car z)
(lambda (lambda (p q) p))
((lambda (p q) p) x y)
x
;; the corresponding definition of cdr
(define (cdr z)
(z (lambda (p q) q)))
;; Exercise 2.5
(define (cons x y)
(* (expt 2 x) (expt 3 y)))
(define (car z)
(factorize z 2))
(define (cdr z)
(factorize z 3))
(define (factorize z base)
; n natural number and i counter
(define (iter n i)
(if (zero? (remainder n base))
(iter (/ n base) (+ 1 i))
i))
(iter z 0))
(define z (cons 3 5))
(car z) ; Value 3
(cdr z) ; Value 5
;; Exercise 2.6
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
;; define one directly using substitution
(define one (add-1 zero))
(add-1 (lambda (f) (lambda (x) x)))
(lambda (f) (lambda (x) (f (((lambda(f) (lambda (x) x)) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) x) x)))))
(lambda (f) (lambda (x) (f x)))
(define one (lambda (f) (lambda (x) (f x))))
;; define two directly using substitution
(define two (add-1 one))
(add-l (lambda (f) (lambda (x) (f x) x)))
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) (f x))) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))
(lambda (f) (lambda (x) (f (f x)))
(define two (lambda (f) (lambda (x) (f (f x)))))
;; add-1 is a factor in the composite function, which is defined to
;; apply f to the smaller composite function f^b(x).
;;
;; (((add-1 b) f) x) maps to f{f^b(x)}
;;
;; Looking at the definition of add-1:
;;
;; (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
;;
;; If we can replace the outermost factor 'f' by (a f), for some a,
;; then this will apply f 'a' times to f^b(x).
;;
(define (+ a b) (lambda (f) (lambda (x) ((a f) ((b f) x)))))
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
(define (inc n) (+ 1 n))
((zero inc) 0) ; Value 0
(((add-1 zero) inc) 0) ; Value 1
((one inc) 0) ; Value 1
(((add-1 (add-1 zero)) inc) 0) ; Value 2
((two inc) 0) ; Value 2
(define (+ a b) (lambda (f) (lambda (x) ((a f) ((b f) x)))))
(((+ one two) inc) 0) ; Value 3
;; Exercise 2.7
(define (add-interval x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (div-interval x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
(define (make-interval a b) (cons a b))
(define (lower-bound c) (car c))
(define (upper-bound c) (cdr c))
;; Exercise 2.8
(define (sub-interval x y)
(add-interval x
(make-inter (- 0 (upper-bound y))
(- 0 (lower-bound y)))))
;; Exercise 2.10
(define (div-interval x y)
(if (zero? (* (upper-bound y) (lower-bound y)))
(error "div-interval: the divisor is zero")
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))
;; case xL xU yL yU min max
;; 1 + + + + xL*yL xU*yU
;; 2 + + + - n/a n/a
;; 3 + + - + xU*yL xU*yU
;; 4 + + - - xU*yL xL*yU
;; 5 + - + + n/a n/a
;; 6 + - + - n/a n/a
;; 7 + - - + n/a n/a
;; 8 + - - - n/a n/a
;; 9 - + + + xL*yU xU*yU
;; 10 - + + - n/a n/a
;; 11 - + - + min(xU*yL,xL*yU) max(xU*yU,xL*yL)
;; 12 - + - - xU*yL xL*yL
;; 13 - - + + xL*yU xU*yL
;; 14 - - + - n/a n/a
;; 15 - - - + xL*yU xL*yL
;; 16 - - - - xU*yU xL*yL
;;
;; (3,9), (4,13), (12,15) we can transpose the arguments
(define (mul-interval x y)
(define (positive-interval? i) (and (positive? (lower-bound i))
(positive? (upper-bound i))))
(define (negative-interval? i) (and (negative? (lower-bound i))
(negative? (upper-bound i))))
(let ((xp (positive-interval? x)) (xn (negative-interval? x))
(yp (positive-interval? y)) (yn (negative-interval? y))
(xu (upper-bound x)) (xl (lower-bound x))
(yu (upper-bound y)) (yl (lower-bound y)))
(cond ((and xp yp) (make-interval (* xl yl) (* xu yu))) ; 1
((and xp yn) (make-interval (* xu yl) (* xl yu))) ; 4
((and xn yp) (mul-interval y x)) ; 13 transpose case 4
((and xn yn) (make-interval (* xu yu) (* xl yl))) ; 16
(xp (make-interval (* xu yl) (* xu yu))) ; 3
(yp (mul-interval y x)) ; 9 transpose case 3
(xn (make-interval (* xl yu) (* xl yl))) ; 15
(yn (mul-interval y x)) ; 12 transpose case 15
(else (make-interval (min (* xl yu) (* xu yl))
(max (* xu yu) (* xl yl))))))) ; 11
(define a (make-interval 1 5))
(define b (make-interval -2 7))
(define c (make-interval -11 -3))
(mul-interval a a) ; Value (1 . 25) ; 1
(mul-interval a c) ; Value (-55 . -3) ; 4
(mul-interval c a) ; Value (-55 . -3) ; 13
(mul-interval c c) ; Value (9 . 121) ; 16
(mul-interval a b) ; Value (-10 . 35) ; 3
(mul-interval b a) ; Value (-10 . 35) ; 9
(mul-interval c b) ; Value (-77 . 22) ; 15
(mul-interval b c) ; Value (-77 . 22) ; 12
(mul-interval b b) ; Value (-14 . 49) ; 11
;; Exercise 2.12
(define (make-center-percent c p)
(let ((t (/ p 100)))
(make-center-width c (* c t))))
(define (percent i)
(let ((c (center i))
(w (width i)))
(* 100 (/ w c))))
No comments. Sign up or log in to comment 
;; Exercise 2.1
(define (make-rat n d)
(let ((g (gcd n d)))
(cond ((and (< n 0) (< d 0)) (cons (/ (abs n) g) (/ (abs d) g)))
((< d 0) (cons (/ (- 0 n) g) (/ (abs d) g)))
(else (cons (/ n g) (/ d g))))))
;; Exercise 2.2
(define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
(define (x-point p) (car p))
(define (y-point p) (cdr p))
(define (make-point x y) (cons x y))
(define (make-segment start end) (cons start end))
(define (start-segment points) (car points))
(define (end-segment points) (cdr points))
(define (midpoint-segment line-segment)
(let ((start (start-segment line-segment))
(end (end-segment line-segment)))
(let ((start-x (x-point start))
(start-y (y-point start))
(end-x (x-point end))
(end-y (y-point end)))
(make-point (/ (+ start-x end-x) 2) (/ (+ start-y end-y) 2)))))
;; Exercise 2.4
(define (cdr z)
(z (lambda (p q) q)))
;; Exercise 2.6
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
(define (+ a b)
(lambda (f) (lambda (x) ((a f) (b f) x))))
;; Exercise 2.7
(define (make-interval a b) (cons a b))
(define (upper-bound interval)(car interval))
(define (lower-bound interval)(cdr interval))
;; Exercise 2.8
(define (sub-interval x y)
(make-interval (- (lower-bound x) (upper-bound y))
(- (upper-bound x) (lower-bound y))))
No comments. Sign up or log in to comment 
I'm not sure about 2.14 and 2.15 ; 2.13 ? ; 2.15 The percision is affected by the number of multiplications and divisions there are, so limiting these will give the least amount of error. So par1 would be best. ; 2.16 Hmm, maybe avoid multiplications/divisions until we can simplify or standardize the equation? There will still be rounding errors, but they could be consitant. I'm not sure how fesible this is. I imagine standardizing all equations would be difficult. ;2.1
(define (make-rat n d)
(let ((g (gcd n d)))
(if (> 0 (* n d))
(cons (/ (* -1 (abs n)) g) (/ (abs d) g))
(cons (/ (abs n) g) (/ (abs d) g)))))
;2.2
(define (make-rat n d)
(let ((g (gcd n d)))
(if (> 0 (* n d))
(cons (/ (* -1 (abs n)) g) (/ (abs d) g))
(cons (/ (abs n) g) (/ (abs d) g)))))
(define (numer x) (car x))
(define (denom x) (cdr x))
;Point
(define (make-point x-point y-point)
(cons x-point y-point))
(define (x-point point) (car point))
(define (y-point point) (cdr point))
(define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
;Line
(define (make-line start-point end-point)
(cons start-point end-point))
(define (start-point line) (car line))
(define (end-point line) (cdr line))
; midpoint
(define (midpoint line)
(define (avg x y) (/ (+ x y) 2.0))
(make-point (avg (x-point (start-point line)) (x-point (end-point line)))
(avg (y-point (start-point line)) (y-point (end-point line)))))
(print-point (midpoint (make-line (make-point 0 0) (make-point 0 6))))
(print-point (midpoint (make-line (make-point 5 89) (make-point 7 83))))
; Output
; (0,3.0)
; (6.0,86.0)
;2.3
; RectangleA
(define (make-rectA height length)
(cons height length))
(define (height rectA) (car rectA))
(define (length2 rectA) (cdr rectA))
(define (perimeter rectA)
(+ (* 2 (height rectA))
(* 2 (length2 rectA))))
(define (area2 rectA)
(* (height rectA)
(length2 rectA)))
(define rectA (make-rectA 5 5))
(perimeter rectA)
(area2 rectA)
; RectangleB
; define length for line
(define (line-length line)
(sqrt (+
(square (abs (-
(x-point (start-point line))
(x-point (end-point line)))))
(square (abs (-
(y-point (start-point line))
(y-point (end-point line))))))))
(define (make-rectB lineHeight lineWidth)
(cons lineHeight lineWidth))
(define (heightB rectB) (line-length (car rectB)))
(define (widthB rectB) (line-length (cdr rectB)))
(define (perimeterB rectB)
(+ (* 2 (heightB rectB))
(* 2 (widthB rectB))))
(define (areaB rectB)
(* (heightB rectB)
(widthB rectB)))
(define rectB (make-rectB
(make-line (make-point 0 0) (make-point 0 5))
(make-line (make-point 0 5) (make-point 5 5))))
(perimeterB rectB)
(areaB rectB)
;2.4
(define (cdr2 z)
(z (lambda (p q) q)))
;2.5
(define (multiple-of-3 n) (= (remainder n 3) 0))
(define (cons a b) (* (expt 2 a) (expt 3 b)))
; Divide by two until we can't
(define (car x)
(define (iter x count)
(if (not (even? x))
count
(iter (/ x 2) (+ count 1))))
(iter x 0))
; Divide by 3 until we can't
(define (cdr x)
(define (iter x count)
(if (not (multiple-of-3 x))
count
(iter (/ x 3) (+ count 1))))
(iter x 0))
;2.6
(define (one) (lambda (x) (f (((lamda (f) (lambda (x) x)) f) x))))
(define (two) (lambda (f) lambda (x) (f (((lambda (x) (f (((lamda (f) (lambda (x) x)) f) x))) f) x ))))
;2.7
(define (make-interval a b) (cons a b))
(define (lower-bound interval)
(if (< (car interval) (cdr interval))
(car interval)
(cdr interval)))
(define (upper-bound interval)
(if (< (car interval) (cdr interval))
(cdr interval)
(car interval)))
;2.8
(define (sub-interval x y)
(let ((p1 (- (lower-bound x) (lower-bound y)))
(p2 (- (lower-bound x) (upper-bound y)))
(p3 (- (upper-bound x) (lower-bound y)))
(p4 (- (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4) (max p1 p2 p3 p4))))
;2.9
interval 1= a to b
width 1 = (b-a)/2
interval 2 = c to d
width 2 - (d-c)/2
int1 + int2
(a + c) to (b + d)
the width would be
((b +d) - (a + c))/2
(b/2 + d/2 - a/2 + c/2)
(b-a)/2 + (d-c)/2
width1 + width2
int1 = -1 to 1 width 1
int2 = 1 to 2 width .5
int1*int2
-2 to 2
width 2
and
int1 = 1 to 2 width .5
int2 = 1 to 2 width .5
int1*int2 = 1 to 4
width=2 again, despite starting with diffrent widths.
;2.10
(define (interval-span-0? interval)
(and (> 0 (lower-bound interval)) (< 0 (upper-bound interval))))
(define (div-interval x y)
(if (or (interval-span-0? x) (interval-span-0? y))
(display "Can not divide when a inverval spans 0")
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))
;2.11
a b c d
+ + + + (ac) (bd)
+ + - + (bc) (bd)
+ + - - (bc) (ad)
- + + + (ad) (bd)
- + - + (bc) (bd) or (bc) (ac)
- + - - (bc) (ac)
- - + + (ad) (bc)
- - - + (bd) (ac)
- - - - (bd) (ac)
;2.11
(define (lower-neg x)
(> 0 (lower-bound x)))
(define (lower-pos x)
(< 0 (lower-bound x)))
(define (upper-neg x)
(> 0 (upper-bound x)))
(define (upper-pos x)
(< 0 (upper-bound x)))
(define (mul-interval2 x y)
(cond
; + + + + ac bd
((and (lower-pos x) (upper-pos x) (lower-pos y) (upper-pos y)
(make-interval (* (lower-bound x) (lower-bound y))
(* (upper-bound x) (upper-bound y)))))
; + + - + bc bd
((and (lower-pos x) (upper-pos x) (lower-neg y) (upper-pos y)
(make-interval (* (upper-bound x) (lower-bound y))
(* (upper-bound x) (upper-bound y)))))
; + + - - bc ad
((and (lower-pos x) (upper-pos x) (lower-neg y) (upper-neg y)
(make-interval (* (upper-bound x) (lower-bound y))
(* (lower-bound x) (upper-bound y)))))
; - + + + ad bd
((and (lower-neg x) (upper-pos x) (lower-pos y) (upper-pos y)
(make-interval (* (lower-bound x) (upper-bound y))
(* (upper-bound x) (upper-bound y)))))
; - + - + bc bd OR bc ac
((and (lower-neg x) (upper-pos x) (lower-pos y) (upper-pos y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4) (max p1 p2 p3 p4)))))
; - + - - bc ac
((and (lower-neg x) (upper-pos x) (lower-neg y) (upper-neg y)
(make-interval (* (upper-bound x) (lower-bound y))
(* (lower-bound x) (lower-bound y)))))
; - - + + ad bc
((and (lower-neg x) (upper-neg x) (lower-pos y) (upper-pos y)
(make-interval (* (lower-bound x) (upper-bound y))
(* (upper-bound x) (lower-bound y)))))
; - - - + bd ac
((and (lower-neg x) (upper-neg x) (lower-neg y) (upper-pos y)
(make-interval (* (upper-bound x) (upper-bound y))
(* (lower-bound x) (lower-bound y)))))
; - - - - bd ac
((and (lower-neg x) (upper-neg x) (lower-neg y) (upper-neg y)
(make-interval (* (upper-bound x) (upper-bound y))
(* (lower-bound x) (lower-bound y)))))))
;2.12
(define (make-center-percentage c p)
(make-center-width c (abs (* c p)))
(define (percentage interval)
(/ (center interval) (width interval)))
; 2.13
(define a (make-center-percentage .25 .01))
(define b (make-center-percentage .10 .01))
(par1 a b)
(par2 a b)
> (0.0693140028288543 . 0.0736002886002886)
> (0.07071428571428572 . 0.07214285714285715)
No comments. Sign up or log in to comment |
No comments. Sign up or log in to comment