SICP Section 1.1

Tagged as LISP, Self-Learning, SICP

Written on 2008-01-19 03:18:23

Well, I said I would do this and I meant it. These entries will be a bit lengthy. I feel a little pain for any feeds I'm aggregated on. So, in the interest of not driving you all mad, these weekly semester updates will be behind a cut.

Like so.

With that out of the way, here are the details. Each week, I'll post the resources I used (i.e. what I read, what I watched, etc) and the solutions to the relevant problems along with any notes of interest I had. I may offer other general musings (or even specific ones) inspired by my studies in other posts but these will tend towards a cut and dry solution to the exercises. Finally, I'll post a link to any sources I might have found or used to check answers I wasn't sure of and if I got the answer wrong I'll disclose that in the post.

As for the math, I haven't decided what to do about that. I mean, it doesn't make sense to post up a ton of math solutions though I suppose by that logic it doesn't make sense to post code snippets either. If I come up with something I'll let you know. If you have suggestions by all means write them in.

Resources:

Read: Chapter 1 through Section 1.1

Watch: Lectures 1-a

Checked against: Eli Bendersky's Blog

SICP Notes and Exercises:

Notes

Pgs. 28-30: Definitions and explanations of scope and locality. It is becoming evident that subtle errors can easily emerge due to differences in locality and scope. These errors are colluded by the fact that there is no distinction in lisp between variables and procedures. (i.e. you could have a procedure that used abs (another procedure) as a variable.)

Quotes

"First, we want to establish the idea that a computer language is not just a way of getting a computer to perform operations but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute." - Preface to the First Edition

"The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology - the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects." - Preface to the First Edition

Exercises

1.2:

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 3))))) (* 3 (* (- 6 2) (- 2 7))))
;Value: -23/90

1.3:

(define (two-of-three x y z)
  (cond ((< x y z) (+ (* y y) (* z z)))
	((< y x z) (+ (* x x) (* z z)))
	((< z x y) (+ (* x x) (* y y)))
	((or (= x y) (= x z)) (+ (* y y) (* z z)))
	((or (= y x) (= y z)) (+ (* x x) (* z z)))
	((or (= z x) (= z y)) (+ (* x x) (* y y)))))
;Value: two-of-three

Comments: The original version of the program lacked the last three lines but I realized if you got inputs that were equal to each other there wasn't a condition that matched that so I changed it. I'm sure there's a much more elegant way to do it but the job is done. And it's mostly readable.

1.4:

This procedure checks to see if B is greater than 0. If it is, it adds A and B. Otherwise, it subtracts B from A.

1.5:

This procedure when evaluated using applicative-order evaluation will not resolve as it infinitely recurses trying to evaluate (p). An interpreter using Normal-order evaluation will not have this problem because in the example the if condition evaluates to true so the p function is never evaluated. (The Scheme interpreter uses Applicative-Order evaluation.)

1.6:

Again, this is a case of infinite recursion due to Applicative-Order evaluation. Sqrt-iter continues to call itself regardless of the value of (good-enough? guess x) if you must know.

1.7:

(define (good-enough? guess x)
  (< (abs (- (improve guess x) guess)) (* 0.000001 guess)))
;Value: good-enough?

1.8:

(define (curt-iter guess x)
  (if (good-enough? guess x)
      guess
      (curt-iter (improve guess x) x)))
;Value: curt-iter

(define (good-enough? guess x)
  (< (abs (- (cube guess) x)) 0.001))
;Value: good-enough?

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

(define (curt x)
  (curt-iter 1.0 x))
;Value: curt

(define (improve guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
;Value: improve

##NOTE:

Here is an example rewrite of the sqrt program using block structure and lexical scoping. It is inserted here because this was the point of discussion but no relevant exercise was assigned.

(define (sqrt x)
    (define (sqrt-iter guess)
        (if (good-enough? guess)
            guess
            (sqrt-iter (improve guess))))
    (define (good-enough? guess)
        (< (abs (- (square guess) x)) 0.001))
    (define (average a b)
        (/ (+ a b) 2))
    (define (improve guess)
        (average guess (/ x guess)))
    (sqrt-iter 1.0))

• ← Previous
• Next →