SICP through §1.2.2

All code available on GitHub.

Most of the stuff here is pretty light if you are familiar with Lisps and programming. Some of ideas presented did get me to understand terminology in a new light though (for instance, the idea that functions are declarative while procedures are imperative).

When I first started learning computer science, I wondered if every recursive algorithm could be converted to iteration. I didn’t understand the equivalence until later, where my understanding was in terms of the underlying computer architecture Function calls and iterative looping constructs like `for` are both implemented as `jump` instructions in assembly. . 1.1.7 shows an example of this equivalence.

Exercise 1.5

The functions look like this in Clojure:

(defn p [] (p))

(defn test* [x y]
  (if (= x 0) 0 y))

(test* 0 (p))

Clojure is applicative order: it evaluates all arguments to test* first. This causes infinite recursion in p. In normal order evaluation, p is not evaluated till it is needed (which is never).

Exercise 1.6

This was initially surprising to me. It took me a while to realize that how new-if is implemented doesn’t really matter. The applicative order evaluation happens when the arguments (then-clause and else-clause) are evaluated before the function body!

(defn new-if [predicate then-clause else-clause]
  (cond predicate then-clause
        :else else-clause))

(new-if (= 2 3) (print "yes") (print "no"))
;; yesno

Exercise 1.7

Here, we implement a square root function using Newton’s method.

(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
        (recur (improve guess x) x))))

This function works for smaller numbers. Did you know Clojure can work with fractions?

(sqrt-iter 1 4) ;; 21523361/10761680

It fails if the numbers are too big or too small.

(sqrt-iter 10 92400000000000000) ;; >>: arithmetic exception
(sqrt-iter 1 0.0005);; >> 0.03640532954316447

This is the improved version with the method suggested by SICP:

(defn sqrt-iter-2 [first-guess x]
  (letfn [(sqrt-iter-2* [prev-guess guess]
            (if (good-enough? prev-guess guess) guess
                (recur guess (improve guess))))
          (good-enough? [prev-guess guess]
            (< (Math/abs ^float (- guess prev-guess))
               0.001))
          (average [x y]
            (/ (+ x y) 2))
          (improve [guess]
            (average guess (/ x guess)))]
    (sqrt-iter-2* x first-guess)))

(sqrt-iter-2 1 0.0005)
;; >>: gives 0.02236... which is far more accurate!

Exercise 1.9

Pretty straightforward - though note that since Clojure uses the Java calling conventions, it does not automatically do tail call optimization. From the docs:

[Clojure] provides the recur special operator, which does constant-space recursive looping by rebinding and jumping to the nearest enclosing loop or function frame. While not as general as tail-call-optimization, it allows most of the same elegant constructs, and offers the advantage of checking that calls to recur can only happen in a tail position.

I also tried looking at the jvm bytecode for a simple function with and without using Clojure’s recur. Indeed, without the optimization there is an invokeinterface (function call) rather than a goto (loop).

Exercise 1.10

(defn ackermann [x y]
  (cond (= y 0) 0
        (= x 0) (* 2 y)
        (= y 1) 2
        :else (recur (dec x)
                     (ackermann x (dec y)))))

(ackermann 1 10) ;; > 1024
(ackermann 2 4) ;; > 65536
(ackermann 3 3) ;; > 65536

;; (define (f n) (A 0 n))
;; (define (g n) (A 1 n))
;; (define (h n) (A 2 n))
;; (define (k n) (* 5 n n))
;; Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n.
;; f = 2n
;; 
;; g = (A 1 n) = (A 0 (A 1 (dec n))) = 2 (A 1 (dec n))
;; 2^n
;; 
;; h = (A 2 n) = (A 1 (A 2 (dec n))) = (A 1 (A 1 ... (A 1 (A 2 0))))
;;   = 2^2^... n times
;; this looks different than the definition on wikipedia?