src/sicp/ch1_1.clj

   1 (ns sicp.ch1-1
   2   (:use sicp.utils))
   3
   4 (defn sum-of-squares [x y]
   5   (+ (square x) (square y)))
   6
   7 (defn ff [a]
   8   (sum-of-squares (+ a 1) (* a 2)))
   9
  10 (defn abs1 [x]
  11   (cond (< x 0) (- x)
  12         :else x))
  13
  14 ;; exercise 1.1: What is the result printed by the interpreter in response
  15 ;;               to each expression (in order) ?
  16
  17 (def a 3)
  18 (def b (+ a 1))
  19
  20 (+ a b (* a b))  ; 19
  21 (= a b) ; false
  22
  23 (if (and (> b a) (< b (* a b)))
  24     b
  25     a)   ; 4
  26
  27 (cond (= a 4) 6
  28       (= b 4) (+ 6 7 a)
  29       :else 25)  ; 16
  30
  31 (+ 2 (if (> b a) b a)) ; 6
  32
  33 (* (cond (> a b) a
  34          (< a b) b
  35          :else -1)
  36    (+ a 1))      ; 16
  37
  38 ;; exercise 1.2: Translate the given expression into prefix form
  39 (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 1 5)))))
  40    (* 3 (- 6 2) (- 2 7)))  ; -71/300
  41
  42 ;; exercise 1.3:  Define a procedure that takes three numbers as
  43 ;;                arguments and returns the sum of the squares of
  44 ;;                the two larger numbers.
  45 (defn sort3 [a b c]
  46   (cond (> b a) (sort3 b a c)
  47         (< b c) (sort3 a c b)
  48         :else [a b c]))
  49
  50 (defn sum-of-sq-of-two-largest [a b c]
  51   (apply sum-of-squares (take 2 (sort3 a b c))))
  52
  53 ;; well, I cheated above. Let me use only the constructs introduced
  54 ;; so far in the book. (follows after the sicp meetup #2 on 28/mar/2010.
  55 (defn sum-of-square-of-two-largest [a b c]
  56   (if (> a b)
  57     (if (> b c)
  58       (sum-of-squares a b) ; a > b > c
  59       (sum-of-squares a c))
  60     (if (> a c)
  61       (sum-of-squares b a)
  62       (sum-of-squares b c))))
  63
  64 ;; exercise 1.4: Observe that our model of evaluation allows for
  65 ;;               combinations whose operators are compound
  66 ;;               expressions. Use this observation to describe the
  67 ;;               behavior of the following procedure:
  68 ;; (defn a-plus-abs-b [a b]
  69 ;;   ((if (> b 0) + -) a b))
  70 (comment
  71   If b is positive, we do (+ a b) and if it is negative, we do (- a b).
  72   This makes use of the fact that the first element in a list is an
  73   operand. Here, the operand is chosen based on other operators.
  74   )
  75
  76 ;; exercise 1.5:  Ben Bitdiddle has invented a test to determine
  77 ;;                whether the interpreter he is faced with is
  78 ;;                using applicative-order evaluation or normal-order
  79 ;;                evaluation. He defines the following two procedures:
  80 ;; (defn p [] (p))
  81 ;; (defn test [x y]
  82 ;;   (if (= x 0)
  83 ;;    0
  84 ;;    y))
  85 ;;
  86 ;; Then he evaluates the expression
  87 ;;
  88 ;; (test 0 (p))
  89 ;;
  90 ;; What behavior will Ben observe with an interpreter that uses
  91 ;; applicative-order evaluation?
  92 (comment
  93   In the case of applicative order evaluation, the test gets into
  94   and infinite loop (eventually using all the stack), as the parameters
  95   are evaluated before they are actualy used in the function.
  96   )
  97 ;; What behavior will he observe with an interpreter that uses
  98 ;; normal-order evaluation? Explain your answer.
  99 (comment
 100   It will print 0, as (p) is not evaluated in this case.
 101   )
 102
 103 ;; 1.1.7 Square root finding using Newton's method
 104 (defn average [x y]
 105   (/ (+ x y) 2))
 106
 107 (defn improve [guess x]
 108   (average guess (/ x guess)))
 109
 110 (defn good-enough? [guess x]
 111   (< (myabs (- (square guess) x)) 0.001))
 112
 113 (defn sqrt-iter [guess x]
 114   (if (good-enough? guess x)
 115     guess
 116     (sqrt-iter (improve guess x)
 117                x)))
 118
 119 (defn sqrt [x]
 120   (sqrt-iter 1.0 x))
 121
 122 ;; exercise 1.6
 123 ;; Alyssa P. Hacker doesn't see why if needs to be provided as a special form.
 124 ;; ``Why can't I just define it as an ordinary procedure in terms of cond?''
 125 (defn new-if [predicate then-clause else-clause]
 126   (cond predicate then-clause
 127         :else else-clause))
 128
 129 (new-if (= 3 2) 0 5)  ; 5
 130 (new-if (= 1 1) 0 5)  ; 0
 131
 132 ;; Delighted, Alyssa uses new-if to rewrite the square-root program:
 133
 134 (defn sqrt-iter [guess x]
 135   (new-if (good-enough? guess x)
 136           guess
 137           (sqrt-iter (improve guess x)
 138                      x)))
 139
 140 ;; what happens when Alyssa attempts to use this to compute square roots? Explain.
 141 (comment
 142   Since `new-if' is a function, when it is called from sqrt-iter, the parameters
 143   are evaluated before it gets called. good-enough? will return a false unless
 144   the guess and x are almost the same. guess evaluated to the initial value of
 145   guess. sqrt-iter gets evaluated, but gets into an infinite loop. The predicate
 146   will have no effect.)
 147
 148 ;; Exercise 1.7: The good-enough? test used in computing square roots will not
 149 ;; be very effective for finding the square roots of very small numbers. Also,
 150 ;; in real computers, arithmetic operations are almost always performed with
 151 ;; limited precision. This makes our test inadequate for very large numbers.
 152 ;; Explain these statements, with examples showing how the test fails for small
 153 ;; and large numbers.
 154 (comment
 155  user> (sqrt (square 0.001))
 156  0.031260655525445276
 157  user> (sqrt (square 0.2))
 158  0.20060990407779591
 159  user> (sqrt (square 0.01))
 160  0.03230844833048122
 161  user> (sqrt (square 0.02))
 162  0.0354008825558513
 163  user> (sqrt (square 10))
 164  10.000000000139897
 165  user> (sqrt (square 100))
 166  100.00000025490743
 167  user> (sqrt (square 200))
 168  200.000000510076
 169  user> (sqrt (square 2))
 170  2.0000000929222947
 171  user> (sqrt (square 0.1))
 172  0.10032578510960607
 173  user> (sqrt (square 0.01))
 174  0.03230844833048122
 175  user> (sqrt (square 10000))
 176  10000.0
 177  user> (sqrt (square 20000))
 178  20000.0
 179  user> (sqrt (square 200000))
 180  200000.0
 181  user> (sqrt (square 20000000))
 182  2.0E7
 183  user> (sqrt (square 20000000000))
 184  2.0E10
 185  user> (sqrt (square 200000.012))
 186  200000.012
 187  user> (sqrt (square 2000000.123))
 188  2000000.123
 189  user> (sqrt (square 200000000.123))
 190  2.00000000123E8
 191  user> (sqrt (square 2000000000.123))
 192  2.000000000123E9
 193  user> (sqrt (square 20000000000.123))
 194  2.0000000000123E10
 195  user> (sqrt (square 2000000000000.123))
 196  2.000000000000123E12
 197  )
 198 ;; An alternative strategy for implementing good-enough? is to watch how guess
 199 ;; changes from one iteration to the next and to stop when the change is a very
 200 ;; small fraction of the guess.
 201 (defn sqrt-iter [old-guess new-guess x]
 202   (if (good-enough? old-guess new-guess x)
 203     new-guess
 204     (sqrt-iter new-guess (improve new-guess x)
 205                x)))
 206
 207 (defn improve [guess x]
 208   (average guess (/ x guess)))
 209
 210 (defn average [x y]
 211   (/ (+ x y) 2))
 212
 213 (defn good-enough? [old-guess new-guess x]
 214   (< (/ (myabs (- new-guess old-guess)) new-guess) 0.0001))
 215
 216 (defn sqrt [x]
 217   (sqrt-iter x 1.0 x))
 218 (comment
 219 user> (sqrt (square 0.01))
 220 0.010000000025490743
 221 user> (sqrt (square 0.001))
 222 0.0010000000000000117
 223 user> (sqrt (square 0.0001))
 224 1.0000000000082464E-4
 225 user> (sqrt (square 0.02))
 226 0.020000000050877154
 227 user> (sqrt (square 0.002))
 228 0.0020000000000000235
 229 user> (sqrt (square 4))
 230 4.000000000000051
 231 user> (sqrt (square 20))
 232 20.000000000298428
 233 user> (sqrt (square 25))
 234 25.000000063076968
 235 user> (sqrt 5)
 236 2.236067977499978
 237 user> (sqrt 25)
 238 5.000000000053722
 239 user> (sqrt 9)
 240 3.000000001396984
 241 user> (sqrt 81)
 242 9.000000000007091
 243 )
 244 ;; exercise 1.8: cube root
 245 (defn improve [guess x]
 246   (/ (+ (/ x (square guess)) (* 2 guess)) 3))
 247
 248 (defn cubert-iter [old-guess new-guess x]
 249   (if (good-enough? old-guess new-guess x)
 250     new-guess
 251     (cubert-iter new-guess (improve new-guess x)
 252                  x)))
 253
 254 (defn cuberoot [x]
 255   (cubert-iter x 1.0 x))
 256
 257 (comment
 258 user> (cuberoot (cube 2))
 259 2.000000000012062
 260 user> (cuberoot (cube 10))
 261 10.000000000000002
 262 user> (cuberoot (cube 9))
 263 9.000000000053902
 264 user> (cuberoot (cube 0.001))
 265 0.001000000000000962
 266 user> (cuberoot (cube 0.0001))
 267 1.000000000000001E-4
 268 user>
 269 )
 270 ;; section 1.1.8
 271 ;; hiding the non-public procedure definitions
 272 (defn- sqrt-iter [guess x]
 273   (if (good-enough? guess x)
 274     guess
 275     (sqrt-iter (improve guess x)
 276                x)))
 277
 278 (defn- improve [guess x]
 279   (average guess (/ x guess)))
 280
 281 (defn- average [x y]
 282   (/ (+ x y) 2))
 283
 284 (defn- good-enough? [guess x]
 285   (< (myabs (- (square guess) x)) 0.001))
 286
 287 (defn sqrt [x]
 288   (sqrt-iter 1.0 x))