On Lisp in Clojure, chapter 10

I am continuing to translate the examples from On Lisp by Paul Graham into Clojure. The examples and links to the rest of the series can be found on github.

Chapter 10 presented some interesting problems. Some of them were the result of rampant mutability, and I have skipped those, but much of the rest applies to Clojure.

Stuart Halloway also has written a post on this chapter on his blog.

Section 10.1 Number of Evaluations

The difference between the correct version of the for loop and the multiple evaluation version is pretty straight forward. By binding ~stop to gstop#, stop only gets evaluated once.

;; correct version
(defmacro for' [[var start stop] & body]
  `(let [~var (atom ~start) gstop# ~stop]
     (while (< (deref ~var) gstop#)
         ~@body
         (swap! ~var inc))))

;; subject to multiple evaluations
(defmacro for' [[var start stop] & body]
  `(let [~var (atom ~start)]
     (while (< (deref ~var) ~stop)
       ~@body
       (swap! ~var inc))))

The the problem with the last version of the for loop really belongs in the next section.

;; incorrect order of evaluation
(defmacro for' [[var start stop] & body]
    `(let [gstop# ~stop ~var (atom ~start)]
       (while (< (deref ~var) ~stop)
         (swap! ~var inc)
         ~@body)))

Section 10.2 Incorrect Order of Evaluation

When I read the for macro labeled as having the incorrect order of evaluation, I thought Graham meant that the counter was being incremented at the top of the loop, and so I wrote my loop that way, and thought it was kind of a silly example. Then I tried the call to for in this section. First, Graham shows us an example where the order of evaluation gives an interesting result.

(def x (atom 10))
(+ (reset! x 3) @x)
;; => 6

In the version of the for loop with the incorrect order of evaluation, the stop variable appears first, so that gets evaluated, which sets x to 13. Then, start gets bound to the value of x, which is now 13, so the loop never actually runs. In the correct version of the for loop, in the let expression, the start is bound first, to 1, and then stop is bound to 13. I think Graham is right when he says that a caller has a right to expect start to be evaluated before stop because they appear left to right in the argument list. He is definitely right when he says this is a pathological way to call for'.

(let [x (atom 1)]
  (for' [i @x (reset! x 13)]
        (println @i)))

Section 10.3 Non-functional Expanders

This section shows a lot of awful things that can happen when you mix macros and mutation. But since we are in Clojure, we already avoid mutation when possible. Moving on...

Section 10.4 Recursion

Graham shows us how write a function with recursion and then shows us how to rewrite the same function in a more imperative manner. He does this because in this section he shows a potential pitfall of recursion in macros, and the imperative loop is an alternative.

The imperative version of our-length is a little extra painful in Clojure. Rather than mutating the list and the counter in a while loop, I am going to stick with the recursive function. We will just be careful when we recurse in macros.

(defn our-length [x]
  (loop [lst x acc 0]
    (if (empty? lst) acc
        (recur (rest lst) (inc acc)))))

Graham's ntha function works just fine. Rewriting it as the macro, nthb causes an infinite loop in the macro expansion.

 
(defn ntha [n lst]
  (if (= n 0)
    (first lst)
    (ntha (- n 1) (rest lst))))

(defmacro nthb [n lst]
  `(if (= ~n 0)
     (first ~lst)
     (nthb (- ~n 1) (rest ~lst))))

(macroexpand-1 '(nthb 2 [1 2 3 4 5]))

Graham shows a couple of ways to rewrite nth as a macro that doesn't lead to an infinite loop. I have just rewritten the version with the recursion in the macro.

(defmacro nthe [n lst]
  `(loop [n# ~n lst# ~lst]
     (if (= n# 0)
       (first lst#)
       (recur (dec n#) (rest lst#)))))

Graham also presents a pair of examples of writing a an `or` macro that sidestep the pitfalls of a recursive macro. In the first, the macro calls a recursive function. The second macro does its own recursion. This seems to be less difficult to do safely in Clojure, because recursion is done with `recur` rather than a function calling itself by name.

(defn or-expand [args]
  (if (empty? args)
    nil
    (let [sym (first args)]
       (if sym
         sym
         (or-expand (rest args))))))

(defmacro ora [& args]
  (or-expand args))

(defmacro orb [& args]
  (loop [lst args]
    (if (empty? lst) false
        (let [sym (first lst)]
          (if sym sym (recur (rest lst)))))))