mizery_guts


Joined 1 year ago
Homeworks submitted:
Homework comments: 		7
2

About Me

No description provided.

Classes

Fifty Challenging Problems in Probability

Class status: Under Construction
Role: Student 		. 0% complete

Structure and Interpretation of Computer Programs

Class status: Established
Role: Student 		. 53% complete

Submitted Assignments

Structure and Interpretation of Computer Programs: Lesson 6, HW 1

;; Exercise 2.55

Reading the quote operator works from left to right, so (car '(quote abracadabra)) is quote.

;; Exercise 2.63

tree->list-1 is a recursive process with time proportional to the number of elements, and space required proportional to the number of elements.

In tree->list-2, each node is visted only once with a procedure that collects elements to the left of the node and a procedure that collects elements to the right of the node. The same technique that is used in tree->list-1.

There is no difference between the orders of growth in either of them.

Exercise 2.67

(a d a b b c a)

Exercise 2.71

The most frequent symbol is encoded in 1 bit and the least frequent in n-1 bits

;; Exercise 2.53

(list 'a 'b 'c); Value (a b c)
(list (list 'george)); Value ((george))
(cdr '((x1 x2) (y1 y2))); Value ((y1 y2))
(cadr '((x1 x2) (y1 y2))); Value (y1 y2)

;; Exercise 2.57

(define (augend s)   
  (accumulate make-sum 0 (cddr s)))

(define (multiplicand p) 
  (accumulate make-product 1 (cddr  p)))


;; Exercise 2.59

(define (union-set set1 set2)
  (cond ((null? set1) set2)
	((null? set2) set1)
	(else (append
	       (filter (lambda (x)
			 (not (element-of-set? x set2))) set1)
	       set2))))


;; Exercise 2.61

(define (adjoin-set x set)
  (cond ((or (null? set) (< x (car set))) (cons x set))
	((= x (car set)) set)
	(else (cons (car set) (adjoin-set x (cdr set))))))

;; Exercise 2.65

(define (union-set-tree tree1 tree2)
  (let ((list1 (tree->list-2 tree1))
	(list2 (tree->list-2 tree2)))
    (list->tree (union-set list1 list2))))

(define (intersection-set-tree tree1 tree2)
  (let ((list1 (tree->list-2 tree1))
	(list2 (tree->list-2 tree2)))
    (list->tree (intersection-set list1 list2))))

;; Exercise 2.69

(define (successive-merge set)
  (if (null? (cdr set))
      (car set)
      (successive-merge (adjoin-set (make-code-tree (car set)
						    (cadr set))
				    (cddr set)))))

;; Exercise 2.71
;;
;; for n = 5:
;;
;;            |31
;;           / \ 
;;          /   |15     
;;         /   / \   
;;        /   /   |7 
;;       /   /   / \ 	       
;;      /   /   /   |3		       
;;     /   /   /   / \ 
;;    16   8   4   2   1

mizery_guts 1 year ago
Structure and Interpretation of Computer Programs: Lesson 7, HW 1

;; Exercise 2.73

a. We have moved the deriv rules into a data-directed table. The slots made in the table are under the operator 'deriv, with types '+, '*, .. etc.

The reason that the predicates number? and same-variable? cannot be assimilated into the types slots is because of the way we have set up the expressions. Expressions involving number? and same-variable? do not require a tag, they are identified by primitive predicates that operate directly on the numbers and the variables. However our default case requires an operator tag, so we need to treat number? and variable? as special cases.

d. If the dispatch line in deriv looked like

((get (operator exp) 'deriv) (operands exp) var)

then the corresponding line in dispatch table must correspond to the same keys. Therefore we have to change the order in the put line in the package

(put '+ 'deriv sum) .. etc

;; Exercise 2.74 d.

The new company must provide the procedures that know how to extract employee information from their file format and install them in the dispatch table.

;; Exercise 2.76

For a system where many new operations are added I would use message passing. Adding a new procedure only requires defining it within the data objects you want to apply it to.

For a system where many new data types are added I would use data directed programming. In dispatching I can elect to have all data types represented and can manipulate all my data with generic procedures.

The simplicity of explicit dispatch is overruled by the hiding of details we achieve in message passing and data directed programming.

;; Exercise 2.73

;; Dispatch table.
;;
(define *op-table* (make-equal-hash-table))

(define (put op type proc)
  (hash-table/put! *op-table* (list op type) proc))

(define (get op type)
  (hash-table/get *op-table* (list op type) '()))



(define (deriv exp var)
  (cond ((number? exp) 0)
	((variable? exp) (if (same-variable? exp var) 1 0))
	(else ((get 'deriv (operator exp)) (operands exp)
					   var))))

(define (variable? x) (symbol? x))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp)) 
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (install-deriv-package)
  ;; internal procedures
  (define (addend s) (car s))      ;; the definitions of accessors (augend,
  (define (augend s) (cadr s))     ;; multiplier, etc.) are different from
  (define (multiplier p) (car p))  ;; the originals, because deriv only
  (define (multiplicand p) (cadr p));; passes the expression without the operator
  (define (base e) (car e))
  (define (exponent e) (cadr e))

  (define (sum exp var)                 
    (make-sum (deriv (addend exp) var)
	      (deriv (augend exp) var)))

  (define (product exp var)
    (make-sum
     (make-product (multiplier exp)
		   (deriv (multiplicand exp) var))
     (make-product (deriv (multiplier exp) var)
		   (multiplicand exp))))

  (define (exponentiation exp var)
    (make-product
     (make-product (exponent exp)
		   (make-exponentiation (base exp)
					(make-sum
					 (exponent exp) -1)))))

  (define (=number? exp num)
    (and (number? exp) (= exp num)))

  (define (make-sum a1 a2)
    (cond ((=number? a1 0) a2)
	  ((=number? a2 0) a1)
	  ((and (number? a1) (number? a2)) (+ a1 a2))
	  (else (list '+ a1 a2))))

  (define (make-product m1 m2)
    (cond ((or (=number? m1 0) (=number? m2 0)) 0)
	  ((=number? m1 1) m2)
	  ((=number? m2 1) m1)
	  ((and (number? m1) (number? m2)) (* m1 m2))
	  (else (list '* m1 m2))))

  (define (make-exponentiation u n)
    (cond ((and (number? u) (number? n)) (expt u n))
	  ((=number? n 0) 1)
	  ((=number? n 1) u)
	  (else (list '** u n))))

  ;; interface to the rest of the system
  (put 'deriv '+ sum)
  (put 'deriv '* product)
  (put 'deriv '** exponentiation)
  'done)

(install-deriv-package)
(deriv '(* (* x y) (+ x 3)) 'x)

;; Exercise 2.74

;; a. Each division supplies appropriate procedures tagged with division name.

(define (get-record division employee)
  ((get 'get-record division) employee))

;; b. Filter the division lists

(define (get-salary employee division-list)
  (filter (lambda (division)
	    ((get 'get-salary division) employee))
	  division-list))

;; c.

(define (find-employee-record employee division-list)
  (filter (lambda (division)
            ((get 'get-record division) employee))
          division-list))



;; Exercise 2.75

(define (make-from-real-imag x y)
  (define (dispatch op)
    (cond ((eq? op 'real-part) x)
	  ((eq? op 'imag-part) y)
	  ((eq? op 'magnitude)
	   (sqrt (+ (square x)(square y))))
	  ((eq? op 'angle) (atan y x))
	  (else
	   (error "Unknown op -- MAKE-FROM-REAL-IMAG" op))))
  dispatch)

(define (make-from-mag-ang r a)
  (define (dispatch op)
    (cond ((eq? op 'real-part) (* r (cos a)))
	  ((eq? op 'imag-part) (* r (sin a)))
	  ((eq? op 'mag) r)
	  ((eq? op 'angle) a)
	  (else
	   (error "Unknown op -- MAKE-FROM-MAG-ANG" op))))
  dispatch)

(define z (make-from-real-imag 3 4))
(z 'real-part)
(z 'imag-part)
(z 'angle)
(z 'magnitude)

mizery_guts 1 year ago
Structure and Interpretation of Computer Programs: Lesson 5, HW 1

;; Exercise 2.29

If we change the representation of mobiles so that the constructor is:

(define (make-mobile left right)(cons left right))

then we only need to change the selector left-branch:

(define (right-branch mobile)(cdr mobile))

;; Exercise 2.32

(1 2 3) ==> (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

The base case is the set containing the empty set. This is described when the if-statement is true.

(subsets nil) ==> (())

For a set containing one element, the base case isn't true, so use the alternative case:

(append (subsets nil) (map f(x) (subsets nil)))

We know (subsets nil) is the set containing the empty set. So we are appending the set containing the empty set and the set containing the element 3. This set containing the element 3 is represented as a list containing the element 3, (3), which is the car of the list (3) cons'd with the empty set:

(cons (car (3)) (())) ==> (3)

Looking at the incomplete line we have for the alternate case, we guess that the procedure f(x) is

(lambda (x) (cons (car s) x))

;; Exercise 2.38

(fold-right / 1 (list 1 2 3)) ; value 3/2

(fold-left / 1 (list 1 2 3)) ; value 1/6

(fold-right list '() (list 1 2 3)) ; Value (1 (2 (3 ())))

(fold-left list '() (list 1 2 3)) ; Value (((() 1) 2) 3)

For fold-left and fold-right to produce the same values the operator must be commutative. That is, (op A B) = (op B A).

;; Exercise 2-17

(define (last-pair items)
  (define (iter items result)
    (if (null? items)
	result
	(iter (cdr items) items)))
  (iter items items))

(last-pair (list 23 72 149 34))
(last-pair '())

;; Exercise 2-20

(define (same-parity f . n)
  (define parity? (if (even? f) even? odd?))
  (define (try-it n)
    (if (null? n)
	n
	(if (parity? (car n))
	    (cons (car n) (try-it (cdr n)))
	    (try-it (cdr n)))))
  (cons f (try-it n)))


(same-parity 1 2 3 4 5 6 7)


;; Exercise 2.23

(for-each (lambda (x) (newline) (display x))
	  (list 57 321 88))

(define (for-each proc items)
  (cond ((not (null? items))
	 (proc (car items))
	 (for-each proc (cdr items)))))


;; Exercise 2.26

(define x (list 1 2 3))
(define y (list 4 5 6))

(append x y) ; (1 2 3 4 5 6)
(cons x y) ; ((1 2 3) 4 5 6)
(list x y) ; ((l 2 3) (4 5 6))


;; Exercise 2.29

(define (make-mobile left right) (list left right))

(define (make-branch length structure)(list length structure))

(define (left-branch mobile)(car mobile))

(define (right-branch mobile)(cadr mobile))

(define (branch-length branch)(car branch))

(define (branch-structure branch)(cadr branch))

(define (weight-mobile m)
  (if (not (pair? m))
      m
      (+ (weight-mobile (branch-structure (left-branch m)))
	 (weight-mobile (branch-structure (right-branch m))))))

(define (balanced-mobile? m)
  (if (not (pair? m))
      true
      (let ((left-m  (branch-structure (left-branch m))))
	    (right-m (branch-structure (right-branch m))))
	(and (= (* (branch-length (left-branch m)) (weight-mobile left-m))
		(* (branch-length (right-branch m)) (weight-mobile right-m)))
	     (balanced-mobile? left-m)
	     (balanced-mobile? right-m)))))

(define b1 (make-branch 1 7/2))
(define b2 (make-branch 1 7/2))
(define b3 (make-branch 2 3))
(define b4 (make-branch 3 2))
(define b5 (make-branch 5 (make-mobile b1 b2)))
(define b6 (make-branch 7 (make-mobile b3 b4)))
(define m (make-mobile b5 b6))

(weight-mobile m)
(balanced-mobile? m)

;; Exercise 2.35

(define (count-leaves t)
  (accumulate +
	      0
	      (map (lambda (x) 1)
		   (enumerate-tree t))))


;; Exercise 2.41

(define (unique-pairs n)
  (flatmap (lambda (i)
	     (map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1))))
	   (enumerate-interval 1 n)))

(define (unique-triples n)
  (flatmap (lambda (i)
	     (map (lambda (p) (cons i p)) (unique-pairs (- i 1))))
	   (enumerate-interval 1 n)))

(define (unique-triples-less-than-or-equal-to-n-that-sum-to-s n s)
  (filter (lambda (triple) (triple-equals-s? s triple))
	  (unique-triples n)))

(define (triple-equals-s? s triple)
  (= s (+ (car triple) (cadr triple) (caddr triple))))

(unique-triples-less-than-or-equal-to-n-that-sum-to-s 6 12)

;; Exercise 2.44

(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
	(below painter (beside smaller smaller)))))


;; Exercise 2.47

(define (make-frame origin edge1 edge2) (list origin edge1 edge2))

(define (origin-frame frame)(car frame))

(define (edge1-frame frame)(cadr frame))

(define (edge2-frame frame) (caddr frame))

(define (make-frame origin edge1 edge2) (cons origin (cons edge1 edge2)))

(define (origin-frame frame)(car frame))

(define (edge1-frame frame)(cadr frame))

(define (edge2-frame frame)(cddr frame))


;; Exercise 2.50

(define (flip-horiz painter)
  (transform-painter painter
		     (make-vect 1.0 0.0)
		     (make-vect 0.0 0.0)
		     (make-vect 1.0 1.0)))

(define (rotate180 painter)
  (transform-painter painter
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 1.0)
                     (make-vect 1.0 0.0)))

(define (rotate270 painter)
  (transform-painter painter
                     (make-vect 0.0 1.0)
                     (make-vect 0.0 0.0)
                     (make-vect 1.0 1.0)))

mizery_guts 1 year ago
Structure and Interpretation of Computer Programs: Lesson 4, HW 1

;; 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))))

mizery_guts 1 year ago
Structure and Interpretation of Computer Programs: Lesson 3, HW 1

;; Exercise 1-35

The equation x = 1 + 1/x has fixed point solutions:

phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5)/2)

To show this we solve for x in the above equation.

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) ;Value: 1.6180327868852458

;; Exercise 1-29

(define (cube x) (* x x x))

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
	 (sum term (next a) next b))))

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

(define (even? n)
  (= (remainder n 2) 0))

(define (simpsons-rule f a b n)
  (define even_n (if (even? n) n (+ n 1)))
  (define h (/ (- b a) even_n))
  (define (add-h x) (+ x h))
  (define (add-2h x) (+ x h h))
  (* (+ (f a)
	(* 2.0 (sum f (+ a h) add-h (- b h)))	
	(* 2.0 (sum f (+ a h) add-2h (- b h)))
	(f b))
     (/ h 3.0)))

(simpsons-rule cube 0 1 1000)

;; Exercise 1-30
	   
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (+ result (term a)))))
  (iter a 0))
    
;; Exercise 1-31

(define (square x) (* x x))

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
	 (product term (next a) next b))))

(define (fact n)
  (define (identity x) x)
  (define (inc n) (+ n 1))
  (product identity 1 inc n))

(define (wallis-pi n)
  (define (wallis-term x)
    (square (/ (+ x 1) x)))
  (define (wallis-next x) (+ x 2))
  (/ (* 2.0 (product wallis-term 3 wallis-next n)) n))

;; Exercise 1-37

(define (cont-frac n d k)
  (define (try-it i)
    (if (> i k)
	0
	(/ (n i) (+ (d i) (try-it (+ i 1))))))
  (try-it 1))

(cont-frac (lambda (i) 1.0)
	   (lambda (i) 1.0)
	   10)

(define phi (/ 2 (+ 1 (sqrt 5))))

(- .6179775280898876 phi)
;Value: -5.6460659971224736e-5

(define (cont-frac n d k)
  (define (iter i denominator)
    (if (= i 0)
	denominator
	(iter (- i 1) (/ (n i) (+ (d i) denominator)))))
  (iter k 0))

;; Example 1-41

(define (inc n) (+ n 1))
(define (double f)
  (lambda (x) (f (f x))))

((double inc) 1) ; Value 3

; let double = d
; let (d d) = g = 4 times
; let (d g) = h = (g g) = ((d d) (d d))
                      = (4 times (4 times))
                      = 16 times
(((double (double double)) inc) 5) ; Value 21

;; Example 1-42

(define (compose f g)
  (lambda (x) (f (g x))))
((compose square inc) 6) ; Value 49

;; Example 1-43

(define (repeated f n)
    (if (= n 1)
	f
	(compose f (repeated f (- n 1)))))

((repeated square 2) 5) ; Value 625

mizery_guts 1 year ago
Structure and Interpretation of Computer Programs: Lesson 2, HW 1

;; Exercise 1-13

The formula is true for F(0) and F(1)

F(0) = (phi0 - psi0)/sqrt(5) = (1 - 1)/sqrt(5) = 0

F(1) = (phi - psi)/sqrt(5) = (1 + sqrt(5) - 1 + sqrt(5))/(2sqrt(5)) = 1

Let us assume it is for all terms upto some value n

F(n+1) = (phi^(n+1) - psi^(n+1))/sqrt(5)

= phi^2 phi^(n-1) - psi^2 psi(n-1)

= (phi + 1)phi^(n-1) - (psi + 1)psi(n-1) where phi^2 = phi + 1 and psi^2 = psi + 1

= F(n) + F(n-1)

If we can can show that F(n) = phi^n/sqrt(5) plus some term whose absolute value is always less than a half, then F(n) must be the closest integer to phi^n/sqrt(5).

psi^n/sqrt*5 = ((1 - sqrt(5))/2)^n/sqrt(5) = -0.618304^n/2.236068

which has an absolute value less than 1/2 for all positive values of n.

;; Exercise 1-23

test values 2,3,4,5,6 ..

1009 *** .06200000000001182

1013 *** .09399999999999409

1019 *** .07800000000000296

10007 *** .23399999999998045

10009 *** .25

10037 *** .23400000000000887

100019 *** .7959999999999923

100043 *** .7350000000000136

100049 *** .7650000000000148

1000003 *** 2.3760000000000048

1000033 *** 2.359000000000009

1000037 *** 2.3899999999999864

test values 2,3,5,7,9..

1009 *** .04599999999999227

1013 *** 4.6999999999997044e-2

1019 *** 4.6999999999997044e-2

10007 *** .14099999999999113

10009 *** .1560000000000059

10037 *** .15699999999998226

100019 *** .48400000000000887

100043 *** .5149999999999864

100049 *** .6560000000000059

1000003 *** 1.4529999999999745

1000033 *** 1.4379999999999882

1000037 *** 1.4839999999999804

ratio

1.35

2.

1.66

1.66

1.60

1.49

1.64

1.43

1.17

1.63

1.64

1.61

The ratios 1.17 1.35 1.43 1.49 1.60 1.61 1.63 1.64 1.64 1.66 1.66 2.0 gives a median of 1.62 and bimodal value of 1.64,1.66

The outliers are explained by extra processes running like updates or too much porn or something external to the prime? procedure. So I will use the median value.

The new prime? procedure is 1.62 times faster. This underperforms the 2 times faster we expected, but it is consistent with having a slightly more involved technique of getting test-divisors.

;; Exercise 1-25

Using the fast-expt library means we need to deal with numbers a^n, which are very large. Using the new version of expmod, We never deal with numbers larger than n.

;; Exercise 1-9

;; The length of the chain of deferred additions
;; grows linearly with n. A linearly recursive process

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(+ 3 10)
(inc (+ 2 10))
(inc (inc (+ 1 10)))
(inc (inc (inc 10)))
(inc (inc 11))
(inc 12)
13

;; The program variables provide a complete description
;; between steps. A linearly iterative process.

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

;; (+ 3 10)
;; (+ 2 11)
;; (+ 1 12)
;; (+ 0 13)
;; 13

;; Exercise 1-11

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
(f 0) ;Value: 0
(f 1) ;Value: 1
(f 2) ;Value: 2
(f 3) ;Value: 4
(f 4) ;Value: 11

(define (f n)
  (define (f-iter a b c n)
    (if (= n 0)
	c
	(f-iter (+ a (* 2 b) (* 3 c)) a b (- n 1))))
  (f-iter 2 1 0 n))
(f 0) ;Value: 0
(f 1) ;Value: 1
(f 2) ;Value: 2
(f 3) ;Value: 4
(f 4) ;Value: 11

;; Exercise 1-15

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))

;; The procedure p is applied 5 times.

;; Both space and time increases by 1 whenever the angle 
;; is multiplied by 3. The orders of growth are logarithmic.


;; Exercise 1-17

(define (double x) (+ x x))

(define (halve x) (/ x 2))

(define (* a b)
  (cond ((= b 0) 0)
	((even? b) (* (double a) (halve b)))
	(else (+ a (* a (- b 1))))))

;; Exercise 1-19

(define (square x) (* x x))

(define (even? n)
  (= (remainder n 2) 0))

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
	((even? count)
	 (fib-iter a
		   b
		   (+ (square p) (square q)) ; compute p'
		   (+ (* 2 p q) (square q))  ; compute q'
		   (/ count 2)))
	(else (fib-iter (+ (* b q) (* a q) (* a p))
			(+ (* b p) (* a q))
			p
			q
			(- count 1)))))


;; Exercise 1-21

(smallest-divisor 199) ;Value: 199
(smallest-divisor 1999) ;Value: 1999
(smallest-divisor 19999) ;Value: 7

;; Exercise 1-27

(define (expmod base exp m)
  (cond ((= exp 0) 1)
	((even? exp)
	 (remainder (square (expmod base (/ exp 2) m))
		    m))
	(else
	 (remainder (* base (expmod base (- exp 1) m))
		    m))))

(define (carmichael-test n)
  (define (try-it a)
    (cond ((= a n) true)
	  ((= (expmod a n n) a) (try-it (+ 1 a)))
	  (else false)))
  (try-it 0))

(carmichael-test 561) ;Value: #t
(carmichael-test 1105) ;Value: #t
(carmichael-test 6601) ;Value: #t

mizery_guts 1 year ago
Structure and Interpretation of Computer Programs: Lesson 1, HW 1

;; Exercise 1-1

10 ;Value: 10

(+ 5 3 4) ;Value: 12

(- 9 1) ;Value: 8

(/ 6 2) ;Value: 3

(+ (* 2 4) (- 4 6)) ;Value: 6

(define a 3) ;Value: a

(define b (+ a 1)) ;Value: b

(+ a b (* a b)) ;Value: 19

(= a b) ;Value: #f

(if (and (> b a) ( b a) b a)) ;Value: 6

(* (cond ((> a b) a) (( b 0) + -) a b)

The problem reduces to the evaluation of a combination of two operands and an operator: (if (> b 0) + -). The operator is a compound expression which adds a and b, for b positive, otherwise the operator subtracts b from a.

;; Exercise 1-5

(test 0 (p))

normal-order results in expansion

(if (= 0 0) 0 (p))

followed by the evaluation of the if expression, and finally the interpreter prints the value 0.

applicative-order the intepreter will first try and evaluate the subexpression (p). Which is a procedure defined as:

(define (p) (p))

The definition defines the procedure (p) as (p), which cannot be further expanded. The interpreter will loop indefinitely.

;; Exercise 1-6

The interpreter bombs out with the message: ;Aborting!: maximum recursion depth exceeded

The new definition, new-if, only works if the operands are values. This means (new-if...) keeps on calling (sqrt-iter ...), improving the guess, but never tests that guess in the cond form because the procedure (sqrt-iter.. ) it never becomes a value.

;; Exercise 1-7

For small numbers, a precision of one thousandth may not be good enough. For example if we try and find the root of a millionth:

(- 0.000001 (square (sqrt 0.000001))) ;Value: -9.762285838805523e-4

we get an unacceptable error, hundreds of times larger than the orginal x of a millionth.

(define (square x) (* x x)) (define (sqrt-iter guess x) (if (good-enuf? guess x) guess (sqrt-iter (improve guess x) x))) (define (improve guess x) (average guess (/ x guess))) (define (average x y) (/ (+ x y) 2)) (define (good-enuf? guess x) (< (/ (abs (- guess (improve guess x))) guess) 0.001))

Using our new procedure definition of (good-enuf? ..)

(- 0.000001 (square (sqrt 0.000001))) ;Value: -1.1080488810337509e-9

has an error 1000s of times smaller than the original x of a millionth.

For large numbers and limited precision, we could have a situation where there is a gap between interpreter's number and our real number. For example the interpreter here, when looking at the number, one-hundred thousand trillion:

(- 100000000000000.0099 100000000000000) ;Value: .015625

gives an error greater than the real error. (Equally the error could have been smaller than the real error.) This means for large numbers we don't know the "goodness" of the calculated root.

;; Exercise 1-8

(define (square x) ( x x)) (define (cube x) ( x x x)) (define (cuberoot-iter guess x) (if (cuberoot-good-enough? guess x) guess (cuberoot-iter (cuberoot-improve guess x) x))) (define (cuberoot-improve guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3)) (define (cuberoot-good-enough? guess x) (< (abs (- (cube guess) x)) 0.001)) (define (cuberoot x) (cuberoot-iter 1.0 x))

(cuberoot 27) ;Value: 3.0000005410641766

(cuberoot (cube 1000)) ;Value: 1000.


mizery_guts 1 year ago