SICP Chapter 1 Complete

All code available on GitHub. Drawings/diagrams available here.

19 days after starting, I’m done with Chapter 1!

Exercise 1.36 in this chapter was pretty interesting - we have to find a solution to x^x = 1000 by finding a fixed point of x -> log(1000)/log(x). I modified fixed-point using the https://github.com/weavejester/hashp #p data reader to print out intermediate values, which makes println-style debugging a lot better.

(def tolerance 1E-5)

(defn fixed-point [f first-guess]
  (let [close-enough? (fn [v1 v2] (< (Math/abs ^float (- v1 v2)) tolerance))
        try* (fn [guess steps] (let [next #p (f guess)]
                                 (if (close-enough? guess next)
                                   (do (print (str "took " steps " steps, guess=" guess))
                                       next)
                                   (recur next (inc steps)))))]
    (try* first-guess 0)))

(defn undampened-x-pow-x [x] (/ (Math/log 1000) (Math/log ^float x)))

(float (fixed-point undampened-x-pow-x 2)) 
;; took 28 steps
;; 4.5555634

(float (fixed-point #(/ (+ (undampened-x-pow-x %) %) 2) 2))
;; took 7 steps
;; 4.5555468
;; no oscillation at the start; nice!

The rest of the exercises really served to hammer home the point that it’s easy and fun to build higher-level abstractions using first-class functions and some thinking. Just contrast the initial and final implementations of sqrt below:

;; initial version
(defn sqrt-iter [guess x]
  (letfn [(good-enough? [guess x]
            (< (Math/abs ^float (- (* guess guess) x))
               0.001))
          (average [x y]
            (/ (+ x y) 2))
          (improve [guess x]
            (average guess (/ x guess)))]
    (if (good-enough? guess x) guess
        (re cur (improve guess x) x))))

;; final version
(defn sqrt-final [num]
  (let [guesser (iterative-improver
                 (fn [a b] (< (Math/abs ^float (- a b))
                              0.001))
                 (fn [guess] (sicp.util/average guess (/ num guess))))]
    (guesser 1))) 

;; Where iterative-improver is from Exercise 1.46:
(defn iterative-improver [test-fn improve-fn]
  (fn [guess] (let [improved-guess (improve-fn guess)
                    good-enough? (test-fn guess improved-guess)]
                (if good-enough? improved-guess
                    (recur improved-guess)))))