# SICP Section 1.3

Tagged as LISP, Self-Learning, SICP

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:

a.

`(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.

b.

`(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:

a.

`(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`

b.

`(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`

a.

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

b.

`(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.9657842846620873.0044722098412146.2791957575071573.7598507024015395.2158437849258954.1822071924013974.82776509834459064.3875933846626774.6712500857638994.4814036168950524.60536574609294.52308496787188654.5771146820473414.5413824801514544.5649032452308334.5493726793033424.5596064919132874.5528538757882714.5573055297482634.5543690644361814.5563053115329994.5550282635735544.5558703967028514.5553150011920794.55568126354332754.5554397157368464.5555990099982914.5554939575313894.5555632372928844.5555175484176514.5555476793063984.5555278085162544.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.98289214233104354.9221687213083434.6282243181954554.5683465131362424.55773059092370054.5559098090451314.5555994116106244.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`

b.

`(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.