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.
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).
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 (
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
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!
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
(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?