SICP through §1.2.2

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

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?