read


read
or learn more

On Lisp -> Clojure (chapter 2)

Sep 26, 2008

Inspired by Stuart Holloway‘s excellent series porting Practical Common Lisp to Clojure and Ola Bini‘s bad-ass port of Paradigm’s of Artificial Intelligence to Ruby. I have started my own quest to port Paul Graham‘s On Lisp to Clojure.

Posts in this series: ch. 2, ch. 2 redux, ch. 3, ch. 4, ch. 5

I have made it through chapter 2 and am ready to start the coding for chapter 3. I will post when the code is “complete”, but my progress can be followed on Github.

; pg. 10
(defn dbl [x]
  (* x 2))

(dbl 39)
(dbl 17872687642786723868743216782)

; pg. 11
(= dbl (first (list dbl)))

; pg. 12
(fn [x] (* x 2))

((fn [x] (* x 2)) 20)

; pg. 13
(def dbl (fn [x] (* x 2)))

; pg. 14
(map (fn [x] (+ x 10)) '(1 2 3))

(map + '(1 2 3) '(10 100 1000))

;; Clojure uses the Java's Comparator on the sort function
;; so there is no need to supply the < function.  In fact,
;; if you did, an exception would be thrown. (l@@k why?)
(sort '(1 4 2 5 6 7 3))

; pg. 15
;; Because Clojure is a Lisp-1, funcall is not needed.  Instead,
;; we just call directly as (f)
(defn remove-if [f lst]
  (if (nil? lst)
    nil
    (if (f (first lst))
      (remove-if f (rest lst))
      (cons (first lst) (remove-if f (rest lst))))))

(remove-if even? '(1 2 3 4 5))
(remove-if nil? '(1 2 nil 3 nil))
(remove-if (fn [x] 
             (if (> x 5)
               nil
               x)) 
           '(3 4 5 6 7))


; pg. 16
(let [y 7]
  (defn scope-test [x]
    (list x y)))

(let [y 5] (scope-test 3)) ;; no shocker here

; pg. 18
(defn list+ [lst n]
  (map (fn [x] (+ x n)) lst))

(list+ '(1 2 3) 10)

;;
;; This is surprisingly difficult given that Clojure does not allow the 
;; modification of local variables defined in a let.  Only vars (globals)
;; and class fields can be modified with the (set!) function.  
;; Therefore, I had to hack it so that the closed counter is an array
;; of one integer element.  Therefore, it is the array that is modified
;; and not the count.  The point being, if you want to create closures
;; for functions modifying local state, then you have to use a mutable object
;; to do so
;;
(let [counter (to-array [0])]
  (defn new-id [] (aset counter 0 (inc (aget counter 0))))
  (defn reset-id [] (aset counter 0 0)))


;; On the other hand, this is extremely easy
(defn make-adder [n]
  (fn [x] (+ x n)))

(def add10 (make-adder 10))
(def add42 (make-adder 42))

(add10 1)
(add42 100)
(add42 (add10 1))

; pg. 19
;; Again we run into the immutable local binding feature.  Since I already 
;; solved this problem before, getting it to work for this case was 
;; a piece of cake.
(let [n (to-array [0])]
  (defn make-adderb [m]
    (aset n 0 m)
    (fn [x & change]
      (if change
        (aset n 0 x)
        (+ (aget n 0) x)))))

(def addx (make-adderb 1))
(addx 3)

(addx 100 true)
(addx 3)


; pg. 22
;; Clojure handles this very nicely.  
(defn count-instances [obj lsts]
  (defn instances-in [lst]
    (if (list? lst)
      (+ 
       (if (= (first lst) obj) 1 0)
       (instances-in (rest lst)))
      0))
  (map instances-in lsts))

(count-instances 'a '((a b c) (d a r p a) (d a r) (a a)))


;; Tail-recursive find-if 
;; returns the first instance satisfying (f)
(defn our-find-if [f lst]
  (if (f (first lst))
    (first lst)
    (our-find-if f (rest lst))))

(our-find-if even? '(1 3 5 7 9 11 14))


; pg. 23
;; Tail-recursive our-length
(defn our-length [lst]
  (defn rec [lst acc]
    (if (nil? lst)
      acc
      (rec (rest lst) (inc acc))))
  (rec lst 0))

(our-length (range 100))
(our-length (range 0 100 2))


; pg. 24
(defn triangle [n]
  (defn tri [c n]
    (if (zero? n)
      c
      (tri (+ n c)
           (- n 1))))
  (tri 0 n))

(triangle 10)
(triangle 30000)  ;; one more zero blew my stack

-m

7 Comments, Comment or Ping

  1. This is cool. “On Lisp” is what convinced me Lisp was actually worth understanding, and without that I would never have given Clojure a chance.

    A couple notes on your code…

    remove-if uses “regular” recursion, but because the JVM does not optimize away tail calls the way Common Lisp (usually) does, this could fail for very long lists. However, if you just replace “cons” with “lazy-cons” and the other recursive call with “recur”, you’ll have a beautiful lazy sequence function that will never blow the call stack.

    I’m sure you’ve noticed that Graham is taking some pains to make tail-recusive versions of his functions. In general to take advantage of this you’ll want to use “recur” instead of the tail call.

    It’s more idiomatic (and more succinct!) to say (if (seq lst) …) than (if (nil? lst) nil …) Also better to use (let [tri (fn [c n] …)] (tri 0 n)) than to have a defn nested inside another defn, since the inner defn is still defining a namespace-global name, even though it’s nested.

    Finally I noticed your clever use of Java arrays to get mutability. This is fine, in that you’ll often find yourself in Clojure working with mutable Java objects, and you just have to deal with it. However, Clojure also provides some very nice multi-threading features if you use refs of immutables instead of mutable objects.

    In your case, you could replace (let [counter (to-array [0])] …) with (def counter (ref 0)). Then use @counter instead of aget, and use (dosync (set-ref …)) instead of aset. For more details on refs, see http://clojure.org/refs

    Anyway, don’t let me discourage you — I’m sure working through On Lisp will be a great way for you to learn Clojure, and will likely help others too. I’m very interested to see the DSLs of the later chapters in Clojure. Keep it up!

    –Chouser

  2. Excellent post! Far from being discouraged, I am enthusiastic by your recommendations. I am far less interested in being correct than in doing it correctly (if that makes any sense at all).

    I was a little discouraged that my implementation of remove-if was ‘dangerous’ to the stack, and I delighted in your pointers in shoring that up. Thank you. It’s clear that I need to study recur more closely.

    I am sure that, at least in the early stages, I will make an abomination of the Clojure idioms, but I hope that over time they will become a part of my lexicon.

    My initial versions of the the closed counter and make-adderb attempted to use refs, but I couldn’t quite get it to work. I will use your advice and attempt to re-implement them, but will most likely keep the old hack laying around as a counter-example/don’t-do-this case.

    Again, thank you for the tips for this Clojure n00b. -m

  3. Dan

    The reason (sort < ‘(1 2 3 4 5)) fails is because the < function returns a boolean, not 0, -1 or 1. So if you create a function that follows that requirement:

    (defn compare-count [x y]
        (let [x-count (count x) y-count (count y)]
            (cond (> x-count y-count) 1
                  (> y-count x-count) -1
                  (= x-count y-count) 0)))

    then you can use it with sort:

    user=> (sort compare-count ‘([2 2] [5 5 5 5 5] [4 4 4 4] [1] [3 3 3])) ([1] [2 2] [3 3 3] [4 4 4 4] [5 5 5 5 5])

    P.S. Hope my formatting comes out okay.

  4. Dan, Thanks for the explanation. I had actually forgotten to go back and L@@k the reason, you saved me some work. ;)

    -m

  5. Gavin Sinclair

    Nice work. Looking forward to reading the other installments.

  6. Thanks for the link, I’ve just posted my version of the same chapter and I checked with yours to see what the differences are.

    Its really nice to have someone else to compare with and learn from :)

  7. Harish

    The above remove-if give error below

    user=> (remove-if even? ‘(1 2 3 4 5)) IllegalArgumentException Argument must be an integer: clojure.core/even? (core.clj:1322)

Reply to “On Lisp -> Clojure (chapter 2)”