Yesterday, we built a simple sqrt using Heron of Alexandria’s algorithm. The problem with the code is that it had some generically useful ideas, but it was all hard-coded to only work with sqrt. Also, it was not clear what exactly the algorithm was.
In the SICP lecture they fix it by passing functions around since Lisp treats functions as first-class data-types. Here’s the fix explained (23:30 in the video, stop at 32:30):
See the video for the Scheme implementation. Here it is in clojure.
(defn sum ([] 0)
([x] x)
([x & more] (+ x (apply sum more) )))
(defn average
([] 0)
([x] x)
([x & more]
(/ (+ x (apply sum more)) (+ 1 (count more)))))
(defn abs [x] (if (< x 0) (- x) x))
(defn close-enough? [u v]
(let [tolerance 0.00001]
(< (abs (- u v)) tolerance)))
(defn fixed-point [f start]
(loop [old start new (f start)]
(if (close-enough? old new)
new
(recur new (f new)))))
(defn sqrt [x] (fixed-point (fn [y] (average (/ x y) y)) 1 ))
(prn (sqrt 9))
A fixed point of a function f is a value y such that f(y) = y. This improved code, which implements the same algorithm as before, uses a generic fixed-point function that takes a function and a guess and tries to find the fixed point by setting the next guess to f(guess). You can see it all in the video. The things in clojure you need to know:
- fn [arg1 arg2] is lambda (λ), so where fixed-point takes a function as the first argument, we create one on the fly to be (average (/ x y) y) where x is the argument to sqrt (closed around our function) and y is the argument defined by fn.
- Since clojure compiles to Java and uses Java calling conventions, it does not have automatic tail-recursion. Instead, you use the recur special operator which will create a constant space loop back to the last loop or function definition. Loop/recur is explained on the Functional Programming page of the clojure site (at the bottom).
But, even this can be improved, as we’ll see tomorrow.