Improved Means for Achieving Deteriorated Ends

Written on 2008-04-01 02:31:48

At long last, I'm through Chapter 1 of SICP. I'm a bit disappointed that Closures haven't been covered yet but they're in the first few pages of Chapter 2 and I've already got a few problems solved. As a matter of fact, I finished Chapter 1 last Wednesday it just takes time to get these posts up. I have a feeling I need to go back and study those explanations of Lexical Scope in Chapter 1 though. I'll try to write more about the experience thus far in a separate post. For now, here are my results for Section 1.3.

Resources:

Read: Chapter 1 through Section 1.3

Watch: Lectures 2-a

Checked against: Eli Bendersky's Blog, SICP Wiki, Ken Dyck's Solutions, Theloserblog, Wfasim's Solutions, Autodidact and Lispy for Inspiration.

SICP Notes and Exercises:

Notes

Pgs. 63-66: Discussion of Let and Local Variable Binding.

Pg. 76: Discussion of First-Class Status in programming languages.

Quotes

"I'm going to write the...procedure here explicitly without giving it a name. I'm doing it anonymously, I don't necessarily have to give a name to something if I just want to use it once." - Gerald Jay Sussman, approx. 17:00, Lecture 2-a

"Procedures can be named by variables. Procedures are not special...Therefore they can be passed from one to another as arguments." - Gerald Jay Sussman, approx. 20:00, SICP Lecture 1-B from Swiss Archive, Higher-Order Functions Explanation

"Talent is to a great extent knowledge that we haven't yet learned how to formalize." - Gerald Jay Sussman, approx. 55:00, The Legacy of Computer Science

Exercises

1.29:

This exercise definitely wasn't easy. I think most of the difficulty is in figuring out how the math works and how the functions are all feeding into each other.

(define (cube x) (* x x x))
;Value: cube

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

(define (simpsons-rule f a b n)
  (define h (/ (- b a) n))
  (define (k-term x)
    (cond ((or (= x 0) (= x n)) 1)
	  ((even? x) 2)
	  (else 1)))
  (define (yk x)
    (* (k-term x)
       (f (+ a (* x h)))))
  (* (sum yk a (lambda (x) (+ x 1)) n)
     (/ h 3)))
;Value: simpsons-rule

(simpsons-rule cube 0 1 100)
;Value: 1/4

(simpsons-rule cube 0 1 1000)
;Value: 1/4

1.30:

Personally I think it's really nice that Abelson and Sussman have been throwing in these sort of review problems. They make me feel like I'm learning something. They give me hope. I solved this one in about 1 minute and a half and thought, "Hey, maybe I'm not a complete idiot. Maybe I'll actually know something about programming one day."

(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (iter a 0))
;Value: sum

1.31:

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

(define (factorial n)
  (product (lambda (x) x) 1 (lambda (x) (+ x 1)) n))
;Value: factorial

(define (pi-approx approximations)
  (define (pi-term denom) (/ (- (square denom) 1) (square denom)))
  (define (next-term denom) (+ denom 2))
  (product pi-term 3 next-term approximations))
;Value: pi-approx

(pi-approx 40)
;Value: 4722366482869645213696/5938020471163465810125 (.795276)

I just changed the variable names and commented pi-approx. The comment is omitted here in favor of this explanation. I couldn't figure out what on earth I was doing in the original so I actually wrote a brand new pi-approx with a different approach before realizing my original version was both correct and, I suspect, faster. I was computing 2 terms at a time based on their shared denominator.

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(* (term a)
	   (product term (next a) next b))))
  (iter a 1))
;Value: product

1.32:

(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
		(accumulate combiner null-value term (next a) next b))))
;Value: accumulate

(define (sum term a next b)
  (accumulate + 0 term a next b))
;Value: sum

(define (product term a next b)
  (accumulate * 1 term a next b))
;Value: product

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
	null-value
	(combiner (term a)
		  (iter (next a) result))))
  (iter a null-value))
;Value: accumulate

1.33:

(define (filtered-accumulate combiner null-value term a next b filter)
  (cond ((> a b) null-value)
	((filter a) (combiner (term a)
			       (filtered-accumulate combiner null-value term
						    (next a) next b filter)))
	(else (filtered-accumulate combiner null-value term
				   (next a) next b filter))))
;Value: filtered-accumulate

(define (sum-square-primes a b)
  (filtered-accumulate + 0 square a inc b prime?))
;Value: sum-square-primes

(define (product-relative-primes n)
  (define (relatively-prime i)
    (= (gcd i n) 1))
  (filtered-accumulate * 1 identity 1 inc n relatively-prime))
;Value: product-relative-primes

1.34:

The procedure f only actually produces output when it's argument is another procedure, specifically a procedure which takes one formal parameter. Given a procedure of a different arity it will produce an error regarding the wrong number of arguments and given a non-procedural argument it will complain about the object not being applicable.

1.35:

(define tolerance 0.00001)
;Value: tolerance

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))
;Value: fixed-point

(define (golden-ratio)
  (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))
;Value: golden-ratio

(golden-ratio)
;Value: 1.6180327868852458

Things are pretty straightforward from 1.29 through 1.36. The main thing to remember on 1.35 and 1.36 is that a transformation is just a function and serves as the f in the fixed-point.

1.36:

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (display guess)
      (newline)
      (if (close-enough? guess next)
	  next
	  (try next))))
  (try first-guess))
;Value: fixed-point

(define (solve-for-x)
  (fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0))
;Value: solve-for-x

(solve-for-x)
2.
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957
;Value: 4.555532270803653

(define (solve-for-x)
  (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0))
;Value: solve-for-x

(solve-for-x)
2.
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
;Value: 4.555537551999825

Pretty impressive. solve-for-x went from taking 34 steps to 9 steps thanks to average damping. I wonder what it does for golden ratio? And sqrt's for various inputs...

1.37:

a.

(define (cont-frac n d k)
  (define (frac-iter i)
    (if (< i k)
	(/ (n i) (+ (d i) (frac-iter (+ i 1))))
	(/ (n i) (d i))))
  (frac-iter 1))
;Value: cont-frac

(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 11)
;Value: .6180555555555556

(define (cont-frac n d k)
  (define (frac-iter count result)
    (if (= count 0)
	result
	(frac-iter (- count 1)
		   (/ (n count) (+ (d count) result)))
  (frac-iter k 0))
;Value: cont-frac

(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 11)
;Value: .6180555555555556

The main thing that's tricky about 1.37 is figuring out the math of continued fractions and starting with the base case of the last term and working backwards.

1.38:

(define (euler-expand)
  (define (d-fun i)
    (cond ((= (modulo i 3) 2) (* (ceiling (/ i 3)) 2))
	  (else 1)))
  (cont-frac (lambda (i) 1.0) d-fun 8))
;Value: euler-expand

(euler-expand)
;Value: .7182795698924731

So, my original iterative version of cont-frac didn't actually work for this problem. The iterative version didn't work for this problem because it treated division as though it's commutative and it isn't. It took me a while to figure that out.

1.39:

(define (tan-cf x k)
  (define (d i)
    (- (* 2 i) 1))
  (define (n i)
    (if (= x 1)
	x
	(square x)))
  (cont-frac n d k))
;Value: tan-cf

(tan-cf 1.0 5)
;Value: 1.5574074074074076

This one is actually fairly tricky. If you fail to notice that this is a continued fraction that subtracts rather than adds you're completely hosed. I modified my cont-frac procedure to fix this once I noticed. There's probably an elegant way to extend cont-frac to accomodate these different uses (subtracting versus adding continued fractions, etc.) but I'm not going to chase it down myself. Anybody feel like improving on this?

1.40:

(define (cubic a b c)
  (lambda (x) (+ (expt x 3) (* a (expt x 2)) (* b x) c)))

(define dx 0.00001)
;Value: dx

(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))
;Value: fixed-point-of-transform

(define (cubic a b c)
  (lambda (x) (+ (expt x 3) (* a (expt x 2)) (* b x) c)))
;Value: cubic

(define (deriv g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
;Value: deriv

(define (newton-transform g)
  (lambda (x) (- x (/ (g x) ((deriv g) x)))))
;Value: newton-transform

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))
;Value: newtons-method

(newtons-method (cubic 4 3 2) 1)
;Value: -3.2695308420809894

I didn't realize I just needed to literally translate the function. After I knew that I was fine. Again, time to study more math.

1.41:

(define (double x)
  (lambda (i) (x (x i))))
;Value: double

(define (inc x) (+ x 1))
;Value: inc

((double inc) 0)
;Value: 2

(((double (double double)) inc) 5)
;Value: 21

;;This is because a double on a (double double) is effectively a square.

(double double)
;Value 16: #[compound-procedure 16]

(((double (double double)) inc) 0)
;Value: 16

((double (double (double inc))) 0)
;Value: 8

(((double (double (double double))) inc) 0)
;Value: 256

1.42:

(define (compose f g)
  (lambda (i) (f (g i))))
;Value: compose

((compose square inc) 6)
;Value: 49

1.43:

(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))
;Value: repeated

((repeated square 2) 5)
;Value: 625

Wow! That was a lot easier to think about using compose.

1.44:

(define (smooth f)
  (define dx 0.00001)
  (lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))
;Value: smooth

((smooth square) 2)
;Value: 4.000000000066667

(define (n-smoothed f n)
  (repeated smooth n) f)
;Value: n-smoothed

((n-smoothed square 16) 2)
;Value: 4

Check The Loser Blog for a potentially better answer.

1.45:

(define tolerance 0.00001)
;Value: tolerance

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
	  next
	  (try next))))
  (try first-guess))
;Value: fixed-point

(define (average x y)
  (/ (+ x y) 2))
;Value: average

(define (average-damp f)
  (lambda (x) (average x (f x))))
;Value: average-damp

(define (nth-root x n)
  (fixed-point (repeated
		(average-damp (lambda (y) (/ x (expt y (- n 1)))))
		(ceiling (/ n 2))) 1.0))
;Value: nth-root

(define (compose f g)
  (lambda (x) (f (g x))))
;Value: compose

(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))
;Value: repeated

(define (nth-root x n)
  (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
			    (repeated average-damp (log2 n)) 1.0))
;Value: nth-root

(define (log2 n)
  (if (= 1 n)
      0
      (+ (log2 (floor (/ n 2))) 1)))
;Value: log2

After testing the first 15 powers with my version of nth-root I couldn't figure out the relationship between n and the times to average damp. Just about everyone had trouble with this but I found the correct answer in Eli's comment thread...

1.46:

(define (iterative-improve tester improver)
  (define (iter guess x)
    (if (tester guess)
	guess
	(iter (improver guess) x)))
  (lambda (x) (iter 1.0 x)))
;Value: iterative-improve

(define (sqrt x)
  ((iterative-improve
    (lambda (guess) (< (abs (- (square guess) x)) 0.00001))
    (lambda (guess) (average guess (/ x guess)))) x))
;Value: sqrt

(define (average x y)
  (/ (+ x y) 2))
;Value: average

(sqrt 2)
;Value: 1.4142156862745097

(define (fixed-point f x)
  ((iterative-improve
    (lambda (guess) (< (abs (- guess (f guess))) 0.00001))
    (lambda (guess) (f guess))) x))
;Value: fixed-point

(fixed-point cos 1.0)
;Value: .7390893414033927

(Edit: 05/18/08) Well, that wraps it up for Section 1.3. I can't believe how long it took me to find the time to come back and clean these answers up a bit. I have had a lot going on though. There will be a few small changes in convention starting in SICP 2.1 to make things more manageable for me. As always, the most up to date code is in the repo.

comments powered by Disqus

Unless otherwise credited all material by Brit Butler

SICP Section 1.3