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[?]. 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"))
;; yesnoExercise 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/10761680It fails if the numbers are too big or too small.
(sqrt-iter 10 92400000000000000) ;; >>: arithmetic exception
(sqrt-iter 1 0.0005);; >> 0.03640532954316447This 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?