Monday, March 5, 2012

On Lisp in Clojure ch 2 (2.7 - 2.10)

This is the fourth post translating the examples from chapter 2 On Lisp by Paul Graham into Clojure.

Section 2.7 Local Functions

;; apply function to all items in list
(map (fn [x] (+ 2 x))
     '(2 5 7 3))
;; or
(map #(+ 2 %)
     '(2 5 7 3))

The copy tree function didn't seem to do anything, the data looks the same to me after as it did before. But I think the point is that you can use map with a named function.

(map inc '(1 2 3))

The next example is a function that applies a function to each element of a list using a closure

(defn list+ [lst n]
  (map #(+ n %) lst))
(list+ '(1 2 3) 3)

The next set of eamples pertain to CLISP's labels function, which does not exist in Clojure. In Clojure let is evaluated sequentially so things that Graham says won't work in CLISP work in Clojure such as:

(let [my-inc (fn [x] (+ x 1))] (my-inc 3))
(let [x 10 y x] y)

The last example in this section is of mapping a recursive function to a list. I did my best to do a translation of this function into Clojure, but it doesn't actually work. It blows the stack. I have included it anyway, because it shows naming a function with the (fn name [params] form. The only recursion you want to use in Clojure is tail recursion, which is the subject of the next section. Generally, in Clojure though, you use sequences instead of recursion, but that discussion doesn't really fit here.

(defn count-instances [obj lists]
  (map (fn instances-in [lst]
    (if (seq? lst)
      (+ (if (= (first lst) obj) 1 0)
         (instances-in (rest lst))) 0)) lists))

Section 2.8 Tail-Recursion

Tail recursion in Clojure uses the recur form. The java virtual machine does not support tail call optimization. The recur form tells the Clojure compiler to compile the code to a loop to compensate.

I skipped the non-tail call recursive example of the our-length function.

(defn our-find-if [pred lst]
  (if (pred (first lst))
    (first lst) (recur pred (rest lst))))
(our-find-if even? [1 2 3 4])
The tail call version of our-length.
(defn our-length [lst]
  (loop [lst lst acc 0]
    (if (= () lst)
      acc
      (recur (rest lst) (+ acc 1) ))))
(our-length '(1 2 3 4))

This section ends with a discussion of optimization of Common Lisp. In Clojure you can get better performance using type hints. This tells the compiler which java type to use for a variable. Here is the Clojure optimized triangle function.

(defn triangle [^long n]
  (loop [c 0 n n]
    (if (zero? n)
    c
    (recur (+ n c) (- n 1)))))
(triangle 1000000)

The type hint gives an extra boost in this case. Normally the type hint makes reflection unnecessary. Here, we are specifying to use a java primitve (long) instead of a java object to hold the number. On my system, without the type hint the (triangle 1000000) call took 521 milliseconds. When I added the type hint, it went down to 11 milliseconds!

Section 2.9 covers compilation. Graham distinguishes between functions that are complied verses functions that are interpreted. In Clojure all functions are compiled.

Clojure does have a compile function, that was added in version 1.3. The documentation says that it is for compiling libraries, so it is not analgous to the compilation discussed in this section of On Lisp.

Section 2.10 does not contain any examples.

That's all for Chapter 2.

2 comments:

  1. Re count-instances this will work:

    (defn count-instances [obj lsts]
    (defn instances-in [lst]
    (if (not (empty? lst))
    (+
    (if (= (first lst) obj) 1 0)
    (instances-in (rest lst)))
    0))
    (map instances-in lsts))

    In Common Lisp (consp lst) where lst is empty returns false, whereas (seq? lst) in Clojure where lst is empty resturns true.

    ReplyDelete