Chapter 1 Review

I haven't had much time to work on SICP in the last couple of weeks, but I consider chapter 1 finished. I have a couple of observations.

I love Scheme. Its a great learning tool. I've spent very little time learning some special syntax and a lot of time learning the underlying concepts. It is remarkably well-suited to thinking recursively. Oddly, it is difficult to do iterative looping. Part of that might have been that the exercises were trying to make me write an iterative algorithm for a problem that was recursive in nature.

The course starts out with no data types other than numbers. This leads to problems and exercises that are very math-heavy. One claim I see often is that you don't need much math beyond high school precalculus for this text. Technically that's true, because the text gives you any formulas you need. I hadn't had any experience with the concept of fixed points o Newton's method, and I completed those sections. Still, I was glad I had studied Simpons' formula in calculus. Moreover, studying infinite series gave me a sense of familiarity with many of the exercises. SICP doesn't require you to solve calculus problems, but I can't help but think that my confusion would be increased greatly if I didn't understand the math behind the exercises.

On to Chapter 2.

Exercises 1.40 - 1.44

These were exercises on writing procedures which return procedures. They went pretty quick, and I don't have a lot to write up for them. I have sample output that verifies the solution for most of them.

Exercise 1.40 Define a procedure cubic to approximate zeros of the cubic x³ + ax² + bx + c.

(define (cube x) (* x x x))
(define (cubic a b c)
  (lambda (x)
    (+ (cube x) (* a (square x)) (* b x) c)))

Exercise 1.41 Define a procedure double that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice.

(define (double f)
  (lambda (x)
    (f (f x))))

((double square) 2)
;Value: 16

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

Exercise 1.42 Define a procedure compose that implements composition.

(define (compose f g)
  (lambda (x) (f (g x))))

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

Exercise 1.43 Write a procedure that takes as inputs a procedure that computes f and a positive integer n and returns the procedure that computes the nth repeated application of f.

(define (repeated f x)
  (lambda (y)
    (if (= x 1)
        (f y)
        ((compose f (repeated f (- x 1))) y))))

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

Exercise 1.44 Write a procedure smooth that takes as input a procedure that computes f and returns a procedure that computes the smoothed f.

(define (smooth f)
  (lambda (x)
    (let ((dx .00001))
      (/ (+ (f (+ x dx)) (f x) (f (- x dx))) 3.0))))

(sqrt 4)
;Value: 2.0000000944796694

(((repeated smooth 10) sqrt) 4)
;Value: 2.0000000944692538

I'm not sure whether sqrt doesn't respond to smoothing, the dx is too large, or this solution isn't right. But I think it's right.

Exercises 1.38, 1.39: More Continued Fraction Fun

Exercise 1.38

Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler's expansion.

The main challenge with this exercise is how to caputure the series 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, .... as a procedure.

• f(x) = x for 1 and 2
• For x > 2, every third term is part of the series 4, 6, 8, ...
• For every other x, f(x) = 1

So I use remainder to check whether the argument is one of those third terms. If it is, its value is 2 greater than the term for x - 3. Or to put it another way, f(x) = 2 + f(x - 3), for x = 5, 8, 11....

;; Exercise 1.38

(define (d x)
  (cond ((< x 3) x)
    ((= 0 (remainder (- x 2) 3)) (+ 2 (d (- x 3))))
    (else 1)))

(+ 2 (cont-frac d (lambda (x) 1.0) 100))

;Value: 2.7182818284590455

Exercise 1.39

Define a procedure (tan-cf x k) that computes an approximation to the tangent function based on Lambert's formula.

A few points I had to keep in mind:

• Procedure n has to operate on the argument x, but n should still take only one value, which is the term for that portion of the contiued fraction.
• Procedure n returns a number, which is the value of an appropriate procedure applied to x.
• Procedure n should return a negative number for values of k greater than 1.

;; Exercise 1.38
(define (tan-cf x k)
  (define (d i)
    (if (= i 1)
        1.0
        (+ 2 (d (- i 1)))))
  (define (n i)
    (if (= i 1)
        x
        (- (* x x))))
  (cont-frac d n k))

Comparing my results with the calculator result of tan(3) = -0.142546543074278:

;; Using recursive version of cont-frac
(tan-cf 3 10)

;Value: -.1425465438397583

; Using iterative Version of cont-frac
(tan-cf 3 10)

;Value: -.14254654300801906

Finally, testing these two exercises revealed an error in my solution for exercise 1.37 (since corrected).

Exercise 1.37: Continued Fraction

Write a procedure to calculate a continued fraction, such as:

In approaching the problem I think of the expression like this:

This lends itself naturally to a recursive definition. "The Rest" is just the next procedure call. The terminating case is when you have called the procedure k times.

I had to define a helper procedure so that I could keep track of the index. The only way I see to avoid this is to define the procedure to take four arguments, like (define cont-frac d n a b), which starts at a and ends at b. Since the exercise specifically asks for a procedure with three arguments, I chose to create a helper function.

(define (cont-frac d n k)
  (define (cont-frac-helper index)
    (if (= index k)
        (/ (n index) (d index))
        (/ (n index) (+ (d index) (cont-frac-helper (+ index 1))))))
  (cont-frac-helper 1))

;; Estimate of golden ratio
(/ 1 (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 10))

The iterative version is a little harder, but by now I'm getting the hang of this. I know I need a results variable to store the results of my work from one iteration to the next. The steps are

• Start with the final term N_k/D_k
• Check whether you're done.
• If you're not done, the new result is N_k-1 / (D_k-1 + Result_k)
• You're done after you've calculated the step with N₁ and D₁. Repeat until k=0

;; Iterative version
(define (cont-frac d n k)
  (define (iter k result)
    (if (= k 0)
        result
        (iter (- k 1) (/ (n k) (+ (d k) result)))))
  (iter k (/ (n k) (d k))))

;; Estimate of golden ratio
(/ 1 (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 10))

---

Update: Fixed an off-by-one error in the iterative version.

Exercise 1.29: Simpson's Rule

Use the sum procedure from the chapter to estimate the definite integral of a procedure based on Simpson's rule.

Here's the summation procedure from the chapter:

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

My function definition should look like: (define (simpsons f a b n) ... where f is the function to integrate (defined as a procedure), a is the upper bound, b is the lower bound, and n is the number of subdivisions on the interval [a, b].

To get it straight in my head, I rewrote Simpson's rule in a way that was more clearly applicable for this problem.

Writing it down this way made two things clearer:

1. The argument of the function in the series changes in a straightforward manner. I just need to add h to get the next argument.
2. The procedure applied is different in each term. Sometimes it's f, sometimes it's 2f, and sometimes it's 4f

First, just to make things easier on myself, I'll define h.

(define h (/ (- b a) n))

Based on the way the sum procedure is defined, I know I need to pass it two procedures. I'll call them simp-term and simp-next.

As mentioned above, it's easy to see how the the function argument changes from term to term. I define simp-next like this.

(define (simp-next x)
    (+ x h))

Figuring out how to apply one of three different procedures to the terms of the summation is a little more puzzling. I start out with some pseudocode:

(define (simp-term x)
    (decide on a procedure)(apply the right procedure to x))

How do I decide on a procedure? With a cond statement, naturally. Something like.

(cond (or (first?) (last?) (f x))
      (even? (* 4 (f x)))
      (odd? (* 2 (f x))))

Next I need to figure out how to recognize the first, last, even, and odd terms. The parameters at my disposal are bounds a, b, total number of intervals n, and the specific function argument x. Looking at my rewritten equation above, I can see the coefficient of h has the pattern 0, 1, 2, 3, ... , n. I can see how to use this to write a test.

• If the coefficient of h = 0, it is the first term.
• If the coefficient = n, it is the last term.
• If the coefficient is odd, multiply the function results by 4.
• If the coefficient is even, multiply the function results by 2.

The parameter x is equal to a + n_kh. I can't get the coefficient directly, but together with a and h, I have enough elements to solve for for the coefficent, n_k.

So my test becomes

(define (simp-term x)
  (cond ((or (= x a) (= x b))(f x))
        ((even? (/ (- x a) h)) (* 2 (f x)))
        ((odd? (/ (- x a) h))(* 4 (f x)))))

I should note that in reality I'm doing a lot of trial-and-error coding at this point. The DrRacket stepper was a godsend, also. In hindsight, I can see why what I came up with is correct, but I don't really approach the problem like a math proof. I approach it more of a jigsaw puzzle, trying to put things together until it works.

Putting it all together I end up with:

(define (simpsons f a b n)
  (define h
    (/ (- b a) n))
  (define (simp-next x)
    (+ x h))
  (define (simp-term x)
    (cond ((or (= x a) (= x b))(f x))
          ((even? (/ (- x a) h)) (* 2 (f x)))
          ((odd? (/ (- x a) h))(* 4 (f x)))))
  (* (/ h 3)
     (sum simp-term a simp-next b)))

I spent a lot of time on this problem. It just about killed me. Working on this blog post was hugely helpful (I started it long before I was finished with the problem). My reasoning was not quite as methodical as this blog post appears. Some things that tripped me up:

• I was confused about data vs. procedures. At one point I was trying to make simp-next and simp-term return procedures. Wrong. The names represent a procedure, but they evaluate to a number.
• I was confused about what simp-next should return. It needs to return the argument to f(x), not the result of f(x).
• It wasn't clear what data I would have available when evaluating simp-term. I was getting hung up that I was defining simp-term inside simpsons, but it would be evaluated in sum. Sum doesn't have access to a, b, and n. Turns out I didn't need to worry where it would be evaluated.

I hope that reading this post help you as much as writing it helped me.

Higher-Order Procedures

This is a long-winded set of notes on section 1.3.1. I've tried to make it through SICP before, and this section is the place I usually stopped. This time, I'm pushing through until I make it. I may belabor points you find obvious, but I needed to make it excruciatingly explicit to understand it thoroughly.

Consider how similar the following three procedures are.

Sum integers from a to b

(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))

Sum the cube of integers from a to b

(define (sum-cubes a b)
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))

Estimate π with the series

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

Each of these procedures is a specific instance of a more general idea of summation.

For the first procedure, sum-integers, the function is f(x) = x, and the argument x increase by 1 each term.

For the second procedure, sub-cubes, the function is f(x) = x³. The argument x increase by 1 each term here too.

Finally, the series for ^π⁄₈. The function is a bit more complicated.

Which means the terms increase by a + 4

This particular sum also assumes we are starting with a = 1 and b is even.

So, for each summation we have

• A function f that we apply to each term
• A method for finding each subsequent argument x to supply our function f.

Saying the same thing a different way: to sum a series

We need a procedure that, given x₁, can calculate x₂. Given x₂, it calculates x₃, and so on. We feed the results of that procedure into a second procedure that calculates our function f(x).

Now you can see how you might generalize the original three procedures above by having two additional procedures, term and next. term calculates the function and gives you the numerical result you will be adding. next advances the series and gets the next value of x, which f will operate on.

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

In the case of sum-integers, the helper procedures are pretty easy. We saw above that f(x) = x, so we need an identity procedure

(define (identity x) x)

And we see that x should increase by on each term, so we make an increment procedure.

(define (inc x) (+ 1 x))

So defining sum-integers in terms of sum we have

(define (sum-integers a b)
  (sum identity a inc b))

For sum-cubes, f(x) = x³, and x increases by one each term. Since we already have cube and inc

(define (sum-cubes a b)
  (sum cube a inc b))

Finally, our estimate for π/8. I define two new procedures for term and next, both of which are straightforward implementations of the observations made above about the function f(x) and how the function argument increases by x + 4.

(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))

The examples above provided specific implementations for the function f(x), which is always the same for every procedure call. We can design a procedure to take a function as an argument, so the function f(x) isn't hard-coded into the implementation. Suppose we want to estimate a definite integral with the following sum.

This method for estimating definite integrals is valid for lots of functions: x², x³, sin(x), log(x) etc. We can define our procedure to take a procedure as an argument. That procedure argument calculates some function f(x). This way, our procedure can calculate the definite integral for any function expressed as a procedure.

We advance to the next x by adding dx each time. The procedure for this estimate is

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

Another notable difference is that the first x to operate on is (a + ^dx⁄₂). Previous procedures started at x = a.