From Common Lisp to Clojure (Part 1)

I recently started tinkering around with Clojure as a test to see if I could replace Java with a Lisp-like language. For those unfamiliar with Clojure, here’s a quick intro to what it’s all about:

Clojure is a dynamic programming language that targets the Java Virtual Machine. It is designed to be a general-purpose language, combining the approachability and interactive development of a scripting language with an efficient and robust infrastructure for multithreaded programming. Clojure is a compiled language – it compiles directly to JVM bytecode, yet remains completely dynamic. Every feature supported by Clojure is supported at runtime. Clojure provides easy access to the Java frameworks, with optional type hints and type inference, to ensure that calls to Java can avoid reflection.

As a regular user of Common Lisp, it has taken some adjustment to get used to Clojure’s syntax choices, but I’m starting to believe that they are for the better and will allow those unfamiliar, or afraid of Lisp, to give it a try. A small example is the new syntax for LET; a function that binds values to variables. The code below in Common Lisp would assign 3 to x, and x + 1 to y:

(let* ((x 3)
  (y (+ x 1)))  ...)

In this case, we have to use LET*, which evaluates things sequentially (LET does the assignment in parallel). In Clojure, however, LET is always LET*, and a lot of the extra parentheses are removed. The above would be written like the following in Clojure:

(let [x 3 y (+ x 1)]  ...)

The []‘s were originally introduced in Scheme to make heavy paren code (LET, COND, etc.) easier to read, but was never enforced. I never used the [] helpers while writing Scheme, but I can understand why they might increase readability. Aside from the few syntactic differences, I felt more or less right at home using Clojure, with the added ability of being able to easily interface with Java programs.

Dynamic Java?

Despite Clojure’s dynamic nature, we can still drop down to enforce typing when performance is an issue. I’ve started to switch over to Clojure as my primary language for Project Euler problems, and one of the first things I needed to write was an efficient prime number sieve. I more or less copied the algorithm from Roger Corman’s Lisp examples, without the type decoration as I was unsure how to do it in Clojure. I ended up with the following as a result:

(defn unoptimized-sieve [n]
  "Returns a list of all primes from 2 to n"
  (let [root (Math/round (Math/floor (Math/sqrt n)))]
     (loop [i 3
            a (make-array Boolean n)
            result (list 2)]
        (if (>= i n)
           (reverse result)
           (recur (+ i 2)
           (if (< i root)
              (loop [arr a, inc (+ i i), j (* i i)]
                 (if (>= j n)
                    arr
                    (recur (do (aset arr j true) arr)
                       inc
                       (+ j inc))))
              a)
        (if (not (aget a i))
           (conj result i)
           result))))))

Notice the use of Java’s java.lang.Math.round/floor/sqrt functions and the Boolean type. The first thing I noticed was how slowly this ran compared to my Common Lisp version. Finding the first 100,000 primes took a little longer than I anticipated.

user> (time (last (unoptimized-sieve 100000)))"Elapsed time: 6160.188 msecs"
99991

I knew being able to tag types would increase my runtime dramatically, as it had done with the Common Lisp version, so I went ahead and did just that.

(defn sieve [#^Integer n]
  "Returns a list of all primes from 2 to n"
  (let [root (Math/round (Math/floor (Math/sqrt n)))]
     (loop [#^Integer i 3
            a (make-array Boolean n)
            result (list 2)]
        (if (>= i n)
          (reverse result)
          (recur (+ i 2)
                 (if (< i root)
                   (loop [arr a
                          #^Integer inc (+ i i)
                          #^Integer j (* i i)]
                      (if (>= j n)
                        arr
                        (recur (do (aset arr j true) arr)
                               inc
                               (+ j inc))))
                    a)
                  (if (not (aget a i))
                    (conj result i)
                    result))))))

A few simple compiler hints (shown in bold) dramatically reduced the running time:

user> (time (last (sieve 100000)))"Elapsed time: 164.058 msecs"
99991

Quite the speed bump for very little work if I do say so myself. Now I can finally start solving more Project Euler puzzles!

So… What Do I Think?

I obviously haven’t played around with Clojure too much, but here are my current pros and cons.

Pros

• On the JVM: For the work that I do, I find myself writing a decent amount of Java code. A great deal of my classes provide code for assignments written in Java and I have to decide between rewriting provided code in a language I like, or using Java. Now, I don’t have to make that choice anymore.
• Data Structures are Immutable: One of the things I love about Lisp is you can do whatever you want. Program functionally, imperatively, object-oriented-ly, …, the list goes on and on. But the more I used it, the more I realized I just did everything functionally. Clojure takes a big step for Lisp in forcing immutable data structures and basically forcing the programmer to think functionally. The main benefit lies in concurrency, which I plan on exploring in the near future.

Cons

• No Tail Call Optimization: You’re probably thinking “how can a functional language not have tail call optimization?” which is exactly what I thought when I read it. Unfortunately the JVM does not provide such a facility, luckily Rich Hickey provided a workaround in the form of RECUR. It essentially is just a goto that rebinds the variables to the new values in the most recent LOOP or DEFN call. In the second RECUR in the example above, (do (aset arr j true) arr) is set to arr, inc is set to inc and (+ j inc) is set to j in the most recent LOOP call, and the forms are re-evaluated. It’s kinda hacky but it works, and with any luck the new JVM will have TCO and we’ll be all set.
• Lack of Robust Documentation: Perhaps I’m a bit spoiled with JavaDocs and the CL HyperSpec, but I do find the Clojure documentation a bit lacking. This is entirely understandable as the language is very new, but it is definitely something that would turn off those new to Lisp. Luckily, with a “Programming Clojure” book on the way, things are looking up in that department as well .

All in all, I think Clojure is very promising and I hope to see the community thrive. It’s slowly winning me over, which isn’t too tough once I can work in a great environment for a REPL-based language.

EDIT: an even faster version that uses primitives (courtesy of Rich Hickey in the comments):

user> (time (last (sieve 100000)))"Elapsed time: 17.963 msecs"
99991

Advertisement

« emacs-w3m 100% CPU Usage on Mac OS X

Copy to Mac OS X Clipboard from Vim »